kzoacn's Blog

由于是渣笔记本的摄像头拍的所以大(gen)概(ben)看不清,要是航爷不发的话，过两天手打一下题面,自己做一下非官方数据

由于出现了一些奇怪的事情导致数据题解成绩以及选手的代码一直没有发，目测发下来要不少时间就自己做了一下数据

http://pan.baidu.com/s/1gdGj9Lp

[4.14]非官方数据+非官方题解出炉

[4.15] 官方成绩出来了，估计官方数据也快了

[4.15]bzoj上已经有官方数据了

[4.16]官方发下来的东西都已经放进去了

P.S. 本来打算把题面手打完再发到bzoj上去的,结果不知道怎么回事bzoj上就有了……

数据的正确性和强度不敢保证，src中的zky文件夹中测试了几个部分分的程序

题解:

1.orzdzy

2.dzy神犇的题解已经很全面了,蒟蒻来做点补充

【D1T1 排序】

dzy神犇写的是标算,航爷讲题的时候说可以证明最坏是 \(O(2^{2n})\)的

【D1T2 寻宝游戏】

标算是LCT或者链剖云云，由于没认真听讲忘记了……求路过的卢爷讲一下

【D1T3 序列统计】

集合中可能含有0……由于\(1\leq x\leq M-1 \) 所以无视它就好了

【D2T1 星际争霸】

……

【D2T2 约数个数和】

……

【D2T3 道路修建】

其实我们还可以利用mst环切的性质来做

考虑合并两个区间的信息,中间联通他们的是两个横向边

于是我们加上这两条边然后删掉环上最大边

环的形态一定是这样的

此图为合并蓝色边的左右两个区间,显然形成的环一定是非黑色线条的形态

于是我们只要维护每个区间生成树的最左右两端的竖向边的位置和竖向边到边界的max就可以了

合并时割掉最大边就没了