Codeforces Round 912 (Div. 2) E - Geo Game

考虑什么时候会改变答案的奇偶，显然可以根据\(x \oplus y\)的奇偶性分组，在组内进行跳跃不会改变，只有当组间跳跃的时候才会改变。

打表观察先手什么时候必胜，其中：\(u\)是当前获胜目标为奇/偶（1/0），\(v\)是位于哪一组，\(a,b\)代表两组还剩多少，\(st\)代表当前答案的奇偶性。

int dfs(int u, int v, int a, int b, int st) {
	if (a == 0 && b == 0) return (u == st);
	if (a == 0) {
		if (v == 0) return !dfs(u ^ 1, v ^ 1, a, b - 1, st ^ 1);
		else return !dfs(u ^ 1, v, a, b - 1, st);
	}
	if (b == 0) {
		if (v == 0) return !dfs(u ^ 1, v, a - 1, b, st);
		else return !dfs(u ^ 1, v ^ 1, a - 1, b, st ^ 1);
	}
	if (v == 0) {
		if (dfs(u ^ 1, v ^ 1, a, b - 1, st ^ 1) && dfs(u ^ 1, v, a - 1, b, st)) return 0;
		return 1;
	}
	else {
		if (dfs(u ^ 1, v ^ 1, a - 1, b, st ^ 1) && dfs(u ^ 1, v, a, b - 1, st)) return 0;
		return 1;
	}
}

void work() {
	rep (i, 0, 20) {
		rep (j, 0, 20) {
			if (dfs(0, 0, i, j, 0)) {
				cout << i << " " << j << "\n";
			}
			// cout << i << " " << j << " " << dfs(0, 0, i, j, 0) << " " << dfs(0, 1, i, j, 0) << "\n";
		}
	}
	
}

根据表，发现只要先手位于的组元素数量大于等于另一组就必胜， 否则必败。

其实这时候就可以根据必胜/必败态转移了，但我比较唐氏，选择肉眼观察必胜策略。

发现不管选择先手还是后手，只要一直跳一开始元素数量较少的那一组就行了，可以手玩一下

void work() {
    int n, sx, sy, st;
    cin >> n >> sx >> sy;
    if ((sx ^ sy) & 1) st = 0;
    else st = 1;
    set<int> a, b;
    rep (i, 1, n) {
    	int x, y;
    	cin >> x >> y;
    	if ((x ^ y) & 1) a.insert(i);
    	else b.insert(i);
    }
    if ((st == 0 && a.size() >= b.size()) || (st == 1 && b.size() >= a.size())) {
    	if (b.size() > a.size() || (a.size() == b.size() && st == 1)) swap(a, b);
    	cout << "First" << endl;
    	rep (i, 1, n) {
    		if (i & 1) {
    			if (b.size()) {
					cout << *prev(b.end()) << endl;
					b.erase(prev(b.end()));
				}
				else {
					cout << *prev(a.end()) << endl;
					a.erase(prev(a.end()));
				}
    		}
    		else {
    			int id;
    			cin >> id;
    			if (a.size() && a.find(id) != a.end()) {
    				a.erase(a.find(id));
    			}
    			else {
    				b.erase(b.find(id));
    			}
    		}
    	}
    } 
    else {
    	if (b.size() >= a.size()) swap(a, b);
    	cout << "Second" << endl;
    	rep (i, 1, n) {
    		if (!(i & 1)) {
    			if (b.size()) {
					cout << *prev(b.end()) << endl;
					b.erase(prev(b.end()));
				}
				else {
					cout << *prev(a.end()) << endl;
					a.erase(prev(a.end()));
				}
    		}
    		else {
    			int id;
    			cin >> id;
    			if (a.size() && a.find(id) != a.end()) {
    				a.erase(a.find(id));
    			}
    			else {
    				b.erase(b.find(id));
    			}
    		}
    	}
    }
}
/*

*/