2021-team1-C01
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2021-team1 返回]
== 概述 ==
solved: 7/12 dirt: 42%
rank: 11
[[Image(2021-C01.png,700px)]]
== 流水账 ==
Qza 开场去开 L，想了半天没找出单调性。同时 Xqj 发现榜上显示 B 是签到，遂去开 B，然而被题意卡了。Qza 半天没想清楚 L，也跟着开 B 了。Qza 把 B 题意搞清楚后便骗 Xqj 上机写代码，自己去开 J 了。Xqj 签过 B 后，全队精神一振。之后 Csr 上机签 E 并且 WA 了，同一时间 Xqj 和 Qza 理解出了 C 的错误题意并且 Qza 成功给出了 C 的错误做法，于是 Xqj 又被骗上机写代码，而 Qza 立刻跑路，和 Csr 去想 E 的问题出在哪里。Xqj 写到一半时，Csr 找到了自己写挂的地方，将 Xqj 撵下机后成功签掉了 E，全队得到了精神鼓舞。
而当 Xqj 写完 C 时，Qza 惊悚地发现交 C 的 5 支队伍均 WA 了一发，遂开始怀疑 C 有什么奇奇怪怪的 Corner Case，与 Xqj 反复核对了好久，似乎没发现什么问题，遂交上去并收获了一发 WA，二人的精神因此陷入低谷，并且开始卡 C。而 Csy 很给力地开出了 G，故立刻上机写 G。期间 Qza 耐不住寂寞去嘴出了 J，并发现自己高消和线性基好像都不会的样子，于是又回来老老实实地想 C。不久后 Csr 过掉了 G，给全队提供了精神支持，与此同时 Xqj 灵光乍现，得到了 C 的正确题意，Qza 因此嘴出了 C 的几乎正确的做法，但因为想错了一个结论导致骗 Xqj 上机后又 WA 了一发。
无奈 Qza 又去开 J，并想到了一个绝妙的输出方案的方法，遂上机写 J。写到一半 Xqj 发现自己会 C 了，Qza 立刻退位让贤，Xqj 遂将卡了两人一个多小时的 C 过掉了。全队的精神再次振奋。而 Qza 用求线性基的方法一发过掉了 J，再一次提高了全队成员的精神。这时 Csr 和 Xqj 抽象出了 H 的题意并告知了 Qza，Qza 觉得 H 很有暴力枚举的味道，而 Csr 觉得 H 很分块，但后来可能被 Qza 卡掉了。这时 Xqj 给出了一种基于 bitset 位运算的枚举并上机写，Qza 因此才反应过来这是个裸的卷积，于是上机以极快的速度写了个过不了样例的 NTT。三人共同大眼瞪小眼地 de 出了 3 个 bug 后，终于一发过掉了 H。全队的精神再次一振。
然而，Qza 和 Xqj 二人又因为 L 陷入了江局，与此同时，Csr 去肝 A。可 Qza 和 Xqj 并不会决策单调性 dp，所以一直没搞出来 L，但却想出来一种看起来很对的三分。于是接下来的时间中，Qza 和 Csr 交替写 L 和 A，最终 Csr 不负众望过了样例后便过掉了 A，而 Qza 却在第 16 个点上 TLE 了。
将线段树改成单调栈后，Qza 又在第 16 个点上 WA 了，此时距离比赛结束只有 10 min的时间，三人一起紧张地 debug，可直到比赛结束还是无力回天。
最终，全队以饱满的精神取得了倒数第一的好成绩！
== 总结 ==
Qza：签到比较慢，尤其是被 C 的假题意卡的时间太久了，不然的话 L 虽然做不出来，但 K 应该能嘴出大概的做法。另外，对 H 这样的裸题见识不够，不能一眼出，导致做题速度下降，对 J 这样的题抽象不够快速，反反复复想了好久才确认下来就是线性基。
Csr：好耶！延续了前一天的梦游表现！快乐交题wawaawaTAT 手在键盘，脑在做梦。
Xqj：
== 题解 ==
A:
B:
C：将题目中所说的“apartment complex”称为关键点。根据题意，易知连接任意两个关键点的路径上的所有点均满足条件，对于这上面的任意一个点 p，和其余任意一个点 q，都能选这两个关键点之一作为 z，使得 d(p,z)>d(q,z)。所以只需要保留关键点和它们两两之间的路径上的点即可。选取任意一个关键点作为根，dfs 下去，只要某点子树内有其他的关键点，则该点对答案有贡献，否则该点连同整个子树都对答案没有贡献，需要拔除。
D：
E：
F：
G：
H：题意抽象一下，就是给定集合 A,B,C，求从 A,B,C 中选出各一个元素 a,b,c，满足 a+c=2b 的三元组 $(a,b,c)$ 的个数。集合元素在 [-30000,30000] 内，可以考虑枚举 b，然后求出有多少对 a,c 满足 a+c=2b，将它们看作系数，则 h_{2b}=\sum f_a*g_c，这明显是卷积式子。同一个集合内的元素不重复，所以 A 和 C 是个次数为 60000，系数为 0 或者 1 的多项式，卷起来后对于每一个 b，取出次数为 2b 的那一项加到答案里即可。注意下标统一加上 30000 避免出现负数。
I：
J：线性基：将第 i 行视作一个 n 位二进制数 xi，题意即求能否取出若干个 xi，使得它们的异或和为 100...00，010...00，001...00,...,000...10,000...01，并输出方案。由于至多有 500 个数，每个数至多 500 位，所以可以暴力逐位异或来求线性基。同时由于数的数量不多，所以可以用一个长度为 n 的 0/1 序列记录每个 xi 是否被选，两个方案合并本质上也是异或操作，所以写个结构体，重载一下异或操作，就很好求线性基并且输出方案了。当原序列 {xi} 不是线性无关组时，无解，直接输出 -1，这个可以在求线性基时同时判断。
K：
L：给出一个三分的反例：10 1 17 8 4 3 2 1 1 1 1，从这个例子里面可以看出 j 的选取并不是单峰的。[/wiki/2021-team1 返回]
概述
solved: 7/12 dirt: 42%
rank: 11
流水账
Qza 开场去开 L，想了半天没找出单调性。同时 Xqj 发现榜上显示 B 是签到，遂去开 B，然而被题意卡了。Qza 半天没想清楚 L，也跟着开 B 了。Qza 把 B 题意搞清楚后便骗 Xqj 上机写代码，自己去开 J 了。Xqj 签过 B 后，全队精神一振。之后 Csr 上机签 E 并且 WA 了，同一时间 Xqj 和 Qza 理解出了 C 的错误题意并且 Qza 成功给出了 C 的错误做法，于是 Xqj 又被骗上机写代码，而 Qza 立刻跑路，和 Csr 去想 E 的问题出在哪里。Xqj 写到一半时，Csr 找到了自己写挂的地方，将 Xqj 撵下机后成功签掉了 E，全队得到了精神鼓舞。
而当 Xqj 写完 C 时，Qza 惊悚地发现交 C 的 5 支队伍均 WA 了一发，遂开始怀疑 C 有什么奇奇怪怪的 Corner Case，与 Xqj 反复核对了好久，似乎没发现什么问题，遂交上去并收获了一发 WA，二人的精神因此陷入低谷，并且开始卡 C。而 Csy 很给力地开出了 G，故立刻上机写 G。期间 Qza 耐不住寂寞去嘴出了 J，并发现自己高消和线性基好像都不会的样子，于是又回来老老实实地想 C。不久后 Csr 过掉了 G，给全队提供了精神支持，与此同时 Xqj 灵光乍现，得到了 C 的正确题意，Qza 因此嘴出了 C 的几乎正确的做法，但因为想错了一个结论导致骗 Xqj 上机后又 WA 了一发。
无奈 Qza 又去开 J，并想到了一个绝妙的输出方案的方法，遂上机写 J。写到一半 Xqj 发现自己会 C 了，Qza 立刻退位让贤，Xqj 遂将卡了两人一个多小时的 C 过掉了。全队的精神再次振奋。而 Qza 用求线性基的方法一发过掉了 J，再一次提高了全队成员的精神。这时 Csr 和 Xqj 抽象出了 H 的题意并告知了 Qza，Qza 觉得 H 很有暴力枚举的味道，而 Csr 觉得 H 很分块，但后来可能被 Qza 卡掉了。这时 Xqj 给出了一种基于 bitset 位运算的枚举并上机写，Qza 因此才反应过来这是个裸的卷积，于是上机以极快的速度写了个过不了样例的 NTT。三人共同大眼瞪小眼地 de 出了 3 个 bug 后，终于一发过掉了 H。全队的精神再次一振。
然而，Qza 和 Xqj 二人又因为 L 陷入了江局，与此同时，Csr 去肝 A。可 Qza 和 Xqj 并不会决策单调性 dp，所以一直没搞出来 L，但却想出来一种看起来很对的三分。于是接下来的时间中，Qza 和 Csr 交替写 L 和 A，最终 Csr 不负众望过了样例后便过掉了 A，而 Qza 却在第 16 个点上 TLE 了。
将线段树改成单调栈后，Qza 又在第 16 个点上 WA 了，此时距离比赛结束只有 10 min的时间，三人一起紧张地 debug，可直到比赛结束还是无力回天。
最终，全队以饱满的精神取得了倒数第一的好成绩！
总结
Qza：签到比较慢，尤其是被 C 的假题意卡的时间太久了，不然的话 L 虽然做不出来，但 K 应该能嘴出大概的做法。另外，对 H 这样的裸题见识不够，不能一眼出，导致做题速度下降，对 J 这样的题抽象不够快速，反反复复想了好久才确认下来就是线性基。
Csr：好耶！延续了前一天的梦游表现！快乐交题wawaawaTAT 手在键盘，脑在做梦。
Xqj：
题解
A:
B:
C：将题目中所说的“apartment complex”称为关键点。根据题意，易知连接任意两个关键点的路径上的所有点均满足条件，对于这上面的任意一个点 p，和其余任意一个点 q，都能选这两个关键点之一作为 z，使得 d(p,z)>d(q,z)。所以只需要保留关键点和它们两两之间的路径上的点即可。选取任意一个关键点作为根，dfs 下去，只要某点子树内有其他的关键点，则该点对答案有贡献，否则该点连同整个子树都对答案没有贡献，需要拔除。
D：
E：
F：
G：
H：题意抽象一下，就是给定集合 A,B,C，求从 A,B,C 中选出各一个元素 a,b,c，满足 a+c=2b 的三元组 $(a,b,c)$ 的个数。集合元素在 [-30000,30000] 内，可以考虑枚举 b，然后求出有多少对 a,c 满足 a+c=2b，将它们看作系数，则 h_{2b}=\sum f_a*g_c，这明显是卷积式子。同一个集合内的元素不重复，所以 A 和 C 是个次数为 60000，系数为 0 或者 1 的多项式，卷起来后对于每一个 b，取出次数为 2b 的那一项加到答案里即可。注意下标统一加上 30000 避免出现负数。
I：
J：线性基：将第 i 行视作一个 n 位二进制数 xi，题意即求能否取出若干个 xi，使得它们的异或和为 100...00，010...00，001...00,...,000...10,000...01，并输出方案。由于至多有 500 个数，每个数至多 500 位，所以可以暴力逐位异或来求线性基。同时由于数的数量不多，所以可以用一个长度为 n 的 0/1 序列记录每个 xi 是否被选，两个方案合并本质上也是异或操作，所以写个结构体，重载一下异或操作，就很好求线性基并且输出方案了。当原序列 {xi} 不是线性无关组时，无解，直接输出 -1，这个可以在求线性基时同时判断。
K：
L：给出一个三分的反例：10 1 17 8 4 3 2 1 1 1 1，从这个例子里面可以看出 j 的选取并不是单峰的。
附加文件
- 2021-C01.png by QwQza