[LibreOJ2305]-[NOI2017]游戏

发布于 2018-02-22  81 次阅读



(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最后一个点被卡掉了