2020-team2-004

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team2 返回]

[[Image(Situation.png,1000px)]]

[[Image(Submission.png,1000px)]]

= 概述 =

 solved: 8/13

 rank: 72



= 流水账 =

第一场~~正式~~比赛

开场yyc秒了J1（6）。Creatix接pb读的题目过了G1（15）。

之后yyc和pb做C，虽然有些波折，但是还是成功AC，C2（31）。

Creatix在此间开出了K，拿到机位后非常'''激动'''，很快写完，一交T了，因为不够冷静，代码有小bug，之后PE了两发才过，K4（40）。

之后pb和yyc分别在做B和E，Creatix开出了M，是个NTT，刚好昨天写过，'''非常激动'''，直接上机，过了，M1（75）。

'''之后陷入僵局。'''

B和E是场上A穿的题目，尤其是B。pb和yyc很快想出了正确的结论，但是需要求大范围内质数和，卡科技了。

同时yyc想出了一个E的事后得知不正确的做法，'''找pb验了后觉得没什么问题'''（这里有一点操作不当），就上机写了。此间Creatix试图到处看题，但是没有收获。

5发wa的E的提交后，全队开始停止手头工作并聚焦于E，并发现算法出现问题。此时由于长时间无过题，队内士气奇低（这种情况需要考虑一个应对方案）。

为了扭转局势，Creatix和pb分别接过E和B的锅，yyc开始看F等题目。

195min，Creatix修完了E的锅，E6（195）。之后考虑到不能让pb卡死在B上，Creatix接过B的锅，pb和yyc一起思考F。

238min，Creatix修完了B的锅，B1（238）。此时pb和yyc开出了F，yyc上机。

Creatix试图开出更多的题，但是发现时间不够，遂弃疗。

pb和yyc成功完成F，F1（286）。

''@pb，yyc你们快来补一点你们的心理活动2333''


= 总结 =

=== pb： ===

第一次打出自闭场的感觉，发现不少问题

第一点还是太菜了吧，感觉做的不够多。因为是网络赛的原因，这个B虽然榜歪了但是还是可以理解，也是自己准备不够充分。数位DP没见过类似的也没很快想出来，而且和以前一样，有一个很正确的思路，但是没有想下去，挺可惜的。

还有就是策略上，这个B确实应该战略性放弃一下，当天状态不是很好去上机多写写也是可以的。

也再次证明了组队赛不能沿用个人赛的思路吧，个人赛更多拼的是能否把榜跟完，因为时间不是很充足，所以并非所有题都会被开出来。组队赛把过得多的题先放一放，去开一下其他题也是可以的，比如这场的F就很简单，题目只要能读懂猜一猜就会做了。在队伍卡住的时候一定要让每个人知道尽量多的题意。

菜就多练

=== Creatix： ===

 * 今天写题太多了。。。

 * 个人一个很大的问题是今天不够冷静。虽然确实本次比赛出的低级错误远少于上次比赛，确实今天状态更好，但是实际上应该适当把题目丢给队友写。
 尤其是在pb卡B的时候应该果断一点把开出来的题目丢给他，而不是有那么一点自己出风头的感觉。

 * 还有一个问题，场上一道题被A穿了，我们却三人都不会，怎么办？
 比如今天的B，只能说：1，我就是菜。2，这榜有点歪，min25筛题会被A穿？
 首先明确一点，'''绝对不能放简单题'''。要有那种既然被A穿，我们一定做的出来的信心。
 然后，'''进度不能停滞'''，要保证有至少一个人在做别的题。
 所以总之，确认了题意之后，就大概'''让两个相关领域的人合力做这道题，另一个人看别的题'''，这是比较好的做法。

 * 关于'''无意义验题'''得在这里讨论一下。所谓无意义验题，即指A有一个不十分确定的做法，然后找一个并没有认真思考过这道题的B报做法。

 当B认为A是对的后，A信心大增，一写，一交，wa......

 这个问题发生的原因pb哥哥总结的很有道理：当你听别人讲做法的时候，你满脑子都是他为什么对。

 '''解决方案'''：首先验题确实是有必要的，因为讲做法的人可以以此把自己的思路梳理一遍，同时听题的人也可能可以指出一些问题。

 但是，请注意，当听题人没有仔细思考过这道题的时候，他很容易被讲题人的思路带跑。这时候后面那个效果的作用就是微乎其微的。

 所以，总而言之，讲题人仍然有必要讲，但是如果听题人未思考过题目，那么讲题人有必要注意到在这种情况下他要对他自己的做法'''负全责'''。

 另一方面，尽可能把题讲给仔细思考过的人吧！ 

=== yyc： ===

今天打的太差了，几乎是负贡献...

对E的做法过于自信了，实际上仔细想想可以发现这个做法过于不自然（虽然2的性质是对的），最后一道题写的时候也没有整理好思路，队伍安排做得也不好，应该及时把卡在机位上的pb拉下来想别的题的。。。

cjb说得对，虽然放弃一个题目很难，但是也值得尝试。就像今天如果先放下B（至少不要2-3个人做），去开榜上过的较多的DFL，说不定会比现在的结果更好。（至少在罚时上）

= 题解 =

 * A：分成横着和竖着，横着就是宽度，竖着是sum|ai-ai+1|，segment tree beats

 * B：要记得区间筛的复杂度是max(sqrt(r)/log(r), (r-l)*lglg(r-l))，打表可以打大概3000个long long。

 * C：略

 * D：

 * E：sg函数 和质因子有关

 * F：由于需要保证每一层连续，所以从后往前验证每一层的关键点在最后一层相等就行了。

 * G：略

 * H：

 * I：

 * J：略

 * K：略

 * L：f[i][xa][yb][xky][ykx][xyw][cxk][cyk]表示考虑前i位，x<=a,y<=b,x+k>=y,y+k>=x，x xor y<=w,x+k，y+k有没有进位的方案数，转移可以感性理解。

 * M：分治FFT

[/wiki/2020-team2 返回]

概述

solved: 8/13

rank: 72

流水账

第一场正式比赛

开场yyc秒了J1（6）。Creatix接pb读的题目过了G1（15）。

之后yyc和pb做C，虽然有些波折，但是还是成功AC，C2（31）。

Creatix在此间开出了K，拿到机位后非常激动，很快写完，一交T了，因为不够冷静，代码有小bug，之后PE了两发才过，K4（40）。

之后pb和yyc分别在做B和E，Creatix开出了M，是个NTT，刚好昨天写过，非常激动，直接上机，过了，M1（75）。

之后陷入僵局。

B和E是场上A穿的题目，尤其是B。pb和yyc很快想出了正确的结论，但是需要求大范围内质数和，卡科技了。

同时yyc想出了一个E的事后得知不正确的做法，找pb验了后觉得没什么问题（这里有一点操作不当），就上机写了。此间Creatix试图到处看题，但是没有收获。

5发wa的E的提交后，全队开始停止手头工作并聚焦于E，并发现算法出现问题。此时由于长时间无过题，队内士气奇低（这种情况需要考虑一个应对方案）。

为了扭转局势，Creatix和pb分别接过E和B的锅，yyc开始看F等题目。

195min，Creatix修完了E的锅，E6（195）。之后考虑到不能让pb卡死在B上，Creatix接过B的锅，pb和yyc一起思考F。

238min，Creatix修完了B的锅，B1（238）。此时pb和yyc开出了F，yyc上机。

Creatix试图开出更多的题，但是发现时间不够，遂弃疗。

pb和yyc成功完成F，F1（286）。

@pb，yyc你们快来补一点你们的心理活动2333

总结

pb：

第一次打出自闭场的感觉，发现不少问题

第一点还是太菜了吧，感觉做的不够多。因为是网络赛的原因，这个B虽然榜歪了但是还是可以理解，也是自己准备不够充分。数位DP没见过类似的也没很快想出来，而且和以前一样，有一个很正确的思路，但是没有想下去，挺可惜的。

还有就是策略上，这个B确实应该战略性放弃一下，当天状态不是很好去上机多写写也是可以的。

也再次证明了组队赛不能沿用个人赛的思路吧，个人赛更多拼的是能否把榜跟完，因为时间不是很充足，所以并非所有题都会被开出来。组队赛把过得多的题先放一放，去开一下其他题也是可以的，比如这场的F就很简单，题目只要能读懂猜一猜就会做了。在队伍卡住的时候一定要让每个人知道尽量多的题意。

菜就多练

Creatix：

  • 今天写题太多了。。。
  • 个人一个很大的问题是今天不够冷静。虽然确实本次比赛出的低级错误远少于上次比赛，确实今天状态更好，但是实际上应该适当把题目丢给队友写。

尤其是在pb卡B的时候应该果断一点把开出来的题目丢给他，而不是有那么一点自己出风头的感觉。

  • 还有一个问题，场上一道题被A穿了，我们却三人都不会，怎么办？

比如今天的B，只能说：1，我就是菜。2，这榜有点歪，min25筛题会被A穿？

首先明确一点，绝对不能放简单题。要有那种既然被A穿，我们一定做的出来的信心。

然后，进度不能停滞，要保证有至少一个人在做别的题。

所以总之，确认了题意之后，就大概让两个相关领域的人合力做这道题，另一个人看别的题，这是比较好的做法。

  • 关于无意义验题得在这里讨论一下。所谓无意义验题，即指A有一个不十分确定的做法，然后找一个并没有认真思考过这道题的B报做法。

当B认为A是对的后，A信心大增，一写，一交，wa......

这个问题发生的原因pb哥哥总结的很有道理：当你听别人讲做法的时候，你满脑子都是他为什么对。

解决方案：首先验题确实是有必要的，因为讲做法的人可以以此把自己的思路梳理一遍，同时听题的人也可能可以指出一些问题。

但是，请注意，当听题人没有仔细思考过这道题的时候，他很容易被讲题人的思路带跑。这时候后面那个效果的作用就是微乎其微的。

所以，总而言之，讲题人仍然有必要讲，但是如果听题人未思考过题目，那么讲题人有必要注意到在这种情况下他要对他自己的做法负全责。

另一方面，尽可能把题讲给仔细思考过的人吧！

yyc：

今天打的太差了，几乎是负贡献...

对E的做法过于自信了，实际上仔细想想可以发现这个做法过于不自然（虽然2的性质是对的），最后一道题写的时候也没有整理好思路，队伍安排做得也不好，应该及时把卡在机位上的pb拉下来想别的题的。。。

cjb说得对，虽然放弃一个题目很难，但是也值得尝试。就像今天如果先放下B（至少不要2-3个人做），去开榜上过的较多的DFL，说不定会比现在的结果更好。（至少在罚时上）

题解

  • A：分成横着和竖着，横着就是宽度，竖着是sum|ai-ai+1|，segment tree beats
  • B：要记得区间筛的复杂度是max(sqrt(r)/log(r), (r-l)*lglg(r-l))，打表可以打大概3000个long long。
  • C：略
  • D：
  • E：sg函数 和质因子有关
  • F：由于需要保证每一层连续，所以从后往前验证每一层的关键点在最后一层相等就行了。
  • G：略
  • H：
  • I：
  • J：略
  • K：略
  • L：f[i][xa][yb][xky][ykx][xyw][cxk][cyk]表示考虑前i位，x<=a,y<=b,x+k>=y,y+k>=x，x xor y<=w,x+k，y+k有没有进位的方案数，转移可以感性理解。
  • M：分治FFT
附加文件