2020-team8-1220

从 Trac 迁移的文章

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

原文章内容如下：

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

开场cy签了G,然后和szy讨论出C的写法并上机写，szy表示会了B并很快过了，cy继续写C然后过了，szy上机写D然后WA了，cy过了I后帮szy一起看D给出一组corner case, szy改过之后A了，接着szy看了cy一直看不懂题意的M，然后让cy写完过了，szy推了E的式子，发现式子假了之后重新推并过了，然后cy开H，szy开L。cy过了H，然后和szy讨论L，cy猜了个结论然后szy证明了是对的，然后cy上机过了L。最后一小时，在F和K中选择了szy擅长的dp题F，推出状态后cy上机写，最终T了。（赛后也一直刚好过不了最大的数据，题解的写法利用区间大小的顺序确实状态更少一点）

== 个人总结 ==
Szy:打的挺好，wa的时候多考虑corner case，而不是随便乱冲

cy：读题能力要加强

== 题解 ==

A:

B:反转和原来地图答案一样，如果两张图不一样的多于nm/2则搞成跟反转的一样

C:数位DP

D:如果在中间相遇解方程，否则考虑一个人走完，一个人走中间加自己，或者互相走到对面的终点(Szy漏了这种情况)

E:考虑1的位置只能在1-k，如果在第J个那么答案就是C(j-1,i-1)*(j-1)!*f(i-j),发现可以前缀和优化，就可以过了

F:DP，一开始想的是状压记录每个位置往右的最远距离，状态太多T了，可以从区间权值从大往小考虑，考虑之前覆盖过的区间贡献都算过了，没覆盖的区间随l的递增r一定不减(如果l,r没覆盖，(l+1,r)不可能被覆盖)，所以这样状态就是C(2n,n)的了，可以大幅减小状态

G:

H:先分别排序，考虑每种选择的必然是连续选，即枚举开头，一共只有n种选法，再计算怎么转更优即可。

I:分别计算每一条线段和圆弧的贡献即可

J:

K:

L:如果起点和终点互质可以直接跑过去，不然只会经过一个中间点，且第一步必然互质，否则一定有更小答案，画画图可以看出来的，这样的话枚举第一步的x，从对角线网上找到第一个跟x互质的数(肯定不可能找很多次，不可能连续一坨都跟x不互质)，求答案取min即可.

M:签到题

流水账

开场cy签了G,然后和szy讨论出C的写法并上机写，szy表示会了B并很快过了，cy继续写C然后过了，szy上机写D然后WA了，cy过了I后帮szy一起看D给出一组corner case, szy改过之后A了，接着szy看了cy一直看不懂题意的M，然后让cy写完过了，szy推了E的式子，发现式子假了之后重新推并过了，然后cy开H，szy开L。cy过了H，然后和szy讨论L，cy猜了个结论然后szy证明了是对的，然后cy上机过了L。最后一小时，在F和K中选择了szy擅长的dp题F，推出状态后cy上机写，最终T了。（赛后也一直刚好过不了最大的数据，题解的写法利用区间大小的顺序确实状态更少一点）

个人总结

Szy:打的挺好，wa的时候多考虑corner case，而不是随便乱冲

cy：读题能力要加强

题解

A:

B:反转和原来地图答案一样，如果两张图不一样的多于nm/2则搞成跟反转的一样

C:数位DP

D:如果在中间相遇解方程，否则考虑一个人走完，一个人走中间加自己，或者互相走到对面的终点(Szy漏了这种情况)

E:考虑1的位置只能在1-k，如果在第J个那么答案就是C(j-1,i-1)*(j-1)!*f(i-j),发现可以前缀和优化，就可以过了

F:DP，一开始想的是状压记录每个位置往右的最远距离，状态太多T了，可以从区间权值从大往小考虑，考虑之前覆盖过的区间贡献都算过了，没覆盖的区间随l的递增r一定不减(如果l,r没覆盖，(l+1,r)不可能被覆盖)，所以这样状态就是C(2n,n)的了，可以大幅减小状态

G:

H:先分别排序，考虑每种选择的必然是连续选，即枚举开头，一共只有n种选法，再计算怎么转更优即可。

I:分别计算每一条线段和圆弧的贡献即可

J:

K:

L:如果起点和终点互质可以直接跑过去，不然只会经过一个中间点，且第一步必然互质，否则一定有更小答案，画画图可以看出来的，这样的话枚举第一步的x，从对角线网上找到第一个跟x互质的数(肯定不可能找很多次，不可能连续一坨都跟x不互质)，求答案取min即可.

M:签到题

附加文件