「NOI2017」游戏 - 2-SAT

有三种数，$n$个位置，每个位置只能填一种数。有$d\in[0,8]$个位置有三种选择，其他位置只有两种选择

给你一些限制$(x, a, y, b)$，表示第$x$个位置选了$a$，那么第$y$个位置就必须选$b$

输出一组合法的选数方案，无解输出$-1$

Links

LOJ 2305

Solution

2-SAT模板题

先$2^d$枚举那$d$个位置不选哪个数，任意枚举两个即可，这样就能包括所有的三种情况

每次跑一遍2-SAT即可

代码写的比较丑，我是一开始先把和那$d$个位置无关的边加好，每dfs一次加入剩下的边

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 50000 + 100, MAXM = 100000 + 100;

int N, d, M;
char S[MAXN];
int A[2][MAXN], Ban[MAXN], Buc[10];

struct edge
{
	int x, a, y, b;
} E[MAXM];

int e, Begin[MAXN << 1], Next[MAXM << 2], To[MAXM << 2];
pii Save_E[MAXM << 2];
int save_cnt;

inline void add_edge (int x, int y) { Save_E[++save_cnt] = mp(x, y); To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

namespace GRAPH
{
	const int maxn = MAXN << 1;

	int dfn[maxn], dfs_clock, low[maxn], Belong[maxn], scc_cnt;
	int Stack[maxn], top, In[maxn];

	inline void tarjan (int x)
	{
		Stack[++top] = x, In[x] = 1;
		dfn[x] = low[x] = ++dfs_clock;

		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			if (!dfn[y]) tarjan (y), Chkmin (low[x], low[y]);
			else if (In[y]) Chkmin (low[x], dfn[y]);
		}
		
		if (dfn[x] == low[x])
		{
			++scc_cnt;
			while (1)
			{
				int a = Stack[top--];
				Belong[a] = scc_cnt, In[a] = 0;
				if (a == x) break;
			}
		}
	}

	int Ans[maxn];

	inline void init ()
	{
		dfs_clock = scc_cnt = top = 0;
		for (int i = 1; i <= 2 * N; ++i) dfn[i] = low[i] = Belong[i] = In[i] = 0;
	}

	inline void solve ()
	{
		init ();
		for (int i = 1; i <= 2 * N; ++i) if (!dfn[i]) tarjan (i);

		for (int i = 1; i <= N; ++i)
		{
			if (Belong[i] == Belong[i + N]) return ;
			if (Belong[i] < Belong[i + N]) Ans[i] = A[0][i];
			else Ans[i] = A[1][i];
		}

		for (int i = 1; i <= N; ++i)
		{
			//cout << A[0][i] << ' ' << A[1][i] << endl;
			printf("%c", Ans[i] + 'A' - 1);
			//cout << Ans[i] << endl;
		}
		exit(0);
	}
}

inline void Add (int x, int a, int y, int b)
{
	if (Ban[x] == a) return ;

	int dx = (a == A[0][x]) ? x : (x + N), ox = (dx <= N) ? (dx + N) : (dx - N);
	int dy = (b == A[0][y]) ? y : (y + N), oy = (dy <= N) ? (dy + N) : (dy - N);

//	cout << x << ' ' << dx << ' ' << ox << endl;
//	cout << y << ' ' << dy << ' ' << oy << endl;

	if (Ban[y] == b) add_edge (dx, ox);
	else add_edge (dx, dy), add_edge (oy, ox);
}

inline void Pop (int now)
{
	while (save_cnt != now)
	{
		int x = Save_E[save_cnt].x, y = Save_E[save_cnt].y; --save_cnt, --e;
		Begin[x] = Next[Begin[x]];
	}
}

inline void Check ()
{
	int save_now = save_cnt;
	for (int i = 1; i <= M; ++i)
	{
		int x = E[i].x, a = E[i].a, y = E[i].y, b = E[i].b;
		Add (x, a, y, b);
	}

	GRAPH :: solve ();

	Pop (save_now);
}

inline void dfs (int step)
{
    if (clock() > 0.9 * CLOCKS_PER_SEC) { cout << -1; exit(0); }
	if (step == d + 1) { Check (); return ; }

	Ban[Buc[step]] = 1, A[0][Buc[step]] = 2, A[1][Buc[step]] = 3;
	if (rand() & 1) swap(A[0][Buc[step]], A[1][Buc[step]]);
	dfs (step + 1);

	Ban[Buc[step]] = 2, A[0][Buc[step]] = 1, A[1][Buc[step]] = 3;
	if (rand() & 1) swap(A[0][Buc[step]], A[1][Buc[step]]);
	dfs (step + 1);
}

inline void Solve ()
{
	dfs (1);
	cout << "-1";
}

inline void Input ()
{
	srand(20030216);
	N = read<int>(), d = read<int>();
	scanf("%s", S + 1);
	int buc_cnt = 0;

	for (int i = 1; i <= N; ++i)
	{
		if (S[i] != 'x') 
		{
			Ban[i] = S[i] - 'a' + 1;
			if (S[i] == 'a') A[0][i] = 2, A[1][i] = 3;
			else if (S[i] == 'b') A[0][i] = 1, A[1][i] = 3;
			else A[0][i] = 1, A[1][i] = 2;
			if (rand() & 1) swap(A[0][i], A[1][i]);
		}
		else A[0][i] = -1, Buc[++buc_cnt] = i;
	}

	int MM;
	M = MM = read<int>(), M = 0;
	while (MM--)
	{
		char str[3];
		int x = read<int>(), a; scanf("%s", str), a = str[0] - 'A' + 1;
		int y = read<int>(), b; scanf("%s", str), b = str[0] - 'A' + 1;

		if (!Ban[x] || !Ban[y]) E[++M] = (edge){x, a, y, b};
		else Add (x, a, y, b);
	}
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}