2017-C03-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(day3board.jpg)]]

== 流水账 ==
今天中午12点开始比赛，开场cjb从1001开始看，yzc从1011开始看，sub是从1004开始看，打算遇到可做的题就拿去签，sub先出1004字符串可做，但cjb否决了它，因为认为要敲板子，不太能快码，cjb看到1003，理解错了题意，认为可以做，去上机，打到一半yzc发现题意有点偏差，陷入了思考，然后sub学长把性质讲出来，交了一发MLE，改小空间后在开场26分33秒过了1003，接下来cjb继续码1004的后缀数组，期间yzc和sub想出了1007和1005，后来cjb发现板子出问题后换yzc敲1005，然后cjb和yzc反复交换电脑，心态接连爆炸，一个半小时之后终于发现板子的错误，交了后缀数组之后tle。此时三人都比较着急，换yzc死调1005，sub跟cjb讲了别的做法后猛然发现扩展kmp可以秒杀，最后yzc在开场2小时22分之后第二次提交AC.在此前接近一个半小时里，我们队没有任何提交.......此时换cjb敲1004，在开场2小时35分贡献一发编译错误后通过，换sub学长敲1005，在2小时43分钟后一次AC，二十分钟内连过三题，多少有种救赎的滋味。接下来50分钟三人开始讨论1001，cjb把sub学长的模型完善后，三人反复研究，最后sub再次提出最后方案，cjb期间写了checker，最后sub和yzc配合下把代码生成好提交，在3小时31分钟后通过。此时剩下一个半小时，我们判断1006比1008更可做，讨论出线段树维护矩阵的做法，让yzc上机，期间cjb和sub在思考各种细节和构造小数据，但因为对矩阵转置的认知有错误，后来细节不断爆炸，结束前挣扎地交了一发获得WA。以5道题外加巨大的罚时，以72名结束了比赛，五队今天25名，恭喜他们。
== 总结 ==
=== chenjb ===
今天我们队表现不好，中期简直像消失了一样，想从以下几个方面总结一下:

一.场上自己的锅: 首先我在签到和卡题的时候都表现得太过急躁，后缀数组板子敲出来炸了之后心态就崩了，这样的状态也影响到了全队，导致我们在开场27分钟后到2小时22分钟前没有任何提交记录，当时如果静下心来，应该很快能发现板子的漏洞(也因为这个板子用过很多次导致，如果那个时候sub学长告诉了我榜的情况估计我们会崩得更厉害). 还好后来连过三题，追平四题，又组织大家讨论了1001，提出了非常有用的想法，才让结果不至于完全爆炸. 另外一个锅是在最后一个半小时的时候，对于1006和1008，不应该根据通过人数去单拼一题，而且就算单拼一题，我也不应该带着sub去思考同一题的细节和数据，应该去看看1008. 总而言之，场上永远不要让榜或者板子影响自己的心态，就像shb说的那样: 我们应该要努力做带榜的人，要有这样的心气，要沉着冷静. [[BR]]

二.关于我们队的中期爆炸: 我觉得有两个原因: [[BR]]    
    1.我们全队在面对中低难度题的时候，都显得太稚嫩，经验不足，不能像shb,lsmll他们对于这样的题目能够很快给出解法，这些题难度最多就是CF div1的前两题，平时打CF的时候我们总是坑坑洼洼，明显手速和反应都比较慢，而且我们总是用力过猛，一但进了死胡同就会浪费时间；[[BR]]    
    2.我们现阶段不应该同时让三道题在等，坑可以开，但对于同一时刻，我们现在还只能做到一题一人在写，一题两人在琢磨，就算很快得到多道题的解法，也应该两题两题地抠细节抠实现，不然会出现三个人每人心里装着一道题的情况，今天的中期也是我们三人互相沟通最差的时候，一个是心态，另一个也是脑子里装着别的题目.[[BR]]

三.关于我们队的后期: 我们这两场在中后期都表现得很稳健(多少填了一波前面挖的坑). 固然我们要努力把中期给完善，但我们也要看到自己队在后期的表现(还算ok?)我觉得我们在选择攻题的时候，三个人都比较配合，后期没人上机的时候，我们并不会出现各自为战缺乏沟通的情况，而从昨天封榜后过了2题，今天四个小时的时候过了1题来看，这样的交流和讨论是卓有成效的，我们能够把自己的奇思妙想，一些不太成熟但有一定道理的想法拿出来讨论，不断推翻、完善，而我们之间经常能够互相完善想法里最后一步的收尾(这点sub学长做得尤其好)，这个要保持下去，但要注意如果讨论结束，一人在上机的时候，不要坐着吃瓜，要开多一个到两个坑去讨论.[[BR]]

四.关于改进: 搞学长说得一针见血啊，我们队现在的主要特点，就是菜啊......QAQ.....所以我们首先要从手速练起，然后要提高自己的算法水平(要思考如何切得又快又准，积累套路)，要坚持不懈地刷CF、AtCoder等等，参加各种各样的比赛，提高自己的姿势水平，至于团队配合，我们要统一一下我们的代码风格，继续根据训练情况安排下各种操作，但本质还是要提高我们的脑力和码力.
=== oipotato ===
今天中期出了大问题，大概总结下来有这么几个问题：[[BR]]
1.三个人在当前能力有限时，不该同时开三个题，导致每个人心中都装着自己的题，各自为政，交流太少。[[BR]]
2.逆风时太过急躁，导致中期两个小时一直不停的换人上机，但是实际上每个人在上机的时候都没有想清楚，又怕拖队伍太多时间，就导致实际上什么进展都没有。[[BR]]
3.后期感觉1006做法科学就全队孤注一掷全队搞一道题，而没去开其实比较好做的1008，导致在发现1006做法有问题之后直接爆炸。[[BR]]

我觉得我自己有个很大的问题就是逆风时自己本来能冷静，但是队友一急也会连带影响到自己，不仅没能帮队友稳住心态，反而把自己搭进去了。导致在打1005一个很简单的二分的时候一直在纠结有没有写错，有点畏首畏尾，在往后的比赛中要注意冷静的思考问题，想清楚了再上机。最后，讲讲我觉得我们队现在做题的一个比较明显的问题，就是做题很刚，每一题都希望马上套上哪个模型解决细节就能出来，看似争分夺秒节奏很紧凑，其实从来没有静下来很有条理的把一道题想明白，想清楚，从而乱了自己的节奏。这种做题方法虽然在做简单题时可能会有一点速度上的优势，但实际上一到中期遇到中等难度的题时，常常想个大概就上机，导致节奏大乱。之后的比赛中应该注意这个问题。以上是我觉得我们队现在存在的比较大的问题，但是我觉得我们队也是有一些不错的需要保持的优点，我们在大劣势的时候如果突然有了突破，就会全队振奋，然后连续过题，完成救赎。而且我们队不会出现后期乏力的情况，在后期还是能很积极的去想题。这个优点还是要保持的。而我们要做的，就是不在前中期陷入劣势，让救赎变为锦上添花。
=== subconscious  ===
今天从04开始往后看起.04看完之后想到二分HASH,被在写03的cjb学长踢了.隐约感觉扩展kmp能做(实际上kmp就能做),放置去看05.05是贪心题,手造后发现与mod4有关,期间讨论了03中n的上界问题.A03后cjb学长想04后缀数组并上机,在发现模板写错后换yzc学长写07,细节出错,陷入僵局.此时我自己在开05,没有和cjb学长做好沟通,导致之后04写了错误算法,卡了2小时.90分钟之间cjb学长和yzc学长不断轮换,最终04调出,交了一发TLE.此时下机后和cjb学长讨论,发现扩展kmp能做,上机后才AC.最后90分钟在06和08之间选了06,推出方程后发现细节爆炸,魔改了初始状态后发现修改操作矩阵顺序会反转,随后程序不断出错,最后垂死挣扎失败WA.总体来说,签到速度仍有改进空间;对于中期的空档,首先是我们三开后做不到交流,没有和cjb学长讨论好具体做法,导致在04上花了太多时间,而我对自己题目用时的把握的打字速度也不够充足,05应该抢上机时间;对于最后开题,除了跟榜之外,我们三个没有分工也是很大的问题,08实际是可能AC的题目,但我们最终吊死在了06上.

== 题解 ==

 * 1006：设f[i][0/1]表示前i位，以0/1结尾的子序列的个数，则显然有DP方程f[i][a[i]]=f[i-1][0]+f[i-1][1]+1, f[i][a[i] xor 1]=f[i-1][a[i] xor 1]. 显然可以用线段树维护转移矩阵的积来维护。对于修改操作，线段树每个区间都维护两个矩阵，一个是区间的积，另一个则是区间的数都抑或之后的积。对区间的一次修改相当于将两个矩阵交换。配合lazy标记很容易便能维护了。
 * 1008：f[i][j][k]表示前i个点，选了j个点，组成了k个联通块的最大代价，对于新加入的点，如果是左进左出，那么对答案贡献是2*d[i]+turncost, 相对应的如果是右进右出，那就是-2*d[i]+turncost，如果左进右出或者反之，则没有贡献. 对读进来d[i]要做一个前缀和，最后答案就是f[n][m][0].
 * 1009：https://en.wikipedia.org/wiki/Descartes%27_theorem 设第i个半径不同的圆半径倒数ai,代入方程,有ai与ai+1的关系.由对称性可以发现ai代入方程后的两解分别是ai-1和ai+1,由韦达定理可得线性关系式ai+1=2(ai+r1+r2)-ai-1,其中r1为-1/max(R1,R2),r2为1/min(R1,R2).递推求和即可,注意精度.

== 补题 ==
 * 1002
 * 1006(√)
 * 1008(√)
 * 1009(√)

流水账

今天中午12点开始比赛，开场cjb从1001开始看，yzc从1011开始看，sub是从1004开始看，打算遇到可做的题就拿去签，sub先出1004字符串可做，但cjb否决了它，因为认为要敲板子，不太能快码，cjb看到1003，理解错了题意，认为可以做，去上机，打到一半yzc发现题意有点偏差，陷入了思考，然后sub学长把性质讲出来，交了一发MLE，改小空间后在开场26分33秒过了1003，接下来cjb继续码1004的后缀数组，期间yzc和sub想出了1007和1005，后来cjb发现板子出问题后换yzc敲1005，然后cjb和yzc反复交换电脑，心态接连爆炸，一个半小时之后终于发现板子的错误，交了后缀数组之后tle。此时三人都比较着急，换yzc死调1005，sub跟cjb讲了别的做法后猛然发现扩展kmp可以秒杀，最后yzc在开场2小时22分之后第二次提交AC.在此前接近一个半小时里，我们队没有任何提交.......此时换cjb敲1004，在开场2小时35分贡献一发编译错误后通过，换sub学长敲1005，在2小时43分钟后一次AC，二十分钟内连过三题，多少有种救赎的滋味。接下来50分钟三人开始讨论1001，cjb把sub学长的模型完善后，三人反复研究，最后sub再次提出最后方案，cjb期间写了checker，最后sub和yzc配合下把代码生成好提交，在3小时31分钟后通过。此时剩下一个半小时，我们判断1006比1008更可做，讨论出线段树维护矩阵的做法，让yzc上机，期间cjb和sub在思考各种细节和构造小数据，但因为对矩阵转置的认知有错误，后来细节不断爆炸，结束前挣扎地交了一发获得WA。以5道题外加巨大的罚时，以72名结束了比赛，五队今天25名，恭喜他们。

总结

chenjb

今天我们队表现不好，中期简直像消失了一样，想从以下几个方面总结一下:

一.场上自己的锅: 首先我在签到和卡题的时候都表现得太过急躁，后缀数组板子敲出来炸了之后心态就崩了，这样的状态也影响到了全队，导致我们在开场27分钟后到2小时22分钟前没有任何提交记录，当时如果静下心来，应该很快能发现板子的漏洞(也因为这个板子用过很多次导致，如果那个时候sub学长告诉了我榜的情况估计我们会崩得更厉害). 还好后来连过三题，追平四题，又组织大家讨论了1001，提出了非常有用的想法，才让结果不至于完全爆炸. 另外一个锅是在最后一个半小时的时候，对于1006和1008，不应该根据通过人数去单拼一题，而且就算单拼一题，我也不应该带着sub去思考同一题的细节和数据，应该去看看1008. 总而言之，场上永远不要让榜或者板子影响自己的心态，就像shb说的那样: 我们应该要努力做带榜的人，要有这样的心气，要沉着冷静.

二.关于我们队的中期爆炸: 我觉得有两个原因:

1.我们全队在面对中低难度题的时候，都显得太稚嫩，经验不足，不能像shb,lsmll他们对于这样的题目能够很快给出解法，这些题难度最多就是CF div1的前两题，平时打CF的时候我们总是坑坑洼洼，明显手速和反应都比较慢，而且我们总是用力过猛，一但进了死胡同就会浪费时间；

2.我们现阶段不应该同时让三道题在等，坑可以开，但对于同一时刻，我们现在还只能做到一题一人在写，一题两人在琢磨，就算很快得到多道题的解法，也应该两题两题地抠细节抠实现，不然会出现三个人每人心里装着一道题的情况，今天的中期也是我们三人互相沟通最差的时候，一个是心态，另一个也是脑子里装着别的题目.

三.关于我们队的后期: 我们这两场在中后期都表现得很稳健(多少填了一波前面挖的坑). 固然我们要努力把中期给完善，但我们也要看到自己队在后期的表现(还算ok?)我觉得我们在选择攻题的时候，三个人都比较配合，后期没人上机的时候，我们并不会出现各自为战缺乏沟通的情况，而从昨天封榜后过了2题，今天四个小时的时候过了1题来看，这样的交流和讨论是卓有成效的，我们能够把自己的奇思妙想，一些不太成熟但有一定道理的想法拿出来讨论，不断推翻、完善，而我们之间经常能够互相完善想法里最后一步的收尾(这点sub学长做得尤其好)，这个要保持下去，但要注意如果讨论结束，一人在上机的时候，不要坐着吃瓜，要开多一个到两个坑去讨论.

四.关于改进: 搞学长说得一针见血啊，我们队现在的主要特点，就是菜啊......QAQ.....所以我们首先要从手速练起，然后要提高自己的算法水平(要思考如何切得又快又准，积累套路)，要坚持不懈地刷CF、AtCoder等等，参加各种各样的比赛，提高自己的姿势水平，至于团队配合，我们要统一一下我们的代码风格，继续根据训练情况安排下各种操作，但本质还是要提高我们的脑力和码力.

oipotato

今天中期出了大问题，大概总结下来有这么几个问题：

1.三个人在当前能力有限时，不该同时开三个题，导致每个人心中都装着自己的题，各自为政，交流太少。

2.逆风时太过急躁，导致中期两个小时一直不停的换人上机，但是实际上每个人在上机的时候都没有想清楚，又怕拖队伍太多时间，就导致实际上什么进展都没有。

3.后期感觉1006做法科学就全队孤注一掷全队搞一道题，而没去开其实比较好做的1008，导致在发现1006做法有问题之后直接爆炸。

我觉得我自己有个很大的问题就是逆风时自己本来能冷静，但是队友一急也会连带影响到自己，不仅没能帮队友稳住心态，反而把自己搭进去了。导致在打1005一个很简单的二分的时候一直在纠结有没有写错，有点畏首畏尾，在往后的比赛中要注意冷静的思考问题，想清楚了再上机。最后，讲讲我觉得我们队现在做题的一个比较明显的问题，就是做题很刚，每一题都希望马上套上哪个模型解决细节就能出来，看似争分夺秒节奏很紧凑，其实从来没有静下来很有条理的把一道题想明白，想清楚，从而乱了自己的节奏。这种做题方法虽然在做简单题时可能会有一点速度上的优势，但实际上一到中期遇到中等难度的题时，常常想个大概就上机，导致节奏大乱。之后的比赛中应该注意这个问题。以上是我觉得我们队现在存在的比较大的问题，但是我觉得我们队也是有一些不错的需要保持的优点，我们在大劣势的时候如果突然有了突破，就会全队振奋，然后连续过题，完成救赎。而且我们队不会出现后期乏力的情况，在后期还是能很积极的去想题。这个优点还是要保持的。而我们要做的，就是不在前中期陷入劣势，让救赎变为锦上添花。

subconscious

今天从04开始往后看起.04看完之后想到二分HASH,被在写03的cjb学长踢了.隐约感觉扩展kmp能做(实际上kmp就能做),放置去看05.05是贪心题,手造后发现与mod4有关,期间讨论了03中n的上界问题.A03后cjb学长想04后缀数组并上机,在发现模板写错后换yzc学长写07,细节出错,陷入僵局.此时我自己在开05,没有和cjb学长做好沟通,导致之后04写了错误算法,卡了2小时.90分钟之间cjb学长和yzc学长不断轮换,最终04调出,交了一发TLE.此时下机后和cjb学长讨论,发现扩展kmp能做,上机后才AC.最后90分钟在06和08之间选了06,推出方程后发现细节爆炸,魔改了初始状态后发现修改操作矩阵顺序会反转,随后程序不断出错,最后垂死挣扎失败WA.总体来说,签到速度仍有改进空间;对于中期的空档,首先是我们三开后做不到交流,没有和cjb学长讨论好具体做法,导致在04上花了太多时间,而我对自己题目用时的把握的打字速度也不够充足,05应该抢上机时间;对于最后开题,除了跟榜之外,我们三个没有分工也是很大的问题,08实际是可能AC的题目,但我们最终吊死在了06上.

题解

  • 1006：设f[i][0/1]表示前i位，以0/1结尾的子序列的个数，则显然有DP方程f[i][a[i]]=f[i-1][0]+f[i-1][1]+1, f[i][a[i] xor 1]=f[i-1][a[i] xor 1]. 显然可以用线段树维护转移矩阵的积来维护。对于修改操作，线段树每个区间都维护两个矩阵，一个是区间的积，另一个则是区间的数都抑或之后的积。对区间的一次修改相当于将两个矩阵交换。配合lazy标记很容易便能维护了。
  • 1008：f[i][j][k]表示前i个点，选了j个点，组成了k个联通块的最大代价，对于新加入的点，如果是左进左出，那么对答案贡献是2*d[i]+turncost, 相对应的如果是右进右出，那就是-2*d[i]+turncost，如果左进右出或者反之，则没有贡献. 对读进来d[i]要做一个前缀和，最后答案就是f[n][m][0].
  • 1009：https://en.wikipedia.org/wiki/Descartes%27_theorem 设第i个半径不同的圆半径倒数ai,代入方程,有ai与ai+1的关系.由对称性可以发现ai代入方程后的两解分别是ai-1和ai+1,由韦达定理可得线性关系式ai+1=2(ai+r1+r2)-ai-1,其中r1为-1/max(R1,R2),r2为1/min(R1,R2).递推求和即可,注意精度.

补题

  • 1002
  • 1006(√)
  • 1008(√)
  • 1009(√)
附加文件