2019-team321/C008

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(Standings.png,500px)]]

== 流水账 ==

G 题 zkx 和 yay 想了假做法，写出来发现过不了样例，就扔了，后面才做出来。

F 题猜了假结论，写了一个很大的几何，浪费了很多时间。

最后一小时决定做 I，但可能如果做 K 和 E 的话就都做出来了。

== 总结 ==

=== zkx ===

1. 求极值的几何题用三分或者二分哪怕不是复杂度最优正解，也往往很靠谱。

2. 在有多个选择的时候，最后一个小时应该慎重考虑做哪个题。

3. 对于猜了结论的题，尽可能地自己去hack 一下结论，有条件的话玩一下样例。

=== yay ===

1. 今天吸取了之前的教训，读完题之后理解更清晰了，而且也先看完了负责的题目。

2. 猜结论有时是必要的，但要认真验证正确性，在没有可以说明不正确的因素后再相信它。如果猜错代价很高的话，需要更谨慎。

3. 正确性第一，速度第二，相互讨论的时候自己也要好好确认和理解。

=== ypl ===

==== 策略 ====

1. 和单打状态有很大差距，因为人一多我就想躺赢。如果认真打的话，每开始连续读一些题、每开始想一道题、每开始写一道题、每开始跟队友讨论、每开始帮队友调试的时候，记得观察一下自己的状态，保持冷静和负责任的态度。

2. 如果没什么想法，就多给老板打工；如果想法多一点，需要时间，可以跟队友商量，看谁写。

3. J 题签到失败，贡献了一发 WA。
[[BR]]
题目无脑，也不要冲动，想清细节再写。
[[BR]]
另外写到一半如果发现实现细节出了大问题，退下来不要写，想清细节再写，哪怕当时没有人在写题，哪怕队友说反正现在没人写你先坐那，也跟队友换个位置。

==== 题目 ====

E：
[[BR]]
问题一：给定一张 n 个点 m 条边的图，选择若干条边使得每个点的度数的 mod 2 = c[i]，求方案数。
[[BR]]
问题二：给定 m 个 n 维向量 (0, 0, 0, ..., 1, 0, 0, ..., 1, 0, 0, ..., 0)，求这些向量的基有多少种。
[[BR]]
两个问题是等价的。对于问题一，分每个连通块讨论，若某个连通块 sum % 2 = 1，则无解，否则任意构建生成树，对任意非树边的选法，树边都有对应选法，通过树形 DP 确定。对于问题二，这些向量的线性基就是任意一棵生成树，也就是个生成树计数的问题而已。
[[BR]]
那么可以出题了。比如 n 个点的带标号一笔画图计数，再比如 n 个点的无标号一笔画图计数。

G：交换尽可能少的次数，使序列先升后降。

I：
[[BR]]
1, 删除某一个元素、其余保留、维护结构的分治套路。
[[BR]]
2. 给定若干个 m 维的 01 向量的基，现在给定一个向量 x，分别问将每一维反转得到的新向量 x' 加入基中，新基的大小，可以在插入单独一个向量 x 的时间内解决，需要一点分析能力。

流水账

G 题 zkx 和 yay 想了假做法，写出来发现过不了样例，就扔了，后面才做出来。

F 题猜了假结论，写了一个很大的几何，浪费了很多时间。

最后一小时决定做 I，但可能如果做 K 和 E 的话就都做出来了。

总结

zkx

1. 求极值的几何题用三分或者二分哪怕不是复杂度最优正解，也往往很靠谱。

2. 在有多个选择的时候，最后一个小时应该慎重考虑做哪个题。

3. 对于猜了结论的题，尽可能地自己去hack 一下结论，有条件的话玩一下样例。

yay

1. 今天吸取了之前的教训，读完题之后理解更清晰了，而且也先看完了负责的题目。

2. 猜结论有时是必要的，但要认真验证正确性，在没有可以说明不正确的因素后再相信它。如果猜错代价很高的话，需要更谨慎。

3. 正确性第一，速度第二，相互讨论的时候自己也要好好确认和理解。

ypl

策略

1. 和单打状态有很大差距，因为人一多我就想躺赢。如果认真打的话，每开始连续读一些题、每开始想一道题、每开始写一道题、每开始跟队友讨论、每开始帮队友调试的时候，记得观察一下自己的状态，保持冷静和负责任的态度。

2. 如果没什么想法，就多给老板打工；如果想法多一点，需要时间，可以跟队友商量，看谁写。

3. J 题签到失败，贡献了一发 WA。

题目无脑，也不要冲动，想清细节再写。

另外写到一半如果发现实现细节出了大问题，退下来不要写，想清细节再写，哪怕当时没有人在写题，哪怕队友说反正现在没人写你先坐那，也跟队友换个位置。

题目

E：

问题一：给定一张 n 个点 m 条边的图，选择若干条边使得每个点的度数的 mod 2 = c[i]，求方案数。

问题二：给定 m 个 n 维向量 (0, 0, 0, ..., 1, 0, 0, ..., 1, 0, 0, ..., 0)，求这些向量的基有多少种。

两个问题是等价的。对于问题一，分每个连通块讨论，若某个连通块 sum % 2 = 1，则无解，否则任意构建生成树，对任意非树边的选法，树边都有对应选法，通过树形 DP 确定。对于问题二，这些向量的线性基就是任意一棵生成树，也就是个生成树计数的问题而已。

那么可以出题了。比如 n 个点的带标号一笔画图计数，再比如 n 个点的无标号一笔画图计数。

G：交换尽可能少的次数，使序列先升后降。

I：

1, 删除某一个元素、其余保留、维护结构的分治套路。

2. 给定若干个 m 维的 01 向量的基，现在给定一个向量 x，分别问将每一维反转得到的新向量 x' 加入基中，新基的大小，可以在插入单独一个向量 x 的时间内解决，需要一点分析能力。