Day.0 热身赛
0.
东北林业大学环境还是挺不错的，去看了森林博物馆，还转了转，不愧是林业大学吗这么多树。饭票可以用在食堂各个窗口不错，甚至连蜜雪冰城都可以用。
A.
签到题。用一用抽屉原理，得知最多填20个格子，对角线空出来即可。第一发不小心以为是填满4*4的16个格子，当时觉得极其的对（，然后WA了一发后被我想出来可以是对角线填20。
B.
江苏省赛原题博弈论。队友一下子就看出来了是原题，我还想了一会又证了一遍。直接判断最大值的个数为奇数则Alice必胜，反之为偶数则Bob必胜。粗略证明：首先可见如果整个数列仅有一个最大值，那么此为终止状态，这时最大值的数目为1为奇数。任意一人每次操作后，最大值的数目减1，于是显然。
*C.
赛场未过。据说是电子科技大学校赛的题目。两两建边，把边权赋给点权，然后发现同一条边的点权如果在两个人手里，答案便会抵消。于是按到其他点的距离之和赋点权，两人都贪心选取最大点权即可。赛场上我们看出来了Alice和Bob都希望最大化自己的S，然而后面没什么思路写了个错误的贪心。
*D.
赛场未过。据说是带权一般图最大图匹配的板子题，过于高级我们也没有对应板子。
Day.1 正式赛
0.
正式赛不知为何推迟了20分钟然后延时结束。前期许多签到题dirt了，罚时和J卡住导致最后10min才过第5题最终紧张刺激的拿下铜牌。赛后看榜发现这场5题除一队打铁外都是铜牌，6题就可以Ag。榜似乎是有点歪的厉害了，不然的话A和B至少再拿下一道可能是可以Ag的。不过本场也没有什么时间留给别的题了。
C.
签到题。开场后我掏档案袋拿出题目，翻到A一眼没看明白往后翻。然后看到B觉得是可做的计算几何，但是接着翻然后就看到了最签到的C。直接模拟输出即可，交之前想了一下要不要关同步流但是觉得应该不至于卡这点，结果还真因为这个dirt了一发。看气球的时候觉得似乎这时候过的M比C要多，如果是真的可见榜是真的很歪。
M.
同样是签到题，队友过的。队友跟我说了一下想法，然后我觉得可以，就直接交了，这也是本场唯一一发直接AC的题目。具体来说是直接根号枚举，得到一个因数区间的值后除一下再减，然后暴力就可以过。
G.
签到的图论题，直接建双向边，busy的人建单向边，然后BFS即可。我因为不是很熟BFS一开始还想拓扑排序，但是确实是直接BFS就可以。因为我不是很熟BFS所以想交给队友来写，但是还是因为奇奇怪怪的小错WA了一发。改了后通过。
K.
看题解好像做法挺多的。我一开始没看出来最优解的特性，想跑一个上下界最大费用可行流（天天看网络流导致的），不过没办法把解除限制的操作转化为网络流建模，暴力的话会T。后来看出来了最优解一定是处理完所有\(l_i\)后跑剩下的\(m\)全贪心，然后很自然得到二分前缀和的做法。发现预处理后，加上二分前缀和，暴力选择解除哪一个的限制，\(O(n\log n)\)可以过。具体一点就是按\(w_i\)排序预处理前缀和，同时预处理出不进行解除操作时剩下的时间\(m-\sum l_i\)和此时的答案\(\sum {(l_i \times w_i)}\)，每次枚举解除限制的点\(x\)的时候剩下的时间加上这个点的\(l_x\)，答案减去这个点的贡献。然后拿剩余的时间在前缀和上二分，前缀和按\(r_i-l_i\)计算（每个点还剩这么多可以取），注意第\(x\)个点这里全部可以选于是它肯定是边界，然后就是一些细节问题了。
J.
最后10min过的，WA了5发，紧张刺激。这个题好像一开始就开始看但是接近最后才想出做法，最开始的时候出了几个错误的贪心策略，一边写一边被一一hack掉。然后hack又被解释掉，然后又被hack掉。我有开始往dp那个思路考虑，准备按充电桩来dp，可是转移不太会。后来听完我的dp想法之后，队友开始做用一个数\(sum\)和一个数\(cnt\)来控制总可走路程和剩余可分配时间的做法，可惜\(cnt\)一个数控制可分配时间的做法存信息是不够的，一开始造了一组点很近的hack，后来发现这组hack是错的然后继续写，然后又发现了一组新hack（。最后靠重叠不影响之类的终于出了正确的贪心策略，但是实现上又遇到了问题。队友写了一个很神奇的set，set里存分块，然后每次把分块去掉一部分。最后其实这个做法是对的，但是我没听过这种set觉得很假一直在想hack造数据拍也没想出来。交了之后一直在WA，改了很多细节最后10min中发现是一个while的条件有误（最后也没造出来什么数据是错的），造就了4h51min通过拿牌的结果。
*B.
赛时未过。其实是非常简单的计算几何。我看一眼B之后就觉得是求出凸包然后枚举内部点看哪个三角形面积最小。后来要了计算几何的板子来看有没有对应的算法，找到以后觉得可做但是发现一直没人过，于是开始觉得可能一开始的凸包减一点可能是错的于是在想有没有什么情况可以卡掉，但是也没想出来（实际上没人过是因为大家都很怕计算几何的样子）。但是这个题过的人实在是太少了，当时也只有十几个队伍过，都是强队，再加上当时正好手里还有J和K于是也没有继续往下想怎么判断凸包快速内部的点围成的三角形。结束后和队友交流了一下题意，很快就讨论出可能是内部再跑一个凸包然后做一做，最后题解也大概是这个意思，如果赛场时间充裕的话应该是可以做出来的。
*A.
赛时未过。赛前靠气球颜色预测签到，觉得A是金色气球比较贵，可能是防AK题，所以我直到最后也没来得及看完A的题意。听说是比较简单的构造题，说不定如果看了的话其实是可做的。
标签：前缀,签到,CCPC,然后,2024,队友,hack,游记,贪心 From： https://www.cnblogs.com/Almond/p/18486573