rt 三面面试官说两周内，but已经过两周了。 update：10.7日oc。

很显然的一个二维矩阵哈希，就是有点卡内存。 离线处理即可。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; #ifdef LOCAL #define debug(x) cout << "["...

三个不同，三个叶子，分治解决。时间复杂度O(n*log m) #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; #ifdef LOCAL #define debug(x) cout << "[" __FUNCTION__ ": " #x " = " << (x) << "]\n" #define TIME cout << "...

可以分开计算，先计算所有区间内的最大值之和，再减去所有区间的最小值之和。 #include <iostream> #include <stdio.h> #include <string.h> #include <time.h> #include <string> #include <stack> #include <algorithm> using namespace std; #define gc p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10...

一道博弈题，可以先用SG函数打表，看看什么时候先手会输。发现(1,2),(3,5),(4,7)...其实就是个威佐夫博弈。实际上向左边移动等价于取第一堆石子，向下移动等价于取第二堆石子，向左下移动等价于两堆同时取相同数目的石子。 #include <stdio.h> #include <utility> #include <vector> #include <string.h> #include <math.h> #include <iostream> #include <stdlib.h> #include ...

SG定理：n个有向图游戏组成的组合游戏当且仅当SG值异或和等于0时先手必输，否则先手必胜。直接求出每个状态的SG值，最后遍历每堆石头第一次取的情况，如果能满足异或和等于0即留给对手一个必败状态，则方案数加1。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; #ifdef LOCAL #define debug(x) cout << "[" __FUNCTIO...

设d[i][j]表示先手面临两堆石子分别为i，j时的取胜状态。直接求SG函数即可。实际上可以通过值看出来两堆石子和为奇数时候先手必胜，否则后手胜。因为每次取的都为奇数并不会对总的石子数奇偶性造成改变。所以奇数时即会有奇数轮，先手必胜。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; #ifdef LOCAL #define debug(x) cout << ...

nim博弈的基础上增加了修改，a ^ a = 0。所以每次修改的时候我们先异或上a[x]再异或上y,最后把a[x]变成y。判断异或和是不是0即可。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; #ifdef LOCAL #define debug(x) cout << "[" __FUNCTION__ ": " #x " = " << (x) ...

比较明显的SG函数。设d[x]表示先手轮到x点时的取胜情况。当子状态有必败状态时，该状态为必胜状态。当子状态全部为必胜状态，该状态为必败状态。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; #ifdef LOCAL #define debug(x) cout << "[" __FUNCTION__ ": " #x " = " << (x) &l...

数字x左边有x - L个数字，右边有R - x个数字。可以看成有两堆石子，分别有x - L个、R - x个。玩家每次可以取多个或者取完，但至少取一个。至此就是一个nim博弈。考虑异或和等于0即可。或者考虑对称博弈，每次先手取多少，对手跟着在另一边取多少，因为两边的数目一样，所以当x - L = R - x时一定是后手Bob赢。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull...

经典Bash博弈。结论：n % (m + 1) = 0时先手必输，否则后手必赢。当n % (m + 1) = 0时，先手如果出k，后手跟着出一个(m + 1 - k)即可。最终会进行(n / (m + 1)) * 2轮，后手胜。当n % (m + 1) != 0可知n % (m + 1) <= m, 所以先手先取出n % (m + 1)。则剩余的石子个数满足n % (m + 1) = 0，轮到后手了这时候后手是必败状态，即先手获胜。 #include <bits/stdc++.h> #include <unordered_map> using namespace ...

当一个状态的后继状态有一个必败状态，我们可以通过移动到必败状态使得对手败。当一个状态的后继状态全部为必胜状态，无论怎么移动对手都会取胜。所以设d[x]表示先手拿到数字x的取胜情况，直接判断后继点的取胜情况即可。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; #ifdef LOCAL #define debug(x) cout << "[" __FUNCTI...

原型nim游戏。当且仅当n堆石子异或和等于0时先手必败。这个时候我们考虑把必败的局面留给对手。所以先计算除了a[k]外的其他数字的异或和，如果a[k]大于这个sum，则我们取掉sum-a[k]即可。留给对手一个必败局面。 #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; #if...

用sam跑出DAG图，再求出sg值。SG定理：n个有向图游戏组成的组合游戏当且仅当SG值异或和等于0时先手必输，否则先手必胜。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; #ifdef LOCAL #define debug(x) cout << "[" __FUNCTION__ ": " #x " = " << (x) << "...