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 2for(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=500for(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();
}