P10873 题解

· · 题解

Problem Link

题目大意

给 n 个人，每个人的帽子为黑色或白色，每个人可以看到其他人的帽子颜色。

你要为每个人确定一组猜自己头上帽子颜色的策略，使得任何情况下，如果当前有 k 个戴黑帽子的人，那么其中猜对自己帽子颜色的人不少于 \lfloor k/2\rfloor 个，戴白帽子且猜对的人不少于 \lfloor(n-k)/2\rfloor 个。

数据范围：n\le 18。

思路分析

从一个简化的问题的开始，如果想让猜对自己帽子颜色的人总数不少于 \lfloor n/2\rfloor 怎么做。

考虑帽子为黑色的人的集合 S，对于某个人 i，设 i\not\in S，他在 S 和 S+\{i\} 中只能猜对一个。

因此我们可以将 S 和 S+\{i\} 连一条边，并对整张图定向，如果最终图中的边是 S\to S+\{i\}，就在当前状态下猜测帽子颜色为白，否则猜测黑。

那么对于每种状态，猜对的人等于其出度，要求就是每个点出度至少为入度 -1。

这是经典欧拉回路模型，把所有度数为奇数的点向一个虚点连边，求出欧拉回路后每个点出度与入度之差 \in[-1,1]。

但这题要对黑帽子的人和白脑子的人分别限制，那么拆点表示两个限制，连边 (S,0),(S+\{i\},1) 即可。

时间复杂度 \mathcal O(n^22^n)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=6e5+5,MAXM=1e7+5;
struct Edge { int v,id,x; };
vector <Edge> G[MAXN];
bool vis[MAXM];
string S[20];
int n,m,cur[MAXN];
int ns(int s,int x) {
    int t=0;
    for(int i=0;i<n;++i) if(i^x) t=t<<1|(s>>i&1);
    return t;
}
void dfs(int u) {
    for(int &i=cur[u];i<(int)G[u].size();++i) {
        Edge e=G[u][i];
        if(vis[e.id]) continue;
        vis[e.id]=true,dfs(e.v);
        if(~e.x) S[e.x][ns(u,e.x)]="BC"[u>>e.x&1];
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;++i) S[i]=string(1<<(n-1),'.');
    int U=(1<<n);
    for(int s=0;s<U;++s) for(int i=0;i<n;++i) if(s>>i&1) {
        G[s|U].push_back({s^(1<<i),m,i}),G[s^(1<<i)].push_back({s|U,m,i}),++m;
    }
    for(int s=0;s<2*U;++s) if(G[s].size()&1) {
        G[s].push_back({2*U,m,-1}),G[1<<n].push_back({2*U,m,-1}),++m;
    }
    for(int i=0;i<=2*U;++i) dfs(i);
    for(int i=0;i<n;++i) cout<<S[i]<<"\n";
    return 0;
}