Educational Codeforces Round 133 (Rated for Div. 2) (C dp D前缀和优化倍数关系dp)

A：能用3肯定用三，然后分类讨论即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,M=2*N,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;

int n,m,k;
int a[N];

void solve()
{
    cin>>n;
    if(n==1) cout<<"2\n";
    else{
        if(n%3==0) cout<<n/3<<"\n";
        if(n%3==1) cout<<(n-4)/3+2<<"\n";
        if(n%3==2) cout<<n/3+1<<"\n";
    }
}
//1 2 3 4
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;

    cin>>t;

    while(t--) solve();
}==0==

B：

我们可以构造n个

分别是

n n-2 n-3... 0

因为一开始交换会改变两个，然后后面全都和第一个换就可以保证递减下去了

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,M=2*N,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;

int n,m,k;
int a[N];

void solve()
{
    cin>>n;
    cout<<1+n-1<<"\n";
    for(int i=1;i<=n;i++) a[i]=i;
    //1 2 3 4 4
    //2 1 3 4 2
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" \n"[i==n];
    }
    swap(a[1],a[2]);
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=n;j++){
            cout<<a[j]<<" \n"[j==n];
        }
        swap(a[i+1],a[1]);
    }
}
//1 2 3 4
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;

    cin>>t;

    while(t--) solve();
}

C：正常都能想到先蛇形再走U字形

dp预处理当前[i,j]走到[i^1,j]的最长等待时间，然后从当前这个时间可以一路往后走，不停下来，

对于同行的dp=max(dp[i][j]+1,a[i][j])

但是对于新增的[i^1,j]也可能造成时间问题

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,M=2*N,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;

int n,m,k;
int a[3][N];

void solve()
{
    cin>>m;n=2;
    vector<vector<int>> dp(m + 1, vector<int>(2));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cin>>a[i][j];
    }
    a[0][m]=a[1][m]=0;
    a[0][0]=-1;
    for(int i=m-1;i>=0;i--){
        for(int j=0;j<2;j++)
        dp[i][j]=max({a[j][i]+1,dp[i+1][j]-1,
        a[j^1][i]-2*(m-i-1)});
    }
    int res=inf;
    array<int,2> pos={0,0};
    int cur=0;
    for(int i=0;i<m;i++){
        res=min(res,max(cur,dp[pos[1]][pos[0]])+2*(m-i)-1);
        pos[0]^=1;
        cur=max(a[pos[0]][pos[1]]+1,cur+1);
        pos[1]++;
        res=min(res,max(cur,dp[pos[1]][pos[0]])+2*(m-i-1));
        
         cur=max(a[pos[0]][pos[1]]+1,cur+1);
    }
    cout<<res<<"\n";
    
}
//1 2 3 4
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;

    cin>>t;

    while(t--) solve();
}

D：

因为 （k+1）*(k)/2<=n,可以推出m等于根号2*n

然后直接前缀和优化dp的倍数和即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,M=2*N,mod=998244353;

typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;

int n,m,k;
int a[N];
LL res[N];
LL f[2][N],s[N];
void solve()
{
    cin>>n>>k;
    f[0][0]=1;
    m=sqrt(2*n);m++;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<=n;j++){
            if(j>=(k+i-1))
            s[j]=(s[j-(k+i-1)]+f[(i-1)&1][j])%mod;
            else s[j]=f[(i-1)&1][j];   
            if(j>=(k+i-1))
            {
                f[i&1][j]=(f[i&1][j]+s[j-(k+i-1)])%mod;
            }
        }
        for(int j=0;j<=n;j++)
        {
            f[(i-1)&1][j]=0;

            res[j]=(res[j]+f[i&1][j])%mod;
        }
    }
        //(x+1)*(x)/2>=n
        //x*x>=2*n
        //max 根号2*n=500
    for(int i=1;i<=n;i++)
    cout<<res[i]<<" ";
}
//1 2 3 4
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;

   // cin>>t;

    while(t--) solve();
}