（bzoj没有spj......很好奇为什么还是有人AC233）
题目（LibreOJ）
题目（洛谷）
来说说这题吧~
看完题就看数据范围：d<=8，嗯，可以暴力枚举了。
注意到题目：“赛车A不适合在地图a上使用，赛车B不适合在地图b上使用，赛车C不适合在地图c上使用，而地图x则适合所有赛车参加。”，这说明：我们只需要将x设为a或b就行。因为设为a的话就可以放BC，设为b的话就可以放AC，两种情况合起来就是ABC，所以我们只需要枚举2^d次情况即可，对每一种情况做一遍2-SAT即可，并找到可以的情况就停止枚举。
打印解的话，就按照原来的图进行tarjan后的图跑拓扑序即可，并且在拓扑序上对需要打印的点和不可以打印的点分别染色，最后从左到右扫一遍就行。
然而重点是这个2-SAT的图怎么建：
假设某一要求为2 A 3 B，即第2局放A的话第3局必须放B，
如果第2局的地图不能放A，好，直接无视；
如果第3局的地图不能放B，就说明第2局的地图也不能放A，但此时第2局的地图可以放A，所以需要连一条边：放A推向不放A，表示选了放A就无解；
如果第2局的地图可以放A，第3局的地图可以放B，那就连两条边：放A推向放B，不放B推向不放A（真命题的逆否命题也是真命题）。
然后就做完了
#include <bits/stdc++.h>
using namespace std;
template <class _E> inline void read(_E &e){
e=0;int ck=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')ck=-1;ch=getchar();}
while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
e*=ck;
}
const int N=150050;
int n,d,m;
char ss[N];
int vis_tarjan[N],low[N],dfn[N],belong[N],idx,huan;
char ans[N];
stack <int> s;
int cnt,mark[N],p[N],e[N],pos[9];
vector <int> f[N],g[N];
int in[N];
struct op{
int a;int ha;
int b;int hb;
}Q[100050];
void tarjan(int u){
s.push(u);vis_tarjan[u]=1;
low[u]=dfn[u]=++idx;
for (int i=0;i<g[u].size();++i){
int v=g[u][i];
if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if (vis_tarjan[v]) low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u]){
int v;++huan;
do{v=s.top();s.pop();belong[v]=huan;vis_tarjan[v]=0;}while(u!=v);
}
}
bool cant=1,dont[N];
inline void check_init(){
memset(dfn,0,sizeof dfn);idx=huan=0;
for (int i=0;i<N;++i) g[i].clear();
}
inline void check(){
check_init();
for (int i=1;i<=n;++i){
int a=(ss[i]-'a')*n+i,b=(a-1+n
dont[a]=1,dont[b]=dont[c]=0;
p[b]=c,p[c]=b;
}
for (int i=1;i<=m;++i){
int a=Q[i].ha*n+Q[i].a,b=Q[i].hb*n+Q[i].b;
if (a==b||dont[a]) continue;
if (Q[i].a==Q[i].b||dont[b]){
g[a].push_back(p[a]);
continue;
}
g[p[b]].push_back(p[a]);
g[a].push_back(b);
}
for (int i=1;i<=3*n;++i) if (!dfn[i]&&!dont[i]) tarjan(i);
for (int i=1;i<=3*n;++i){
if (dont[i]) continue;
if (belong[i]==belong[p[i]]) return;
e[belong[p[i]]]=belong[i],e[belong[i]]=belong[p[i]];
}
cant=0;
}
void dfspos(int now){
if (now==d+1){
check();
return;
}
ss[pos[now]]='a';dfspos(now+1);
if(!cant)return;
ss[pos[now]]='b';dfspos(now+1);
}
void color(int u){
if (mark[u]!=-1) return;
mark[u]=0,mark[e[u]]=1;
for (int i=0;i<f[u].size();++i) color(f[u][i]);
}
inline void printans(){
if (cant) puts("-1"),exit(0);
for (int i=1;i<=3*n;++i){
if (dont[i]) continue;
for (int j=0;j<g[i].size();++j){
int v=g[i][j];
if (belong[v]==belong[i]) continue;
f[belong[v]].push_back(belong[i]);++in[belong[i]];
}
}
queue <int> q;
memset(mark,-1,sizeof mark);
for (int i=1;i<=huan;++i) if (!in[i]) q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
for (int i=0;i<f[u].size();++i){
int v=f[u][i];
--in[v];if (!in[v]) q.push(v);
}
if (mark[u]==-1) color(e[u]);
}
for (int i=1;i<=3*n;++i)
if (!dont[i]&&mark[belong[i]]==1)
ans[(i-1
printf(
}
int main(){
read(n),read(d);
scanf(
read(m);
for (int i=1;i<=m;++i){
char hha[2],hhb[2];
read(Q[i].a);scanf(
read(Q[i].b);scanf(
}
for (int i=1;i<=n;++i) if (ss[i]=='x') pos[++cnt]=i;
dfspos(1);
printans();
return 0;
}
另外不要像我一样用vector...uoj最后一个点被卡掉了
Comments NOTHING