Contest Info

date: 2019.02.22 09:30-14:30

practice link

Solutions

C. Called Convergient

题目大意：一个人开始有 \(x\) 元钱，每轮他可以下注不超过他当前钱数，且不小于上一轮的钱。每轮赢的概率为 \(p\)，\(0<p<\frac{1}{2}\)。如果他的钱大于等于 \(1\) 元，那么他就赢，如果钱数为 \(0\)，他就输。求最优策略下他赢的概率。

题解：没学过随机过程的我不会证。。只能上结论了：

设 \(x\) 的二进制表示为 \(0.b_{1}b_{2}\cdots\)，那么赢的概率为 \(\displaystyle{\sum_{i=1}^{+\infty}b_{i}p^{i-\sum_{j=1}^{k-1}b_{j}}(1-p)^{\sum_{j=1}^{k-1}b_{j}}}\)。这个式子只要找一下循环节就很好求了。

F. Formally, You Choose Three Integers

签到题。

H. Hat With An Integer

题目大意：给你长度为 \(n-1\) 的数列 \(b\) 和 \(c\)，定义一个长度为 \(a\) 的数列合法，当且仅当至少存在某个 \(1\le i\le n-1\)，使得 \(a_{i+1}<a_{i}+b_{i}\) 和 \(a_{i+1}>a_{i}+c_{i}\) 中至少有一个成立。

现在有 \(n\) 个哲学家，第 \(i\) 个人头上有一顶写着 \(a_{i}\) 的帽子，这个数列 \(a\) 会告诉你。每个人能看到别人帽子上的数，但是看不到自己的。保证 \(a\) 合法，每个哲学家也都知道这一事实。每一天，如果有某个哲学家确认某个数不可能是自己帽子上的数，那么游戏结束。问游戏在第几天结束。

题解：设 \(S_{i}\) 表示第 \(i\) 天，所有人都知道不可能是 \(a\) 的数列集合。如果 \(S_{i}\) 中存在某个数列与 \(a\) 恰有一个位置不同，那么显然第 \(i\) 天游戏就会结束。显然 \(S_{1}\) 是所有非法的数列，而 \(S_{i}(i\ge2)\) 是所有与 \(S_{i-1}\) 中的某个数列至多有一个位置不同的数列（因为假如这种数列是 \(a\)，那么第 \(i-1\) 天游戏就该结束了）。那么显然，结束的天数是所有非法的数列中，和 \(a\) 不同的位置数的最小值。

首先注意到如果存在某个 \(b_{i}>c_{i}\)，那么所有数列都是合法的，游戏永远不会结束。否则我们反过来求非法数列与 \(a\) 相同位置数的最大值。设 \(dp_{i}\) 表示第 \(i\) 个位置与 \(a\) 相同，前 \(i\) 个位置中最多有多少个位置与 \(a\) 相同。我们从 \(dp_{j}\) 转移到 \(dp_{i}\) 时，必须满足 \(j<i\)，以及 \(a_{j}+\sum_{k=j}^{i-1}b_{k}\le a_{i}\le a_{j}+\sum_{k=j}^{i-1}c_{k}\)。第二个条件我们可以稍微改写一下，变成 \(a_{j}-\sum_{k\le j-1}b_{k}\le a_{i}-\sum_{k\le i-1}b_{k}\)，且 \(a_{j}-\sum_{k\le j-1}c_{k}\ge a_{i}-\sum_{k\le i-1}c_{k}\)。这样看起来我们要枚举 \(dp\) 这一维，然后再维护一个二维的数据结构。但是我们还可以进一步优化，注意到如果 \(j<i\)，且 \(a_{j}-\sum_{k\le j-1}b_{k}\ge a_{i}-\sum_{k\le i-1}b_{k}\land a_{j}-\sum_{k\le j-1}c_{k}\le a_{i}-\sum_{k\le i-1}c_{k}\) 的话，只能有这两个不等式都取等号（由 \(b_{i}\le c_{i}\) 很容易证明）。也就是说，只要满足了 \(a_{j}-\sum_{k\le j-1}b_{k}\le a_{i}-\sum_{k\le i-1}b_{k}\)，且 \(a_{j}-\sum_{k\le j-1}c_{k}\ge a_{i}-\sum_{k\le i-1}c_{k}\)，就必然有 \(i<j\)。这样我们就省去了一维。

时间复杂度 \(\mathcal{O}(n\log n)\)。

I. Intersect With Other Balls

题目大意：给你一个宽 \(3r\)，高 \(h>2r\) 的矩形桶。两个人轮流往矩形里扔半径为 \(r\) 的圆。首先把圆放在严格在矩形内，与顶部相切，不和已有的圆相交的位置上。然后让其下落，圆只要接触到之前的某个圆或者碰到底部即会停止。无法放置圆的人输。问谁胜。

题解：考虑把圆缩成点，那么矩形变为宽 \(r\)，高 \(h-2r\)，每次放一个点需要恰好和之前的那个点距离 \(2r\)。然后对矩形中的每个点分析一下胜负态即可，pattern 是有规律的。

J. \(J\) The Attacker Has

题目大意：两个人打牌，牌总共有 \(n\) 种花色，每种花色有 \(m\) 个数字。一些花色是 trump。同花色数字的牌可以有若干张。\(n,m\le18\)。

第一轮，先手可以任意出一张牌；之后先手只能出两人已经出过的数字。后手出牌时必须大过先手刚刚出的牌，大过是指要么花色相同，数字严格大；要么后手出了一张 trump，而先手出的不是 trump。注意先手不必大过后手。

问先手的第一张牌有多少种选择使得他必胜。同花色数字的牌如果有若干张，需要重复计算。

题解：我们定义一个数字集合 \(S\) 是好的，当且仅当双方只出 \(S\) 中的牌时，后手必胜。注意这里我们不要求先手只能出已经出过的数字。先手先出某个数字 \(x\) 必败，当且仅当存在一个好的集合 \(S\)，使得 \(x\in S\)。

充分性是显然的，因为后手在更加不利的规则下仍然能赢得比赛。而如果后手对 \(x\) 存在一种必胜策略，我们证明在新规则下后手仍然胜利：不论先手如何改变出牌顺序，后手只需要出原策略对应的那张牌就可以了。这样一来，原策略中出现的所有数字就是我们的 \(S\)。

对于每个 \(S\) check 就比较简单了。贪心地选择最小的大于先手所出的牌即可。需要稍微注意一下 trump 的问题。

时间复杂度 \(\mathcal{O}(2^{m}nm)\)。