什么是人类智慧题？

为了方便通过关键词搜索到这篇文章，在此解释一下我对人类智慧题的定义：构造（交互、通信）、Ad-hoc、随机。

题单

CF1110E Magic Stones

牛炸了的 Ad-hoc。

首先特判 $a_1,t_1$ 与 $a_n,t_n$ 是否相等。

先看一组变化：

$$[a_1,a_2,a_3]\to [a_1,a_1+a_3-a_2,a_3]$$

尝试差分，得到：

$$[a_2-a_1,a_3-a_2]\to [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\text{[PARSE ERROR: Undefined("Command("le")")]}{a}_i\text{[PARSE ERROR: Undefined("Command("le")")]}i-1$，考虑变化成：$1\text{[PARSE ERROR: Undefined("Command("le")")]}i-a_i\text{[PARSE ERROR: Undefined("Command("le")")]}n$。

如果连边：$i\to 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;
}`