[UOJ317]【NOI2017】游戏 题解

题意

​ 小 L 计划进行 \(n\) 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

​ 小 L 的赛车有三辆，分别用大写字母 A、B、C 表示。地图一共有四种，分别用小写字母 x、a、b、c 表示。其中，赛车 A 不适合在地图 a 上使用，赛车 B 不适合在地图 b 上使用，赛车 C 不适合在地图 c 上使用，而地图 x 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 \(d\) 张。

​ \(n\) 场游戏的地图可以用一个小写字母组成的字符串描述。例如：\(\underline{S=xaabxcbc}\) 表示小 L 计划进行 8 场游戏，其中第 1 场和第 5 场的地图类型是 x，适合所有赛车，第 2 场和第 3 场的地图是 a，不适合赛车 A，第 4 场和第 7 场的地图是 b，不适合赛车 B，第 6 场和第 8 场的地图是 c，不适合赛车 C。

​ 小 L 对游戏有一些特殊的要求（共 \(m\) 条），这些要求可以用四元组 \((i,h_i,j,h_j)\) 来描述，表示若在第 \(i\) 场使用型号为 \(h_i\) 的车子，则第 \(j\) 场游戏要使用型号为 \(h_j\) 的车子。

​ 你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “-1”（不含双引号）。

数据范围

\(n \le 50000,d \le 8,m\le100000.\)

题解

话说我NOI的题改起来好费力啊TAT 一道就一天（还对着数据改）

不难发现这和之前一道题类似LA 3713。

虽然有很多种类，但每个人也只有两种可以选择，并且关系也是二元的。

所以我们就可以套2-SAT模板了qwq 不会2-SAT请点这里.

首先暴力枚举每个 \(x\) 的状态，从 \(a,b,c\) 中选取一个就行了。

然后对于那些二元关系 \((i,h_i,j,h_j)\)，就如下考虑。

1. \(i\) 可以选择 \(h_i\) 这种赛车
   1. \(j\) 无法选择 \(h_j\) 这种赛车，那么 \(i\) 就必不能选 \(h_i\) 了，就连一条 \(h_i \to \lnot h_i\) 的边（此处 \(\lnot h_i\) 表示 \(i\) 可以选择的另一种赛车）
   2. \(j\) 可以选择 \(h_j\) 这种赛车，那么就只要连 \(h_i \to h_j\) 的边就好了
2. \(i\) 不可以选择 \(h_i\) 这种赛车：那就直接跳过就行了。

然后记得要建逆否命题等价的另一条边。

如果用DFS复杂度为 \(\Theta(3^d nm)\)，Tarjan就是 \(\Theta(3^d (n+m))\) 啦。

其实第二个Tarjan复杂度已经足够过了。。。但是能更优！

有这样一个结论：

如果一个 \(x\) 已经考虑过 \(a,b\) 两个状态了，那么我们就不用考虑为 \(c\) 的状态。

这是为什么呢？

因为 \((A,B)\) 和 \((B,C)\) 的两种选择你都已经考虑过了，那么剩下一种 \((A,C)\) 你前面一定会在前面一种选过。（因为每个点只能从那三种中选择一种赛车，如果另外两种都不可行，剩下一种也不行了）

这样我们就可以将复杂度降为 \(\Theta(2^d(n+m))\) qwq

然而又有垃圾UOJ hack数据 我判了一下快到0.8s的时候，直接输出"-1"...才过 （卡常数真的恶心）

代码

我一开始写了个DFS的可以跑过85分.... 然而有人能用这个A掉 Orz

  #include <bits/stdc++.h>
  #define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
  #define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
  #define Set(a, v) memset(a, v, sizeof(a))
  using namespace std;

  inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
  inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

  inline int read() {
      int x = 0, fh = 1; char ch = getchar();
      for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
      for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
      return x * fh;
  }

  void File() {
  #ifdef zjp_shadow
  	freopen ("317.in", "r", stdin);
  	freopen ("317.out", "w", stdout);
  #endif
  }

  const int N = 100010;
  char str[N];
  int Jump[N], len, Last;

  int m;
  struct Limit { int u, v; char colu, colv; } lt[N];

  char opt[N][2];

  struct Two_SAT {
  	bitset<N> mark;
  	int Next[N], Head[N], to[N], e, n;

  	void Init(int n) { this -> n = n; mark.reset(); Set(Head, 0); e = 0; }

  	void add_edge(int u, int v) { to[++ e] = v; Next[e] = Head[u]; Head[u] = e; }

  	void Add(int x, int xv, int y, int yv) {
  		x = x << 1 | xv; y = y << 1 | yv;
  		add_edge(x, y); add_edge(y ^ 1, x ^ 1);
  	} //(x,xv) -> (y,yv)

  	int sta[N], top;
  	bool Dfs(int x) {
  		if (mark[x ^ 1]) return false;
  		if (mark[x]) return true;
  		sta[++ top] = x; mark[x] = true;
  		for (int i = Head[x]; i; i = Next[i])
  			if (!Dfs(to[i])) return false;
  		return true;
  	}

  	bool Solve() {
  		for (int i = 2; i <= 2 * n; i += 2)
  			if (!mark[i] && !mark[i ^ 1]) {
  				top = 0;
  				if (!Dfs(i)) {
  					while (top) mark[sta[top --]] = false;
  					if (!Dfs(i ^ 1)) { return false; }
  				}
  			}
  		return true;
  	}

  } T;
  int n;

  inline bool Check() {
  	T.Init(n);
  	For (i, 1, m) {
  		int u = lt[i].u, v = lt[i].v, colu = lt[i].colu, colv = lt[i].colv;
  		if (u == v && colu == colv) continue ;
  		For (v1, 0, 1) if (opt[u][v1] == colu) {
  			bool flag = false;
  			For (v2, 0, 1) if (opt[v][v2] == colv) { flag = true; T.Add(u, v1, v, v2); }
  			if (!flag)
  				T.Add(u, v1, u, v1 ^ 1);
  		}
  	}
  	return T.Solve();
  }

  inline void Out() {
  	For (i, 1, n) For (j, 0, 1) if (T.mark[i << 1 | j]) putchar(toupper(opt[i][j]));
  }

  void Dfs(int pos) {
  	if (pos == len + 1) { if (Check()) { Out(); exit(0); } return ; }
  	opt[pos][0] = 'b'; opt[pos][1] = 'c'; str[pos] = 'a'; Dfs(Jump[pos]);
  	opt[pos][0] = 'a'; opt[pos][1] = 'c'; str[pos] = 'b'; Dfs(Jump[pos]);
  }

  int main () {
  	File();
  	n = len = read(); read();
  	scanf ("%s", str + 1);
  	Last = len + 1;
  	Fordown(i, len, 1)
  		if (str[i] == 'x') { Jump[i] = Last; Last = i; }
  		else { int cnt = 0; For (j, 0, 2) if (str[i] != 'a' + j) { opt[i][cnt ++] = 'a' + j; } }
  	m = read();
  	For (i, 1, m) {
  		int u, v; char colu, colv;
  		scanf ("%d %c %d %c", &u, &colu, &v, &colv);
  		lt[i].u = u; lt[i].v = v; lt[i].colu = tolower(colu); lt[i].colv = tolower(colv);
  	}

  	Dfs(Last);
  	puts("-1");
      return 0;
  }

正解就用Tarjan缩点就行咯qwq

  #include <bits/stdc++.h>
  #define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
  #define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
  #define Set(a, v) memset(a, v, sizeof(a))
  using namespace std;

  inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
  inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

  inline int read() {
      int x = 0, fh = 1; char ch = getchar();
      for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
      for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
      return x * fh;
  }

  void File() {
  #ifdef zjp_shadow
  	freopen ("317.in", "r", stdin);
  	freopen ("317.out", "w", stdout);
  #endif
  }

  const int N = 200100;
  char str[N];
  int Jump[N], len, Last;

  int m;
  struct Limit { int u, v; char colu, colv; } lt[N];

  char opt[N][2];

  struct Two_SAT {
  	int Next[N], Head[N], to[N], e, n;

  	void Init(int n) { this -> n = n; For(i, 2, n << 1 | 1) Head[i] = 0; e = 0; }

  	void add_edge(int u, int v) { to[++ e] = v; Next[e] = Head[u]; Head[u] = e; }

  	void Add(int x, int xv, int y, int yv) {
  		x = x << 1 | xv; y = y << 1 | yv;
  		add_edge(x, y); add_edge(y ^ 1, x ^ 1);
  	} //(x,xv) -> (y,yv)

  	int sccno[N], scc_cnt;
  	int dfn[N], lowlink[N];
  	int sta[N], top, clk;
  	void Tarjan(int u) {
  		lowlink[u] = dfn[u] = ++clk; sta[++ top] = u;
  		for (int i = Head[u]; i; i = Next[i]) {
  			int v = to[i];
  			if (!dfn[v]) { Tarjan(v); chkmin(lowlink[u], lowlink[v]); }
  			else if (!sccno[v]) chkmin(lowlink[u], dfn[v]);
  		}
  		if (lowlink[u] == dfn[u]) {
  			++ scc_cnt; for (;;) { int now = sta[top --]; sccno[now] = scc_cnt; if (now == u) break ; }
  		}
  	}

  	bool Solve() {
  		For (i, 2, n << 1 | 1) dfn[i] = sccno[i] = 0; scc_cnt = clk = 0;
  		For (i, 2, n << 1 | 1) if (!dfn[i]) Tarjan(i);
  		For (i, 1, n)
  			if (sccno[i << 1] == sccno[i << 1 | 1]) return false;
  		return true;
  	}

  	void Out() {
  		For (i, 1, n) { putchar(toupper(opt[i][sccno[i << 1] > sccno[i << 1 | 1]])) ; }
  	}
  } T;
  int n;

  int cnt = 0;
  inline bool Check() {
  	T.Init(n);
  	For (i, 1, m) {
  		int u = lt[i].u, v = lt[i].v, colu = lt[i].colu, colv = lt[i].colv;
  		if (u == v && colu == colv) continue ;
  		For (v1, 0, 1) if (opt[u][v1] == colu) {
  			bool flag = false;
  			For (v2, 0, 1) if (opt[v][v2] == colv) { flag = true; T.Add(u, v1, v, v2); }
  			if (!flag) T.Add(u, v1, u, v1 ^ 1);
  		}
  	}
  	int res = T.Solve();
  	return res;
  }

  void Dfs(int pos) {
  	if ((double) clock() / CLOCKS_PER_SEC >= 0.8) { puts("-1"); exit(0); }
  	if (pos == len + 1) { if (Check()) { T.Out(); exit(0); } return ; }
  	opt[pos][0] = 'a'; opt[pos][1] = 'c'; str[pos] = 'b'; Dfs(Jump[pos]);
  	opt[pos][0] = 'b'; opt[pos][1] = 'c'; str[pos] = 'a'; Dfs(Jump[pos]);
  }

  int main () {
  	File();
  	n = len = read(); read(); scanf ("%s", str + 1); Last = len + 1;
  	Fordown(i, len, 1)
  		if (str[i] == 'x') { Jump[i] = Last; Last = i; }
  		else { int cnt = 0; For (j, 0, 2) if (str[i] != 'a' + j) { opt[i][cnt ++] = 'a' + j; } }
  	m = read();
  	For (i, 1, m) {
  		int u, v; char colu, colv; scanf ("%d %c %d %c", &u, &colu, &v, &colv);
  		lt[i].u = u; lt[i].v = v; lt[i].colu = tolower(colu); lt[i].colv = tolower(colv);
  	}
  	Dfs(Last); puts("-1");
      return 0;
  }

​