这场cf，结论加思维居多。想的道就能秒写,比赛开始1分钟后，A题ac了，第4分钟B题ac了，然后第11分钟交了c，wa了，第33分钟后ac了，没有想会可以直接找字符串，wa了几发，后面暴力直接通过，在这里我挖了一下好的c题代码，然后就是D题，第一眼，看到树，我有点慌，后面看完题目，第53分钟左右ac了。最后比赛还有一个多小时，去刷题去了。写不来E，F。
E，F待补。
A.M. Deviation
题意，就是找三个数，然后按照他给的规则找最小值。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while (t--) { int x,y,z,s; cin>>x>>y>>z; s=x+y+z; x=s/3;y=s/3;z=s-x-y; if (z-y==2) --z,++y; cout<<abs(x+z-2*y)<<'\n'; } }
B.
题意就是，给一个串，然后把他变成单调不递减的，要求你用一个子串（单独不递增）的使输入的串变成不递减的，很显然答案只会有0和1；
#include <bits/stdc++.h> using namespace std; int st[1002],tp; int main() { ios::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while (t--) { int n,cnt=0;tp=0; string s; cin>>n>>s; int i; for (i=0;i+1<n;i++) if (s[i]>s[i+1]) break; if (i+1==n) {cout<<"0\n";continue;} cout<<"1\n"; for (i=0;i<n;i++) cnt+=s[i]=='0'; for (i=0;i<cnt;i++) if (s[i]=='1') st[++tp]=i+1; for (i=cnt;i<n;i++) if (s[i]=='0') st[++tp]=i+1; cout<<tp; for (i=1;i<=tp;i++) cout<<' '<<st[i];cout<<'\n'; } }
C.
题意就是找一个a的数量比b或者c数量多的最长子串，我们可以删前面和后面的字符串来得到这个子串。
最后就是查找固定子串判断就行。
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { string s; int n; cin >> n >> s; if (s.find("aa") < n) puts("2"); else if (s.find("aba") < n || s.find("aca") < n) puts("3"); else if (s.find("abca") < n || s.find("acba") < n) puts("4"); else if (s.find("abbacca") < n || s.find("accabba") < n) puts("7"); else puts("-1"); } }
D
类似二分图，然后结论个数就是n，我们要找一个最多的点要求先手的人能赢，并且要通过
- u⊕v≤min(u,v)这个条件。
- 最后我们建一个树，然后用a[0],a[1]来代表二分图存点。通过深搜来赋值，就行了。
#include <bits/stdc++.h> using namespace std; const int N=2.1e5; vector<int> e[N],a[2]; int dep[N],p[N]; void dfs(int u) { a[dep[u]&1].push_back(u); for (auto &v:e[u]) if (!dep[v]) { dep[v]=dep[u]+1; dfs(v); } } int main() { ios::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while (t--) { int n,i,j; cin>>n; memset(dep+1,0,n*sizeof dep[0]); for (i=0;i<=1;i++) a[i].clear(),a[i].reserve(n); for (i=1;i<=n;i++) e[i].clear(); for (i=1;i<n;i++) { int u,v; //u=i+1;v=rand()%i+1; cin>>u>>v; e[u].push_back(v);e[v].push_back(u); } dfs(dep[1]=1); if (a[0].size()<a[1].size()) swap(a[0],a[1]); for (i=1;i<=n;i<<=1); i>>=1; for (j=i;j<=n;j++) p[a[0].back()]=j,a[0].pop_back(); for (i=0;i<20;i++) if (a[0].size()>>i&1) for (j=1<<i;j<1<<i+1;j++) p[a[0].back()]=j,a[0].pop_back(); for (i=0;i<20;i++) if (a[1].size()>>i&1) for (j=1<<i;j<1<<i+1;j++) p[a[1].back()]=j,a[1].pop_back(); for (i=1;i<=n;i++) for (auto &v:e[i]) assert((p[i]^p[v])>min(p[i],p[v])); for (i=1;i<=n;i++) cout<<p[i]<<" \n"[i==n]; } }
