2018 ECNU AK ICPC/CCPC Typing Speed Contest

One,Two,Three,AK

Problem A

Unsolved.

Problem B

Solved by oxx1108 && Xiejiadong. 03:04:19(+)

题意：给出初始位置和最后的位置，求合法的方案数。

题解：暴力+记忆化直接就过了，时间复杂度$O(3^n)$。

Xiejiadong: dfs 都写丑了。背锅。

Problem C

Solved by oxx1108. 01:27:32(+2)

题意：只能从度数小的点走到度数大的点，求最长路径。

题解：转化成一个 DAG，然后拓扑排序之后 DP 一下就可以。看错结点下标卡了好久，初值也赋错导致卡了好久。

Problem D

Solved by oxx1108. 00:15:13(+2)

签到题。

Problem E

Solved by Xiejiadong. 04:44:16(+)

题意：$h[i]$表示最小需要删掉几条边，可以使得$i$边在最小生成树上，求$\sum h[i]$。

题解：显然，会对$i$边产生影响的，一定是权值比他小的边，把所有权值比他小的边拿出来，作为新的图，然后求最小割，就是$h[i]$。

Problem F

Solved by Xiejiadong. 01:11:10(+)

题意：给出路径递归生成方式，求第$x$步的位置。

题解：按照题意递归，注意第一部分和第四部分的旋转以后，起点和终点互换了。

Problem G

Upsolved by Xiejiadong.

题意：给出两条折线U和L，求U在上时的封闭面积。

题解：在$y$发生变化的$x$上打一个标记，因为$x$比$50000$小，直接扫一遍，算一下就可以了。

有一个特殊情况是样例3，可能$y$的变化会在$x=0$的时候发生。

Problem H

Solved by oxx1108. 02:02:32(+5)

题意：给两个石头剪刀布的序列，求最好的匹配位置使得你赢的次数尽量多。

题解：分三种匹配情况跑三次 FFT（等于字符串匹配，校赛原题），然后求和最大，bitset被卡了。

Problem I

Upsolved by Xiejiadong.(-6)

题意：给出一个字符串，去掉某一部分前缀以后，一定是一个循环字符串。

题解：kmp的next数组的应用。

反串构造next数组，那么对于反串的前$i$为，他的最小循环节长度一定是$i-next[i]$，这个就是$p$，那么$k=n-i+1$，这里直接美枚举所有$k$和$p$去$k+p$的最小值即可。

还要注意$k=0$的情况，所以枚举的时候要向后多找一位。

Problem J

Unsolved.

Problem K

Solved by Xiejiadong. 03:31:05(+1)

题意：给定平面上折线的行进方向和距离，要求修改距离使得不自相交。

题解：水平的和垂直的分开考虑，水平的如果和上一次的方向相同，走一步，否则走$i$步，可以有效避免冲突。垂直的处理方式类似。

Problem L

Unsolved.