洛谷 P3825

题目传送门

解法说明

题目理解

本题有 $n$ 个地图，每次要求选择一辆车跑，地图分四种即 a ， b ， c ， x ，车分三种 A ， B ， C ， a 型地图不能放 A ， b 型地图不能放 B ， c 型地图不能放 C ， x 型地图能放任何车 ， 但是只有 $d$ 张 x 型地图。

题目思路

显而易见，对于任意的 a ， b ， c 型地图，我们都能很容易的建立出推导关系，不看 x 型地图的话是一个很简单的 2-SAT 裸题。

但是... x 地图并不能按照普通的建立方式建立，那该怎么办？？

观察数据 $k$ 的范围，可以发现 x 图最多只有 $8$ 张，那就简单了，直接暴力枚举，一种情况是不选 A ，一种情况是不选 B ， A 型车被包含在情况 1 中， B 型车被包含在情况 2 中， C 两种情况都有。

通过上述操作，我们将 x 种地图转化为 a 种和 b 种图, 本题的时间复杂度为 $O(2^k⋅(M+N))$ ，并不会超时。

那就可以愉快的写代码了！！！

题目代码

#include<iostream>
#include<cstring>
#define ch getchar
#define in getint
#define ts timestamp
#define ins in_stack
using namespace std;
const int N=100010,M=200010;
int n,d,m;
char s[N];
int h[N],e[M],ne[M],idx;//邻接表 
int dfn[N],low[N],timestamp;// tarjan 算法数组
int stk[N],top;//栈 
bool in_stack[N]; //记录是否在栈中
int id[N],cnt;//纪录每个点所在的强连通分量 
int pos[10];//记录 x 的位置
struct Op
{
	int x,y;
	char a,b;
}op[M];//记录条件
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int in(int x,char b,int t)//返回 x 选 b 时的编号，t 为 1 表示选 -b，t 为 0 表示选 b 
{
	char a=s[x]-'a';
	b-='A';
	if(((a+1)%3!=b)^t) return x+n;
	return x;
}
char ch(int x,int t)
{
	int y=s[x]-'a';
	return 'A'+(y+3+(t? -1 :1))%3;
}
void tarjan(int u)
{
	dfn[u]=low[u]=++ts;
	stk[++top]=u,ins[u]=true;
	for(int i=h[u];~i;i=ne[i])//枚举邻接点
	{
		int j=e[i];
		if(!dfn[j])
		{
			tarjan(j);
			low[u]=min(low[u],low[j]);
		}
		else if(ins[j])
		    low[u]=min(low[u],dfn[j]);
	}
	if(dfn[u]==low[u])
	{
		cnt++;//强连通分量编号
		int y;
		do{
			y=stk[top--];
			ins[y]=false;//出栈 
			id[y]=cnt;
		} while(y!=u);
	}
}
bool launch()
{
	memset(h,-1,sizeof h);
	memset(dfn,0,sizeof dfn);
	idx=ts=cnt=0;
	for(int i=0;i<m;i++)
	{
		int x=op[i].x-1,y=op[i].y-1;//下标改为从 0 开始 
		char a=op[i].a,b=op[i].b;
		if(s[x]!=a-'A'+'a')
		{
			//第 y 张图能取 b 时，即 x 选 a 时 y 必须选 b，得出推导公式 a -> b, -b -> a
			if(s[y]!=b-'A'+'a') add(in(x,a,0),in(y,b,0)),add(in(y,b,1),in(x,a,1));
			//第 y 张图不能取 b 时，即 x 选 a 时 y 无法选 b，则 x 不能选 a，得出推导公式 a -> -a
		    else add(in(x,a,0),in(x,a,1));
		}
	}
	for(int i=0;i<n*2;i++)
	    if(!dfn[i])
	        tarjan(i);
	for(int i=0;i<n;i++)
	    if(id[i]==id[i+n])
		    return false;
	for(int i=0;i<n;i++)
	    if(id[i]<id[i+n]) printf("%c",ch(i,0));
	    else printf("%c",ch(i,1));
	return true;   
}
int main()
{
	scanf("%d%d%s",&n,&d,s);
	for(int i=0,j=0;i<n;i++)
	    if(s[i]=='x')
	        pos[j++]=i;//记录 x 的位置 
	scanf("%d",&m);
	for(int i=0;i<m;i++) scanf("%d %c %d %c",&op[i].x,&op[i].a,&op[i].y,&op[i].b);
	for(int k=0;k<1<<d;k++)//枚举所有可能的 x 的情况 
	{
		for(int i=0;i<d;i++)
		    if(k>>i&1) s[pos[i]]='a';// 0 则转变成 a，1 则转变成 b 
		    else s[pos[i]]='b';
		if(launch()) return 0;//有解直接退出即可 
	}
	//无解 
	puts("-1");
	return 0;
}

D42 2-SAT+二进制枚举

// 2-SAT+二进制枚举 O(2^8*(n+m))
#include<bits/stdc++.h>
using namespace std;

const int N=100005;
int head[N],to[N<<1],ne[N<<1],idx;
int dfn[N],low[N],tim,stk[N],top,scc[N],cnt;
int n,d,m,pos[10]; //pos:x位置
char s[N];         //地图
struct Rule{int i,j;char x,y;}R[N]; //规则

void add(int a,int b){
  to[++idx]=b,ne[idx]=head[a],head[a]=idx;
}
void tarjan(int x){
  dfn[x]=low[x]=++tim;
  stk[++top]=x;
  for(int i=head[x];i;i=ne[i]){
    int y=to[i];
    if(!dfn[y]){ //若y尚未访问
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if(!scc[y]) //若y已访问且未处理
      low[x]=min(low[x],dfn[y]);
  }
  
  if(low[x]==dfn[x]){ //若x是SCC的根
    ++cnt;
    for(int y=-1;y!=x;)
      scc[y=stk[top--]]=cnt;
  }
}
int get(int i,char c,int t){
  return 'A'+(s[i]-'a'+t)%3==c?i:i+n;
}
char put(int i,int t){
  return 'A'+(s[i]-'a'+t)%3;
}
bool solve(){
  memset(head,0,sizeof head);
  memset(dfn,0,sizeof dfn);
  memset(scc,0,sizeof scc);
  idx=tim=top=cnt=0;  
  for(int k=0;k<m;k++){
    int i=R[k].i-1,j=R[k].j-1;
    char x=R[k].x,y=R[k].y;
    if(s[i]==x+32) continue; //i不用x车
    if(s[j]==y+32)           //j不用y车
      add(get(i,x,1),get(i,x,2)); //i→i'
    else{
      add(get(i,x,1),get(j,y,1)); //i→j
      add(get(j,y,2),get(i,x,2)); //j'→i'      
    }
  }
  for(int i=0;i<2*n;i++)if(!dfn[i])tarjan(i);
  for(int i=0;i<n;i++)
    if(scc[i]==scc[i+n]) return false;
  for(int i=0;i<n;i++)
    if(scc[i]<scc[i+n]) putchar(put(i,1));
    else putchar(put(i,2));
  return true;
}
int main(){
  scanf("%d%d %s %d",&n,&d,s,&m);
  for(int i=0;i<m;i++)
    scanf("%d %c %d %c",&R[i].i,&R[i].x,&R[i].j,&R[i].y);
  for(int i=0,j=0;i<n;i++)
    if(s[i]=='x') pos[j++]=i; //x位置
  for(int i=0;i<1<<d;i++){
    for(int j=0;j<d;j++)
      s[pos[j]]=(i>>j&1)?'a':'b'; //x→a或b
    if(solve()) return 0;
  }
  puts("-1"); return 0;
}