Game

Link. 做 vjudge 的题有一种美丽的窒息的感觉。 设 \(f_{i, j}\) 表示前 \(i\) 个选 \(j\) 段出来的最小代价，转移 \(f_{i, j} = \min_{0 \leq k < i} \{f_{k, j - 1} + w_{k + 1, i} \}\)，\(w_{k ......

Game on Sum (Hard Version) 题面翻译 Alice 和 Bob 正在玩一个游戏，游戏分为 \(n\) 个回合，Alice 和 Bob 要轮流对一个数 \(x\) 进行操作，已知这个数初始值是 \(0\)。 具体每个回合的行动规则如下： Alice 选择一个在区间 \([0,k ......

洛谷传送门 CF 传送门 容易转化成经典的有向图博弈模型。每张牌建一个点，若 \(x\) 能打败 \(y\) 就连一条 \(x \to y\) 的边。入度为 \(0\) 的点为必败态，之后类似拓扑排序倒推即可。 具体就是若存在边 \(u \to v\)，若 \(u\) 为必败态则 \(v\) 为必胜 ......

前言 传送门 本题思维难度：橙。 本题代码难度：橙或红。 综合难度：橙。 本人代码码量位居第二，但是呢，我的空格多，所以，还不来看一下？ 题意 根据题目，若两人一人有 $j$，一人没 $j$，则异或后，第 $j$ 位为 $1$。 那么，题目转化为：已知有 $m + 1$ 个数，求出满足 $a_i$ ......

题目传送门 一开始就想着整个过程，觉得逃跑的那个人的路线要考虑好多，包括路径长度，是否脱离追击者的范围要受到额外伤害等等。比较复杂没想明白。 后来发现，可以划分成两个阶段，即追击者传送前后。传送后逃跑者肯定走最短路线最优，因为和追击者的距离变化已经完全固定了，并且传送后的代价可以通过dijk预处理实 ......

题目链接 题面翻译 现在有 \(K\) 个队，飞机有 \(N\) 排座位，每排能坐 \(8\) 个人，不同队伍的人不能坐相邻的位置。 相邻情况有 \(5\) 种 \((1, 2), (3, 4), (4, 5), (5, 6), (7, 8)\)。请问这 \(n\) 排座位是否够坐。 （\(K\) ......

Given an integer array arr of distinct integers and an integer k. A game will be played between the first two elements of the array (i.e. arr[0] and a ......

Problem StatementThere are $2N$ integers written on a blackboard. The $i$-th integer is $A_i$. Alice and Bob will play a game consisting of $N$ rounds ......

CF1764D Doremy's Pegging Game 你怎么连简单题也不会？ 考虑满足条件当且仅当有连续的n/2向下取整段被删除。 考虑最终状态一定是一次删除联通了两个连续段，然后结束。 我们枚举这个连续段的长度 i 。 最后一个删除的位置有 n/2下取整*2-i 种方案，设另外删除了 j 种 ......

啊啊啊每次补完题都感觉这题我场上应该是能想出来的啊！ 考虑简化问题：若每个栈内只有一个元素，how。 此时我们发现所有栈之间构成了一个内向基环树。且环是没有用的，因为我们在环上走一圈之后仍然会回到原点。所以不妨把所有环边删除，此时每棵树的答案即为树根。 而对于原问题，同理，我们可以考虑不断找环，每找 ......

题目 有一个长度为 \(m\) 的书架，以及 \(n\) 个长度 \(a_1,a_2,\dots,a_n\) Alessia 和 Bernardo 从书架上取书。每次由 Alessia 选择一个之前没选过的 \(i\)， 并选择一个长度为 \(a_i\) 的区间，需要保证这个区间内的书全都没有被取过 ......

题目链接 Game Bundles 分析 很神奇的一道题目 先想想如何计算一个集合和为60的子集个数 可以想到通过 \(DP\) 求解： 记 \(f[i][j]\) 为前 \(i\) 个数字，和为 \(j\) 的子集个数 则 \(f[i][j]+=f[i-1][j-a[i]]\) \(f[i][a[ ......

这个机器人的原点在世界坐标系下的(4.5,1.5),而她右肩膀上的那个灯的模型坐标系为(-1,5),怎样计算这个灯的世界坐标呢？ 开始： 获取原点，这个原点为(4.5,1.5) 向右移动一个位置，机器人的"左边"是[0.87,0.50],这样得到的位置为(4,5,1.5) + (-1)X[0.87, ......

一系列 \(n\) 个数组，第 \(i\) 个数组的大小 \(m_i \geq 2\) 。第 \(i\) 个数组为 \(a_{m_1}, a_{m_2}, \cdots, a_{m_i}\) 。 对于每个数组，你可以移动最多一个元素到另一个数组。 一系列 \(n\) 个数组的 \(beauty\) ......

你需要击败一只巨龙，他有 \(h\) 点血量，你可以使用以下两种攻击方式： 黑洞：使巨龙的血量变为 \(\lfloor \frac{h}{2} \rfloor + 10\) 。可以使用 \(n\) 次。 雷击：使巨龙的血量变为 \(h - 10\) 。可以使用 \(m\) 次/ 当巨龙的血量 \(h ......

\(Alice\) 和 \(Bob\) 在玩一个 \(01\) 游戏，一开始有一个 \(01\) 串 \(s\) 。\(A\) 先开始，两人轮流操作。在每一步操作中，玩家可以选择 \(s\) 中两个相邻的不同数并且将他们删除。最后不能删数的玩家将失败。询问 \(Alice\) 是否可以获得胜利。 首 ......

题目链接（Easy） 题目链接（Hard） Part1 神奇的博弈类型 \(Dp\) 。 我们发现与当前状态有关的量，有且只有 现在是第几轮，还有 Bob 用了几次加的操作 ,这都会影响之后的决策，而和之前的决策无关，换句话说，当前决策有后效性，没有前效性。那我们考虑倒着 \(Dp\). Part2 ......

CF1867C Salyg1n and the MEX Game 简单博弈论题。 设给出序列的 \(\text{mex}\) 为 \(x\)，那么 Alice 第一次操作时加入 \(x\) 一定是最优的。此时显然有 \(\text{mex(s)} \ge x\)。 因为如果加入的数 \(y<x\)， ......

\(R\) 和 \(B\) 在玩一个数字游戏，给一个含有 \(n\) 位的正整数 \(x\) 。俩人轮流操作， \(R\) 先行动。 在每一步中，\(R\) 可以选择 \(x\) 中一个未被标记的奇数位置并标记，\(B\) 可以选择 \(x\) 中一个未被标记的偶数位置并标记。 当最后只剩下一个未被 ......

当前的状态有：传送门的激活状态，已经完成的任务数量，当前的位置（传送门/任务），经过的时间。显然我们会先将所有任务按照 \(t_i\) 升序排序。把前三维列为状态，后一维列为答案，此时我们可以得到一个状态数为 \(O(2^nm^2)\)，转移为 \(O(m)\) 的 dp。 状态数很没救，显然要被优 ......

C. Card Game There are $n$ cards stacked in a deck. Initially, $a_{i}$ is written on the $i$-th card from the top. The value written on a card does no ......

[ARC155D] Avoid Coprime Game 一个暴力思路是直接记录选了哪些 \(a\) 然后转移，但是我们显然没办法将已选择的 \(a\) 的信息用状压全部记录下来。但是你注意到题目中对 \(a\) 的选择有着不错的性质，具体如下： 若确定当前 \(G\)，则先前选择的所有 \(a_i ......

题目描述 Rishi is developing games in the 2D metaverse and wants to offer game bundles to his customers. Each game has an associated enjoyment value. A ga ......

洛谷传送门 AtCoder 传送门 考虑若 \(n\) 是奇数怎么做。枚举 Alice 第一次选的数 \(a_i\)，然后考虑把剩下的数两两结成一个匹配，若 Bob 选了其中一个，Alice 就选另一个。容易发现排序后奇数位和它右边的偶数位匹配最优。那么设奇数位的和为 \(A\)，偶数位的和为 \( ......

思路 题意大概是两人都有一组数，奇数轮，第一个人可以选择和第二个人交换一个数字也可以不换，偶数轮，第二个人可以选择和第一个人交换一个数字也可以不换。 首先可以猜测，我们每次都应该选择交换对方的最大值和自己的最小值，如果自己的最小值都比对方大的话就不交换。应该比较好想，这里感性证明一下。 如果用的不是 ......

洛谷传送门 AtCoder 传送门 若图中存在点使得删去它后 \(S, T\) 不连通，那么 A 可以一步获胜。 否则，双方都不会删去一个点使得删去它后会产生一个点使得删去它后 \(S, T\) 不连通。那么到最后图上会剩下两条 \(S \to T\) 的不交路径。此时一方无论如何操作都会使得另一方 ......

某种程度上的抽卡游戏？ 有这样一个结论：一个后缀中\([i+1,n]\) 中所有的正数都可以被取到，所以维护一个正数后缀和 \(s_i\)，枚举每个位置 \(i\)，如果 \(i\) 为奇数，答案对 \(a_i+s_{i+1}\) 取 \(\max\)，否则对 \(s_{i+1}\) 取 \(\ma ......

如果考虑 \([x,y]\) 中什么位置能乘到 \([l,r]\) 就比较麻烦，简单的做法是考虑 \(l\) 和 \(r\) 对应到 \([x,y]\) 中的位置。左边界至少是 \(\frac{l-1}{k}+1\)，右边界至多是 \(\frac{r}{k}\)，判断一下与 \([x,y]\) 是否 ......

题意：树的最小点覆盖，选择最少的点覆盖所有边。 分析： 状态：f[u][0/1] 表示不选/选编号u的点的最优解 转移： 不选u，则一定选u的儿子v，即 f[u][0] +=f[v][1] 选u，则可以选，也可以不选u的儿子v，即 f[u][1] += min(f[v][0], f[v][1]); ......

Graph Game 乌克兰逃兵在线发题解。 好像要用期望去推,但是像我这种看到序列的期望题只想得到线性性的弱鸡只能感理了。 我们把点分治过程当成点分树,y 能在 x 被爆时做贡献当且仅当 y 为 x 的子树。 先考虑树的情况。 考虑把遍历 t 的次数分到单个点上发现仅当 x 为 x->y 路径上第 ......