2019-team666-0004
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2019-team666 返回]
== 概述 ==
[[Image(Screenshot from 2019-07-23 06-15-34.png,1000px)]]
七月集训第4场
上来tjc稳稳签掉G，'''G1y26'''，yyc说A有想法就上机写了，其余两人各自开题，期间tjc开出I，hyw开出J，觉得很稳就上机写了，挂一发longlong，'''J2y88'''，换yyc上机接着写A，很快交了一发WA on 116，吹响了A题爆炸的号角。于是yyc打印下机调A，换tjc上机摸了一发I，再次稳过，'''I1y106'''，yyc继续调A，hyw和tjc各自开题，讨论出H是个凸包加三分，这时yyc的A再次WA on 116，遂打印下机，换tjc写H的凸包，hyw写H的三分，结果凸包和三分各假了一次，'''H3y216'''。这时大家确认场上除了F没有可做题，C想到是插头dp但太麻烦、K的解法不确定对不对，tjc提出F可以多次扩欧贪心构造方案，yyc的A开了个排序顺序CE一发+WA on 91两发，hyw上机很快写完扩欧，和tjc调参调了一会儿，然后换tjc写贪心，hyw帮yyc查代码，觉得可以shuffle一波。最后5分钟的时候F写完了，交了一发TLE，觉得没戏了，于是把A随机了一波狂交一波，疯狂WA180+，这就有了上图中的盛况。
== 总结 ==
=== yyc ===
这把没我.jpg，全程自闭，我是谁我在哪泥萌怎么什么都会...
=== tjc ===
再一次想出来的题>写出来的题，是时候提升代码能力了（）
看错题计数器++
=== hyw ===
今天这场感觉大家都尽力了，除了A这个坑题以外能做的题都差不多了，代码上还是有些地方不够细致，除此以外也没有什么特别大失误的地方，感觉队伍磨合得也越来越好了。这一场借用了乌鸦队的经验队员互查代码，虽然最后A还是没过不过效果很好。另外就是longlong背锅，还有队友变量名CE了一波，以后是不是也要像别的队一样要开个计数器记一下XD
A这个题shuffle了11发没过，据说别的队压个bitset就过了，还有的队去掉了相同的状态，但还是感觉很迷
F居然没想到模背包...一直纠结于扩欧而且不知道为啥超时...总之有点可惜
J题二分很稳，开心。但是很快H题我写的三分就出锅了，主动背锅。
K题看题的时候觉得没什么头绪，后来知道可分类讨论可dp。
最后凭着罚时优势居然rk4了，还是挺惊喜的。
=== 题解 ===
A：dp[i][j][k]（是个pair）表示前i个物品最多的和次多的比最少的分别多j,k的编号，转移即可。
直接对输入序列跑可能会WA，由于答案与顺序无关，所以可以预处理输入序列，使得每一种数都在序列里均匀分布即可通过
B：博弈，大概是除了起点以外左边的点的度要是偶数。
C：插头dp
D：物理题，不会
E：不会
F：对最大的数取模做一遍背包，贪心构造方案
G：签到
H：在下凸包上三分即可
I：/*队友写的，留坑*/ 相当于每次规定一个区间[l,r]内任意一个数和r+1位置上的数不同，于是贪心填数字，发现贪心的过程相当于求区间mex，经典例题bzoj3585，注意到每次更新r+1时只和r有关，于是把可持久化去掉即可
J：把a,b都从大到小排序，由于最后可以运行的电器一定是b的一个前缀，二分这个前缀的位置，然后贪心验证即可
K：分类讨论去掉直径上一段以后新直径的可能情况，发现要用的东西都可以n^2^预处理出来[/wiki/2019-team666 返回]
概述
七月集训第4场
上来tjc稳稳签掉G，G1y26，yyc说A有想法就上机写了，其余两人各自开题，期间tjc开出I，hyw开出J，觉得很稳就上机写了，挂一发longlong，J2y88，换yyc上机接着写A，很快交了一发WA on 116，吹响了A题爆炸的号角。于是yyc打印下机调A，换tjc上机摸了一发I，再次稳过，I1y106，yyc继续调A，hyw和tjc各自开题，讨论出H是个凸包加三分，这时yyc的A再次WA on 116，遂打印下机，换tjc写H的凸包，hyw写H的三分，结果凸包和三分各假了一次，H3y216。这时大家确认场上除了F没有可做题，C想到是插头dp但太麻烦、K的解法不确定对不对，tjc提出F可以多次扩欧贪心构造方案，yyc的A开了个排序顺序CE一发+WA on 91两发，hyw上机很快写完扩欧，和tjc调参调了一会儿，然后换tjc写贪心，hyw帮yyc查代码，觉得可以shuffle一波。最后5分钟的时候F写完了，交了一发TLE，觉得没戏了，于是把A随机了一波狂交一波，疯狂WA180+，这就有了上图中的盛况。
总结
yyc
这把没我.jpg，全程自闭，我是谁我在哪泥萌怎么什么都会...
tjc
再一次想出来的题>写出来的题，是时候提升代码能力了（）
看错题计数器++
hyw
今天这场感觉大家都尽力了，除了A这个坑题以外能做的题都差不多了，代码上还是有些地方不够细致，除此以外也没有什么特别大失误的地方，感觉队伍磨合得也越来越好了。这一场借用了乌鸦队的经验队员互查代码，虽然最后A还是没过不过效果很好。另外就是longlong背锅，还有队友变量名CE了一波，以后是不是也要像别的队一样要开个计数器记一下XD
A这个题shuffle了11发没过，据说别的队压个bitset就过了，还有的队去掉了相同的状态，但还是感觉很迷
F居然没想到模背包...一直纠结于扩欧而且不知道为啥超时...总之有点可惜
J题二分很稳，开心。但是很快H题我写的三分就出锅了，主动背锅。
K题看题的时候觉得没什么头绪，后来知道可分类讨论可dp。
最后凭着罚时优势居然rk4了，还是挺惊喜的。
题解
A：dp[i][j][k]（是个pair）表示前i个物品最多的和次多的比最少的分别多j,k的编号，转移即可。
直接对输入序列跑可能会WA，由于答案与顺序无关，所以可以预处理输入序列，使得每一种数都在序列里均匀分布即可通过
B：博弈，大概是除了起点以外左边的点的度要是偶数。
C：插头dp
D：物理题，不会
E：不会
F：对最大的数取模做一遍背包，贪心构造方案
G：签到
H：在下凸包上三分即可
I：/*队友写的，留坑*/ 相当于每次规定一个区间[l,r]内任意一个数和r+1位置上的数不同，于是贪心填数字，发现贪心的过程相当于求区间mex，经典例题bzoj3585，注意到每次更新r+1时只和r有关，于是把可持久化去掉即可
J：把a,b都从大到小排序，由于最后可以运行的电器一定是b的一个前缀，二分这个前缀的位置，然后贪心验证即可
K：分类讨论去掉直径上一段以后新直径的可能情况，发现要用的东西都可以n2预处理出来