2019-Acyclic_SD/AugTrain-18
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(Train-18.png,500px)]]
== 流水账 ==
== 总结 ==
=== Todobe ===
今天由于一些不可为外人道的原因，bb和jj的大脑的变得清醒了许多，于是今天就打的还比较欢乐。
得出结论：**************（jj能看懂就行了）
A题，jj以为写一个暴力就能随便过，然后T10，之后被指出算法时间复杂度是不对的，然后就暂时弃掉了这道题。最后jj手写bitset通过了这道题。
'''bitset中有_Find_first()函数和_Find_next()函数'''，分别查找从低位到高位的第一个1的位置和查找当前位置下一个1的位置。
[https://www.cnblogs.com/zwfymqz/p/10565487.html bitset]
B题挺jj讲完题意上去就写了个贪心，WA5。WA掉之后jj和xx就想出了另一种最大生成树的做法，bb觉得挺对的，jj上去写。写完之后WA4。 bb:你是不是没有没判最大生成树上有负边的情况？ jj加了一句话在上面。 jj：你先别交，我总觉得有什么不太对。 但是此时眼疾手快的xx已经以迅雷不及掩耳之速把B交上去了。然后返回了一个OK，为我们节省了不少思考的时间。好的我们全都懂了，xx就是锦鲤。
bb读了E题，跟队友复述题意的时候就直接说把一个数拆成最少的形如3*n*n-3*n+1的数的和。然后jj就开始疯狂推式子，她说要可以变成n*(n-1)的形式。过了一会儿，bb恍然大悟，复述题意的时候好像忘记了说题目里给的那条重要的性质，任意一个数可以拆成不超过三个这样的数之和，告诉jj之后。jj：你怎么不早点告诉我（一副关爱智障的眼神）。然后jj：时间复杂度1000*根号n,1e9。 bb：你先写吧，莽一发。事实证明，是可以过的。该莽就得莽。
F题我想了一会儿之后，出了解法，发现把方块拆一拆，询问拆一拆就是一个简单的二维数点问题。然后跟两个队友讲了题意之后就上去写（因为发现题目有一些特殊的性质没有用上所以有点虚），然后我上来就是一个CDQ分治再加上一个树状数组。都写完了，一看，这tm一个二维数点问题我咋直接莽了一个三维数点出来呢？？？凭空多出来一个log，还多写好几行代码。纠结了一会儿是删CDQ还是删树状数组，最后把CDQ分治删掉，写一个循环就结束了。 测样例，过了。交上去1A。今天的数据结构没坑队友还是挺好的。
赛后听了lsy学长的做法，突然发现了我们队和他们队的巨大差距。我现在好像也没有完全理解他们的做法，用一个线段树来维护一个一次函数，然后区间修改区间查询这样，就挺复杂的。如果这个题没有发现简单做法的话，这种思维深度和代码复杂度的题，我大概率是驾驭不来的，可能最后能过也要卡很久，我觉得我应该找点代码复杂的题做做来练练手/笑哭。
D题我们最后写了个斜率优化，线段树维护凸包有点虚，就在推这个题有没有决策单调性之类，最后并没有调完。在最后一分钟的时候交了一发意思一下，顺便保存一下代码。（话说dhr的分治好强）
J：我们需要学习更多的博弈论知识。 '''翻硬币博弈结论之——局面的SG 值为局面中每个正面朝上的棋子单一存在时的SG 值的异或和。'''
=== ZhljJoan ===
不太会用bitset亏爆。还有40分钟左右fby写斜率优化我就摸了……最后仨人开一个题的话一个人写代码剩下俩人到底该干啥……我们队没有一个人会博弈论，也没有一个人擅长打表找规律，经过前几场比赛我觉得我们队在不会做的题瞎搞上有了进步，但是我们好像不擅长瞎搞过题……
== 补题 ==
J [wxx] : 第一发PE了，原因是return 0过早；第二发wa20，原因是sg数组没开大；第三发wa3，是因为删减代码的时候改错了，在i=1的时候会GG。。细想了一下数据很水，很多构造的答案都是直接拿第一个。。。 
流水账
总结
Todobe
今天由于一些不可为外人道的原因，bb和jj的大脑的变得清醒了许多，于是今天就打的还比较欢乐。
得出结论：**************（jj能看懂就行了）
A题，jj以为写一个暴力就能随便过，然后T10，之后被指出算法时间复杂度是不对的，然后就暂时弃掉了这道题。最后jj手写bitset通过了这道题。
bitset中有_Find_first()函数和_Find_next()函数，分别查找从低位到高位的第一个1的位置和查找当前位置下一个1的位置。
B题挺jj讲完题意上去就写了个贪心，WA5。WA掉之后jj和xx就想出了另一种最大生成树的做法，bb觉得挺对的，jj上去写。写完之后WA4。 bb:你是不是没有没判最大生成树上有负边的情况？ jj加了一句话在上面。 jj：你先别交，我总觉得有什么不太对。 但是此时眼疾手快的xx已经以迅雷不及掩耳之速把B交上去了。然后返回了一个OK，为我们节省了不少思考的时间。好的我们全都懂了，xx就是锦鲤。
bb读了E题，跟队友复述题意的时候就直接说把一个数拆成最少的形如3*n*n-3*n+1的数的和。然后jj就开始疯狂推式子，她说要可以变成n*(n-1)的形式。过了一会儿，bb恍然大悟，复述题意的时候好像忘记了说题目里给的那条重要的性质，任意一个数可以拆成不超过三个这样的数之和，告诉jj之后。jj：你怎么不早点告诉我（一副关爱智障的眼神）。然后jj：时间复杂度1000*根号n,1e9。 bb：你先写吧，莽一发。事实证明，是可以过的。该莽就得莽。
F题我想了一会儿之后，出了解法，发现把方块拆一拆，询问拆一拆就是一个简单的二维数点问题。然后跟两个队友讲了题意之后就上去写（因为发现题目有一些特殊的性质没有用上所以有点虚），然后我上来就是一个CDQ分治再加上一个树状数组。都写完了，一看，这tm一个二维数点问题我咋直接莽了一个三维数点出来呢？？？凭空多出来一个log，还多写好几行代码。纠结了一会儿是删CDQ还是删树状数组，最后把CDQ分治删掉，写一个循环就结束了。 测样例，过了。交上去1A。今天的数据结构没坑队友还是挺好的。
赛后听了lsy学长的做法，突然发现了我们队和他们队的巨大差距。我现在好像也没有完全理解他们的做法，用一个线段树来维护一个一次函数，然后区间修改区间查询这样，就挺复杂的。如果这个题没有发现简单做法的话，这种思维深度和代码复杂度的题，我大概率是驾驭不来的，可能最后能过也要卡很久，我觉得我应该找点代码复杂的题做做来练练手/笑哭。
D题我们最后写了个斜率优化，线段树维护凸包有点虚，就在推这个题有没有决策单调性之类，最后并没有调完。在最后一分钟的时候交了一发意思一下，顺便保存一下代码。（话说dhr的分治好强）
J：我们需要学习更多的博弈论知识。 翻硬币博弈结论之——局面的SG 值为局面中每个正面朝上的棋子单一存在时的SG 值的异或和。
ZhljJoan
不太会用bitset亏爆。还有40分钟左右fby写斜率优化我就摸了……最后仨人开一个题的话一个人写代码剩下俩人到底该干啥……我们队没有一个人会博弈论，也没有一个人擅长打表找规律，经过前几场比赛我觉得我们队在不会做的题瞎搞上有了进步，但是我们好像不擅长瞎搞过题……
补题
J [wxx] : 第一发PE了，原因是return 0过早；第二发wa20，原因是sg数组没开大；第三发wa3，是因为删减代码的时候改错了，在i=1的时候会GG。。细想了一下数据很水，很多构造的答案都是直接拿第一个。。。