（一道sb题卡了我40min，成功GG）
A：
送分题。sry说他没看懂所以先开D然后成功吊打我，看来Div2不能顺着开题。。
#include<bits/stdc++.h> #define maxn 100005 #define maxm 500005 #define inf 0x7fffffff #define ll long long using namespace std; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } int main(){ int t=read(); while(t--){ int a=read(),b=read(),c=read(),d=read(),k=read(); int t1=a/c+(a%c?1:0),t2=b/d+(b%d?1:0); if(t1+t2<=k) cout<<t1<<" "<<t2<<endl; else cout<<-1<<endl; } return 0; }
B：
送分题。
#include<bits/stdc++.h> #define maxn 1005 #define maxm 500005 #define inf 0x7fffffff #define ll long long using namespace std; char str[maxn]; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } int main(){ int T=read(); while(T--){ int n=read(); cin>>str+1; int l=0,r=0,ans=n,flag=0; for(int i=1;i<=n;i++){ if(str[i]=='1' && !flag) l=i,flag=1; if(str[i]=='1') ans=max(ans,max(i*2,(n-i+1)*2)); } for(int i=n;i>=1;i--) if(str[i]==1) {r=i;break;} if(!l) cout<<ans<<endl; else if(l==r) cout<<ans<<endl; else cout<<max(ans,(r-l+1)*2+max(l-1,n-r))<<endl; } return 0; }
C：
回收开头。
题意简洁明了，求方程$ax+by=c$的一组正整数解，满足$x+yleq n$
数据范围$nleq 10^{12},cleq 10^{17},b<aleq 10^{5}$
花了10min写了一个exgcd，然后wa on 5。当时我就自闭了。
注意到exgcd求出答案后要乘$frac{c}{gcd(a,b)}$，而这个会爆long long，cf又好像不支持__int128。
换一种思路，能不能求一个x使得$axequiv c(mod b)$呢？
首先我们容易发现，至多枚举b个x就会出现0。
如果我们将x从大往小枚举，那么当第一次出现一个x满足题意时，这个答案一定是a最多且b最少的。
此时由于$a>b$，那么$x+y$的值一定是最小的。
或者，注意到$d>w$，那么必定有$y>w$，或者说求出y后需要$mod w$
因为每w个d的贡献等于d个w的贡献，而后者用的个数较少。
那么由于$d,wleq 10^5$，枚举y求解即可。
（当然你把c先膜一下然后做，最后再加回来也是可以的，我还是太蔡了）
#include<bits/stdc++.h> #define maxn 100005 #define maxm 500005 #define inf 0x7fffffff #define ll long long using namespace std; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } int main(){ ll n=read(),p=read(),a=read(),b=read(),x=p/a,T=maxn; while(T--){ if((p-x*a)%b==0){ if(x<0 || x+(p-x*a)/b>n){cout<<-1<<endl;return 0;} else{cout<<x<<" "<<(p-x*a)/b<<" "<<n-(x+(p-x*a)/b)<<endl;return 0;} } x--; } cout<<-1<<endl; return 0; }
D：
送分题，注意到只有一条链满足题意就完事了。
（那么div2开题应该从D开始开？）
#include<bits/stdc++.h> #define maxn 100005 #define maxm 500005 #define inf 0x7fffffff #define ll long long using namespace std; int N,hd[maxn],to[maxn<<1],nxt[maxn<<1],cnt,siz[maxn],deg[maxn]; ll cst[3][maxn],dp[maxn][3][3]; int from[maxn][3][3][2],cl[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void addedge(ll u,ll v){ to[++cnt]=v,nxt[cnt]=hd[u],hd[u]=cnt; } inline void dfs(int u,int fa){ int son=0; //cout<<u<<":"<<fa<<endl; for(int i=hd[u];i;i=nxt[i]) if(to[i]!=fa) son=to[i],dfs(son,u); //cout<<son<<endl; if(!son){ for(int i=0;i<3;i++) dp[u][i][i]=cst[i][u]; return; } for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) if(dp[u][i][j]>dp[son][j][k]+cst[i][u] && i!=j && i!=k) dp[u][i][j]=dp[son][j][k]+cst[i][u],from[u][i][j][0]=j,from[u][i][j][1]=k; return; } inline void find(int u,int fa,int x,int y){ cl[u]=x; int son=0; for(int i=hd[u];i;i=nxt[i]) if(to[i]!=fa) son=to[i]; if(son) find(son,u,from[u][x][y][0],from[u][x][y][1]); return; } int main(){ memset(dp,127,sizeof(dp)); N=read(); for(ll k=0;k<3;k++) for(ll i=1;i<=N;i++) cst[k][i]=read(); for(ll i=1;i<=N-1;i++){ ll u=read(),v=read(); addedge(u,v),addedge(v,u); deg[u]++,deg[v]++; } bool flag=0; ll num=0,rt=0; for(ll i=1;i<=N;i++){ if(deg[i]>=3){flag=1;break;} if(deg[i]==1) rt=i; } if(flag) cout<<-1<<endl; else{ dfs(rt,0); ll ans=(1ll<<62),r1=0,r2=0; for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(dp[rt][i][j]<ans) ans=dp[rt][i][j],r1=i,r2=j; find(rt,0,r1,r2); cout<<ans<<endl; for(int i=1;i<=N;i++) cout<<cl[i]+1<<" "; cout<<endl; } return 0; }
E：
送分题，排个序之后从两边往中间依次考虑即可。
我都不知道这题为啥不出到B。
#include<bits/stdc++.h> #define maxn 100005 #define maxm 500005 #define inf 0x7fffffff #define ll long long using namespace std; ll N,K,A[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } int main(){ N=read(),K=read(); for(ll i=1;i<=N;i++) A[i]=read(); sort(A+1,A+1+N); ll ans=0; for(ll i=1;i<=N;i++){ ll l=i,r=N-i+1; if(l>r){ans=0;break;} if(K>=(A[l+1]-A[l])*i) K-=(A[l+1]-A[l])*i,l++; else{ans=A[r]-(A[l]+(K/i));break;} if(K>=(A[r]-A[r-1])*i) K-=(A[r]-A[r-1])*i,r--; else{ans=(A[r]-(K/i))-A[l];break;} } ans=max(ans,1ll*0); cout<<ans<<endl; return 0; }
F：
本场最难写的送分题。
注意到一个长度超过2的相同字符串一定不会改变。
于是我们统计出所有这样的不变子串，那么相邻两个子串间一定是01交替出现。
每次变换相当于将每个不变子串向左右扩张一位。
如果和这个子串相邻的也是不变子串那么停止扩张。
注意把数组开大。
#include<bits/stdc++.h> #define maxn 1000005 #define maxm 500005 #define inf 0x7fffffff #define ll long long using namespace std; int N,k; char str[maxn],res[maxn],ans[maxn]; pair<int,int> p[maxn]; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline char cn(char a){ if(a=='B') return 'W'; else return 'B'; } int main(){ N=read(),k=read(); cin>>str+1; for(int i=1;i<=N;i++) str[N+i]=str[i]; for(int i=1;i<=N;i++) str[2*N+i]=str[i]; str[0]=str[N]; int s=0,tot=0; for(int i=1;i<=N;i++) if(str[i+1]==str[i] && str[i-1]!=str[i]) {s=i;break;} if(!s){ if(str[1]==str[2]){for(int i=1;i<=N;i++) cout<<str[i];cout<<endl;} else if(k%2){for(int i=1;i<=N;i++) cout<<cn(str[i]);cout<<endl;} else{for(int i=1;i<=N;i++) cout<<str[i];cout<<endl;} return 0; } for(int i=s;i<=s+N-1;){ int j=i; while(str[j]==str[j+1]&&j+1<=s+N-1) j++; if(j==i){i=j+1;continue;} p[++tot]=make_pair(i,j),i=j+1; } p[++tot]=p[1],p[tot].first+=N,p[tot].second+=N; for(int j=2;j<=tot;j++){ int l=p[j-1].second+1,r=p[j].first-1; if(l<=r){ if(str[p[j].first]==str[p[j-1].first]){ char co=str[p[j].first]; if(k*2>=(r-l+1)) for(int i=l;i<=r;i++) res[i]=co; else{ for(int i=l;i<=l+k-1;i++) res[i]=co; for(int i=r;i>=r-k+1;i--) res[i]=co; for(int i=l+k;i<=r-k;i++) res[i]=(k%2)?cn(str[i]):str[i]; } } else{ char co=str[p[j].first],coo=str[p[j-1].first]; if(k*2>=(r-l+1)){ int num=(r-l+1)>>1; for(int i=l;i<=(l+r)>>1;i++) res[i]=coo; for(int i=r;i>((l+r)>>1);i--) res[i]=co; } else{ for(int i=l;i<=l+k-1;i++) res[i]=coo; for(int i=r;i>=r-k+1;i--) res[i]=co; for(int i=l+k;i<=r-k;i++) res[i]=(k%2)?cn(str[i]):str[i]; } } } for(int i=p[j-1].first;i<=p[j-1].second;i++) res[i]=str[p[j-1].first]; } for(int i=s;i<=s+N-1;i++) ans[(i-1)%N+1]=res[i]; for(int i=1;i<=N;i++) cout<<ans[i]; cout<<endl; return 0; }
G：
需要想一下的送分题。
容易发现两个序列都顺着排答案最小，一个顺着排一个倒着排最大。
那么如果k小于最小的答案直接-1，大于最大的答案直接最大。
对于其他的情况，我们先固定A是顺着排的，然后考虑第i个位置的max是A还是B。
假如是A，那么将B里面当前没用的最小的放在这里，容易证明这个东西一定小于A。
假如是B，注意到任意$[0,K-n imes(n-1)]$之间的数一定能用1-n凑出来。（因为仅用1-n之间2的幂次就能凑出来了）
那么从左向右依次考虑B中的最大数填在哪即可实现凑出来的过程，此时答案一定为K。
#include<bits/stdc++.h> #define maxn 1000005 #define maxm 500005 #define inf 0x7fffffff #define ll long long using namespace std; ll N,K,A[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } int main(){ N=read(),K=read(); ll mx=0,ans=0; for(ll i=1;i<=N;i++) ans+=i,mx+=max(i,N-i+1); if(K<ans){cout<<-1<<endl;return 0;} if(K>=mx){ cout<<mx<<endl; for(ll i=1;i<=N;i++) cout<<i<<" ";cout<<endl; for(ll i=1;i<=N;i++) cout<<N-i+1<<" ";cout<<endl; return 0; } ll l=1,r=N; for(ll i=1;i<=N;i++){ if(K>=ans+r-i && r-i>=0) ans+=r-i,A[i]=r,r--; else A[i]=l,l++; } cout<<ans<<endl; for(ll i=1;i<=N;i++) cout<<i<<" ";cout<<endl; for(ll i=1;i<=N;i++) cout<<A[i]<<" ";cout<<endl; return 0; }
总结：
1.当你一个题写完后wa on pretest而且并不知道为什么，那么如果你没有读错题就果断跳过。
2.Div2可以考虑倒着开题，或者中间开题。
3.能请一个人来帮你口胡总是好的。