Alice and Bob IV
题目背景：
分析：
懂套路的大牛可能又要吐槽了，这个不是二分图匹配 + 博弈论吗，好吧，的确是，但是这个题的出题人显然是想搞事情······竟然搞出交互题来让我们陪checker愉快的玩耍······（我有一句XXX不知当不当讲）因为本题宝宝自己都还是比较懵逼的情况，但是我呢还是听话的先去做了bzoj2437[NOI2011]兔兔与蛋蛋（可以当作是前置技能），我们把这50000种状态进行黑白染色，对于每一种当前状态一次操作后会变成另一种颜色，然后我们把相邻的状态进行连边然后进行二分图匹配即可，如果最终的结果是完全匹配那么则意味着，从任意点出发均为先手必胜，直接走匹配即可，但是如果不是完全匹配，则说明有一边是多一个点的，那么则多一个点的那一边后手必胜，我们就选择在评委进行了第一次操作之后，重新删掉这个点，重新跑一次匹配即可，如果是少一个点的那一边则先手必胜，同样选择走匹配。（为什么没有main函数，蛤？交互题有main函数？）
Source：
#include #include #include #include #include #include #include #include #include "alice.h" using namespace std; const int MAXN = 18; const int MAXM = 50000 + 20; vector edge[MAXM]; int n, m; int type[MAXM], match[MAXM], p[MAXN], c[MAXN]; bool vis[MAXM], walk[MAXM]; inline int zip(int *x) { int s = 0; for (int i = 1; i <= n; ++i) s *= c[i], s += x[i]; return s; } inline void unzip(int s, int *x) { for (int i = n; i; --i) x[i] = s % c[i], s /= c[i]; } inline void addEdge(int x, int y) { edge[x].push_back(y); } void getpath(int s) { static int x[MAXN]; unzip(s, x); type[s] = 0; for (int i = 1; i <= n; ++i) type[s] ^= x[i] & 1; for (int i = 1; i <= n; ++i) { if (x[i] - 1 >= 0) --x[i], addEdge(s, zip(x)), ++x[i]; if (x[i] + 1 < c[i]) ++x[i], addEdge(s, zip(x)), --x[i]; } } inline bool dfs(int cur) { for (int p = 0; p < edge[cur].size(); ++p) { if (!vis[edge[cur][p]]) { vis[edge[cur][p]] = true; int temp = match[edge[cur][p]]; if (temp == -1 || dfs(temp)) { match[edge[cur][p]] = cur; match[cur] = edge[cur][p]; return true; } } } return false; } inline Data getans(int s) { int t = match[s]; static int x[MAXN], y[MAXN]; unzip(s, x), unzip(t, y); walk[t] = true; for (int i = 1; i <= n; ++i) if (x[i] != y[i]) { if (x[i] < y[i]) { Data temp; temp.id = i, temp.ops = '+'; return ++p[i], temp; } else { Data temp; temp.id = i, temp.ops = '-'; return --p[i], temp; } } } bool first; int start; bool init(int n1, const int *c1, const int *p1) { n = n1, m = 1; int s = 1; for (int i = 1; i <= n; ++i) c[i] = c1[i], m *= ++c[i]; for (int i = 1; i <= n; ++i) p[i] = p1[i], s += p[i]; if (n == 1) return c[1]--, (((c[1] - p[1]) & 1) || (p[1] & 1)); memset(type, -1, sizeof(type)); memset(walk, false, sizeof(walk)); walk[zip(p)] = true; for (int i = 0; i < m; ++i) getpath(i); memset(match, -1, sizeof(match)); start = zip(p); for (int i = 0; i < m; ++i) if (type[i] == type[start]) memset(vis, false, sizeof(vis)), dfs(i); if ((m & 1) && (s & 1)) return first = true, false; else return true; } Data getNextMove(Data x) { if (x.ops == '+') p[x.id]++; else p[x.id]--; if (n == 1) { if (x.id == 0) { if ((c[1] - p[1]) % 2) { Data temp; temp.id = 1, temp.ops = '+'; return temp; } else { Data temp; temp.id = 1, temp.ops = '-'; return temp; } } else { Data temp = x; return temp; } } if (first) { first = false; int start_this = zip(p); memset(match, -1, sizeof(match)); for (int i = 0; i < m; ++i) if (type[i] == type[start_this]) { memset(vis, false, sizeof(vis)); vis[start] = true, dfs(i); } } return getans(zip(p)); }