洛谷P3825 [NOI2017] 游戏 题解
洛谷P3825 [NOI2017] 游戏 题解
题目链接：P3825 [NOI2017] 游戏
题目描述
小 L 计划进行 \(n\) 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。
小 L 的赛车有三辆，分别用大写字母 \(A\)、\(B\)、\(C\) 表示。地图一共有四种，分别用小写字母 \(x\)、\(a\)、\(b\)、\(c\) 表示。
其中，赛车 \(A\) 不适合在地图 \(a\) 上使用，赛车 \(B\) 不适合在地图 \(b\) 上使用，赛车 \(C\) 不适合在地图 \(c\) 上使用，而地图 \(x\) 则适合所有赛车参加。
适合所有赛车参加的地图并不多见，最多只会有 \(d\) 张。
\(n\) 场游戏的地图可以用一个小写字母组成的字符串描述。例如：\(S=\texttt{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。输入格式
输入第一行包含两个非负整数 \(n\), \(d\)。
输入第二行为一个字符串 \(S\)。
\(n\), \(d\), \(S\) 的含义见题目描述，其中 \(S\) 包含 \(n\) 个字符，且其中恰好 \(d\) 个为小写字母 \(x\)。
输入第三行为一个正整数 \(m\) ，表示有 \(m\) 条用车规则。
接下来 \(m\) 行，每行包含一个四元组 \(i,h_i,j,h_j\) ，其中 \(i,j\) 为整数，\(h_i,h_j\) 为字符 \(A\) 、\(B\) 或 \(C\)，含义见题目描述。
输出格式
输出一行。
若无解输出
-1。若有解，则包含一个长度为 \(n\) 的仅包含大写字母 A、B、C 的字符串，表示小 L 在这 \(n\) 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。
数据范围
\(n\le 5\times 10^4,d\le 8,m\le 10^5\)
什么恶心卡常题，心态要崩了。
update20261104 据说有 \(O(n+m+d2^d)\) 的解法，GPT-6.1 Sol 写的，看得懂的话我会更新这种做法
以下暂时只有旧的题解，敬请期待～说实话我 2-SAT 什么的已经不太记得了，不知道什么时候才会开始写
这篇题解在uoj是过不了Extra Test 12的，但是洛谷可以过hack数据。
显然 \(\mathtt{2-SAT}\) ，但是
x 的出现意味这道题还要加一个 \(\mathtt{3-SAT}\)
众所周知， \(\mathtt{k-SAT}\) 在 \(k>2\) 时被证明是NP完全的
因此只能暴力枚举所有 x 的选法
这里的暴力可以优化为枚举每个 x 地图为 a
地图还是 b 地图
这样为什么对呢？
因为 a 适合 BC ，b 适合
AC ，然后我们就把填 ABC 的三种情况都试过了
考虑没有 x 的部分怎么做
如果 \(i\) 的位置适合 \(h_i\) 赛车，但 \(j\) 不适合 \(h_j\) 赛车
则把 \(u_i\) 向 \(u_{i}^{\prime}\) 连有向边，表示如果选了 \(h_i\) 一定无解
如果 \(i\) 的位置适合 \(h_i\) 赛车，\(j\) 的位置适合 \(h_j\) 赛车
那就把 \(u_i\) 向 \(v_i\) 连有向边，\(v_{i}^{\prime}\) 向 \(u_{i}^{\prime}\) 连有向边，显然。
时间复杂度 \(O(2^d \times (n+m))\)
代码：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
// #define gc() readchar()
#define gc() getchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
void readc(char &ch)
{
char t=getchar();
while(!isupper(t)) t=gc();
ch=t;
}
}using namespace FastIO;
#define N ((int)(2e5+15))
bitset<N> vis,ins;
mt19937 rd(time(0));
int n,m,d,scnt,top,dfncnt,pos=1;
char s[N],col[N],a2[N],b2[N];
int head[N],id[N],a1[N],b1[N],stk[N],dfn[N],low[N],scc[N];
struct Edge{int u,v,next;} e[N];
int tran(int x,char c)
{
if(s[x]=='a') return c=='B'?x:x+n;
if(s[x]=='b'||s[x]=='c') return c=='A'?x:x+n;
if(c=='C') return x+n; return x;
}
int neg(int x){return x > n ? x-n : x+n;}
void addEdge(int u,int v)
{
e[++pos]={u,v,head[u]};
head[u]=pos;
}
bool Tarjan(int u)
{
dfn[u]=low[u]=++dfncnt;
ins[stk[++top]=u]=vis[u]=1;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(!vis[v])
{
if(!Tarjan(v)) return 0;
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
int v; scc[u]=++scnt; ins[u]=0;
while(v=stk[top--],v!=u)
{
scc[v]=scnt,ins[v]=0;
if(scc[v]==scc[neg(v)]) return 0;
}
}
return 1;
}
bool solve()
{
scnt=dfncnt=top=0; pos=1; vis=ins=0;
for(int i=1; i<=(n<<1); i++) scc[i]=head[i]=dfn[i]=0;
for(int i=1; i<=m; i++)
{
if(s[a1[i]] != 'x' && s[b1[i]] != 'x')
{
if(a2[i] == s[a1[i]]-32) continue;
int u=tran(a1[i],a2[i]),v;
if(b2[i] == s[b1[i]]-32) {addEdge(u,neg(u)); continue;}
v=tran(b1[i],b2[i]); addEdge(u,v);
addEdge(neg(v),neg(u));
}else
{
char o = s[a1[i]], p = s[b1[i]];
int u,v, x=id[a1[i]], y=id[b1[i]];
if(o == 'x' && p == 'x')
{
if(a2[i] == col[x]) continue;
u=tran(a1[i],a2[i]);
if(b2[i] == col[y]) {addEdge(u,neg(u)); continue;}
v=tran(b1[i],b2[i]); addEdge(u,v);
addEdge(neg(v),neg(u));
}
else if(o == 'x' && p != 'x')
{
if(a2[i] == col[x]) continue;
u=tran(a1[i],a2[i]);
if(b2[i] == s[b1[i]]-32) {addEdge(u,neg(u)); continue;}
v=tran(b1[i],b2[i]); addEdge(u,v);
addEdge(neg(v),neg(u));
}
else
{
if(a2[i] == s[a1[i]]-32) continue;
u=tran(a1[i],a2[i]);
if(b2[i] == col[y]) {addEdge(u,neg(u)); continue;}
v=tran(b1[i],b2[i]); addEdge(u,v);
addEdge(neg(v),neg(u));
}
}
}
for(int i=1; i<=(n<<1); i++) if(!vis[i]&&!Tarjan(i)) return 0;
for(int i=1; i<=n; i++)
{
if(scc[i]<scc[i+n])
{
if(s[i]=='a') pc('B');
else if(s[i]=='b'||s[i]=='c') pc('A');
else if(col[id[i]]=='A') pc('B');
else pc('A');
}else
{
if(s[i]=='a'||s[i]=='b') pc('C');
else if(s[i]=='c') pc('B');
else if(col[id[i]]=='A') pc('C');
else pc('B');
}
}
puts("");
return 1;
}
signed main()
{
int st=clock();
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int _; read(n); read(_); scanf("%s",s+1); read(m);
for(int i=1; i<=n; i++) if(s[i]=='x') id[i]=++d;
for(int i=1; i<=m; i++) read(a1[i]),readc(a2[i]),read(b1[i]),readc(b2[i]);
for(int i=0; i<(1<<d); i++)
{
for(int j=0; j<d; j++) col[j+1]=((i>>j)&1)?'B':'A';
if(solve()) return 0;
}
puts("-1");
// printf("times used %.3lf s",(1.0*clock()-st)/CLOCKS_PER_SEC);
return 0;
}
![洛谷P14671 [ICPC 2025 Seoul R] Clean Arrangement 题解](/qwq/img/p55.webp)
