第二十次CCF计算机软件能力认证

1. 略
2. 略
3. 拓扑排序
4. 对每个点对(A)和(B),计算它们分别到(O)的距离(|OA|)和(|OB|),以及它们之间距离(|AB|).
   如果(angle OAB)或者(angle OBA)为钝角,那么答案就是(|AB|).
   使用面积公式计算(O)到(|AB|)的距离,如果大于或等于半径,答案也是(|AB|).
   否则距离是两条切线加一段弧,切线长度为(sqrt{|OA|^2-r^2})和(sqrt{|OB|^2-r^2}).
   使用余弦定理计算(angle AOB),减去(arccosdfrac r{|OA|})和(arccosdfrac r{|OB|}),即为弧对应的圆心角.
5. 动态规划,(dp[i][j][k][p])表示长度为(i),密文对应自动机状态为(j),明文对应Trie树节点为(k),当前页数为(p).
   注意对每对(k)和(p),可以转移的字符是有限制的.可以计算状态数和转移数均为(O(nm|s|^2)).