BZOJ4817 [Sdoi2017] 树点涂色

题目链接

Solution

这题很???
我们把相同颜色的点之间连的边看成preferred edge
那么操作1就是access
查询的时候用链剖维护一下区间最值就行了。

Hints

然而LCT写挂了两次
先是rotate的时候把一个x打成了k,
然后是splay的时候没有判isroot(fa[x])。
一些注意的地方:
1、LCT和链剖的father要分开记。
2、access的时候要注意处理now断开的那部分子树。

Code

SCOI 2018 不知道干了什么记

省选复习

做了10联测,感觉被大佬们各种虐,有种省选完挂的预感啊。。。

上了OJ才发现自己rating好低。。。炫酷蓝紫色。。。

期间做了ZJOI Day1和一些不知道哪里来的题,看题发现自己啥都不会,只会暴力。。。

然而做完以后发现自己并不会暴力,只会瞎骗分。。。。

然而评测的时候发现,自己并不会骗分,只会报零。。。。

总之就是被各种吊打,只有最后一天的题稍微良心一点。。。写了傻逼的T1和T3.。。但是好像有很多人AK。。。。

省选集训 (Day -4 ~ Day -1)

Day -4

上午去神大ACM,只A了3到签到题。A迷之wa,交了十多发都被卡在了第11个点。。。。

佬队AK后提前离场了,吊打神大,%%%。

下午去中和中学。。好偏僻啊。。听说是在一个镇上???!!!

没去学校看,直接去酒店了。。。

Day -3

上午去听课了??不知道哪里的人来讲的。

讲的线性基,感觉好水啊。然后就开始突突突。

下午上机练习。中和的电脑配置看起来不错,但用着挺糟糕的。。

花了半个小时配环境(大半时间实在卸载。。)然后开始突突突。。

晚上会酒店,看了会儿题,然后突突突。。

Day -2

和前一天好像没啥区别。。

下午lxs发了一套题,把T1、T3写了。。

Day -1

同上

不过这次写的是T2和T3

Day 0

上午起来好困啊。。

以为是下午才模拟考,导致前一天晚上睡得晚。。。

T1傻逼DP。。写了2小时。。。我好菜啊。。(后来发现状态数多了一点,写复杂了。。但是懒得改了。。。)

T2会一个线段树上二分的log方做法。。。然而数据范围很水的样子。。好像这套题里所有的n都没有超过1e4的(雾)

于是写了n方暴力。事实证明我并不能够卡过。。。

T3好像是维护一个最小割。。并不知道怎么维护。。时间也不太够了,就写了一个网络流加一点小优化。。

结果T1T了3个点(真心慢),T2T了4个,T3T了2个。。。

然后下午去神大天街。

好好睡了一觉。

Day 1

早上起的很早,有点困。到了神大,发现两边都坐的是石室的。结果两人都进队了。被支配的恐惧有没有。。

T1写了4个小时。。乍眼一看以为是一道傻逼题。先是想用链剖维护,发现不会。然后又上动态点分。码了两百多行一测样例,然后想了想发现不对。然后觉得是道树套树裸题,发现写不来。

最后写了个跟树深度有关的方法,事实证明出题人没有恶意卡。

然后看T2,推了一下,发现是个二次剩余。但是模数1e16,觉得没法做。最后放弃了,写了个55分暴力。

然后看T3,发现不会。瞎写了一下。

然后,开始绝望。。

最后10分钟突然发现T2要乘爆long long,没时间了,果断选择不改了、继续绝望。

最后75+15+0

但是看大家分好像都很低的样子。。然而佬还是那么高,255碾压全场。。

Day2

密码好像是什么吃葡萄不吐葡萄皮。

T1发现是线段树维护一个凸函数。。看起来不是那么好写。。先放着。

T2计算几何??放弃。。。

T3是个什么玩意儿。我只会10分好不好。再看了一遍题,确认无误后,果断选择放弃。。

然后开始码T1。写了大概1h,调过了大样例。然后开始对拍。

可能是我的写法太丑了,对拍居然发现了4个错。。

然后调完,发现常数大。。可能要跑4、5秒。

各种卡常。

最后30+0+0.

Day 3

省赛完挂,退役AFO
要是明年再这样就真GG了