https://codeforces.com/problemset/problem/1561/C

c

根据所需能力值排序

依次遍历，如果之前得到的能力比第i关所需的最小能力大，那么能力就加上关卡长度  

否则所需最小能力就是第i关所需的最小能力减去之前所有关的关卡长度。

以为进入洞后，打怪的顺序可以任意，就排序了。。。。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=1e5+5;
vector<int> v[maxn];
vector<pair<int,int> > s;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k,a;
        cin>>n;
        s.clear();
        for(int i=0;i<n;i++)
        {
            v[i].clear();
            scanf("%d",&k);
            while(k--)
            {
                scanf("%d",&a);
                v[i].emplace_back(a);
            }
            for(int j=0;j<v[i].size();j++)
            {
                cout<<v[i][j]<<"  ";

            }
            cout<<endl;
        }

        for(int i=0;i<n;i++)
        {
            int ma=0;
           // sort(v[i].begin(),v[i].end());
            for(int j=0;j<v[i].size();j++)
            {
                v[i][j]=v[i][j]-j;
                if(v[i][j]>=ma)
                    ma=v[i][j]+1;
                //cout<<"ma="<<ma<<endl;
            }
            s.emplace_back(make_pair(ma,v[i].size()));//保存长度和入洞需要最小的“力量”；
        }

        sort(s.begin(),s.end());//从最容易打的开始

        int ans=s[0].first;
        int id=-1;
        int l=s[0].first;
        int len=s[0].second;

        for(int i=1;i<s.size();i++)
        {
            if(s[i].first+1<=l+len)//直接入洞
            {
                len=len+s[i].second;//长度一直累计，为不能入洞的条件做准备
            }
            else
            {
                id=i;
                l=s[i].first,len=s[i].second;
                ans=l;//
            }
        }
        for(int i=0;i<id;i++)
            ans-=s[i].second;
        printf("%d\n",ans);
    }
    return 0;
}

D1

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=2e5+5;
vector<int> v[N];
vector<pair<int,int>> s;
ll dp[N];

int main()
{
    ll n,m;
    cin>>n>>m;
    dp[1]=1;
    ll sum=1;
    for(int i=2;i<=n;i++)
    {
        dp[i]+=sum;
        for(int l=2,r=0;l<=i;l=r+1)
        {
            r=min(i,i/(i/l));
            dp[i]+=1ll*dp[i/l]*(r-l+1);
            dp[i]%=m;
        }

        sum+=dp[i];
        sum%=m;
    }
    cout<<dp[n];
    return 0;
}

d2

https://www.bilibili.com/video/BV1UM4y1V7V1?p=4

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define dec(x,y,z) for(int x=y;x>=z;x--)
#define int long long
const int maxn=4e6+105;
int n,mod;
int dp[maxn],pre[maxn],sav=0;
bool isPrime[maxn];
int Prime[maxn], cnt = 0;
void GetPrime(int n)
{
    memset(isPrime,1,sizeof(isPrime));
    isPrime[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(isPrime[i])
            Prime[++cnt] = i;

        for(int j = 1; j <= cnt && i*Prime[j] <= n; j++)
        {
            isPrime[i*Prime[j]] = 0;
            if(i % Prime[j] == 0)
                break;
        }
    }
}
vector<pair<int,int>>save;
int ii;
void dfs(int pos,int val)//暴力遍历i的各种因数项 
{
    if(pos==save.size())
    {
        if(val>1)
            (sav=sav+   dp[ii/val]-dp[ii/val-1]+mod)%=mod;
        return;
    }
    int v=1;
    dfs(pos+1,val);
    for(int i=0;i<save[pos].second;i++)//2*2*2 
    {
        v*=save[pos].first;
        dfs(pos+1,val*v);
    }
}
void solve()
{
    cin>>n>>mod;
    dp[1]=1,pre[1]=1;
    dp[2]=2,pre[2]=2,sav=2;

    rep(i,3,n)
    {
        //(sav+=dp[1])%=mod;//3->4时，4/3=1，肯定会多一个因子，单独加上 //别看，按照up的思路写的，这个地方我觉得他说的不对，就连同另外一个地方改了
        int x=i;
        save.clear();

        for(int j=1;Prime[j]*Prime[j]<=x;j++)//遍历每一个质数 
        {
            if(x%Prime[j]!=0)  continue;//如果不是是因数 跳过
            else//是因数 
            {                    
                int cnt=0;
                while(x%Prime[j]==0)
                {
                    cnt++;
                    x/=Prime[j];
                }
                save.push_back({Prime[j],cnt});  //存入了质因数，与这个质因数的个数 
             } 
        }
        if(x>1)save.push_back({x,1});    //存入了质因数，与这个质因数的个数 

        ii=i;
        dfs(0,1);//求sav 
        //pre[i]   前i项的和 
        dp[i]=(pre[i-1]+sav)%mod;//直接加转移过来的 + 因数转移过来


        pre[i]=(dp[i]+pre[i-1])%mod;
    }
    cout<<dp[n]<<"\n";
}
signed main()
{
    GetPrime(maxn-20);
    solve();
    return 0;
}