Day 7: MIPT Contest, GP of Dolgoprudny¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 17/76 | 4 | 4 | 11 |
A¶
**upsolved by **
题意¶
题解¶
B¶
**upsolved by **
题意¶
题解¶
C¶
**upsolved by **
题意¶
题解¶
D¶
solved by YZW
题意¶
题解¶
E¶
**upsolved by **
题意¶
题解¶
F¶
**upsolved by **
题意¶
题解¶
G¶
solved by JLK
题意¶
有\(n\)个人，每个人有一个硬币，硬币的两面有正整数\(a_i,b_i\)。现在我要造一枚硬币，如果两面的数字分别为\(a,b\)，那么花费为\(a\times b\)。然后我和每个人各玩一次扔硬币游戏，比较谁的数字大，赢的人赚\(x_i\)钱，否则亏\(x_i\)钱（平局算我赢）。求最优策略下的期望收益（可能为负）。
\(1 \le n \le 2\times 10^5,1 \le a_i,b_i,x_i \le 10^9\)
题解¶
实际上我的硬币两面可以分开考虑。因为扔出每一面的概率都是\(\frac 12\)，而两面是独立的。
设\(f(x)\)表示我扔出\(x\)数字时和别人比较赚的钱。这可以用一个差分得到。
那么对于一个\(a,b\)，我最后的收益是\(\frac{f(a)+f(b)}2 -a\times b\)。要让这个最大。
分析一下这个式子，设\(\frac{f(a)+f(b)}2 -a\times b=m\)，当\(a\)固定时，\(a\times 2b+m=f(a)+f(b)\)，可以用类似于斜率优化DP的思路来求每个\(a\)的最大\(m\)。即把\((2b,f(b))\)看成点，然后求一个凸包，再扫一遍求切线的截距。显然可以用栈来维护，所以这一部分是线性的。
只有一开始离散化需要一个sort，故总复杂度为\(O(n\log n)\)。
H¶
solved by YZW
题意¶
题解¶
I¶
solved by JLK
题意¶
有\(2n+1\)个点编号为\([-n,n]\)，一个人从0点开始走，有一个走路序列，第\(i\)次有\(p\)的概率不动，\(1-p\)的概率向左或向右（方向为给定序列里的方向，-1/1）走一格。他的家是所有点里等概率随机的一个，第一次走到家就结束。如果最后也没走到家就无了。求走到家的概率。
\(1 \le n \le 5000\)
题解¶
设\(f_{i,j}\)表示\(i\)时刻走到\(j\)的位置的概率，\(g_{i,j}\)表示\(i\)时刻恰好第一次走到\(j\)的概率。
由于每个点作为家的概率相同，只要第一次走到家就结束，所以答案就是\(\frac{\sum g_{i,j}}{2n+1}\)。
\(f_{i,j}\)可以简单递推求出。考虑用\(f\)推出\(g\)，如果不是第一次走到，那么设第一次走到\(j\)的时刻是\(k\)，这种情况被计算到\(g_{i,j}\)当且仅当\([k+1,i]\)的操作序列的和为0。用\(h_{k+1,i}\)表示这样和为0的概率。可以得到\(g_{i,j}=f_{i,j}-\sum\limits_{k=0}^{i-1}g_{k,j}\times h_{k+1,i}\)。
如果可以求出\(h\)，那么这样计算是\(O(n^3)\)的。但是注意到答案只和\(\sum\limits_{i,j} g_{i,j}\)有关，记\(F_{i}=\sum\limits_{j}f_{i,j},G_i=\sum\limits_{j}g_{i,j}\)。那么答案为\(\sum\limits_{i=0}^n G_i\)。而\(G_i=F_i-\sum\limits_{k=0}^{i-1}G_k\times h_{k+1,i}\)。这样就可以\(O(n^2)\)求出\(G_i\)了。（实际上，在这种情况下，所有\(F_i=1\)）
而对于\(h\)，实际上一段操作\(sum=0\)的概率只和-1/1的个数有关，和-1/1的相对位置无关。可以看做是把-1和1拆开考虑，各选出等量的数走，剩下的不走。那么用\(H_{i,j}\)表示用了\(i\)个-1，\(j\)个1，\(sum=0\)的概率。
转移方程为\(H_{i,j}=p\times (H_{i-1,j}+H_{i,j-1})+(1-p)^2\times H_{i-1,j-1}-p^2\times H_{i-1,j-1}\)。
后面减去是因为\(H_{i-1,j-1}\)两个都不选的话转移到\(H_{i,j}\)会被算两次。
这样就可以\(O(n^2)\)解决了。注意卡常。
J¶
**solved/upsolved by **
题意¶
题解¶
K¶
**solved/upsolved by **
题意¶
题解¶
L¶
**solved/upsolved by **
题意¶
题解¶
记录¶
开局YZW过了H(0:35)。
跟榜看DI，都不太会写。D复杂度大了，在想优化。
JLK想到一个方法把log去掉了，准备开始写，但是YZW提出一个更好实现的方法，于是YZW写，然后过了(2:44)。
YZW写的过程中JLK和TYB会G了，但一开始想用李超线段树。看了看板子怕TLE，然后想到更好的办法，JLK开写，WA一次后AC(3:27)。
然后想I，一开始没有头绪，JLK口胡了一种方法，写着写着发现不对劲。不断改进后就可以了。TLE一次后AC(4:57)。
总结¶
Dirt¶
G(-1)
I(-1)