2021-team1-C03
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2021-team1 返回]
== 概述 ==
solved: 7/10 dirt: 30%
rank: 10
[[Image(2021-C03.png,700px)]]
== 流水账 ==
开场 Qza 倒着开 M，Csr 正着开 A，Xqj 从中间开。Qza 觉得 M 是个签到题，并发现大家把 M 都 A 穿了，仔细确认了一下，便上机过了这道题。然后换 Csr 签 A，Qza 试图去开 I。然而 Qza 对 I 并没有什么想法，便和 Xqj 一起开 G，并迅速胡出了 G 的做法。趁 Csr 挂了一发去 debug，Qza 上机把 G 写了大半，此时 Xqj 去开 C。后来 Csr 找到问题并撵下 Qza，Qza 于是去给 Xqj 的 C 的做法捧场。Csr 迅速过掉了 A，便换 Qza 上去签 G。Qza 写完 G 没过样例，很快发现自己想错一个小问题，改了之后便迅速签掉了 G。立刻换 Xqj 上机签 C，而 Csr 此时已经读完了 B 并说这是个板子，然后去开其他题，Qza 并不会计算几何，于是也去开其他题。Csr 做出了 D 并等待机时；Qza 开 I 开了一年终于确定这是个不可做题。Xqj 签掉 C 后立刻换 Csr 写 D，而 Xqj 和 Qza 开始开 F 和 J。听完 F 的题意后 Qza 开始试图构造一个最优方案。构造了半天后，Qza 用贪心的思路猜了两个结论但是拿不出证明，Csr 过掉 D 后 Qza 猜了第三个结论，并试图验证，Csr 见机时空着便立刻骗 Xqj 上机写计算几何。Qza 脑部出了前两个结论的证明，而 Csr 尝试用数学的方法给出证明。Xqj 并不擅长半平面交，所以写出了一些 bug，Qza 趁 Xqj 调 bug 之际，抢过机时自己写 F。Xqj 找到问题后，上机改了代码并交了一发，发现挂掉了，就和 Csr 开了一会儿的 J。Csr 很快给出了 J 的一个貌似正确的做法，并和 Xqj 一起验证它的正确性。Qza 写完 F 后用一种未知的方法把自己卡掉了，遂怀疑贪心的正确性并开始想办法调整构造方法。Qza 觉得自己的 F 估计很难写出来便把机时分给了 Csr 的 J。Csr 不负众望很快过掉了 J，而 Qza 宣称自己有了更加正确的调整方法，便上机修改代码，但是被 Csr 的对拍卡掉了。Csr 写对拍时，Qza 开出了 E，并开始胡做法。Csr 拍掉 Qza 的 F 后，Qza 又上机修 bug。Csr 又很快开出了 K，并上机写，不久后便过了。
之后的机时便在 Qza 的 F 和 Xqj 的 B 之间反复横跳，每当 Qza 改掉一处 bug 时，Csr 就上机用对拍验证，然后 Qza 就又有了一个 bug。期间 Qza 发现 Csr 造出一组假数据，Csr 便开始研究自己的暴力有什么问题。于是 Qza 便动手写 E。写完 E 后还没有编译，Csr 便发现了暴力的一些问题，上机改了 bug 后，又拍出了 Qza 的一个 bug。于是 Qza 和 Csr 二人又开始了漫长的修 bug 之旅，期间 Xqj 发现自己的板子假了，但是改了之后还是不对。Csr 对拍中发现了 Qza 代码中缺少一个特判，加上之后交了一发，结果出人意料地过了 F。Qza 立刻上机编译 E。改掉一些 bug 后，E 过了样例，此时距离比赛结束仅有不到 10s，Qza 立刻交了一发，但很遗憾没有过。
== 总结 ==
Qza：一整场都在口胡。其实 F 一开始口胡的三个结论都是对的，但后来被卡了就以为是错的。反反复复搞了好久，最终换了另一种奇怪的姿势写了 F。赛后经 ljm 提点，发现自己有两个结论没猜出来，导致前面的结论理论依据不充足。M 和 G 签得速度还行，但后面的题基本就帮不上忙了；E 也想地很快，但是代码能力低下，没写出来。
Csr：今天前半场游戏体验不错！后半场有点挂机了TAT 本质还是签到题选手只会写水题555 后半场队友写了很久的F，我还剩一个小时多一点上手写暴力对拍，不到二十分钟的时候才知道队友想写啥，打算上机重写TAT 写了读入后第一个if语句，福至心灵去看了一眼队友的代码，果然没有corner case…其实应该早点去关注一下上机队友在写啥，还有加了corner case还过不了，十五分钟我并不觉得我能重写AC
Xqj：
== 题解 ==
A:
B:
C：易知：如果和为奇数，一定无解；和为偶数，无解的情况大概就是：存在一个很大的取不完数，即便每次取数都会从这个数上面取走 1，最终也无法取完这个数。于是方案就是：每次挑最大的两个数取，若最终只剩一个，则输出无解。事实上，无解的唯一情况就是：最大的数超过了所有数之和的一半。
D：
E：先将纵坐标缩一半，再整体逆时针转动 45°并根据需要放缩根号2倍。则所有 - 点都没用，删掉即可；所有 P 点的右下方一定都是 P 点；所有 N 点左上方一定没有 P 点。易知 impossible 一定产生于 N 点，所以先判是否 impossible，再寻找最优方案。判断 impossible 是个二维数点问题，扫描线+树状数组可以解决。取最少的 P 点是个贪心，从上到下取，每行取最左边的点，保证方案中最左边的点横坐标递减即可。
F：首先判掉 k 不为 m 的倍数的无解情况，然后有三个结论。第一个结论：若存在总和为 k 的方案，则一定存在期望较大的 k/m 个人打 m 分，剩余人的 n-k/m 人打 0 分的方案；证明：若期望打分 a<b 但 a 打出了 m，b 打出了 0，则它们俩互换后两个位置的打分结果不变，所以任意一种可行方案都会换成目标方案。第二个结论：打 0 分的那部分人一定是期望大的人先打分，打 m 分的那部分人一定是期望小的人先打分；证明：对于期望大的人 a 和 b，假设 a<b 但 b 在 a 前打分，设 b 在 i 处，a 在 j 处，i<j，且 i+1 到 j-1 是一段打 0 分的人。诶然后我不会了。
G：考虑枚举 1 和 3，设中间有 n 个 2，则这对儿 1、3 对答案的贡献为 2^n^-1。考虑只枚举 1，并将能与这个 1 共同产生贡献的 3 做为一个后缀和来统计。可以用前缀和 O(1) 得到 1 和 3 之间的 2 的个数，将 2 的个数带来的 2^n^ 的贡献放到 3 上并求后缀和，枚举到一个 1，则用 1 后面 3 的贡献之和除掉 1 前面的 2 产生的 2 的幂次的贡献，再减去后面 3 的个数，就是这个 1 的贡献。于是做法就是：预处理 2 的幂次和 2 的幂次的逆元，从前到后求 2 的前缀和，记为 sum2[i]=sum2[i-1]+(a[i]==2)；从后到前求 3 的贡献的后缀和以及 3 的后缀和，记为 sum3[i]=sum3[i+1]+(a[i]==3)*pow2[sum2[i]]，s3[i]=s3[i+1]+(a[i]==3)；最后从前到后统计 1 的贡献，贡献为 (a[i]==1)*(sum3[i]*invpow2[sum2[i]]-s3[i])。
H：
I：
J：
K：位数不同的地方肯定不需要改，所以从前到后找到第一个需要进位的地方，前面位置上的 1 不用改动，而本位以及之后的位不论怎么加减，都一定会向前一位进 1，所以最好的办法是将一个数变为 100...00 的形式，最高位的 1 即为进位的 1。这样另一个数加上来也不会产生进位。所以用 100...00 和两数的剩余位做个高精度减法，取较小的那个即可。
M：设第一个字符串里有 a 个 S，第二个字符串里有 b 个 S，则输出的字符串里有 a*b 个 S。[/wiki/2021-team1 返回]
概述
solved: 7/10 dirt: 30%
rank: 10
流水账
开场 Qza 倒着开 M，Csr 正着开 A，Xqj 从中间开。Qza 觉得 M 是个签到题，并发现大家把 M 都 A 穿了，仔细确认了一下，便上机过了这道题。然后换 Csr 签 A，Qza 试图去开 I。然而 Qza 对 I 并没有什么想法，便和 Xqj 一起开 G，并迅速胡出了 G 的做法。趁 Csr 挂了一发去 debug，Qza 上机把 G 写了大半，此时 Xqj 去开 C。后来 Csr 找到问题并撵下 Qza，Qza 于是去给 Xqj 的 C 的做法捧场。Csr 迅速过掉了 A，便换 Qza 上去签 G。Qza 写完 G 没过样例，很快发现自己想错一个小问题，改了之后便迅速签掉了 G。立刻换 Xqj 上机签 C，而 Csr 此时已经读完了 B 并说这是个板子，然后去开其他题，Qza 并不会计算几何，于是也去开其他题。Csr 做出了 D 并等待机时；Qza 开 I 开了一年终于确定这是个不可做题。Xqj 签掉 C 后立刻换 Csr 写 D，而 Xqj 和 Qza 开始开 F 和 J。听完 F 的题意后 Qza 开始试图构造一个最优方案。构造了半天后，Qza 用贪心的思路猜了两个结论但是拿不出证明，Csr 过掉 D 后 Qza 猜了第三个结论，并试图验证，Csr 见机时空着便立刻骗 Xqj 上机写计算几何。Qza 脑部出了前两个结论的证明，而 Csr 尝试用数学的方法给出证明。Xqj 并不擅长半平面交，所以写出了一些 bug，Qza 趁 Xqj 调 bug 之际，抢过机时自己写 F。Xqj 找到问题后，上机改了代码并交了一发，发现挂掉了，就和 Csr 开了一会儿的 J。Csr 很快给出了 J 的一个貌似正确的做法，并和 Xqj 一起验证它的正确性。Qza 写完 F 后用一种未知的方法把自己卡掉了，遂怀疑贪心的正确性并开始想办法调整构造方法。Qza 觉得自己的 F 估计很难写出来便把机时分给了 Csr 的 J。Csr 不负众望很快过掉了 J，而 Qza 宣称自己有了更加正确的调整方法，便上机修改代码，但是被 Csr 的对拍卡掉了。Csr 写对拍时，Qza 开出了 E，并开始胡做法。Csr 拍掉 Qza 的 F 后，Qza 又上机修 bug。Csr 又很快开出了 K，并上机写，不久后便过了。
之后的机时便在 Qza 的 F 和 Xqj 的 B 之间反复横跳，每当 Qza 改掉一处 bug 时，Csr 就上机用对拍验证，然后 Qza 就又有了一个 bug。期间 Qza 发现 Csr 造出一组假数据，Csr 便开始研究自己的暴力有什么问题。于是 Qza 便动手写 E。写完 E 后还没有编译，Csr 便发现了暴力的一些问题，上机改了 bug 后，又拍出了 Qza 的一个 bug。于是 Qza 和 Csr 二人又开始了漫长的修 bug 之旅，期间 Xqj 发现自己的板子假了，但是改了之后还是不对。Csr 对拍中发现了 Qza 代码中缺少一个特判，加上之后交了一发，结果出人意料地过了 F。Qza 立刻上机编译 E。改掉一些 bug 后，E 过了样例，此时距离比赛结束仅有不到 10s，Qza 立刻交了一发，但很遗憾没有过。
总结
Qza：一整场都在口胡。其实 F 一开始口胡的三个结论都是对的，但后来被卡了就以为是错的。反反复复搞了好久，最终换了另一种奇怪的姿势写了 F。赛后经 ljm 提点，发现自己有两个结论没猜出来，导致前面的结论理论依据不充足。M 和 G 签得速度还行，但后面的题基本就帮不上忙了；E 也想地很快，但是代码能力低下，没写出来。
Csr：今天前半场游戏体验不错！后半场有点挂机了TAT 本质还是签到题选手只会写水题555 后半场队友写了很久的F，我还剩一个小时多一点上手写暴力对拍，不到二十分钟的时候才知道队友想写啥，打算上机重写TAT 写了读入后第一个if语句，福至心灵去看了一眼队友的代码，果然没有corner case…其实应该早点去关注一下上机队友在写啥，还有加了corner case还过不了，十五分钟我并不觉得我能重写AC
Xqj：
题解
A:
B:
C：易知：如果和为奇数，一定无解；和为偶数，无解的情况大概就是：存在一个很大的取不完数，即便每次取数都会从这个数上面取走 1，最终也无法取完这个数。于是方案就是：每次挑最大的两个数取，若最终只剩一个，则输出无解。事实上，无解的唯一情况就是：最大的数超过了所有数之和的一半。
D：
E：先将纵坐标缩一半，再整体逆时针转动 45°并根据需要放缩根号2倍。则所有 - 点都没用，删掉即可；所有 P 点的右下方一定都是 P 点；所有 N 点左上方一定没有 P 点。易知 impossible 一定产生于 N 点，所以先判是否 impossible，再寻找最优方案。判断 impossible 是个二维数点问题，扫描线+树状数组可以解决。取最少的 P 点是个贪心，从上到下取，每行取最左边的点，保证方案中最左边的点横坐标递减即可。
F：首先判掉 k 不为 m 的倍数的无解情况，然后有三个结论。第一个结论：若存在总和为 k 的方案，则一定存在期望较大的 k/m 个人打 m 分，剩余人的 n-k/m 人打 0 分的方案；证明：若期望打分 a
G：考虑枚举 1 和 3，设中间有 n 个 2，则这对儿 1、3 对答案的贡献为 2n-1。考虑只枚举 1，并将能与这个 1 共同产生贡献的 3 做为一个后缀和来统计。可以用前缀和 O(1) 得到 1 和 3 之间的 2 的个数，将 2 的个数带来的 2n 的贡献放到 3 上并求后缀和，枚举到一个 1，则用 1 后面 3 的贡献之和除掉 1 前面的 2 产生的 2 的幂次的贡献，再减去后面 3 的个数，就是这个 1 的贡献。于是做法就是：预处理 2 的幂次和 2 的幂次的逆元，从前到后求 2 的前缀和，记为 sum2[i]=sum2[i-1]+(a[i]==2)；从后到前求 3 的贡献的后缀和以及 3 的后缀和，记为 sum3[i]=sum3[i+1]+(a[i]==3)*pow2[sum2[i]]，s3[i]=s3[i+1]+(a[i]==3)；最后从前到后统计 1 的贡献，贡献为 (a[i]==1)*(sum3[i]*invpow2[sum2[i]]-s3[i])。
H：
I：
J：
K：位数不同的地方肯定不需要改，所以从前到后找到第一个需要进位的地方，前面位置上的 1 不用改动，而本位以及之后的位不论怎么加减，都一定会向前一位进 1，所以最好的办法是将一个数变为 100...00 的形式，最高位的 1 即为进位的 1。这样另一个数加上来也不会产生进位。所以用 100...00 和两数的剩余位做个高精度减法，取较小的那个即可。
M：设第一个字符串里有 a 个 S，第二个字符串里有 b 个 S，则输出的字符串里有 a*b 个 S。