TCO 2019 2B

Beijing Onsite 的热身,不过居然晋级了,下一场还是好好打(受虐)一下吧。。。

250 MedianFaking

Brief Description

给定 n 个人,每个人有 m 个测量结果。取所有人所有测量结果的中位数(偶数时下去整)为最终结果。
已知测量结果应该是 goal,问至少修改几个测量结果可以使得结果恰好为 goal,在这种情况下最少需要参与修改的人数又是多少。

Analysis

如果要让结果恰好为 goal,那么比 goal 小的数和比 goal 大的数都不能超过一半,显然这两边只会有一边不符合。
于是我们只要关心这一边需要修改几个数就好了,并且现在只需要考虑一边,第二问只要统计出每个人可以带来的贡献,排序贪心即可。

500 DivisorSequences

Brief Description

给定 n,我们将 n 拆分成若干个整数相加的形式:n = a1 + a2 + … + am。
要求 a 序列严格递增且 a_i 整除 a_{i+1},问 m 最大可以是多少。

Analysis

观察 15 = 1 + 2 + 4 + 8…
我们发现如果把 1 去掉的话,有 14 = 2(1 + 2 + 4)…
这样我们就发现了一个子问题!
定义 f(n) 表示将 n 分解,并且第一个数是 1 的方案数,每次减去 1 后枚举约数递归即可。那么实际的答案可能第一个数不为 1,所以开始再额外枚举一次约数就好。
复杂度虽然不太容易估计,但貌似不记忆化也能过。

1000 SlightlyBigger

Brief Description

Alice 和 Bob 报数,从 1 到 oo,目标是比对方报的数只大一点。
– 如果恰好差小于等于 maxDiff,那么大的一方获胜,并得到 ifNear 分。
– 否则,小的一方获胜,并得到 ifFar 分。

双方都采取最优策略时,问 Alice 报的数恰好为 query 的概率。
(ifNear < ifFar <= 2×ifNear)

Analysis

第一眼感觉这个题很神,看了一下大家后来都是高斯消元做的。但是不知道怎么列方程。后来请教了一下毕克老师,毕老师说其实这个问题跟剪刀石头布是一样的,就你想象一个剪刀石头布游戏,然后给你一个收益矩阵。
对方把自己的策略的概率分布向量已经告诉你了,在最优情况下,你发现你即便知道这个向量也并不能让你取得任何优势。
这就是传说中的 纳什均衡,于是只要设表示报 x_i 的概率,根据上面这些关系,列出线性方程组,高斯消元即可。

纳什均衡虽然提供了 n 组方程,但是 rank 似乎是 n-1 的,最后别忘了加上所有概率分布之和等于 1。
可以预计答案不会很大,可以带极限数据跑一下看看边界。