2020牛客暑期多校第十场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 23/906 | 5 | 6 | 10 |
A¶
solved by 2sozx
题意¶
给定一个质数 \(p\) 问是否存在一个排列使得每一位满足 \(a_{i+1}=2a_i(mod p)\) 或 \(a_{i+1}=3a_i(mod p)\) 其中一个条件。
题解¶
令 \(a_1=1\) ，之后能用 \(2\) 就用 \(2\) ，否则就用一个 \(3\) ，之后再用 \(2\) 。完全不会证明。
B¶
upsolved by
题意¶
题解¶
C¶
upsolved by JJLeo
题意¶
题解¶
大致看没毛病，一细想就不会了，我裂开。
D¶
solved by 2sozx JJLeo Bazoka13
题意¶
炉石传说背景，有四种随从：一.剧毒；二.剧毒圣盾；三.剧毒亡语；四.剧毒圣盾亡语。其中亡语生成一个 \(1/1\) 的植物，其余随从为 \(1/10^9\)，现在你拥有一些随从，电脑拥有一些随从，问在你做出最优决策，电脑做出最劣决策下你是否能赢。
题解¶
这里是全网最详细的炉石传说攻略（
以下小亡语即为植物，小兵为仅有剧毒的随从。
1.如果咱们有小亡语 对面有圣盾 优先撞 如果有圣盾亡语 撞圣盾亡语
2.如果咱们有没有圣盾的 对面有小亡语 白吃一个
3.如果有只有亡语的，优先撞亡语>小兵>圣盾亡语>其它
4.如果咱们有圣盾亡语的 优先撞亡语>圣盾亡语>小兵>其它
5.如果咱们有小兵 优先撞亡语>圣盾亡语>小兵>其它
6.如果咱们有圣盾的 优先撞亡语>圣盾亡语>小兵>其它
7.如果有小亡语 撞小亡语>亡语的
8.如果有小亡语 对面有小兵，圣盾，圣盾亡语则我们必输
上述25种随从的对应方式优先级全部排列完毕，按优先级模拟即可。
E¶
solved by JJLeo
题意¶
水题。
题解¶
二分即可。
F¶
upsolved by
题意¶
题解¶
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
solved by Bazoka13
题意¶
题解¶
J¶
solved by Bazoka13
题意¶
给出两棵根给定的树，尽量少地重排编号使得两棵树相同
题解¶
考虑用费用流转移,\(dp[i][j]\)表示第一颗树里的\(i\)节点的子树变成第二棵树里\(j\)节点的子树需要的费用，每次对相同子树大小和儿子数量的节点跑一个最小费用最大流，根据最大流和儿子数量判断可行性，\(dp[rt_0][rt_1]\)即为答案
记录¶
0min：开局分题
30min：CSK ZYF冲E，MJX看A
38min：ZYF AC E，MJX 冲A
49min：MJX AC A
50min~180min：集体自闭ing
180min：D rejudge 了，重测了，发现挺可做的集体搓炉石
234min：巨大讨论后 ZYF AC D，CSK看J
245min：CSK AC J
286min：CSK 猜结论 WA1 后AC
总结¶
- MJX：要提高打代码速度和准确率，虽然C最后想错了但是也没打出来。
- ZYF：比较早的时候就想到了J，但是认为复杂度过高遂自闭两个小时，要敢于尝试，减少这种无意义的自闭时间。