CSP-S2019游记

Day0

到了广州的瑞季悦居酒店,酒店设施显然不如从前(谁说之前的酒店烂的来着?),而且位置极为偏僻。
LJF甚至疑惑这家酒店设立在这里究竟是为了什么样的经济效益。
拼房时被人背叛,于是在高一中被挤出来。跟LJF一个房间。
晚上无聊下楼来健身房玩一玩,和一位看起来像大学生的人谈笑风生。
后来才知道那是左谭励大佬……我才记起来他还是最后一届GDKOI的出题人之一……


Day1

早餐还可以(尽管不如先前的酒店)
到了广州二中,很快进了考场。
开始了,解压密码输了我三次(原来是监考员写错了)
匆匆打开题目

看完了三题,开始搞T1。
T1很水,本来可以直接打,但我还是规规矩矩地写下了递推式(尽管没有花多长时间)。
后来检查的时候加了unsigned long long

过了样例之后直接去搞T2。
T2按照常规套路搞个前缀和。考虑计算某个点结尾的方案数(记为(g_x))。对于一个节点(x),若有祖先(y)满足(sum_y=sum_x),并且中间的(sum_k)都大于等于(sum_x),则方案数加一。
然后发现可以找到深度最大的(y),如果满足后面的那个条件,就直接(g_x=g_y+1)
于是线段树做法get√
接着很快发现,由于前缀和是连续的,所以只需要判断上一个(sum_x-1)是否在(x)(y)之间。如果在,那肯定不行。
最终打了(O(n))做法。
样例过了,没有打拍。两题只花了一个小时,自我感觉良好……

开始刚T3。
肯定是从小到大枚举数字,让每个数字移到它能到的最小的点。
然而要考虑它对后面的影响,比较麻烦。
分析了一波,感觉链和菊花都会了。
不管它,先打个暴力看看,后面还要用来拍……
这暴力还调了很久,原因是读入的时候读的是每个数字在的点的编号,我以为是每个点上数字的编号……
打完暴力中之后推正解。
想到差分约束,就是比较选择边的时间顺序,从先选的边往后选的边连一条边。搞完了之后拓扑排序就好了。
大概推了推:从(S)(T),假设路径为(S o u o...v o T)
(S)(T)中间的边都是从前往后连,
((S,u))连向跟(S)相连的其它边。
(打出来调了调后发现)跟(T)相连的其他边连向边((v,T))
(发现了什么?后来看了题解我才意识到,我漏了这样的东西:对于中间的(y o x o z),跟(x)相连的其它边要么在((y,x))之前,要么在((x,z))之后。这个东西不好直接差分约束,所以要对于每个点连出的所有边来搞个链表,具体来说,最先是哪些边,最后是哪些边,中间有哪些边是连在一起的)
各种乱搞各种调试,第一个样例终于过了前面三个数据,然而最后一个一直都没有过,于是这个伪正解就没有交上去(后来发现其实这样完全是可以把链的情况过掉的,可惜我没有将它和暴力复制粘贴到一起。血亏)

出来之后,周围的人都估分210。
(实际上,后来我才发现T1只有95分,因为1ull<<64居然等于(1)。我当时在自然溢出的角度上来看这一点,认为这个是(0)

下午的时候跟着高三的大佬们去了一下植树公园,在踌躇一阵后决定回来吃饭,再去广州奥园广场逛,然而发现对逛购物中心没有兴趣(一行人都是这样)。最终和LJF走路回酒店。


Day2

还是先看完三题。
T1没有一眼AC,很不爽。
T3似乎有点思路,但还是按照正常顺序来(后来我发现我错了)。

刚T1。
一开始真的没有头绪……听到旁边的人已经在啪啪啪,心中或多或少都会有些焦躁。
突然想到正难则反,求不合法的方案数。
然后搞出了一条性质:设出现次数最多(也就是大于(frac{k}{2}))的为(x),则(x)的出现次数大于等于其它的出现次数之和。
于是就可以搞出了一个三维DP(顺便吐槽一下,我有好长一段时间想着如何用多项式来搞,看那(998244353)很诱人
最后我发现,将这两个东西做个差,差大于(0)就行了。
于是DP减了一维,时间复杂度(O(n^2m))
这时候已经过了一个小时……
我太难了

刚T2。
没刚出来。
随便推了个最简单的DP:状态(f_{i,j}),表示最后一个区间为((j,i])的答案。
可以(O(n^2))转移。
刚不出来,只能看T3。

然后发现T3是道大水题。类似于这样的题之前是做过的。
将整棵树剖一下。对于一棵子树,重心一定在从根节点下来的那条重链上。
对于每个点,求出它的重儿子,它的重心从重儿子转移过来。具体来说,将重儿子所在子树的重心复制过来,然后试着往上跳一跳。
这样就很好地搞出每棵子树的重心了。
子树的补集的重心怎么求?
直接换根DP啊!
我先打了个暴力的(O(n^2))换根DP,然后开始刚(O(n))正解。
打代码和调试的过程很不顺利。正解没有调出来,于是交了暴力。
比大众分还低,血亏……


总结

总分大概400多一点吧……太菜了……
其实这次比赛时真的憋屈:Day1T3没有交伪正解,Day2T3没有调出来。
关于Day1,我想最大的教训就是打题要有些理性,不要太有激情。比赛时我甚至连最后两分钟都在调T3。实际上应该在最后五分钟的时候,将暴力和伪正解合并在一起,这样起码分数会高一点。
关于Day2,T3没有调出来显现出我代码的实现能力还不行。换根DP打得还是不够多(实际上这次换根DP的打法跟我平常时的打法很不一样)。
至于策略,其实我认为Day2在策略上没有犯什么毛病,因为当时我感觉自己真的可以切T3,并且实际上也不是特别难。如果当时我一开始就换种打法,说不定已经AC了。如果有毛病,只能说是我太在意题目的顺序(可能是平常的NOIplus模拟赛做多了,于是CSP-S中潜意识里告诉自己要按照顺序来),先刚T2再刚T3。事实上,如果实现不太难,先做后面的题再做前面的题也未尝不可。
Day2T2只想出了(O(n^2))的做法,而周围的人基本上都会(O(n lg n))
这是我能力问题吧……比赛时这题我也刚了很久的……在猜结论、贪心这一块,我是真的不行。

一句话——我还是太菜了

原文地址:https://www.cnblogs.com/jz-597/p/11878589.html