ZR 集训 Day18 - 人类智慧题合集 · ooliver

什么是人类智慧题？为了方便通过关键词搜索到这篇文章，在此解释一下我对人类智慧题的定义：构造（交互、通信）、Ad-hoc、随机。题单 CF1110E Magic Stones 牛炸了的 Ad-hoc。首先特判 a_1,t_1 与 a_n,t_n 是否相等。先看一组变化： [a_1,a_2,a_3] \rightarrow [a_1,a_1+a_3-a_2,a_3] 尝试差分，得到： [a_2-a_1,a_3-a_2] \rightarrow [a_3-a_2,a_2-a_1] 会发现以上操作对于差分数组而言就是交换相邻项，所以直接判断差分数组构成的集合是否相等即可。代码： C++ #include using namespace std; const int N=2e5+5; int n; int a[N],t[N]; multiset s1,s2; int main(){ cin>>n; for(int i=1;i>a[i]; if(i>1) s1.insert(a[i]-a[i-1]); } for(int i=1;i>t[i]; if(i>1) s2.insert(t[i]-t[i-1]); } if(a[1]==t[1]&&a[n]==t[n]&&s1==s2) cout `#include using namespace std; const int N=2e5+5; int n; int a[N],t[N]; multisetint> s1,s2; int main(){ cin>>n; for(int i=1;in;i++){ cin>>a[i]; if(i>1) s1.insert(a[i]-a[i-1]); } for(int i=1;in;i++){ cin>>t[i]; if(i>1) s2.insert(t[i]-t[i-1]); } if(a[1]==t[1]&&a[n]==t[n]&&s1==s2) cout"Yes"; else cout"No"; return 0; }` CF1270G Subset with Zero Sum 看到这个特殊的数据范围：i-n \le a_i \le i-1，考虑变化成：1 \le i-a_i \le n。如果连边：i \rightarrow i-a_i，之后找到一个环 S，则有： \begin{aligned} \sum_{i\in S} i&=\sum_{i\in S} next_i \\ \sum_{i\in S} i&=\sum_{i\in S} i-a_i \\ \sum_{i\in S} a_i &= 0 \end{aligned} 此时输出找到的环的下标即可。代码： C++ #include using namespace std; const int N=1e6+5; int T,n,now,idx; int a[N],nxt[N],tag[N],ans[N]; void solve(){ now=1,idx=0; scanf("%d",&n); for(int i=1;i `#include using namespace std; const int N=1e6+5; int T,n,now,idx; int a[N],nxt[N],tag[N],ans[N]; void solve(){ now=1,idx=0; scanf("%d",&n); for(int i=1;in;i++){ scanf("%d",a+i); nxt[i]=i-a[i],tag[i]=0; } while(!tag[now]) tag[now]=1,now=nxt[now]; ans[++idx]=now,now=nxt[now]; while(now!=ans[1]) ans[++idx]=now,now=nxt[now]; coutidx"\n"; for(int i=1;iidx;i++) coutans[i]" "; cout"\n"; } int main(){ scanf("%d",&T); while(T--) solve(); return 0; }` CF1672E notepad.exe 观察限制，显然询问次数是 (n+\log V) 次的。暴力的想法肯定是枚举一个高度，对于当前高度二分找到最小的宽度。不难发现，当高度递增，为了使答案最优，我们肯定希望宽度递减。这是我们先二分找出当高度为 1 时最小的宽度 w_1，之后枚举高度 h，最优情况下可以省去 (h-1) 个空格，也就是最优的宽度应为 \frac{w_1-h+1}{h}，向上取整一下就是 \lfloor \frac{w_1}{h} \rfloor。又因为想要更新答案，宽度至少为 \lfloor \frac{w_1}{h} \rfloor，发现此时宽度的取值是一定的，那就直接猜这个值，如果符合条件就更新答案。代码： C++ #include using namespace std; int n,x,w1,ans; int main(){ cin>>n; int l=1,r=4002000; while(l>1; cout>x; if(x==1) r=mid; else l=mid+1; } ans=w1=l; for(int h=2;h>x; if(x!=0) ans=min(ans,w1/h*x); } cout `#include using namespace std; int n,x,w1,ans; int main(){ cin>>n; int l=1,r=4002000; while(lr){ int mid=(l+r)>>1; cout"? "midendl; cin>>x; if(x==1) r=mid; else l=mid+1; } ans=w1=l; for(int h=2;hn;h++){ cout"? "w1/hendl; cin>>x; if(x!=0) ans=min(ans,w1/h*x); } cout"! "ansendl; return 0; }` HDOJ6664 Andy and Maze 随机算法。直接做的话，要求 k 个点不能重复，这个状态很难记录，所以我们考虑随机染色，找颜色不同的路径。这样答案路径被统计的概率就应该是 \frac{k!}{k^k}，重复差不多 300 次正确率就非常高了。代码： C++ #include using namespace std; const int N=1e4+5; int T,n,m,k; int col[N],dp[N][64],u[N],v[N],w[N]; void solve(){ int ans=-1,num=300; cin>>n>>m>>k; for(int i=1;i>u[i]>>v[i]>>w[i]; while(num--){ memset(dp,-0x3f,sizeof dp); for(int i=1;i>T; while(T--) solve(); return 0; } `#include using namespace std; const int N=1e4+5; int T,n,m,k; int col[N],dp[N][64],u[N],v[N],w[N]; void solve(){ int ans=-1,num=300; cin>>n>>m>>k; for(int i=1;im;i++) cin>>u[i]>>v[i]>>w[i]; while(num--){ memset(dp,-0x3f,sizeof dp); for(int i=1;in;i++) col[i]=rand()%k,dp[i][1col[i]]=0; for(int s=1;s(1k);s++) for(int i=1;im;i++){ if(s&(1col[u[i]])) dp[u[i]][s]=max(dp[u[i]][s],dp[v[i]][s^(1col[u[i]])]+w[i]); if(s&(1col[v[i]])) dp[v[i]][s]=max(dp[v[i]][s],dp[u[i]][s^(1col[v[i]])]+w[i]); } for(int i=1;in;i++) ans=max(ans,dp[i][(1k)-1]); } if(ans!=-1) coutans"\n"; else cout"impossible\n"; } int main(){ cin>>T; while(T--) solve(); return 0; }` CF1408F Two Different 不难发现，对于 n=2^k 是很好构造的，我们甚至可以做到让所有数字都变得一样。因为相邻两个是可以变成相同数字的，我们可以用类似归并的思想，递归直到只剩两个元素，否则对左右两边一一配对，就完成了合并。其他情况呢？这里题目要求至多两种不同的数字，根据上面的分析，我们要把 n 拆成两个 2^k 相加的形式，但如果拆不了呢？可以想到，如果这两个 2^k 有重合的部分也是没关系的，因为后面的会把前面的覆盖掉，所以就做完了。代码： C++ #include using namespace std; int n,p,q,x; vector> ans; void solve(int id,int k){ if(k==0) return; if(k==1){ ans.push_back({id+1,id+2}); return; } solve(id,k-1),solve(id+(1>n; for(int i=0;i `#include using namespace std; int n,p,q,x; vectorpairint,int>> ans; void solve(int id,int k){ if(k==0) return; if(k==1){ ans.push_back({id+1,id+2}); return; } solve(id,k-1),solve(id+(1(k-1)),k-1); for(int i=1;i(1(k-1));i++) ans.push_back({id+i,id+i+(1(k-1))}); } signed main(){ cin>>n; for(int i=0;i20;i++) if(n&(1i)) q=p,p=i; if(q!=0) q++,x=n-(1p); solve(0,q); solve(x,p); coutans.size()"\n"; for(auto[x,y]:ans) coutx" "y"\n"; return 0; }` QOJ141 8 染色蒟蒻第一次做通信题，核心就是两个优化：对于度数 $ 代码： C++ #include using namespace std; vector Alice(int n,int m,vector u,vector v,vector c){ vector x,deg(n,0); for(int i=0;i=8) x.push_back(c[i]>>2),x.push_back((c[i]>>1)&1); return x; } vector Bob(int n,int m,vector u,vector v,vector x){ int idx=0; vector c(n,-1),tag(n,-1),deg(n,0),g[200005]; for(int i=0;i=8) c[i]=(x[idx] dfs=[&](int u){ for(int v:g[u]) if(c[u]==c[v]&&tag[v]==-1){ tag[v]=tag[u]^1; dfs(v); } }; for(int i=0;i t(8); for(int v:g[i]) if(c[v]!=-1) t[c[v]]=1; for(int j=0;j `#include using namespace std; vectorint> Alice(int n,int m,vectorint> u,vectorint> v,vectorint> c){ vectorint> x,deg(n,0); for(int i=0;im;i++) deg[u[i]]++,deg[v[i]]++; for(int i=0;in;i++) if(deg[i]>=8) x.push_back(c[i]>>2),x.push_back((c[i]>>1)&1); return x; } vectorint> Bob(int n,int m,vectorint> u,vectorint> v,vectorint> x){ int idx=0; vectorint> c(n,-1),tag(n,-1),deg(n,0),g[200005]; for(int i=0;im;i++) g[u[i]].push_back(v[i]),g[v[i]].push_back(u[i]),deg[u[i]]++,deg[v[i]]++; for(int i=0;in;i++) if(deg[i]>=8) c[i]=(x[idx]1)+x[idx+1],idx+=2; functionvoid(int)> dfs=[&](int u){ for(int v:g[u]) if(c[u]==c[v]&&tag[v]==-1){ tag[v]=tag[u]^1; dfs(v); } }; for(int i=0;in;i++) if(tag[i]==-1&&c[i]!=-1) tag[i]=0,dfs(i); for(int i=0;in;i++) if(tag[i]!=-1) c[i]=(c[i]1)+tag[i]; for(int i=0;in;i++){ if(c[i]!=-1) continue; vectorbool> t(8); for(int v:g[i]) if(c[v]!=-1) t[c[v]]=1; for(int j=0;j8;j++) if(!t[j]) c[i]=j; } return c; }`