【10.17校内测试】【二进制数位DP】【博弈论/预处理】【玄学（？）DP】
Solution
几乎是秒想到的水题叻！
异或很容易想到每一位单独做贡献，所以我们需要统计的是区间内每一位上做的贡献，就是统计区间内每一位是1的数的数量。
所以就写数位dp辣！（昨天才做了数字统计不要太作弊啊！）
Code
#include<bits/stdc++.h> #define LL long long #define mod 1000000007 using namespace std; inline void read(LL &x) { x = 0; char ch = getchar(); while(ch > '9' || ch < '0') ch = getchar(); while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } } int num[33]; LL L, R, dp[33][2][2]; LL dfs(int dep, int up, int is, int idc) { if(!dep && is) return 1; if(!dep) return 0; if(~dp[dep][up][is]) return dp[dep][up][is]; int h = up ? num[dep] : 1; LL tmp = 0; for(int i = 0; i <= h; i ++) { if(dep == idc && i == 1) tmp += dfs(dep - 1, up && i == h, 1, idc); else tmp += dfs(dep - 1, up && i == h, is, idc); } return dp[dep][up][is] = tmp; } LL sov(int x, int idc) { memset(dp, -1, sizeof(dp)); memset(num, 0, sizeof(num)); int tot = 0; while(x) { num[++ tot] = x % 2; x /= 2; } return dfs(tot, 1, 0, idc); } void work() { int t = R, dep = 0; LL ans = 0; while(t) { dep ++; LL t1 = sov(R, dep); LL t2 = L ? sov(L - 1, dep) : 0; LL num1 = t1 - t2; ans = (ans + 2 * num1 % mod * (R - L + 1 - num1) % mod * (1 << dep - 1) % mod) % mod; t >>= 1; } printf("%lld\n", ans); } int main() { freopen("xor.in", "r", stdin); freopen("xor.out", "w", stdout); int T; scanf("%d", &T); while(T --) { read(L); read(R); work(); } return 0; }
Solution
博弈论什么的完全不了解啊....然后看到题就乱打了个记忆化搜索，结果就70pts！！
原来这样暴力是$n^4$的复杂度啊...运气太好了...
只有两堆石子的做法：
大名鼎鼎的威佐夫博弈
通过一个简单的搜索，不难发现它的必败状态为：
$(1, 2), (3, 5), (4, 7), (6, 10), (8, 13)$……
通过这个表，能发现什么规律？
每个自然数出现一次
相邻两个必败态中，石子个数之差恰好增加 1
这样两个现象其实是非常合理的：
给定$x$，应该只存在一个$y$使得 $(x, y)$ 是先手必败态
所有不同的先手必败态的 $(y-x)$ 应该互不相同
它们都来源于同一个事实：先手必败状态无法转移到另一个先手必败状态。
一般做法：
我们考虑优化之前的筛法
根据上一页的思路，不难想到，给定 $x, y$ 之后，使得$(x, y, z)$ 为先手必败态的$z$只有一个
不妨用$f(x, y)$ 表示这个$z$
我们从小到大枚举一个变量$i$，然后计算：
有多少个$f(x, y)$ 的值为$i$
如果我们从小到大枚举 i，枚举到当前的 i 时：
所有$f(x, y)<i$的状态已经计算完毕，若一个$f(x, y)=k<i$，那么代表着$f(x+k, y), f(x, y + k), f(x+k,y+k) 均不可能是$i$
所有$f(x, y)=i$的状态中，每个自然数出现不超过 1 次，且$|x-y|$ 应该互不相同
根据这三个原则，我们可以在$O(n^2)$的枚举中，发现所有$f(x, y)=i$的状态$(x,y)$。
然而并不是很懂题解....然后$yuli$dalao讲解了另一种更好理解的方法！
当确定了一个数时，如果另外两个数的差相同，那么就可以一步转化。
同理，确定了两个数，另一个数多少也可以一步转化。
确定了三个数大小之间的差，也可以一步转化。
以上7种情况，如果按顺序从小到大枚举三个数，如果出现上述情况中存在必败态，那么当前状态可以必胜。
预处理$n^3$即可。
Code
标程
#include <bits/stdc++.h> #define rep(i, x, y) for (int i = (x), _ = (y); i < _; ++i) #define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i) #define fi first #define se second #define mp(x, y) make_pair(x, y) #define pb(x) push_back(x) #define bin(x) (1 << (x)) #define SZ(x) int((x).size()) //#define LX_JUDGE using namespace std; typedef pair<int, int> pii; typedef vector<int> Vi; typedef long long ll; template<typename T> inline bool upmax(T &x, T y) { return x < y ? (x = y, 1) : 0; } template<typename T> inline bool upmin(T &x, T y) { return x > y ? (x = y, 1) : 0; } namespace MATH_CAL { const int mod = 1e9 + 7; inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; } inline int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; } inline int mul(int a, int b) { return (ll) a * b % mod; } inline void Add(int &a, int b) { (a += b) >= mod ? a -= mod : 0; } inline int qpow(int x, int n) { int r = 1; for ( ; n; n /= 2, x = mul(x, x)) if (n & 1) r = mul(r, x); return r; } inline int mod_inv(int x) { return qpow(x, mod - 2); } } using namespace MATH_CAL; const int MAX_N = 305; int f[MAX_N][MAX_N], now[MAX_N][MAX_N]; int dif[MAX_N], vlef[MAX_N], tim; int main() { #ifdef LX_JUDGE freopen(".in", "r", stdin); #endif freopen("stone.in", "r", stdin); freopen("stone.out", "w", stdout); int N = 305; rep (i, 0, N) memset(f[i], 0x3f, sizeof(int) * N); for (int i = 0; i < N; ++i) { ++tim; for (int j = 0; j < N; ++j) { for (int k = 0; k <= j; ++k) { if (f[j][k] < i) { int v = i - f[j][k]; if (j + v < N) now[j + v][k] = tim; if (k + v < N) now[j][k + v] = tim; if (max(j, k) + v < N) now[j + v][k + v] = tim; } else if (max(now[j][k], now[k][j]) < tim and max(dif[abs(j - k)], max(vlef[j], vlef[k])) < tim) { f[k][j] = f[j][k] = i; dif[abs(j - k)] = tim; vlef[j] = tim; vlef[k] = tim; } } } } int T; scanf("%d", &T); while (T--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); puts(f[x][y] == z ? "No" : "Yes"); } return 0; } /* f_0[i][j] is easy to compute f_1[i][j] = !(f_0[i - 1][j] or f_0[i][j - 1] or f_0[i - 1][j - 1] or f_1[i - k][j - k]) Let S1 = { f[i - k][j - k], f[i - k][j], f[i][j - k] }; S2 = { f[i - k][j - k] + k, f[i - k][j] + k, f[i][j - k] + k }; f[i][j] = mex { S1, S2 } */
第二解
#include<bits/stdc++.h> #define RG register using namespace std; int SG[305][305][305]; inline void read(int &x) { x = 0; char ch = getchar(); while(ch > '9' || ch < '0') ch = getchar(); while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } } int QAQ[305][305][4], f[305][305][305]; void work() { for(int i = 0; i <= 300; i ++) for(int j = 0; j <= i; j ++) for(int k = 0; k <= j; k ++) { int pd = 1; if(QAQ[i][j - k][0]) pd = 0; if(QAQ[j][i - k][0]) pd = 0; if(QAQ[k][i - j][0]) pd = 0; if(QAQ[i][j][1]) pd = 0; if(QAQ[i][k][1]) pd = 0; if(QAQ[j][k][1]) pd = 0; if(QAQ[i - j][j - k][2]) pd = 0; if(pd) { f[i][j][k] = 1; QAQ[i][j - k][0] = QAQ[j][i - k][0] = QAQ[k][i - j][0] = QAQ[i][j][1] = QAQ[j][k][1] = QAQ[i][k][1] = QAQ[i - j][j - k][2] = 1; } } } int main() { freopen("stone.in", "r", stdin); freopen("stone.out", "w", stdout); int T; scanf("%d", &T); work(); while(T --) { int q[3]; read(q[0]); read(q[1]); read(q[2]); sort(q, q + 3); if(!f[q[2]][q[1]][q[0]]) printf("Yes\n"); else printf("No\n"); } return 0; }
Solution
完全不想写题解....
七高欢乐全场爆零题~
Code
#include<bits/stdc++.h> using namespace std; int n, k, a[30005]; int f[30005][205][4]; int main() { freopen("optimization.in", "r", stdin); freopen("optimization.out", "w", stdout); scanf("%d%d", &n, &k); for(int i = 1; i <= n; i ++) scanf("%d", &a[i]); memset(f, -0x3f3f3f3f, sizeof(f)); for(int i = 0; i <= n; i ++) f[i][0][1] = f[i][0][3] = 0; for(int i = 1; i <= n; i ++) for(int j = 1; j <= k; j ++) { int flag = 2 - (j == 1 || j == k); f[i][j][0] = max(f[i - 1][j][0], max(f[i - 1][j - 1][2], f[i - 1][j - 1][3])) + flag * a[i]; f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0]); f[i][j][2] = max(f[i - 1][j][2], max(f[i - 1][j - 1][1], f[i - 1][j - 1][0])) - flag * a[i]; f[i][j][3] = max(f[i - 1][j][3], f[i - 1][j - 1][2]); if(j > 1) { f[i][j][1] = max(f[i - 1][j - 1][1], f[i][j][1]); f[i][j][3] = max(f[i - 1][j - 1][3], f[i][j][3]); } } int ans = -1e9; for(int i = k; i <= n; i ++) ans = max(ans, max(f[i][k][0], f[i][k][2])); printf("%d", ans); return 0; }优质内容筛选与推荐>>
1、Direct UI 思想阐述（好多相关文章）
2、JAVA的历史
3、算法导论课后习题解析 第六章
4、有助于你编程而立即要做的10件事
5、django的ajax提交示例