Problem

https://www.luogu.org/problemnew/show/P1039

Solution

考虑将每个人拆成四个点 $(x, x', y, y')$，代表说真 / 假和是否为罪犯。

然后针对题目建立约束条件。天数进行特殊处理，对不能确定说假话的人进行枚举。

时间复杂度约 $O(C_m^nmp)$，然而手造数据很水跑得很快。

顺便 2 -sat 部分甚至可以直接并查集... 因为连的都是双向边。

可能我就是不太能想到好做法吧，不能一遍 AC。

争取下次一遍 A。

注意一些细节：尽量选择不是罪犯的选项。如果出现了可以全部都不是罪犯，则判断是否有 n - 1 个确定不为罪犯，那么剩下那个肯定是罪犯，否则就是 Not Determine。如果压根无解，就是 Impossible（这里我觉得题面有点不严谨）。

Code

// Code by ajcxsu
// Problem: detective

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

unordered_map<string, int> mp, s2day;

const int N=200, M=1e4+10, D=100, H=50;
int day[N];
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
int opp[N];

bool rcov[N], rcov2[N];
bool cov[N];

int m, n;
int stk[N], t;
bool dfs(int x) {
    if(cov[opp[x]]) return 0;
    if(cov[x]) return 1;
    cov[x]=1, stk[++t]=x;
    for(int u=h[x];u;u=nexp[u])
        if(!dfs(to[u])) return 0;
    return 1;
}

int ans=0;
void sel(int x, int k) {
    if(x>n ) {
        if(k!=m) return;
        memset(cov, 0, sizeof(cov));
        for(int i=1;i<=n;i++)
            if(rcov2[i] && !dfs(i)) return;
            else if(rcov2[i+D] && !dfs(i+D)) return;
        int nans=0, oans;
        int cnt=0;
        for(int i=1;i<=n;i++) if(!cov[i+H] && !cov[i+D+H]) {
            oans=i;
            t=0;
            if(!dfs(i+H+D)) {
                while(t) cov[stk[t--]]=0;
                if(!dfs(i+H)) return;
            }
        }
        else cnt+=cov[i+D+H];
        for(int i=1;i<=n;i++) if(cov[i+H]) {
            if(nans) puts("Cannot Determine"), exit(0);
            nans=i;
        }
        if(!nans) {
            if(cnt==n-1) nans=oans;
            else puts("Cannot Determine"), exit(0);
        }
        if(ans && nans!=ans) puts("Cannot Determine"), exit(0);
        ans=nans;
    }
    else {
        if(rcov2[x+D] || rcov2[x]) { sel(x+1, k+rcov2[x+D]); return; }
        if(k<m) rcov2[x+D]=1, sel(x+1, k+1);
        rcov2[x+D]=0, rcov2[x]=1, sel(x+1, k);
    }
}

void choday(int x) {
    memcpy(rcov2, rcov, sizeof(rcov));
    for(int i=1;i<=n;i++)
        if(day[i]==x) rcov2[i]=1;
        else if(day[i] && day[i]!=x) rcov2[i+D]=1;
    for(int i=1;i<=n;i++) if(rcov2[i] && rcov2[i+D]) return;
    sel(1, 0);
    return;
}

string name[N];
int main() {
    s2day["Monday"]=1, s2day["Tuesday"]=2, 
    s2day["Wednesday"]=3, s2day["Thursday"]=4, 
    s2day["Friday"]=5, s2day["Saturday"]=6,
    s2day["Sunday"]=7;
    int p;
    cin>>n>>m>>p;
    string s, t;
    for(int i=1;i<=n;i++) cin>>s, mp[s]=i, opp[i+D]=i, opp[i]=i+D, opp[i+H+D]=i+H, opp[i+H]=i+H+D, name[i]=s;
    string sent;
    int pos;
    char ch;
    for(int i=1;i<=p;i++) {
        sent=""; ch=getchar();
        while(ch=='\r' || ch=='\n') ch=getchar();
        while(ch!='\r' && ch!='\n') sent+=ch, ch=getchar();
        pos=sent.find(':');
        s=sent.substr(0, pos);
        t=sent.substr(pos+2, sent.size()-pos-2);
        pos=mp[s];
        if(t=="I am guilty.") ins(pos, pos+H), ins(pos+D, pos+H+D), ins(pos+H, pos), ins(pos+H+D, pos+D);
        else if(t=="I am not guilty.") ins(pos, pos+D+H), ins(pos+D, pos+H), ins(pos+D+H, pos), ins(pos+H, pos+D);
        else if(t.size()>=10 && t.substr(t.size()-10, 10)=="is guilty.") {
            t=t.substr(0, t.size()-11);
            cerr<<t<<endl;
            if(!mp.count(t)) continue;
            int j=mp[t];
            ins(pos, j+H), ins(pos+D, j+D+H), ins(j+H, pos), ins(j+D+H, pos+D);
        }
        else if(t.size()>=14 && t.substr(t.size()-14, 14)=="is not guilty.") {
            t=t.substr(0, t.size()-15);
            if(!mp.count(t)) continue;
            int j=mp[t];
            ins(pos, j+H+D), ins(pos+D, j+H), ins(j+H+D, pos), ins(pos+D, j+H);
        }
        else if(t.size()>=9 && t.substr(0, 8)=="Today is") {
            t=t.substr(9, t.size()-10);
            if(!s2day.count(t)) continue;
            if(day[pos]) rcov[pos+D]=1;
            day[pos]=s2day[t];
        }
    }
    for(int i=1;i<=7;i++) choday(i);
    if(!ans) puts("Impossible");
    else cout<<name[ans]<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1039.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆