并不对劲的bzoj4945:loj2305:uoj317:p3825[NOI2017]游戏

题目大意

2-SAT，其中有\(d\)(\(d\leq 8\))个点是\(3-SAT\)。

题解

枚举\(d\)个点不取三个中（假设三个为\(a,b,c\)）的哪一个，然后整体变成做\(2-SAT\)。

注意枚举完不选\(a\)（即选\(b或c\)）和不选\(b\)（即选\(a或c\)）后，不选\(c\)（即选\(a或b\)）已经包含在前两种中，因此搜索部分的时间复杂度是\(\Theta(2^d)\)的。

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iomanip>

#include<iostream>

#include<set>

#include<stack>

#include<vector>

#include<queue>

#define LL long long

#define maxn 100007

#define maxm 400007

#define rep(i,x,y) for(int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(int i=(x);i>=(y);--i)

#define view(u,k) for(int k=fir[u];~k;k=nxt[k])

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)&&ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

void write(int x)

{

    int f=0;char ch[20];

    if(x==0){putchar('0');putchar(' ');return ;}

    if(x<0){putchar('-'),x=-x;}

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);putchar(' ');

}

int n,m,d,fir[maxn],nxt[maxm],v[maxm],cnte,dfn[maxn],low[maxn],ans[maxn],ins[maxn],stk[maxn],tp,tim,col[maxn],num;

void ade(int u1,int v1){v[cnte]=v1,nxt[cnte]=fir[u1],fir[u1]=cnte++;}

void tar(int u)

{

	dfn[u]=low[u]=++tim,ins[u]=1,stk[++tp]=u;

	view(u,k)

	{

		if(!dfn[v[k]])tar(v[k]),low[u]=min(low[u],low[v[k]]);

		else if(ins[v[k]])low[u]=min(low[u],dfn[v[k]]);

	}

	if(dfn[u]==low[u])

	{

		num++;

		while(1)

		{

			col[stk[tp]]=num,ins[stk[tp]]=0;

			if(stk[tp--]==u)break;

		}

	}

}

int gx(int x,int f){return x+f*n;}

int getf(char ci,char ti)

{

	if(ti=='a')return ci=='C';

	else if(ti=='b')return ci=='A';

	else return ci=='B';

}

void reset(){int li=n<<1;rep(i,1,li)fir[i]=-1,dfn[i]=ins[i]=0;tim=cnte=tp=0;}

char s[maxn],t[maxn],c1[maxm],c2[maxm];

int pos[10],cntp,x1[maxm],x2[maxm];

int check()

{

	reset();

	rep(i,1,m)

	{

		if(c1[i]-'A'+'a'==t[x1[i]]||(x1[i]==x2[i]&&c1[i]==c2[i]))continue;

		//cout<<gx(x1[i],getf(c1[i],t[x1[i]]))<<" "<<gx(x2[i],getf(c2[i],t[x2[i]]))<<endl;

		if(x1[i]==x2[i]&&c1[i]!=c2[i])

		{

			//cout<<"yes"<<endl;

			ade(gx(x1[i],getf(c1[i],t[x1[i]])),gx(x1[i],getf(c1[i],t[x1[i]])^1));

		}

		else if(c2[i]-'A'+'a'==t[x2[i]])

		{

			ade(gx(x1[i],getf(c1[i],t[x1[i]])),gx(x1[i],getf(c1[i],t[x1[i]])^1));

		}

		else ade(gx(x1[i],getf(c1[i],t[x1[i]])),gx(x2[i],getf(c2[i],t[x2[i]]))),ade(gx(x2[i],getf(c2[i],t[x2[i]])^1),gx(x1[i],getf(c1[i],t[x1[i]])^1));

	}int li=n<<1;

	rep(i,1,li)if(!dfn[i])tar(i);

	rep(i,1,n)if(col[gx(i,0)]==col[gx(i,1)])return 0;

	return 1;

}

int force(int x)

{

	if(x==d+1)return check();

	t[pos[x]]='a';

	if(force(x+1))return 1;

	t[pos[x]]='b';

	return force(x+1);

}

int main()

{

	memset(fir,-1,sizeof(fir));

	n=read(),d=read();

	scanf("%s",s+1);

	rep(i,1,n)if(s[i]=='x')pos[++cntp]=i;

	rep(i,1,n)t[i]=s[i];

	m=read();

	rep(i,1,m)scanf("%d %c %d %c",&x1[i],&c1[i],&x2[i],&c2[i]);

	int yes=force(1);

	if(!yes)puts("-1");

	else

	{

		rep(i,1,n){if(col[gx(i,0)]>col[gx(i,1)])ans[i]=1;}

		rep(i,1,n)

		{

			if(t[i]=='a')putchar(ans[i]?'C':'B');

			if(t[i]=='b')putchar(ans[i]?'A':'C');

			if(t[i]=='c')putchar(ans[i]?'B':'A');

		}

	}

	return 0;

}

一些感想

uoj的最后一组hack数据好毒啊

巴特西

并不对劲的bzoj4945:loj2305:uoj317:p3825[NOI2017]游戏

题目大意

题解

代码

一些感想

最新文章

热门文章