Minimax Theorem
ABC427D - The Simple Game 有向图，保证每个点的出度至少为 111。棋子最初放在顶点 111 上，两人交替将棋子移动到出点各 KKK 次。若最终停在 A，则 Alice 获胜，否则 Bob 获胜。 12345678for (int _ = 0; _ < 2 * K; _++) { std::vector<int> nf(N); for (const auto& [x, y] : edges) { nf[x] |= !f[y]; } f = nf;}std::cout << (f[0] ? "Alice" : "Bob") << std::endl; CF2140E 给定下标集合 CCC 。 现有长度为 NNN 的石子数量序列 aaa，满足对于 1⩽i⩽N1 \leqslant i \leqslant N1⩽i⩽N，1⩽ai⩽M1 \leqslant a_i \leqslant M1⩽ai⩽M。 针对序列 aaa...
打表手玩找规律
经典 Turning Turtles 游戏 VJwin14C - Game with Marbles (Hard Version) 两人各有 nnn 堆石子，分别编号 1∼n1\sim n1∼n。两人轮流选择石子，选择其中一个编号，自己弃这个编号的石子堆的其中一颗石子，对方弃这个编号的石子堆的所有石子。最终得分为甲和乙的石子总数之差，甲希望得分最大化，乙希望得分最小化。求两人的获胜策略，并给出最终得分。 记每方的得分为他最终剩下的石子，实际双方都希望自己得分尽可能大。 设某一堆石子甲有 aaa 颗，乙有 bbb 颗，如果甲选择了，它的得分会增加 a−1a-1a−1，否则甲不选，乙的得分增加 b−1b-1b−1。对于两堆石子 a1,b1a_1,b_1a1,b1 和 a2,b2a_2,b_2a2,b2，如果甲先选择编号为 111 的，乙就只能选择编号为 222 的，最终得分为 W1=(a1−1)−(b2−1)=a1−b2W_1=(a_1-1)-(b_2-1)=a_1-b_2W1=(a1−1)−(b2−1)=a1−b2，如果甲先选择编号为 222...
ICG-SG
ICG 最忌讳的就是在状态里区分 Alice 和 Bob。既然是 ICG，胜败只与局面有关，不应当区分玩家。 hdu summer 05 - 1006 支配游戏 两个玩家在一张无向图上进行博弈，任意两个节点之间最多一条边相连。这张图由若干个 互不相交的连通块 组成，每个连通块要么是一条 简单路径 （记为 1），要么是一个 简单环。 在游戏中，两个玩家轮流行动。在每一轮中，当前玩家必须选择一个顶点 u，该顶点需能 支配 至少一个 未被支配 的顶点，注意，该顶点并不要求是未被支配的。一个顶点 u 能够支配它自己以及所有与它相邻的顶点。 当某个顶点被选中后，它以及所有被其支配的顶点都会被标记为 已支配。 若某位玩家在其回合无法进行操作（即没有可以支配未被支配顶点的顶点可选），则该玩家输掉游戏。 判断在双方都采取最优策略的前提下，先手玩家是否必胜。 设 sg[n][i]sg[n][i]sg[n][i] 为长度为 nnn 且所有节点都没有被选择的链的两端有 iii 个已经被支配。 打表枚举选择每个点支配取 sgsgsg 。 长度为 nnn 的环 sgsgsg 值为...
经典博弈模型
博弈有 3 种题，打表手玩找规律、经典模型结论、程序模拟计算 1451F N×MN \times MN×M 网格，每个点有非负权值。 ICG。 任选一个值不为零的起始格子，任选一个左下方的终止格子，并任选最短路径，将每个格子修改为任意值，但起始格子的值只能减少。 无法操作者败。
图论建模
ABC437G ABC437G - Colorful Christmas Tree 一道题建了三个新图，算上原树总共四个图 ww 给定 NNN 点树，每个节点初始被染成 012 三种颜色之一。 执行以下操作 N−1N-1N−1 次：选择一条当前存在、且两端点颜色不同的边，将其删除，然后将这条边两端点的颜色，按照 0 →\to→ 1 →\to→ 2 →\to→ 0 的循环顺序变为下一种颜色。 判断是否存在一种合法的删边顺序，能够把树上的边全部删完。若存在，输出之。 Step.1 转化为匹配 在全过程中，顶点 vvv 处于颜色 kkk 时参与删除，这个操作次数确定，记为 Av,kA_{v, k}Av,k。这给定了每个点在特定颜色下需要消耗的额度，因此这本质上是一个匹配问题。 建图： 点：将一个点 vvv 拆成 Av,kA_{v,k}Av,k 个点 (v,k)(v,k)(v,k)。 边：对于一条边 u−vu-vu−v，如果 (u,k1)(u,k_{1})(u,k1) 和 (v,k2)(v,k_{2})(v,k2) 颜色不同，则连边 (u,k1)−(v,k2)(u,...
延迟决策
又名：反悔贪心。 CF1974G 第一天早上你没有钱，每天晚上得到 XXX 元。在第 iii 天里，你可以花费 CiC_iCi 元买一个菠萝派。在任何时刻你都不能欠钱，问这 NNN 天最多能吃多少菠萝派。 先不考虑钱，无脑买。如果钱变成负数，就从之前买过的挑一个最贵的不买，即延迟决策。 1234567891011121314i64 sum = 0;std::priority_queue<int> h;for (int i = 0; i < N; i++) { int c; std::cin >> c; h.push(c); sum -= c; if (sum < 0) { sum += h.top(); h.pop(); } sum += X;}std::cout << h.size() << "\n"; CF865D 在第 iii 天里，菠萝派的价格调整为...
刷子
...
染色
...
01 grid
105633K - Scheduling Two Meetings 给定 N×MN \times MN×M 的 01 矩阵 AAA。 选取两行 i,ji, ji,j，满足对于所有列 mmm，有 Ai[m]=1A_{i}[m] = 1Ai[m]=1 或 Aj[m]=1A_{j}[m] = 1Aj[m]=1 至少一者成立。 最大化满足 Ai[m]=1A_{i}[m] = 1Ai[m]=1 且 Aj[m]=1A_{j}[m] = 1Aj[m]=1 的列数。 输出所选的 iii 和 jjj。若有多种选择，则选择 iii 最小的对；若 iii 相同，则选择 jjj 最小的对。 2≤N≤2×1052 \le N \le 2 \times 10^52≤N≤2×105，2≤M≤202 \le M \le 202≤M≤20。 给定长度为 NNN 的非负整数数组 AAA，其中每个元素 0≤Ai<2M0 \le A_{i} < 2^M0≤Ai<2M。 选取两个下标 i,ji, ji,j，满足 Ai∣Aj=2M−1A_{i} \mid A_{j} =...