2020-team12-024

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]
[[Image(standing.png, 1000px)]]
== 惨痛教训 ==
以后一个人写挂以后，要果断换人写题。
== 题解 == 
A:应该是签到，然而whn表演了把图题读成树。
B:三分套三分，先算好起点到终点的合法张角，然后三分起点接到圆的位置和终点接到圆的位置，在圆上就每次走t是最优的。
C:赛时whn写爆搜挂了好久，赛后ctc很快就过了，就是大模拟广搜。
D:赛时ctc写半平面交挂了好久，赛后whn很快就过了，就是无脑三分。
E:
F:线段树维护同H题的内容，nlog^2n。比赛时没写。
G:枚举所有最短路，SPFA求最小需要去掉的点。因为爆搜最短路时没有判两个有没有联通挂了好几发。
H:签到，直接记当前后缀不同的最大公约数，数量是log级直接向后转移即可。
I:签到。
J:2^n*n^2状压dp，预处理一个按钮收集完金币到按下下一个按钮的最小花费，然后状压按钮的按没按过的情况，dp就行了，一开始没有前面的预处理，复杂度多一个n以为11亿能过5s，但机器太弱了，还给了一会卡常（无用功）。

[/wiki/2020-team12 返回]

惨痛教训

以后一个人写挂以后，要果断换人写题。

题解

A:应该是签到，然而whn表演了把图题读成树。

B:三分套三分，先算好起点到终点的合法张角，然后三分起点接到圆的位置和终点接到圆的位置，在圆上就每次走t是最优的。

C:赛时whn写爆搜挂了好久，赛后ctc很快就过了，就是大模拟广搜。

D:赛时ctc写半平面交挂了好久，赛后whn很快就过了，就是无脑三分。

E:

F:线段树维护同H题的内容，nlog^2n。比赛时没写。

G:枚举所有最短路，SPFA求最小需要去掉的点。因为爆搜最短路时没有判两个有没有联通挂了好几发。

H:签到，直接记当前后缀不同的最大公约数，数量是log级直接向后转移即可。

I:签到。

J:2n*n2状压dp，预处理一个按钮收集完金币到按下下一个按钮的最小花费，然后状压按钮的按没按过的情况，dp就行了，一开始没有前面的预处理，复杂度多一个n以为11亿能过5s，但机器太弱了，还给了一会卡常（无用功）。

附加文件