The 2020 ICPC Asia Macau Regional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 16/50 | 4 | 5 | 12 |
A¶
solved by 2sozx
题意¶
给定长度为 \(n\) 的数组\(a_i\) ，随机排列 \(p_i\) ，求 \(((((0 + 1) *a_{p_1} + 1) * a_{p_2} + \cdots) + 1) * a_{p_n}\) 期望，\(n \le 10^5\)
题解¶
将式子展开得 \(\prod\limits_{i = 1}^{n}a_{p_i} + \prod\limits_{i = 2}^{n}a_{p_i} + \cdots + \prod\limits_{i = n}^{n}a_{p_i}\) ，设 \(f_i\) 为原数组取 \(i\) 个数的乘积和，因此总贡献即为 \(\sum\limits_{i = 1} ^ {n} f_i\times i! \times (n - i) !\) ，\(f\) 数组求法是裸的分治 \(NTT\)
B¶
upsolved by
题意¶
题解¶
C¶
upsolved by 2sozx
题意¶
太sb了这题，当时没写很绝望。
题解¶
\(siz\le 4\) 暴力分就行。
D¶
solved by JJLeo Bazoka13
题意¶
题解¶
E¶
upsolved by
题意¶
题解¶
F¶
upsolved by 2sozx JJLeo Bazoka13
题意¶
傻逼题爬
题解¶
傻逼题爬
G¶
solved by JJLeo
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by
题意¶
题解¶
J¶
upsolved by
题意¶
题解¶
K¶
upsolved by
题意¶
题解¶
L¶
solved by JJLeo
题意¶
题解¶
记录¶
1h：MJX看眼A发现是到分治NTT，在推会式子，CSK开始看F，感觉很会，ZYF,CSK看L好写先写L，然后14minAC，MJX去抄板子，然后CSK看D是个小模拟，等MJX写完就写。MJX写挂了，拖到旁边然后ZYF写D，60+min过了D。
2h：MJX测试NTT，ZYF看BGI，MJX发现板子挂了，调了半天，ZYF重抄了个板子，样例过了，交上去WA了，然后发现maxn开小了。CSK想F想飞了（当时觉得很正确），感觉能过就去想H了（F的问题从0～300min一直存在，单独思考），H喂了个假题意，MJX直接听了，发现有点奇怪，不会做，换题。
3h：CSK看了眼E，ZYF继续想F，MJX去想C，CSK把E的题意——平面上选择k个矩形覆盖最大面积（实际上矩形的位置是固定的）（完全错误）喂给了mjx（实际上到讲题才看对E的题意）然后看了一会觉得不可做。。。于是三个人开始CF交替卡题，之后看到榜上G过得比较多，就跳出卡题圈去开了G并在封榜前AC
4h：封榜之后就继续卡在CF，还有40+min的时候mjx来搞F并且大致搞出来一个具体的做法。然后就开始三人写代码环节。。。经历了RE（忘记return 0）和WA之后开始debug，最后没能de出来，开局想抢F一血来着结果裂开到了最后。
赛后讨论是没有特判d=1的corner case，并且删边后加边有一些细节写烂掉了。
总结¶
MJX：我是傻逼
Dirt¶
A(+1)：数组开小了