太菜了真的很对不起...

Problem

http://uoj.ac/problem/317

Solution

d 很小，考虑枚举。

ABC 考虑拆点。

如果 ABC 中有一个肯定不选，那么另外两个就可以用异或约束。枚举 A 选不选即可。

约束条件常规建边即可，记得对称。

卡常跑 2 -SAT 即可。

然而 chank 有更好的方法跑得飞快 orz 太强了

具体而言，因为若不选 A，则因为异或的约束，B-C'缩点，C-B' 缩点。

那么枚举的内容改为不选 A / 不选 C，并只拆两个大点，能做到高效率的跑 tarjan（省下很多边）。

chank orzzzzzzzz

太菜了真的很对不起，UOJ 最后一个 hack 怎样都 TLE，只好写卡时判 -1....

Code

// Code by ajcxsu
// Problem: game

#include<bits/stdc++.h>
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}
inline char gc() {
    char ch=getchar();
    while(!isalpha(ch)) ch=getchar();
    return ch;
}

const int N=5e5+10, M=5e6+10, D=N>>1;
int h[N], to[M], nexp[M], p=1;
int bh[N], bp;
extern inline void ins(int a, int b) {
    nexp[p]=h[a], h[a]=p, to[p]=b, p++;
}
char S[N];
int pos[10];
extern inline int opp(int x) { return x>=D?x-D:x+D; }

int dfn[N], low[N], stk[N], t, scc[N], idx, sidx, tag[N], tidx;
char instk[N], ka;
extern inline int mmin(int a, int b) { return a<b?a:b; }
void tarjan(int x) {
    tag[x]=tidx, dfn[x]=low[x]=++idx, stk[++t]=x, instk[x]=1;
    for(int u=h[x];u && !ka;u=nexp[u])
        if(tag[to[u]]!=tidx) tarjan(to[u]), low[x]=mmin(low[x], low[to[u]]);
        else if(instk[to[u]]) low[x]=mmin(low[x], dfn[to[u]]);
    if(dfn[x]==low[x]) {
        sidx++;
        do {
            instk[stk[t]]=0, scc[stk[t]]=sidx;
            if(scc[stk[t]]==scc[opp(stk[t])] && tag[opp(stk[t])]==tidx) ka=1;
        } while(stk[t--]!=x);
    }
}

int n, d;
int cac[10];
void dfs(int x) {
    if(x>d) {
        for(int i=1;i<=d;i++)
            for(int j=pos[i]*3;j<pos[i]*3+3;j++) h[j]=bh[j], h[opp(j)]=bh[opp(j)];
        p=bp;
        for(int i=1;i<=d;i++) {
            if(cac[i]%3==0)
                for(int j=pos[i]*3;j<pos[i]*3+3;j++) {
                    if(j!=cac[i]) ins(opp(j), j);
                    else ins(j, opp(j));
                }
            else {
                ins(opp(cac[i]-1), cac[i]-1);
                ins(cac[i], opp(cac[i]+1)), ins(cac[i]+1, opp(cac[i]));
                ins(opp(cac[i]), cac[i]+1), ins(opp(cac[i]+1), cac[i]);
            }
        }
        idx=sidx=0, tidx++;
        ka=0;
        for(int i=0;i<n*3;i++) {
             if(tag[i]!=tidx) tarjan(i);
             if(tag[i+D]!=tidx) tarjan(i+D);
             if(ka) return;
        }
        char ok=1;
        for(int i=0;i<n*3 && ok;i++) if(scc[i]==scc[opp(i)]) ok=0;
        if(!ok) return;
        for(int i=0;i<n;i++)
            for(int j=i*3;j<i*3+3;j++)
                if(scc[opp(j)]<scc[j]) { putchar('A'+j%3); break; }
        putchar('\n');
        exit(0);
    }
    for(int i=pos[x]*3;i<pos[x]*3+2;i++)
        cac[x]=i, dfs(x+1);
}

int main() {
    gn(n), gn(d), scanf("%s", S), d=0;
    int m, a, c; char b, d;
    gn(m);
    for(int i=1;i<=m;i++) {
        gn(a), b=gc(), gn(c), d=gc();
        ins(opp((a-1)*3+b-'A'), opp((c-1)*3+d-'A'));
        ins((c-1)*3+d-'A', (a-1)*3+b-'A');
    }
    for(int i=0;i<n;i++)
        if(S[i]=='x') pos[++::d]=i;
        else {
            ins(opp(i*3+S[i]-'a'), i*3+S[i]-'a');
            for(int x=i*3;x<i*3+3;x++)
                for(int y=x+1;y<i*3+3;y++)
                    if(x!=i*3+S[i]-'a' && y!=i*3+S[i]-'a')
                        ins(x, opp(y)), ins(y, opp(x)), ins(opp(x), y), ins(opp(y), x);
        }
    for(int i=1;i<=::d;i++)
        for(int j=pos[i]*3;j<pos[i]*3+3;j++) bh[j]=h[j], bh[opp(j)]=h[opp(j)];
    bp=p;
    dfs(1);
    puts("-1\n");
    return 0;
}

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