2020-team8-1227

从 Trac 迁移的文章

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

原文章内容如下：

== Rank ==
[[Image(Standings.png,1000px)]] 

TYPE: contest

NAME: 2020 ICPC 济南

PLAT: win-pintia

MODE: online

TIME: 2020.12.27 11:00~16:00

TEAM: 你的林皇，无限张狂[詹哲远, 黄文翀, 陈逸]

RANK: 8/545 1.47%

SOLVE: 8/13

A 01:22:55

C 00:33:34

D 00:45:21

G 00:30:01

J 03:32:44(-2)

K 04:52:45(-2)

L 02:21:00

M 00:13:17 (-2)

== 流水账 ==


开场cy正序看题，Ebola倒着看，Szy从中间看，Ebola和cy讲了M的题意，发现是签到题,然后Ebola上机签M，WA了两发。Szy和cy讨论C的做法，Ebola跟榜，上机过了G。Szy上机写C的贪心。Ebola过了D。cy过了A。Szy有了L的做法，和cy讨论后，cy上机写L。三人一起想J的构造，最后Ebola上机莽了一发随机来划分01，本机测试构造成功率很高，调了两发然后过了。Szy给出K的真题意，cy先想了个dsu的写法，后来发现利用树的高度直接合并复杂度是对的而且可以不用离线，直接预处理。然后cy上机写K，在最后十分钟过了。期间Ebola和Szy分别想出了E和F的写法，但没时间写了。


== 个人总结 ==

Szy:本场Szy是演员，一开始看错K的题意，把题看难了，结果整个人前半场几乎没了，以后做不出来重新看一遍题目，同时寒假要提高代码能力了。

cy:中期有段时间很迷，开不出题，总的来说打的还可以。

== 题解 ==

A:答案的每一列方案独立，然后高斯消元求秩就可以计算方案数。

B:

C:3的相当于没有，先把1的和2的能和就和，然后把3个2可以花6的代价合，3个1可以花3的代价合

D:

E:先搞成一个留一个尾巴的菊花，然后把点按子树分配搞下去

F:先预处理Pair(i,i-1)的各自一个因数，然后对Cnt[x][y]++,枚举GCD(i,k)和GCD(i-1,k),套一个莫比乌斯反演应该可以了，因为数量不会很多

G:

H:我的做法，不知道对不对，F[I][J][K]表示I子树内，打了J个点，爬到最上面的没有被覆盖线段是爬到K的概率，然后提前预处理，G[i][j]，表示在i个点中，要打中K个不重复的点，期望打几次，然后DP

I:

J:我们随机过了，正解黑白染色，然后对于黑点前面为10，白点为01，这样黑黑和白白间没有边，然后对于每个白点其他全是1，自己编号是0，对于每个黑点除了相连白点为1以外其他都是0

K:对于每个点维护一个数组表示第I个最小可以是多少，然后暴力合并即可

L:考虑在哪里进位，然后预处理2^n下面100个位置就好了。

M:签到题

Rank

TYPE: contest

NAME: 2020 ICPC 济南

PLAT: win-pintia

MODE: online

TIME: 2020.12.27 11:00~16:00

TEAM: 你的林皇，无限张狂[詹哲远, 黄文翀, 陈逸]

RANK: 8/545 1.47%

SOLVE: 8/13

A 01:22:55

C 00:33:34

D 00:45:21

G 00:30:01

J 03:32:44(-2)

K 04:52:45(-2)

L 02:21:00

M 00:13:17 (-2)

流水账

开场cy正序看题，Ebola倒着看，Szy从中间看，Ebola和cy讲了M的题意，发现是签到题,然后Ebola上机签M，WA了两发。Szy和cy讨论C的做法，Ebola跟榜，上机过了G。Szy上机写C的贪心。Ebola过了D。cy过了A。Szy有了L的做法，和cy讨论后，cy上机写L。三人一起想J的构造，最后Ebola上机莽了一发随机来划分01，本机测试构造成功率很高，调了两发然后过了。Szy给出K的真题意，cy先想了个dsu的写法，后来发现利用树的高度直接合并复杂度是对的而且可以不用离线，直接预处理。然后cy上机写K，在最后十分钟过了。期间Ebola和Szy分别想出了E和F的写法，但没时间写了。

个人总结

Szy:本场Szy是演员，一开始看错K的题意，把题看难了，结果整个人前半场几乎没了，以后做不出来重新看一遍题目，同时寒假要提高代码能力了。

cy:中期有段时间很迷，开不出题，总的来说打的还可以。

题解

A:答案的每一列方案独立，然后高斯消元求秩就可以计算方案数。

B:

C:3的相当于没有，先把1的和2的能和就和，然后把3个2可以花6的代价合，3个1可以花3的代价合

D:

E:先搞成一个留一个尾巴的菊花，然后把点按子树分配搞下去

F:先预处理Pair(i,i-1)的各自一个因数，然后对Cnt[x][y]++,枚举GCD(i,k)和GCD(i-1,k),套一个莫比乌斯反演应该可以了，因为数量不会很多

G:

H:我的做法，不知道对不对，F[I][J][K]表示I子树内，打了J个点，爬到最上面的没有被覆盖线段是爬到K的概率，然后提前预处理，G[i][j]，表示在i个点中，要打中K个不重复的点，期望打几次，然后DP

I:

J:我们随机过了，正解黑白染色，然后对于黑点前面为10，白点为01，这样黑黑和白白间没有边，然后对于每个白点其他全是1，自己编号是0，对于每个黑点除了相连白点为1以外其他都是0

K:对于每个点维护一个数组表示第I个最小可以是多少，然后暴力合并即可

L:考虑在哪里进位，然后预处理2^n下面100个位置就好了。

M:签到题

附加文件