====== 2020牛客暑期多校训练营(第五场) ======
===== Results =====
==== Summary ====
* Solved 5 out of 11 problems
* Rank 71/1145 in official records
* Solved 5 out of 11 afterwards
# | Who | = | Penalty | A | B | C | D | E | F | G | H | I | J | K | Dirt |
7 | 大吉大利,今晚吃 mian(); | 5 | 574 | | + 03:27 | | +1 03:16 | +1 00:30 | +1 00:14 | | | +1 00:47 | -1 | | 44% 4/9 |
==== Member Distribution ====
^ Solved ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^
| Pantw | | | | | √ | √ | | | √ | - | |
| Withinlover | | | | √ | | | | | | | |
| Gary | | √ | | | | | | | | | |
(√ for solved, O for upsolved, - for tried but not solved)
----
====== Solutions ======
===== A =====
===== B =====
任选一个点做根,所有点到根的路径长异或即为这两点之间的边长度,要维护最小的生成树,需要在所有路径长组成的01trie树上维护,如果一个节点的01两个子树均有节点,则需要在该位置上连一条边使得子树联通,只需要再在子树上跑一遍就能算出连边的最小值
===== C =====
===== D =====
把数组当成一个环,那么第一个操作就没啥用了。
在环上考虑,第二个操作其实是交换了两个数的位置,由于多次操作算一次,所以每次可以把任何一个数字移动到任何一个位置。
最终想要使得环有序。
找出从每个位置开始的最长上升子序列,保持这个子序列不动,把余下的数字移动到正确位置。枚举一下起点就做完了。
===== E =====
ptw: 这个题是 hzy 做的,我直接拿 py 莽了出来,坐等题解
withinlover:这个题是个签到题,然而WA了一发才发现需要高精。甚至差点手撸高精度(
===== F =====
水题不解释
===== G =====
===== H =====
===== I =====
ptw: 队友推了个 9/5 一个 5/3,我直觉感觉是 2/3,就直接交了
===== J =====
在一个扇形上求两圆的交的面积,情况太多了不会写
===== K =====
-------------
====== Comments ======
ptw:
* 这几场一直想错题,很奇怪。队友说了之后尽量自己再想想有没有别的好方法,第一眼很可能是假做法。(D)
* K 应该再仔细想想的,转移没优化出来,其实只需要考虑一点点状态。
withinlover:
* 开始写之前多想几步(假做法害人不浅)(D)
* I 应该多想几步,性质都猜的差不多了没总结成做法。
Gary:
* B想的有点久,还写了一个假做法