2021-team1-C04
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2021-team1 返回]
== 概述 ==
solved: 6/14 dirt: 45%
rank: 12
[[Image(2021-C04.png,700px)]]
== 流水账 ==
开场 Qza 去找题面最短的题目，Xqj 开 J。Qza 说 G 一定是个签到题但是自己不会，于是 Qza 和 Xqj 一起开了 J，发现是个判二分图然后求最小点覆盖的题。于是 Xqj 上机写 J。写到一半发现复杂度肯定过不了，Qza 果断认为 J 做法假了，于是去推 G，推了两次假式子后，Qza 终于在 55min 的时候签掉了 G。Xqj 觉得 J 不能就这么扔了，于是换了 Dinic 交了一发，果不其然地挂了。此时 Qza 觉得自己会 M 了，就上去写，结果做法假了，WA7，于是一边自闭一边想构造。而 Xqj 发现 I 好像很好做的样子，随便推了推发现自己会了，便上机签了 I，但由于代码上出了一点小问题，调了一会儿才过。Qza 决定请 Xqj 一起做 M。得知 M 的题意后，Xqj 没一会儿便得到了一个看起来很对的做法，Qza 便立刻上去写。本地测了最大值后，发现恰好卡满了题目给定的下限，遂觉得信心十足，一交果然 AC。此时二人回头又开始想 J，Qza 略微冷静了一下，发现两人思路想偏了，J 本来是个很水的 dfs，硬生生被两人做成了网络流。于是 Qza 立刻上机，花了 5min 终于签掉了 J。
此时全队罚时爆炸，二人又去开 D。写出 n^2^ 的 dp 式子后却没了优化的手段。后来 Xqj 想到了一个按位的贪心，便过掉了 D。两人又开了 C 和 N，Qza 宣称 C 是个 dp，但是终究没有想明白怎么 dp；而 N 二人一开始想了很多假做法，后来 Xqj 上了个厕所，突然就会 N 了。过掉 N 之后，二人便一直卡在 C 上，无法寸进。比赛结束前 10min 左右，Qza 有了 C 的大致做法，但是对需要减掉的数还没有一个清晰的思路，遂 gg。
== 总结 ==
Qza：还是太菜了，缺乏做题经验，很容易想偏导致 gg。
Csr：在家睡觉好舒服（逃
Xqj：
== 题解 ==
A: 据说是 FWT，但是还不会。大概是根据每一位的运算规则，给它安排一种我们熟悉的位运算，如或运算，然后可以 FWT。
B:
C：设 f[i] 表示以 i 结尾的满足条件的序列个数，则先令 f[i]=f[i-1]+f[i-2]+...+f[1]，然后考虑从中减去不合法的情况。对于以 i 结尾的序列，我们考虑其末尾三个元素为 y，y^i，i，则所有以 y 结尾的、满足条件的序列都被统计到、被以 y^i 结尾的合法序列中，进而进入以 i 为结尾的合法序列中，这部分应该被减去。所以我们枚举 y，如果 y<y^i<i，则从 f[i] 中减去由 y 产生的 f[y] 个不合法的答案。考虑这样的 y 满足什么条件，发现只需要保证 y<y^i<i 即可。考虑 y 的最高位，如果 i 的对应位为 0，则 y^i 比 i 大，不符合条件，否则必然符合 y<y^i<i 的条件。所以按照最高位的 1 维护一个 f 的和，每次计算 f[i] 时枚举 y 的最高位，满足条件就把这部分答案减掉。
D：dp，设 f[i] 表示以 i 结尾的序列的“安全值”的最大值，则朴素的转移是直接枚举上一个数是谁。考虑枚举 i 在与的过程中剩下来的最高的 1，对于每一位，维护这一位为 1 的最近的数的位置。因为与的结果若不是零，则一定存在最高位的 1，所以贪心取最近的即可。
E：
F：
G：特判 n 为奇数时无解这点就不说了。首先，对于任意一个存在完美匹配的树，树形确定时，匹配即确定。所以可以先完成匹配，后确定匹配的点对之间的连接关系。完成匹配这一步，可以先 n! 生成一个排列，然后相邻两个做匹配，则匹配间可以互换位置，有 (n/2)! 的重复；匹配内部可以互换位置，有 2^n/2^ 的重复。然后将每对匹配点作为点，生成一棵无根树，由 prufer 序列可知有 (n/2)^n/2-2^ 种树。然后考虑每对点之间的连接关系，发现每条边有四种连接方法，所以再乘个 4^n/2-1^。
H：
I：
J：
K：
L：
M：
N：[/wiki/2021-team1 返回]
概述
solved: 6/14 dirt: 45%
rank: 12
流水账
开场 Qza 去找题面最短的题目，Xqj 开 J。Qza 说 G 一定是个签到题但是自己不会，于是 Qza 和 Xqj 一起开了 J，发现是个判二分图然后求最小点覆盖的题。于是 Xqj 上机写 J。写到一半发现复杂度肯定过不了，Qza 果断认为 J 做法假了，于是去推 G，推了两次假式子后，Qza 终于在 55min 的时候签掉了 G。Xqj 觉得 J 不能就这么扔了，于是换了 Dinic 交了一发，果不其然地挂了。此时 Qza 觉得自己会 M 了，就上去写，结果做法假了，WA7，于是一边自闭一边想构造。而 Xqj 发现 I 好像很好做的样子，随便推了推发现自己会了，便上机签了 I，但由于代码上出了一点小问题，调了一会儿才过。Qza 决定请 Xqj 一起做 M。得知 M 的题意后，Xqj 没一会儿便得到了一个看起来很对的做法，Qza 便立刻上去写。本地测了最大值后，发现恰好卡满了题目给定的下限，遂觉得信心十足，一交果然 AC。此时二人回头又开始想 J，Qza 略微冷静了一下，发现两人思路想偏了，J 本来是个很水的 dfs，硬生生被两人做成了网络流。于是 Qza 立刻上机，花了 5min 终于签掉了 J。
此时全队罚时爆炸，二人又去开 D。写出 n2 的 dp 式子后却没了优化的手段。后来 Xqj 想到了一个按位的贪心，便过掉了 D。两人又开了 C 和 N，Qza 宣称 C 是个 dp，但是终究没有想明白怎么 dp；而 N 二人一开始想了很多假做法，后来 Xqj 上了个厕所，突然就会 N 了。过掉 N 之后，二人便一直卡在 C 上，无法寸进。比赛结束前 10min 左右，Qza 有了 C 的大致做法，但是对需要减掉的数还没有一个清晰的思路，遂 gg。
总结
Qza：还是太菜了，缺乏做题经验，很容易想偏导致 gg。
Csr：在家睡觉好舒服（逃
Xqj：
题解
A: 据说是 FWT，但是还不会。大概是根据每一位的运算规则，给它安排一种我们熟悉的位运算，如或运算，然后可以 FWT。
B:
C：设 f[i] 表示以 i 结尾的满足条件的序列个数，则先令 f[i]=f[i-1]+f[i-2]+...+f[1]，然后考虑从中减去不合法的情况。对于以 i 结尾的序列，我们考虑其末尾三个元素为 y，yi，i，则所有以 y 结尾的、满足条件的序列都被统计到、被以 yi 结尾的合法序列中，进而进入以 i 为结尾的合法序列中，这部分应该被减去。所以我们枚举 y，如果 y D：dp，设 f[i] 表示以 i 结尾的序列的“安全值”的最大值，则朴素的转移是直接枚举上一个数是谁。考虑枚举 i 在与的过程中剩下来的最高的 1，对于每一位，维护这一位为 1 的最近的数的位置。因为与的结果若不是零，则一定存在最高位的 1，所以贪心取最近的即可。 E： F： G：特判 n 为奇数时无解这点就不说了。首先，对于任意一个存在完美匹配的树，树形确定时，匹配即确定。所以可以先完成匹配，后确定匹配的点对之间的连接关系。完成匹配这一步，可以先 n! 生成一个排列，然后相邻两个做匹配，则匹配间可以互换位置，有 (n/2)! 的重复；匹配内部可以互换位置，有 2n/2 的重复。然后将每对匹配点作为点，生成一棵无根树，由 prufer 序列可知有 (n/2)n/2-2 种树。然后考虑每对点之间的连接关系，发现每条边有四种连接方法，所以再乘个 4n/2-1。 H： I： J： K： L： M： N：