2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_3
目录
2020牛客暑期多校训练营（第三场）
Results
Summary
- Solved 7 out of 12 problems
- Rank 96/1178 in official records
- Solved 8 out of 12 afterwards
Virtual Participation
| # | Who | = | Penalty | A | B | C | D | E | F | G | H | I | J | K | L | Dirt |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 11 | 大吉大利，今晚吃 mian(); | 7 | 837 | + 00:27 | +2 01:17 | + 00:44 | -6 | + 02:03 | + 02:29 | +5 04:35 | + 00:02 | 50% 7/14 |
Member Distribution
| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Pantw | √ | √ | √ | √ | ||||||||
| Withinlover | √ | √ | ||||||||||
| Gary | O | √ |
(√ for solved, O for upsolved, - for tried but not solved)
Solutions
A
这个题 2/3 的情况一定直接选🐟是最优的，然后维护后缀 0+1 的个数，判断是否继续制作诱饵即可。
B
把整个字符串当成一个环，其实就是顺时针和逆时针偏移（然而一开始当成Splay了）
C
这个题先找到掌根那条长为 9 的边，然后找一下 6 和 8 分别在哪一侧，直接叉积判断手性即可。
D
构造题，先把所有点放在一起尽量凑成正方形的形状，从而保证了最小值，最大值为n*4，奇数值不可能取到，对于要求的值
开始取得时候要保证不影响原近似正方形的长宽，单独取出放在较远处可以保证ans+=4，当与所需结果差为2时，取出放在正方形左下角的下方可以保证ans+=2
当必须影响长宽时，即原类似正方形已变成L的形状，从两边开始取，放在较远处可以保证ans+=2
这样的方式保证了任意最小值与最大值间的偶数都可以取到
E
发现4个和6个是一个小节，结果是区间差*2，直接dp，f(i)转移(i-4)和f(i-6)的值即可
F
讨论一下就行，$\gcd(a, b)>1$的时候通分一下答案就有了，$\gcd(a,b)=1$的时候如果 $b$ 是质数就无解了，不是质数的话枚举因子，然后能推出ExGCD的式子。
G
这个题直接用 set 存当前块向外的连边，然后合并的时候启发式合并一些 set，在并查集里标记代表元即可。
H
I
J
K
L
水题。
Comments
ptw：
- 希望自己别再把简单题看成 Splay
- 可以一个人看代码一个人写对拍，迅速定位 bug
- 加强沟通交流
Withinlover
- 打暴力也别纯模拟。。。该写BFS就写BFS，该写并查集就写并查集
- 读错题害死人
Gary：
- 有思路早点动手，早几分钟就能过D了
- 尽量多沟通
2020-2021/teams/mian/nowcoder_training/2020_multi-university_training_contest_3.txt · 最后更改: 2020/07/21 18:10 由 gary
