2020-team8-1119

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(Standings.png,1000px)]]
[[Image(Submissions.png,1000px)]]
== 流水账 ==

(by Ebola)开场都在做梦，傻逼Ebola先开了个L，看完题发现很简单就写了一发，然后WA了，发现读错题了。重新看题后和Szy讨论，然后又搞了个算法，调到将近两小时，我防出去、全防出去了啊，但这个CF它不讲武德，还搞了几发WA1和RE1，它也承认，是我本地先过样例的，我说婷婷，就丢给Szy重写，Szy花了10分钟左右搞定了，很快啊，并且发现Ebola的算法是假的……

在Ebola被L困住的时候，Szy和cy两人快速解决了A、D、H，然后cy被C卡住了，但是也在L过后的几分钟搞定了C

然后cy开始上J了，是个博弈题，但上机前没想到细节这么多，一上机，WA了几发，才发现这个题明显是有备而来，来骗、来偷袭我们几个未经世事的ACMer，搞了一个小时啊，终于调过去了

然后到点了，Ebola的精神状态差不多恢复了，接下了Szy的B题算法之后就开始上机，这个很快啊，就写完了，然后过了样例。但这个CF它又不讲武德，我交上去，又WA1了，逼我Custom Test，过了之后MLE34了。这时候离结束还有4分钟，我想不到到底是哪里错了，仔细检查之后，是因为我new的数组会爆掉。我大意了啊，没有算，然后自然就是传统码代码，替换、全部替换啊，还有10秒，按照传统ACM点到为止，已经是认栽了，但是很快啊，我在最后2秒交了，过了

我劝！CF评测机，耗子尾汁，不要搞本地过样例提交WA1的小聪明，ACM要以和为贵，不要再犯这种小聪明，小聪明，啊。谢谢朋友们！

== 个人总结 ==

Szy:个人代码能力有进步，但是自信心不足，看到cy在机上卡住的时候应该直接上G，后来补题从开始写到过也就40分钟，以后赛场上也要有信心上机.


== 题解 ==

A: 

B:考虑以两点为对角的矩形内部如果没有坏点，可以直接走过去，如果有坏点，则一定有一条最短路会贴着某个坏点的边过去，所以对坏点周边四个点各跑一遍单源最短路

C: 

D:

E:

F:

G:线段树维护哈希值，考虑超过65535的次数只有nq/65536次，暴力维护这些即可。

H:签到题

I:

J:

K:我们可以把节点分成3类，第一类出现在可以修改的一段前，第二类为可以修改，第三类在后面，考虑对于连续一段2，3类点可以挂在一个确定的1类节点上，对于连续一段3号节点，要么挂在值比它小1的节点上，要么在大1的上面，所以可以对可修改的一段，按大小排序，区间DP，F[I][J]表示从第I个到第J个的最小答案，F[I][J]=Min(f[i][k]+f[k][j]+cost),cost可以预处理出来。

L:考虑可以证明只会拆分程Pri的k次方，f[i][j]表示前i个质数拆出j的最优答案，多出来的1可以证明可以全部处理掉不会使答案减小，DP即可。

流水账

(by Ebola)开场都在做梦，傻逼Ebola先开了个L，看完题发现很简单就写了一发，然后WA了，发现读错题了。重新看题后和Szy讨论，然后又搞了个算法，调到将近两小时，我防出去、全防出去了啊，但这个CF它不讲武德，还搞了几发WA1和RE1，它也承认，是我本地先过样例的，我说婷婷，就丢给Szy重写，Szy花了10分钟左右搞定了，很快啊，并且发现Ebola的算法是假的……

在Ebola被L困住的时候，Szy和cy两人快速解决了A、D、H，然后cy被C卡住了，但是也在L过后的几分钟搞定了C

然后cy开始上J了，是个博弈题，但上机前没想到细节这么多，一上机，WA了几发，才发现这个题明显是有备而来，来骗、来偷袭我们几个未经世事的ACMer，搞了一个小时啊，终于调过去了

然后到点了，Ebola的精神状态差不多恢复了，接下了Szy的B题算法之后就开始上机，这个很快啊，就写完了，然后过了样例。但这个CF它又不讲武德，我交上去，又WA1了，逼我Custom Test，过了之后MLE34了。这时候离结束还有4分钟，我想不到到底是哪里错了，仔细检查之后，是因为我new的数组会爆掉。我大意了啊，没有算，然后自然就是传统码代码，替换、全部替换啊，还有10秒，按照传统ACM点到为止，已经是认栽了，但是很快啊，我在最后2秒交了，过了

我劝！CF评测机，耗子尾汁，不要搞本地过样例提交WA1的小聪明，ACM要以和为贵，不要再犯这种小聪明，小聪明，啊。谢谢朋友们！

个人总结

Szy:个人代码能力有进步，但是自信心不足，看到cy在机上卡住的时候应该直接上G，后来补题从开始写到过也就40分钟，以后赛场上也要有信心上机.

题解

A:

B:考虑以两点为对角的矩形内部如果没有坏点，可以直接走过去，如果有坏点，则一定有一条最短路会贴着某个坏点的边过去，所以对坏点周边四个点各跑一遍单源最短路

C:

D:

E:

F:

G:线段树维护哈希值，考虑超过65535的次数只有nq/65536次，暴力维护这些即可。

H:签到题

I:

J:

K:我们可以把节点分成3类，第一类出现在可以修改的一段前，第二类为可以修改，第三类在后面，考虑对于连续一段2，3类点可以挂在一个确定的1类节点上，对于连续一段3号节点，要么挂在值比它小1的节点上，要么在大1的上面，所以可以对可修改的一段，按大小排序，区间DP，F[I][J]表示从第I个到第J个的最小答案，F[I][J]=Min(f[i][k]+f[k][j]+cost),cost可以预处理出来。

L:考虑可以证明只会拆分程Pri的k次方，f[i][j]表示前i个质数拆出j的最优答案，多出来的1可以证明可以全部处理掉不会使答案减小，DP即可。

附加文件