注册网站的信息网站,网站建设课程体会,看seo,网站主机价格T1 [JZOJ2642] 游戏 题目描述 Alice和Bob在玩一个游戏#xff0c;游戏是在一个N*N的矩阵上进行的#xff0c;每个格子上都有一个正整数。当轮到Alice/Bob时#xff0c;他/她可以选择最后一列或最后一行#xff0c;并将其删除#xff0c;但必须保证选择的这一行或这一列所有… T1 [JZOJ2642] 游戏 题目描述 Alice和Bob在玩一个游戏游戏是在一个N*N的矩阵上进行的每个格子上都有一个正整数。当轮到Alice/Bob时他/她可以选择最后一列或最后一行并将其删除但必须保证选择的这一行或这一列所有数的和为偶数。如果他/她不能删除最后一行或最后一列那么他/她就输了。两人都用最优策略来玩游戏Alice先手问Alice是否可以必胜 分析 这个说辞...一看就知道是博弈论 众所周知博弈论有两个重要结论 1.一个状态是必败状态当且仅当它任意后继都是必胜状态 2.一个状态是必胜状态当且仅当它存在后继是必败状态 于是设 $f[i][j]$ 为矩阵为 $i$ 行 $j$ 列时该回合操作方的状态$1$ 为必胜$0$ 为必败显然 $f[1][1]1$ 同时需要将 $f[1][i]$ 和 $f[i][1]$ 初始化还要记录所有横轴和纵轴的前缀和 然后分别讨论删除最后一行和最后一列时的后继状态若该行或该列无法被删除则该后继视为必胜 考场上写这题的时候已经不早了感觉有点慌幸好最后过了 #include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
#include queue
using namespace std;
#define N 1005int T, n;
int g[N][N], f[N][N], p1[N][N], p2[N][N];int main() {scanf(%d, T);while (T--) {scanf(%d, n);for (int i 1; i n; i)for (int j 1; j n; j) {scanf(%d, g[i][j]);p1[i][j] p1[i][j - 1] g[i][j];p2[i][j] p2[i - 1][j] g[i][j];}f[1][1] 1;for (int i 2; i n; i) {int t1, t2;if (p1[1][i] % 2) t1 1;else t1 0;if (p2[1][i] % 2) t2 1;else if (f[1][i - 1]) t2 1;else t2 0;if (t1 t2) f[1][i] 0;else f[1][i] 1;}for (int i 2; i n; i) {int t1, t2;if (p2[i][1] % 2) t2 1;else t2 0;if (p2[i][1] % 2) t1 1;else if (f[i - 1][1]) t1 1;else t1 0;if (t1 t2) f[1][i] 0;else f[i][1] 1;}for (int i 2; i n; i)for (int j 2; j n; j) {int t1, t2;if (p1[i][j] % 2) t1 1;else if (f[i - 1][j]) t1 1;else t1 0;if (p2[i][j] % 2) t2 1;else if (f[i][j - 1]) t2 1;else t2 0;if (t1 t2) f[i][j] 0;else f[i][j] 1;}if (f[n][n]) printf(W\n);else printf(L\n);}return 0;
} View Code T2 [JZOJ2643] 六边形 题目描述 棋盘是由许多个六边形构成的共有5种不同的六边形编号为1到5棋盘的生成规则如下 1.从中心的一个六边形开始逆时针向外生成一个个六边形。 2.对于刚生成的一个六边形我们要确定它的种类它的种类必须满足与已生成的相邻的六边形不同。 3.如果有多个种类可以选我们选择出现次数最少的种类。 4.情况3下还有多个种类可以选我们选择数字编号最小的。 现在要你求第N个生成的六边形的编号 前14个六边形生成图如下 分析 这是个纯模拟感觉没有什么要分析的 主要就是要多注意细节考场上少写了一句代码直接掉到了 $45.5$ 分 而且每次一写模拟就写得贼慢 //考场上写得有点繁琐
#include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
#include queue
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 10005int T, n, c 2, now 8, s, e, ok, g1, g2;
int q[25], g[N], book[6], sum[6];int main() {scanf(%d, T);for (int i 1; i T; i) {scanf(%d, q i);n max(n, q[i]);}g[1] 1; g[2] 2; g[3] 3;g[4] 4; g[5] 5; g[6] 2; g[7] 3;sum[1] sum[4] sum[5] 1;sum[2] sum[3] 2; sum[0] inf;s 2; e 7;while (c) {for (int i 1; i 6; i) {for (int j 1; j c; j) {memset(book, 0, sizeof book);int minsum inf;if (j ! c - 1) {if (now e 1) {book[g[s]] book[g[e]] 1;for (int k 1; k 5; k)if (!book[k])minsum min(minsum, sum[k]);for (int k 1; k 5; k)if (!book[k] sum[k] minsum) {g[now] k; sum[k]; break;}g1 s; g2 s 1; s e 1;}else {book[g[g1]] book[g[g2]] book[g[now - 1]] 1;for (int k 1; k 5; k)if (!book[k])minsum min(minsum, sum[k]);for (int k 1; k 5; k)if (!book[k] sum[k] minsum) {g[now] k; sum[k]; break;}g1; g2;}}else {if (i 6) e now, book[g[s]] 1;book[g[g1]] book[g[now - 1]] 1;for (int k 1; k 5; k)if (!book[k])minsum min(minsum, sum[k]);for (int k 1; k 5; k)if (!book[k] sum[k] minsum) {g[now] k; sum[k]; break;}}if (now n) {ok 1; break;}}if (ok) break;}if (ok) break;}for (int i 1; i T; i)printf(%d\n, g[q[i]]);return 0;
} View Code T3 [JZOJ2644] 数列 题目描述 给你一个长度为N的正整数序列如果一个连续的子序列子序列的和能够被K整除那么就视此子序列合法求原序列包括多少个合法的连续子序列 对于一个长度为8的序列,K4的情况2, 1, 2, 1, 1, 2, 1, 2 。它的答案为6子序列是位置1-位置8,2-4,2-7,3-5,4-6,5-7。 分析 看到题目就先写了前缀和枚举区间 $O(n^2)$ 暴力 $30 \, pts$ 当时看了半天觉得这是最可做的一题结果看了数据范围还是没想出来 $O(n \, log \, n)$ 做法 结果考完试下午看了下大家的讨论发现正解是 $O(k)$ 具体就是把每个前缀和按 $k$ 取模记录每个余数出现的次数 $sum$ 显然前缀和所得余数相同的的两项之间的区间和一定能被 $k$ 整除 所以在余数相同的项中我们可以任意挑选两项组成一个合法区间 因此答案为 $\sum\limits_{i0}^{k-1} \binom{sum[i]}{2}$ 要注意第 $0$ 项的前缀和余数视为 $0$ #include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
#include queue
using namespace std;
#define ll long long
#define N 50005
#define K 1000005int T, n, k, x;
int pre[N], sum[K];
ll ans, c[K];int main() {c[2] 1;for (int i 3; i N; i)c[i] c[i - 1] i - 1;scanf(%d, T);while (T--) {ans 0;scanf(%d%d, k, n);for (int i 1; i k; i) sum[i] 0;sum[0] 1;for (int i 1; i n; i) {scanf(%d, x);pre[i] (pre[i - 1] x) % k;sum[pre[i]];}for (int i 0; i k; i)ans c[sum[i]];printf(%lld\n, ans);}return 0;
} View Code 转载于:https://www.cnblogs.com/Pedesis/p/11284483.html
