2020-team1-074

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]

== 概述 ==

solved: 5/10  dirt: 29%

rank: 42

[[Image(Rank.png,800px)]]

== 总结 ==

Grammy开场签了H后对着J自认为出了个假做法，然后就一直在不断的修和debug中自闭了2个多小时，出来出了B的做法过了B后又回去J，最后做法被叉了。感觉头脑不是很清醒，在早期和队友缺乏交流，又是这么一个思路不清晰，且写起来非常麻烦的做法，非常的不行。



== 题解 ==

A: 

B: 对横纵的坐标建二分图，将点（x，y）看做左边的x连向右边的y的一条边，那么问题相当于问对于每条边，把它去掉后剩下的图是否能给每个边分配一边使每个点连的边都为偶数条。如果一个联通块里面有偶数条边，一定是有解的（证明考虑生成树上搞搞），所以就是看去掉每条边后剩余图的每个联通块内是不是都有偶数条边，tarjan缩边双后维护一下。

C: 有个性质是最优解一定是从大到小每次将一个家庭放在两边。dp，f[i][k]表示已经放了i个家庭，其中左边一共放了k个人，当前的距离。

D: 按x排序，每次取mid的x和所有点的y配对建新点，然后两边递归，总点数大致nlogn

E: 跑个暴力，打出n、m较小情况的方案，观察发现左斜线上方向必然相等，方案一定是左上角gcd*gcd大小的方格复制出来的，且可行性只和一行中向右的个数有关。

设g=gcd(n,m)

再根据小情况的答案猜出柿子是对于所有满足 0<k<g 且 gcd(nk,m(g-k))=k 的k，答案=C(g,k)求和

F: 

G: 对任意的质数p可以构造出一种p*p行p*p列共p*p*p个O的方案


p=3时如下
{{{
O..O..O..
.O..O..O.
..O..O..O
O...O...O
.O...OO..
..OO...O.
O....O.O.
.O.O....O
..O.O.O..
}}}

取p=13，保留前150行150列

H: 用线段树维护每个sg值最晚出现的位置，求出每个位置的sg

I: 倒着考虑，枚举起点后dfs

J: dp，f[i][j][k][m][s][t]表示dp完前i个人，选了j个人，有k条链，距离和为m，起点s终点t是否已经选定的方案数，转移考虑不选当前点，选当前点作为新链，加在链尾/头，作为s/t作为新链或加在链头/尾几种情况dp

[/wiki/2020-team1 返回]

概述

solved: 5/10 dirt: 29%

rank: 42

总结

Grammy开场签了H后对着J自认为出了个假做法，然后就一直在不断的修和debug中自闭了2个多小时，出来出了B的做法过了B后又回去J，最后做法被叉了。感觉头脑不是很清醒，在早期和队友缺乏交流，又是这么一个思路不清晰，且写起来非常麻烦的做法，非常的不行。

题解

A:

B: 对横纵的坐标建二分图，将点（x，y）看做左边的x连向右边的y的一条边，那么问题相当于问对于每条边，把它去掉后剩下的图是否能给每个边分配一边使每个点连的边都为偶数条。如果一个联通块里面有偶数条边，一定是有解的（证明考虑生成树上搞搞），所以就是看去掉每条边后剩余图的每个联通块内是不是都有偶数条边，tarjan缩边双后维护一下。

C: 有个性质是最优解一定是从大到小每次将一个家庭放在两边。dp，f[i][k]表示已经放了i个家庭，其中左边一共放了k个人，当前的距离。

D: 按x排序，每次取mid的x和所有点的y配对建新点，然后两边递归，总点数大致nlogn

E: 跑个暴力，打出n、m较小情况的方案，观察发现左斜线上方向必然相等，方案一定是左上角gcd*gcd大小的方格复制出来的，且可行性只和一行中向右的个数有关。

设g=gcd(n,m)

再根据小情况的答案猜出柿子是对于所有满足 0

F:

G: 对任意的质数p可以构造出一种p*p行p*p列共p*p*p个O的方案

p=3时如下

O..O..O..
.O..O..O.
..O..O..O
O...O...O
.O...OO..
..OO...O.
O....O.O.
.O.O....O
..O.O.O..

取p=13，保留前150行150列

H: 用线段树维护每个sg值最晚出现的位置，求出每个位置的sg

I: 倒着考虑，枚举起点后dfs

J: dp，f[i][j][k][m][s][t]表示dp完前i个人，选了j个人，有k条链，距离和为m，起点s终点t是否已经选定的方案数，转移考虑不选当前点，选当前点作为新链，加在链尾/头，作为s/t作为新链或加在链头/尾几种情况dp

附加文件