CodeForces Global round 8 CF1368D,CF1368E,CF1368F题解

D. AND, OR and square sum

首先必须要知道的是: $$x+y=xANDy+xORy$$ 然后就可以发现操作结束后总和不会变。 然后显然可以发现这些数应该使得大的尽可能大，这样才能满足$$\sum _{i=1}^n{a}_i^2$$ 尽可能大。 然后做法就显然了，对于操作$i,j$,其实就是把$a_i$所拥有的$a_j$没有的bit移给$a_j$。 code:

#include<bits/stdc++.h> #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a<b;++a) #define KEEP while(1) #define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define random(a) rng()%a #define ALL(a) a.begin(),a.end() #define POB pop_back #define ff fflush(stdout) #define fastio ios::sync_with_stdio(false) #define debug_pair(A) cerr<<A.FIR<<" "<<A.SEC<<endl; using namespace std; const int INF=0x3f3f3f3f; typedef pair<int,int> mp; typedef pair<mp,mp> superpair; int cnt[31]; int main(){ fastio; int n; cin>>n; rb(i,1,n) { int ai; cin>>ai; rep(j,31){ if(ai&(1<<j)) { cnt[j]++; } } } LL res=0; rb(i,1,n){ LL ai=0; rep(j,31){ if(cnt[j]){ ai+=1<<j; cnt[j]--; } } res+=ai*ai; } cout<<res<<endl; return 0; }

E. Ski Accidents

*把边反过来：所有的点的入度 $\le 2$ * 从前往后考虑，考虑第i个，如果以这个点开始存在一条dangerous path 就关闭这个点。 这样会删掉多少个点呢? 首先，先分一个组。 对于删掉后的图，如果从一个点走出去最多走出去1个(包括这个点)则分到组$G_1$如果2个分到组$G_2$，剩下删掉的分到$G_3$。 由于每一给点的入度$\le 2$所以,$|G_2|\ge |G_3|/2$,同理$|G_1|\ge |G_2|/2$,由于$|G_1|+|G_2|+|G_3|=n$可得： $$(7/4)\ast |G_3|\le n\Rightarrow |G_3|\le (4/7)\ast n$$ code:

#include<bits/stdc++.h> #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a<b;++a) #define KEEP while(1) #define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define random(a) rng()%a #define ALL(a) a.begin(),a.end() #define POB pop_back #define ff fflush(stdout) #define fastio ios::sync_with_stdio(false) #define debug_pair(A) cerr<<A.FIR<<" "<<A.SEC<<endl; using namespace std; const int INF=0x3f3f3f3f; typedef pair<int,int> mp; typedef pair<mp,mp> superpair; int T; int n,m; vector<int> g[200000+2]; bool vis[200000+2]; void solve(){ cin>>n>>m; rb(i,1,n) g[i].clear(),vis[i]=0; rb(i,1,m) { int u,v; cin>>u>>v; g[v].PB(u); } vector<int> res; rb(i,1,n){ bool ok=0; for(auto it:g[i]){ if(ok) break; if(!vis[it]) for(auto it2:g[it]){ if(!vis[it2]){ ok=1; break; } } } if(ok){ vis[i]=1; res.PB(i); } // done:; } cout<<res.size()<<endl; for(auto it:res){ cout<<it<<" "; } cout<<endl; } int main(){ fastio; cin>>T; while(T--) { // cout<<"#\n"; solve(); } return 0; }

F. Lamps on a Circle

首先可以发现如果你放了k个后存在一段连续的长度为k的开着的灯，那么这k个灯可以被削掉，这样总数上并没有变。 当然你也不可能故意让对手消掉这么多，换取更优解，毕竟你无法控制对方。 所以上述操作是一次无效操作。 可以获得性质1：

操作完剩余最长的连续的1长度$<k$

然后就可以发现如果你的策略最终造成的局面不是很"均匀"那么，对方完全可以在密集的地方删除,所以稀疏的地方就浪费了。 可以获得性质2：

尽可能均匀

所以可以大概想到最终的结果是一段一段长度为k的连续的1，中间空着0（1表示亮着），每次点亮k+1个就ok了，因为每次最多消掉k个。其中k可以枚举。 code:

#include<bits/stdc++.h> #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a<b;++a) #define KEEP while(1) #define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define random(a) rng()%a #define ALL(a) a.begin(),a.end() #define POB pop_back #define ff fflush(stdout) #define fastio ios::sync_with_stdio(false) #define debug_pair(A) cerr<<A.FIR<<" "<<A.SEC<<endl; using namespace std; const int INF=0x3f3f3f3f; typedef pair<int,int> mp; typedef pair<mp,mp> superpair; bool on[1002],need[1002]; int n,m; void query(vector<int> v){ // cerr<<"?"; cout<<v.size()<<" "; for(auto it: v){ on[it]=1; cout<<it<<" "; } cout<<endl; ff; int pos; cin>>pos; rb(i,1,v.size()){ on[(pos+i-1)%n ? (pos+i-1)%n:n]=0; // cout<<((pos+i-1)%n ? (pos+i-1)%n:n)<<endl; } } int main(){ fastio; cin>>n; if(n<=3){ cout<<0<<endl; ff; return 0; } int best=-INF; rb(i,1,n){ rb(j,1,n) need[j]=0; for(int j=1,cnt=1;j<=n;j++,cnt++){ if(cnt==i+1){ cnt=0; continue; } need[j]=1; } need[n]=0; int tmp=0; rb(j,1,n) tmp+=need[j]; if(tmp>best+i){ best=tmp-i; m=i; } } // cout<<m<<" "<<best<<endl; rb(j,1,n) need[j]=0; for(int j=1,cnt=1;j<=n;j++,cnt++){ if(cnt==m+1){ cnt=0; continue; } need[j]=1; } need[n]=0; while(1){ vector<int> que; rb(i,1,n){ if(need[i]&&!on[i]){ que.PB(i); if(que.size()==m+1) break; } } // cout<<que.size()<<endl; if(que.size()<=1) break; query(que); bool ok=1; rb(i,1,n){ if(need[i]){ if(i>que[que.size()-1]) ok=0; } } if(ok){ break; } } cout<<0<<endl; return 0; }