好无聊,然后就参加了洛谷7月月赛。
据说题目很简单所以是oi赛制?

T1

一看:啊!贪心!好水!
再看:啊!可以卡空间!
又看:不卡?太水了吧!
然后就交代码了。
因为如果有两个盒子里的糖果超过了$k$,那么优先吃后面那个盒子里的好些,因为后面那个盒子还可能产生贡献,但前面那个盒子不行了。

T2

一看:搜索?太水了吧!
然后就没有然后了。代码:

T3

做完T2就去吃了个午饭,回来看了一下T3,一眼没有看出题解,不爽。发现三十分暴力很好拿,枚举就行。后来发现70分暴力也很好拿,因为每个点之间的转移是O(1)的(这个见下),后来boshi说可能车站建在房子处一定能取最优解,我随便瞎写了写,发现样例3都过了(样例1的解释很坑人,因为车站建在坐标50也可以取最优解),于是就写了一个枚举车站的程序,后来下午无聊证明了一下:

假设在建车站的房子处有r个人,左边的路段上有A个人,右边的路段上有B个人。$A \textlesst B$
如果我现在把车站向右移动dis,那么答案更新量为$dis×(A+r)-dis×B$,显然是不明智的。
如果我把车站向左移dis,那么答案更新量为$disc×(B+r)-dis×A$ 如果$A \textless B+r$,不用移动,否则在移到下一个房子之前,肯定越往左移动,能获得越优的解,所以有r个人的那个房子不会是最优解。
综上:车站建在一个房子处可以得到最优解。 那么枚举每一个房子即可。

后来听boshi大佬说其实就是在人数中位数处的房子是最优解,我发现接着我上面那个证明也可以证。既然A>B+r的时候就可以继续左移获得更优解,那么左移到中位数位置不就没法继续移了吗?
我当时交的程序:

T4

懒得想了,打了30分暴力走人。
下午大jay形说是并查集,然后我一开始想到了并查集,觉得很有道理,所以就愉快的开始打。
打了一个小时后,出了组数据把自己HAKE掉了,因为我是对于点进行并查集,在水改陆地的时候直接删掉这个点,但是如果这个点是一个集的父亲节点的话就会出大问题,后来和boshi还有大jay形讨论了一下(这不会算集体作弊吧QAQ)说可以不用删掉节点,直接缩小这个集的大小即可,感觉很有道理,于是我愉快地改了改,用上午打的暴力进行对拍,80分?诶诶诶?
boshi也借了我的暴力去对拍(又是集体作弊QAQ),他的程序70分,好尴尬。
最后boshi检查数据发现数据有分割两块温泉,他很高兴地说那应该没问题是数据的锅,于是我就把新程序交了。
最后结果出来我50分,boshi 40分,很符合对拍结果QAQ
考后看了题解,原来并查集不是对于每个节点做,而是对于每个节点所在的连通块做,这样即使这个连通块里已经被删的没有节点了,它还是可以作为一个虚拟父亲存在,就不会出现问题。
好吧,就这样,AC代码: