什么是人类智慧题？
为了方便通过关键词搜索到这篇文章，在此解释一下我对人类智慧题的定义：构造（交互、通信）、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]
$$
会发现以上操作对于差分数组而言就是交换相邻项，所以直接判断差分数组构成的集合是否相等即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
int a[N],t[N];
multiset<int> s1,s2;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(i>1) s1.insert(a[i]-a[i-1]);
}
for(int i=1;i<=n;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}
$$
此时输出找到的环的下标即可。
代码：
#include<bits/stdc++.h>
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<=n;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];
cout<<idx<<"\n";
for(int i=1;i<=idx;i++) cout<<ans[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$，发现此时宽度的取值是一定的，那就直接猜这个值，如果符合条件就更新答案。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,x,w1,ans;
int main(){
cin>>n;
int l=1,r=4002000;
while(l<r){
int mid=(l+r)>>1;
cout<<"? "<<mid<<endl;
cin>>x;
if(x==1) r=mid;
else l=mid+1;
}
ans=w1=l;
for(int h=2;h<=n;h++){
cout<<"? "<<w1/h<<endl;
cin>>x;
if(x!=0) ans=min(ans,w1/h*x);
}
cout<<"! "<<ans<<endl;
return 0;
}HDOJ6664 Andy and Maze
随机算法。
直接做的话，要求 $k$ 个点不能重复，这个状态很难记录，所以我们考虑随机染色，找颜色不同的路径。
这样答案路径被统计的概率就应该是 $\frac{k!}{k^k}$，重复差不多 $300$ 次正确率就非常高了。
代码：
#include<bits/stdc++.h>
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<=m;i++) cin>>u[i]>>v[i]>>w[i];
while(num--){
memset(dp,-0x3f,sizeof dp);
for(int i=1;i<=n;i++) col[i]=rand()%k,dp[i][1<<col[i]]=0;
for(int s=1;s<(1<<k);s++) for(int i=1;i<=m;i++){
if(s&(1<<col[u[i]]))
dp[u[i]][s]=max(dp[u[i]][s],dp[v[i]][s^(1<<col[u[i]])]+w[i]);
if(s&(1<<col[v[i]]))
dp[v[i]][s]=max(dp[v[i]][s],dp[u[i]][s^(1<<col[v[i]])]+w[i]);
}
for(int i=1;i<=n;i++) ans=max(ans,dp[i][(1<<k)-1]);
}
if(ans!=-1) cout<<ans<<"\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$ 有重合的部分也是没关系的，因为后面的会把前面的覆盖掉，所以就做完了。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,p,q,x;
vector<pair<int,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;i<=20;i++) if(n&(1<<i)) q=p,p=i;
if(q!=0) q++,x=n-(1<<p);
solve(0,q);
solve(x,p);
cout<<ans.size()<<"\n";
for(auto[x,y]:ans) cout<<x<<" "<<y<<"\n";
return 0;
}QOJ141 8 染色
蒟蒻第一次做通信题，核心就是两个优化：
- 对于度数 $<8$ 的点是不需要传递信息的，可以直接根据其临边判断出其颜色。
- 我们完全可以把两个颜色压缩成一个颜色，等 Bob 拿到后对于相同的颜色跑一遍黑白染色即可。
代码：
#include<bits/stdc++.h>
using namespace std;
vector<int> Alice(int n,int m,vector<int> u,vector<int> v,vector<int> c){
vector<int> x,deg(n,0);
for(int i=0;i<m;i++) deg[u[i]]++,deg[v[i]]++;
for(int i=0;i<n;i++) if(deg[i]>=8) x.push_back(c[i]>>2),x.push_back((c[i]>>1)&1);
return x;
}
vector<int> Bob(int n,int m,vector<int> u,vector<int> v,vector<int> x){
int idx=0;
vector<int> c(n,-1),tag(n,-1),deg(n,0),g[200005];
for(int i=0;i<m;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;i<n;i++) if(deg[i]>=8) c[i]=(x[idx]<<1)+x[idx+1],idx+=2;
function<void(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;i<n;i++) if(tag[i]==-1&&c[i]!=-1) tag[i]=0,dfs(i);
for(int i=0;i<n;i++) if(tag[i]!=-1) c[i]=(c[i]<<1)+tag[i];
for(int i=0;i<n;i++){
if(c[i]!=-1) continue;
vector<bool> t(8);
for(int v:g[i]) if(c[v]!=-1) t[c[v]]=1;
for(int j=0;j<8;j++) if(!t[j]) c[i]=j;
}
return c;
}
Comments NOTHING