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)