「NOI2017」游戏 | dinnerhunt

小 L 计划进行nn场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母A、B、C表示。地图一共有四种，分别用小写字母x、a、b、c表示。其中，赛车A不适合在地图a上使用，赛车B不适合在地图b上使用，赛车C不适合在地图c上使用，而地图x则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有d张。

$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。例如：S=xaabxcbc表示小 L 计划进行 $8$ 场游戏，其中第 $1$ 场和第 $5$ 场的地图类型是x，适合所有赛车，第 $2$ 场和第 $3$ 场的地图是a，不适合赛车A，第 $4$ 场和第 $7$ 场的地图是b，不适合赛车B，第 $6$ 场和第 $8$ 场的地图是c，不适合赛车C。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 (i, h_i, j, h_j)来描述，表示若在第 $i$ 场使用型号为 $h_i$ 的车子，则第 $j$ 场游戏要使用型号为 $h_j$
的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “-1’’（不含双引号）。

输入格式

链接🔗

P3825 [NOI2017]游戏

题解

因为每个地形只能选2种颜色的车，考虑2-SAT
因为x可选3种，不好处理，我们考虑枚举x的颜色，因为每次可以选择两种颜色，所以对于每个x，枚举两种不同颜色即可

代码

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 2e5+10;
struct node
{
    int v,net;
}e[maxd<<1];
int f[maxd],eid;
void init()
{
    memset(f,-1,sizeof(f));
    eid = 0;
}
void insert(int a,int b)
{
    //printf("%d %d\n",a,b);
    e[eid].v = b;
    e[eid].net = f[a];
    f[a] = eid++;
}
int dfn[maxd],low[maxd],idx;
int belong[maxd],scc;
int stk[maxd],top;
bool in_stack[maxd];
void tarjan(int u)
{
    dfn[u] = low[u] = ++idx;
    stk[top++] = u;
    in_stack[u] = true;
    for(int i=f[u];i+1;i=e[i].net)
    {
        int v = e[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]= min(low[u],low[v]);
        }
        else if(in_stack[v]) 
            low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        ++scc;
        do
        {
            belong[stk[--top]] = scc;
            in_stack[stk[top]] = false;
        }while(stk[top] != u);
    }
}
struct
{
    int i,j;
    char hi,hj;
}a[maxd];
char s[maxd];
vector<int> pp;
int n,d,len;
char pos[2][maxd];
int re(int x){
    if(x > len) return x-len;
    return x + len;
}
void print()
{
    for(int i=1;i<=len;i++)
    {
        if(belong[i] < belong[re(i)] )
            printf("%c",pos[0][i]);
        else printf("%c",pos[1][i]);
    }
}
bool check()
{
    //memset(belong,0,sizeof(belong));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));  
    memset(belong,0,sizeof(belong));  
    init();
    top = scc = idx = 0;
    for(int i=1;i<=n;i++)
    {
        if(s[a[i].i] == a[i].hi) continue;
        int tt = (a[i].hi == pos[0][a[i].i]?a[i].i:a[i].i+len);
        if(s[a[i].j] == a[i].hj) insert(tt,re(tt));
        else
        {
            int ttt = (a[i].hj== pos[0][a[i].j]?a[i].j:a[i].j+len);
            insert(tt,ttt),insert(re(ttt),re(tt));
        }
    }
    for(int i=1;i<=2*len;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=len;i++)
        if(belong[i] == belong[i+len]) return 0;
    return print(),1;
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    
    scanf("%d %d %s",&n,&d,s+1);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %c %d %c",&a[i].i,&a[i].hi,&a[i].j,&a[i].hj);
    for(int i=1;s[i];i++)
    {
       if(s[i] == 'x') pp.push_back(i);
       s[i] = s[i] - ('a' - 'A');
    }
    len = strlen(s+1);
    //printf("%s\n",s+1);
    for(int i=0;i<(1<<d);i++)
    {
        for(int j=0;j<d;j++)
        {
            if(((i>>j)&1) == 1) s[pp[j]] = 'A';
            else s[pp[j]] = 'B';
        }
        //printf("\n%s\n",s+1);
        for(int j=1;s[j];j++)
        {
            if(s[j] == 'A') pos[0][j] = 'B',pos[1][j] = 'C';
            if(s[j] == 'B') pos[0][j] = 'A',pos[1][j] = 'C';
            if(s[j] == 'C') pos[0][j] = 'A',pos[1][j] = 'B';
            //printf("%c %c\n",pos[0][j],pos[1][j]);
        }

        
        if(check()) return 0;
    }
    printf("-1");
    return 0;
}