【题解】炉心融解

· · 题解

令 S 表示一种可能的卡片状态，T 为真实的卡片状态。对于每个人而言，有四种不同的可能状态 S（相邻的两个人的卡片的值有四种可能）。

考虑玩家在什么情况下会宣布胜利：事实上他并不需要准确地知道左右两边的人的卡片分别是什么，只要所有仍然可能的状态得出的答案相同，他就可以做出唯一推断。

玩家推断状态是否合法的信息源：

公布的信息很好处理，玩家只需要排除掉所有与信息冲突的 S 即可。

第二种信息怎么处理暂时还摸不着头脑，不妨先放一放。

假设目前处于第 i 轮，某个玩家在此前还未宣布胜利。若该玩家已经得知可能的四种状态哪些是合法（暂未被排除）的，就可以得出相邻卡片逻辑或/异或的可能值。若该值唯一，则该玩家会宣布胜利。

求出对于卡片状态 S，在第 i 轮结束后已经有哪些玩家宣布了胜利，记这个胜利集合为 vic_S。同样的，对于真实卡片状态 T，也可以求出对应的 vic_T。那么，由于玩家们都知道每一轮宣布胜利的情况，所以若某种卡片状态 S 的 vic_S\neq vic_T，那么集合 S 也应该被所有玩家排除。

于是，玩家们宣布胜利的信息也成功应用了。

每一轮的流程大致如下：

看起来非常正确，但是仍然存在一些漏洞。

流程中的第三步需要用到当前每一种仍然可能的集合的 vic_S，这意味着每个玩家并不能 仅对 于他而言可能的四种集合 进行判断，无论集合 S 对于该玩家合不合法都需要枚举。这里指的合法性并非 mark_S。除了相邻玩家的卡片以外，即使其他玩家（包括自己）的卡片与该玩家所看到的不同，都需要枚举，其他玩家会利用这一点排除他们猜测的集合。

用状态压缩动态规划解决这个问题，时间复杂度为 O(2^nnm+2^n\sum k)。

#include<bits/stdc++.h>
using namespace std;

const int N=17;
int n,m,X;
int mark[1<<N],vic[1<<N],ans[N];
int get_id(int x){return (x<0)?(n-1):((x>=n)?0:x);}
bool check(int i,int s){
    int i0=get_id(i-1),i1=get_id(i+1);
    int s00,s01,s10,s11,res0,res1;
    s11=s|(1<<i0)|(1<<i1);
    s00=s11^(1<<i0)^(1<<i1);
    s01=s00^(1<<i1);
    s10=s00^(1<<i0);
    if((s>>i)&1) res0=mark[s11]|mark[s00],res1=mark[s01]|mark[s10];
    else res0=mark[s00],res1=mark[s01]|mark[s10]|mark[s11];
    if(res0&res1) return false;
    return true;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0,x;i<n;i++) scanf("%d",&x),X|=(x<<i),ans[i]=-1;
    int S=(1<<n)-1;
    for(int i=0;i<=S;i++) mark[i]=1;
    for(int turn=1,T;turn<=m;turn++){
        scanf("%d",&T);
        while(T--){
            int p,x,s1=0,w;
            scanf("%d",&p);
            for(int i=1;i<=p;i++) scanf("%d",&x),s1|=(1<<x);
            scanf("%d",&w);
            for(int i=0;i<=S;i++){
                if(w&&((i&s1)==0)) mark[i]=0;
                if((!w)&&((i&s1)==s1)) mark[i]=0;
            }
        }
        for(int i=0;i<=S;i++){
            if(!mark[i]) continue;
            for(int j=0;j<n;j++)
                if((!((vic[i]>>j)&1))&&check(j,i)) vic[i]|=1<<j;
        }
        for(int i=0;i<=S;i++)
            if(mark[i]&&(vic[i]!=vic[X])) mark[i]=0;
        for(int i=0;i<n;i++)
            if(ans[i]==-1&&((vic[X]>>i)&1)) ans[i]=turn;
    }
    for(int i=0;i<n;i++) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}