LOJ#2305 [NOI2017] Game 2-sat Question qwq

Topic link: Portal

2_sat2-sat2_sat good question.
Because D is less than 8dleq8d is less than 8, Coe takes into account that Volley O(2d)O(2^d)O(2d) enumerates all x.
It is found that if'x'takes'a' or'b'here, it can contain the case of this person choosing A/B/CA/B/CA/B/C, so only enumerating two kinds is used to get qwq.
After Fuli enumerates, a certain string strstrstr is obtained.
Then consider transforming this problem into a dependency problem:
For each bit on the string, three nodes are constructed to represent the selection of A,B,CA,B,CA,B,C, respectively.
For each requirement (x,hx,y,hy)(x,h_x,y,h_y)(x,hx, y,hy) classification discussion.

(1)hx==str[x]h_x==str[x]hx​==str[x]
That is to say, this requirement can not be fulfilled. Keyi skipped it.

(2)hy==str[y]h_y==str[y]hy​==str[y]
That is to say, location y y cannot select hy.h_y.hy.
Because if location xxx chooses hxh_xhx, location YY must choose hyh_yhy, so location xxx cannot choose hxh_xhx.
Consider how to force location xxx not to select hxh_xhx:
Assuming that the position xxx has TTT as the other character besides hxh_xhx, it connects an edge from hxh_xhx to ttt.
So if hxh_xhx is selected, it is contradictory that hxh_xhx and ttt must be in the same strongly connected component.
So it's equivalent to mandatory ttt selection.

(3) h x!= str[x] h_x!= str[x] hx!= str[x] hx!= str[x] and H y!= str[y] h_y!= str[y] hy!= str[y]
This is a general situation. According to the common 2_sat2-sat2_sat routine, it is qwq to build the edge of "If A is selected, B is selected" and "If B is not selected, then A is not selected".

After the construction, Dali ran 2_sat2-sat2_sat to get qwq.
Note: Because each point has 333 cases, the processing of characters is very stinky.

Tumor code

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<vector>
#include<cctype>
#define re register int
#define rl register ll
#define lowbit(x) x&(-x)
using namespace std;
typedef long long ll;
int read() {
	re x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9') {
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9') {
		x=10*x+ch-'0';
		ch=getchar();
	}
	return x*f;
}
inline void write(int x) {
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
inline char GetChar() {
	char ch=getchar();
	while(ch!='A' && ch!='B' && ch!='C')	ch=getchar();
	return ch;
}
namespace I_Love {

const int Size=300005;
int n,m,d,x[Size],y[Size];
char hx[Size],hy[Size];
char str[Size];
int pos[15];
void oper(int x) {
	for(re i=1; i<=d; x>>=1,i++) {
		if(x&1) {
			str[pos[i]]='A';
		} else {
			str[pos[i]]='B';
		}
	}
}
int cnt,head[Size<<1];
struct Edge {
	int v,next;
} w[Size<<2];
void AddEdge(int u,int v) {
	w[++cnt].v=v;
	w[cnt].next=head[u];
	head[u]=cnt;
}
inline char getpre(char ch) {
	if(ch=='A')	return 'B';
	return 'A';
}
inline char getnxt(char ch) {
	if(ch=='C')	return 'B';
	return 'C';
}
inline int getid(int x,char ch) {
	if(x>n) x-=n; if(x>n) x-=n;
	if(ch=='A')	return x;
	if(ch=='B')	return x+n;
	return x+(n<<1);
}
inline char getother(int x,char ch) {
	char now=str[x];
	if(now=='A')	return (int)'B'+'C'-ch;
	if(now=='B')	return (int)'A'+'C'-ch;
	return (int)'A'+'B'-ch;
}
int tim,top,tot,dfn[Size],stk[Size],belong[Size],low[Size];
bool vis[Size];
void Tarjan(int x) {
	dfn[x]=low[x]=++tim;
	stk[++top]=x;
	vis[x]=true;
	for(int i=head[x]; i; i=w[i].next) {
		int nxt=w[i].v;
		if(!dfn[nxt]) {
			Tarjan(nxt);
			low[x]=min(low[x],low[nxt]);
		} else if(vis[nxt]) {
			low[x]=min(low[x],dfn[nxt]);
		}
	}
	if(low[x]==dfn[x]) {
		int y;
		tot++;
		while(y=stk[top--]) {
			belong[y]=tot;
			vis[y]=false;
			if(x==y)	return;
		}
	}
}
char ans[Size];
void Fujibayashi_Ryou() {
//	freopen("game16.in","r",stdin);
//	freopen("WA.txt","w",stdout);
	n=read();
	d=read();
	scanf("%s",str+1);
	m=read();
	for(re i=1; i<=m; i++) {
		x[i]=read();
		hx[i]=GetChar();
		y[i]=read();
		hy[i]=GetChar();
	}
	int now=0;
	for(re i=1; i<=n; i++) {
		if(str[i]=='x')	pos[++now]=i;
		str[i]=toupper(str[i]);
	}
	int maxn=1<<d;
	for(re i=0; i<maxn; i++) {
		oper(i);
		memset(head,0,sizeof(head)); cnt=0;
		memset(belong,0,sizeof(belong)); tot=0;
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		for(re j=1; j<=m; j++) {
			if(hx[j]==str[x[j]]) {
				continue;
			} else if(hy[j]==str[y[j]]) {
				//You can't make x[j] hx[j] 
				AddEdge(getid(x[j],hx[j]),getid(x[j],getother(x[j],hx[j])));
			} else {
				//If x[j] chooses hx[j], y[j] chooses hy[j] 
				AddEdge(getid(x[j],hx[j]),getid(y[j],hy[j]));
				//If y[j] does not choose hy[j], then x[j] does not choose hx[j] 
				AddEdge(getid(y[j],getother(y[j],hy[j])),getid(x[j],getother(x[j],hx[j])));
			}
		}
		for(re j=1; j<=n*3; j++) {
			int id=j; if(id>n) id-=n; if(id>n) id-=n;
			if(getid(id,str[id])!=j && !dfn[j]) {
				Tarjan(j);
			}
		}
		bool fail=false;
		for(re j=1; j<=n; j++) {
			int t1=getid(j,getpre(str[j]));
			int t2=getid(j,getnxt(str[j]));
			if(belong[t1]==belong[t2]) {
				fail=true;
				break;
			}
			if(belong[t1]<belong[t2]) {
				ans[j]=getpre(str[j]);
			} else {
				ans[j]=getnxt(str[j]);
			}
		}
		if(!fail) {
			puts(ans+1);
			return;
		}
	}
	printf("-1");
}

}
int main() {
	I_Love::Fujibayashi_Ryou();
	return 0;
}

Tags: less

Posted on Sat, 05 Oct 2019 22:36:35 -0700 by my8by10