2020-team0x06-C02
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2020-team0x06 返回]
[[Image(Standings.png, 1000px)]][[BR]][[Image(Submissions.png, 600px)]]
== Statistics ==
* TYPE: Contest
* NAME: 2020 - CCPC - Mianyang
* PLAT: Oms-pintia
* MODE: Online
* TIME: 2020.11.01 09:00-14:00
* TEAM: Refrain[ntwbvdbl_oe, Orange_User, functionendless]
* RANK: 8/268(Au)
* SOLVE: 7/12(1157)
* B-04:12(-1)
* D-00:12
* G-01:22(-2)
* H-03:58(-1)
* J-01:22(-1)
* K-01:45(-1)
* L-03:06(-4)
* ATTEMPTING
* C
== Comp ==
* 一本没有打开过的Claris板子
* 一个中场掉线黑屏但是没有发现的后置摄像头
* 三位发挥稳定的参赛选手
== Day1 ==
fx一上来就找到签到题D并喂给czyh，由于忘调语言CE了一发，'''D1Y12'''。暂时没有可做题，czyh上机对着G大力打表，lmh和fx讨论了一会K，剩一种hard情况不好解决，先放着。fx给lmh讲了J的题意，lmh胡了个大力分块做法，fx觉得太暴力太复杂并表示听不懂。lmh给fx讲了讲E的'''假题意'''，两人推了一半发现不会做，决定先看其他题。
czyh在机上推了两个结论，但是都WA了，lmh觉得J可写，换czyh下来。czyh和fx讨论了一会G，然后fx去想L了。lmh写完获得RE，czyh上机，换了个打表姿势并成功找到规律，'''G2Y82'''。fx给lmh讲了讲L的做法，lmh觉得没啥问题。lmh觉得除了数组开小以外没什么修改余地了，抱着TLE让自己死心的想法试了一发，'''J2Y82'''，(1.8s/2s卡过，本机6s)。fx上机写L，czyh从lmh手上接过想了一半的K，两人一致觉得这种情况下答案不会很大，于是czyh上机打表验证了结论，写了个小范围暴力，提交WA了，lmh过来一眼看出'''czyh输出又没换行'''，'''K2Y105'''。
fx20分钟写完L，莽了一发WA。lmh重新捡起E，想了很久还是不会，又和czyh讨论了H，czyh觉得是分类讨论，lmh想了想也没有其他做法，然后lmh开始自闭。期间fx一直在机上写写调调，但是一直在WA，经历了对拍和多次调错以及部分重构才艰难地过了，'''L5Y186'''。czyh开出B上机写，fx独立把B秒了并感叹就不应该上机写题，并帮czyh核对方程，核对边界，提交WA。lmh写了两页纸的分类讨论，上机敲了七八个if，获得WA，打印代码发现少加了一个cornercase，'''H2Y238'''，czyh对着lmh小黄鸭调试，fx造了一组数据卡掉了czyh的代码，czyh改完'''B2Y252'''。
三人看了看榜，觉得稳Au了，但不想挂机争取再开一题。lmh捡起E继续想继续不会，又想了想C，fx和czyh想了想I不会，直到fx遇到C并秒了，czyh上机写，可惜没写完。[[BR]]
赛后，lmh看了看题解[[BR]]
lmh: 我E题题意假了。。。[[BR]]
fx：我就不应该上机写题。
== Conclusion ==
=== ntwbvdbl_oe ===
* 正如cjb所说，很多题不同做法和写法在过题效率上差别巨大，这个L题我们由于写的不好花了1h+调试，但最快的队伍17min就能秒掉。这个H题机下推了非常非常久，占用机时只有10min，如果适当打表找规律能省去很多不必要的推导时间。
* 对于一道题，想出来和写出来是有差距的，对于代码能力不强的我们，一定要想好实现细节后再上机，切忌盲目防止空机。空机时用来打表，写对拍，提前写check都是不错的选择，同样在机时紧张的情况下可以一人写代码，一人在旁边盯着。这场比赛后面的题细节都不少，这个C题实际上再给10min也不能写对，因为当时我们的做法还有很多细节没考虑到。
* 读题真的真的很重要，每道题要有两个人不交流的情况下独立读完题，否则赛后发现读错题是非常难受的，E题读错了，C题读晚了，如果前面省出时间是有机会过的
=== Orange_User ===
* 打表真好玩
* 多组数据真恶心
* 奇怪的特判真麻烦
=== functionendless ===
* 一个想题型选手在机上那么长时间我也是醉了.
* 比上次比赛还是好那么一点的，和队友的讨论比较到位
== Solutions ==
A:
B: 考虑一个块影响两个下标的位置，记录是否达成高度并进行DP，转移相对复杂，注意首位的特判
C: 定义trA为未知trie，trB为输入构建的trie，trB中一个子树的值如果全部相同则只保留子树的根。trB中u点的孩子有一次讲权值缩到u的机会，条件是u无权值，注意多孩子重复权值则必选，若有多个被重复权值则无解。构造完之后遍历一遍查看是否有重复权值即可
D: 签到
E:
F:
G: 发现0号卡对操作次数的贡献为其数量-（（其他卡的数量）==0），对答案的贡献可用0/1表示，然后3号卡对答案无贡献，1，2号卡对答案的贡献打表可知有规律，但最终答案不能把两者直接相加，需要对1号卡、2号卡、0号卡的数量打表再找一边规律。
H: 大力分类讨论，注意0的情况
I:
J: 垃圾做法：大力分块，ti大于block的，周期数小于n/block，直接在线段树上做，ti小于block的数量不多，在枚举m时暴力枚举n/block个周期，总复杂度O(n\sqrt{nlogn})
正解：不同的周期数是nlogn级别的(调和级数)，并查集区间染色
K: n&1 -> 1 ; n=4k -> 2 ; n=4k+2 : 在n/3除小范围暴力
L: 进位，使每一位只剩下0/1/2个选择，结合二进制位的性质DP即可，注意离散化技巧[/wiki/2020-team0x06 返回]
Statistics
- TYPE: Contest
- NAME: 2020 - CCPC - Mianyang
- PLAT: Oms-pintia
- MODE: Online
- TIME: 2020.11.01 09:00-14:00
- TEAM: Refrain[ntwbvdbl_oe, Orange_User, functionendless]
- RANK: 8/268(Au)
- SOLVE: 7/12(1157)
- B-04:12(-1)
- D-00:12
- G-01:22(-2)
- H-03:58(-1)
- J-01:22(-1)
- K-01:45(-1)
- L-03:06(-4)
- ATTEMPTING
- C
Comp
- 一本没有打开过的Claris板子
- 一个中场掉线黑屏但是没有发现的后置摄像头
- 三位发挥稳定的参赛选手
Day1
fx一上来就找到签到题D并喂给czyh，由于忘调语言CE了一发，D1Y12。暂时没有可做题，czyh上机对着G大力打表，lmh和fx讨论了一会K，剩一种hard情况不好解决，先放着。fx给lmh讲了J的题意，lmh胡了个大力分块做法，fx觉得太暴力太复杂并表示听不懂。lmh给fx讲了讲E的假题意，两人推了一半发现不会做，决定先看其他题。
czyh在机上推了两个结论，但是都WA了，lmh觉得J可写，换czyh下来。czyh和fx讨论了一会G，然后fx去想L了。lmh写完获得RE，czyh上机，换了个打表姿势并成功找到规律，G2Y82。fx给lmh讲了讲L的做法，lmh觉得没啥问题。lmh觉得除了数组开小以外没什么修改余地了，抱着TLE让自己死心的想法试了一发，J2Y82，(1.8s/2s卡过，本机6s)。fx上机写L，czyh从lmh手上接过想了一半的K，两人一致觉得这种情况下答案不会很大，于是czyh上机打表验证了结论，写了个小范围暴力，提交WA了，lmh过来一眼看出czyh输出又没换行，K2Y105。
fx20分钟写完L，莽了一发WA。lmh重新捡起E，想了很久还是不会，又和czyh讨论了H，czyh觉得是分类讨论，lmh想了想也没有其他做法，然后lmh开始自闭。期间fx一直在机上写写调调，但是一直在WA，经历了对拍和多次调错以及部分重构才艰难地过了，L5Y186。czyh开出B上机写，fx独立把B秒了并感叹就不应该上机写题，并帮czyh核对方程，核对边界，提交WA。lmh写了两页纸的分类讨论，上机敲了七八个if，获得WA，打印代码发现少加了一个cornercase，H2Y238，czyh对着lmh小黄鸭调试，fx造了一组数据卡掉了czyh的代码，czyh改完B2Y252。
三人看了看榜，觉得稳Au了，但不想挂机争取再开一题。lmh捡起E继续想继续不会，又想了想C，fx和czyh想了想I不会，直到fx遇到C并秒了，czyh上机写，可惜没写完。
赛后，lmh看了看题解
lmh: 我E题题意假了。。。
fx：我就不应该上机写题。
Conclusion
ntwbvdbl_oe
- 正如cjb所说，很多题不同做法和写法在过题效率上差别巨大，这个L题我们由于写的不好花了1h+调试，但最快的队伍17min就能秒掉。这个H题机下推了非常非常久，占用机时只有10min，如果适当打表找规律能省去很多不必要的推导时间。
- 对于一道题，想出来和写出来是有差距的，对于代码能力不强的我们，一定要想好实现细节后再上机，切忌盲目防止空机。空机时用来打表，写对拍，提前写check都是不错的选择，同样在机时紧张的情况下可以一人写代码，一人在旁边盯着。这场比赛后面的题细节都不少，这个C题实际上再给10min也不能写对，因为当时我们的做法还有很多细节没考虑到。
- 读题真的真的很重要，每道题要有两个人不交流的情况下独立读完题，否则赛后发现读错题是非常难受的，E题读错了，C题读晚了，如果前面省出时间是有机会过的
Orange_User
- 打表真好玩
- 多组数据真恶心
- 奇怪的特判真麻烦
functionendless
- 一个想题型选手在机上那么长时间我也是醉了.
- 比上次比赛还是好那么一点的，和队友的讨论比较到位
Solutions
A:
B: 考虑一个块影响两个下标的位置，记录是否达成高度并进行DP，转移相对复杂，注意首位的特判
C: 定义trA为未知trie，trB为输入构建的trie，trB中一个子树的值如果全部相同则只保留子树的根。trB中u点的孩子有一次讲权值缩到u的机会，条件是u无权值，注意多孩子重复权值则必选，若有多个被重复权值则无解。构造完之后遍历一遍查看是否有重复权值即可
D: 签到
E:
F:
G: 发现0号卡对操作次数的贡献为其数量-（（其他卡的数量）==0），对答案的贡献可用0/1表示，然后3号卡对答案无贡献，1，2号卡对答案的贡献打表可知有规律，但最终答案不能把两者直接相加，需要对1号卡、2号卡、0号卡的数量打表再找一边规律。
H: 大力分类讨论，注意0的情况
I:
J: 垃圾做法：大力分块，ti大于block的，周期数小于n/block，直接在线段树上做，ti小于block的数量不多，在枚举m时暴力枚举n/block个周期，总复杂度O(n\sqrt{nlogn})
正解：不同的周期数是nlogn级别的(调和级数)，并查集区间染色
K: n&1 -> 1 ; n=4k -> 2 ; n=4k+2 : 在n/3除小范围暴力
L: 进位，使每一位只剩下0/1/2个选择，结合二进制位的性质DP即可，注意离散化技巧
附加文件
- Standings.png by functionendless