csp2019前后

csp2019前后

第一次参加csp,好紧张

初赛

非常怕初赛炸,所以赛前每天做一套找回感觉,不出意外高三也想去玩所以记录一下错题好了

14年真题成绩:63,错题:说多都是泪

15年真题成绩:88,错题:「指针相关」、「27题填最后一个空的时候忘记读题意时看到的间隔1了,以后做完每题应再看一次题意」

16年真题成绩:92.5,错题:「地址总线宽度是w位,内存最多为$2^{w}$,然而脑抽觉得kb和字节之间还有个叫k的单位……」、「28题错最后两空……」

17年真题成绩:89,错题:「不想算日期」、「稳定排序相关」、「射线题在最后一步算错gcd」、「27题空1空5」

18年真题成绩:78,错题:「不会T17」、「T18算错」、「康拓展开时最后3位求稳手贱去手算,结果算了第4个而不是+4,光荣白算」、「23题空1」

最终成绩:91.5,错题:「并查集x!=y,-1.5pt」、「cin无法读空串,-4pt」、「取石子的dp初值(至今懵逼),-3pt」

报名

似乎是一些奇妙的原因(我能不能赖输入法啊)名字前多了个空格,然后考号就变成GD-00004了……

我去我现在想起都感觉很难受,要是真作废了怎么办,希望只看身份证

Day0经历

一天都在听歌+看书,晚上看了萤火之森和玉子的爱情故事,十点出去跑了一大圈步顺便思考着大春物的种种,感觉心态极为平和(flag)

Day1游记

发现t1比历年简单很多就细看了很多次题意,怀着忐忑过了大样例;

t2没有一眼秒,细细推了一会,然后又写错了一处导致调了三四次拍才彻底注意到,此时剩2h觉得按历年看时间够用

t3感觉链和菊花具有指向性,过了足足1h才会链而依然想不到菊花,此时有点慌,又想了20min还是不会菊花,此时彻底懵逼了,模型一直在考虑交换来最小化字典序所以完全不知道阶乘做法怎么写(现在感觉自己炒鸡睿智的说),绝望中30开写链55才过样例感觉不太可能有分了,出来的时候看湖面都感觉是灰暗的,毕竟上限都比去年少70,想着一些「大家像去年对pp一样对我说你怎么回事」之类的展开

中午吃饭发现我校全都垂头丧气,似乎标配是210,下午和可爱的弟弟玩耍+和qzz/sakits去看天气之子(我觉得比昨天两部加起来好看)+晚上和胡策联盟十八人盛大面基(分两桌成败笔,气氛全靠mld)让心态逐渐好了很多,以及某人可能的关心

当做noip只有一天就好了

Day1题解

t1是个模拟但需要注意一下unsigned的问题;

t2将括号反转后从每个点出发考虑向上,只需要统计包含最后一个括号的新增子串,括号不溢出的条件就是向上跳的链前缀最小值非负,符合这个条件的一定是段前缀,二分找到深度限制,然后我开了n个vec去二分判断有多少个合法端点,$O(nlogn)$;据出题人说大的数据只是卡了卡复杂度,所以可能小数据暴力+大数据乱搞有高分?rqy给出了一个线性做法

t3的链因为没时间拍并不知道对不对

正解做法:code

考虑一个数从x想恰当地移动到y,直接去移动是不行的,这时候一种很有用的思路就是考虑究竟带来了哪些限制条件

第一条边必须是与x相连的边中第一个被删的,最后一条边必须是与y相连的边中最后一个被删的,而且对于中转节点t的路径上两条边,一定是一条紧接着另一条被删除(注意以上所有的时间,都是以公共点作为参考系而相对的)

想出这点(本质上就是将每个点作为参考系后限制独立)后基本上就做完了,从小到大枚举每个数字按位确定,在树上dfs找到能去的编号最小节点,边走边判断我新增加的限制是否会导致「对于每个点相邻的边,隐式建图后是若干条链」的性质被破坏(显然是能构造出方案的充要条件),因为是一棵树我们中途判断限制的时候并不需要做修改,因为这个参考系在本轮dfs中不需要再考虑了,关于这部分怎么写代码中有注释

疑问:一定能保证以后不会出现「某个数没点可去导致边删不完」的问题吗?故搞个并查集维护链的大小(其实在确保不会成环的时候已经要写并查集了),用siz确保合并的时候不会导致一条链过早形成(因为本题是对最后链的头尾有具体限制的)

讲道理这个大致思路(即不说上述具体实现)如果告诉我是对的,我能很好理解其正确性,但如果我自己想出来,大概会被我莫名叉掉,因为感觉正确性并不显然

时间复杂度为$O(n^2+n \alpha (n))$

Day2游记

t1居然是计数题!40min

t2算是我的翻盘题(感谢myy),果断先写$O(n^3)$暴力,观察一下式子发现记录后缀max已经可以$O(n^2)$了但并没有减少状态规模,换一种思路发现也可以$O(n^2)$,因为写了暴力验证一些结论啥的很方便,再推推可以$O(nlogn)$了,可以获得88,剩1.5h,决定先看t3

怎么感觉ZR国庆集训讲过,当时口胡了来着,想了10min不记得了。总觉得应该不会很好写吧就像去年d2t3一样,加上似乎可以直接获得75以及感觉t2如芒在背很难受,于是又回去看t2了,稍微冷静一下发现可以单调队列,于是时间降低为线性,但空间不会解决……等下!发现我sb了,前缀和数组是不需要开高精的,只有f需要(1e31),而我的做法计算转移点的时候并不需要f,所以矛盾点只有f,那么做完单调队列从n开始把分割点拉出来得到一个序列(其实就是直接计算出分割点了),只需要保存序列上一项的f值递推!然而很久之前uoj上有仙人说int128可以两ll代替是咋搞啊不会啊,写4个ll会不会很慢啊相当于带个log吧,咋办啊啊啊

此时只剩1h而只有188,只好先写t3的40pt暴力,然后发现15pt的链很好写,进而发现20pt的二叉树更好写!感谢不知是谁的出题人救了我一命,忽然有了信心

剩30min,仔细想想发现求平方、加法都是4而不是16的常数,woc为啥这个输入这么麻烦啊,测了发从样例3改的随机极限1.6s,看到评测机这么神应该不会读入很慢吧(flag)就不管了,剩几min默默写下退役快乐

Day2题解

t1相当于每行最多选一个数,每列不能选超过别的列之和,注意到每种方案非法的最多一个,枚举是哪一个直接做就是$O(n^3m)$,注意到并不需要背包出选了多少行,直接看「在这列选」-「在其他列选的和」>0即可,$O(n^2m)$

t2
$$
\\ f(i,j)=(S_i-S_j)^2+min_{S_j-S_{lst} \le S_i-S_j}f(j,lst),
条件其实是S_{lst} \ge 2S_j-S_i而S递增,能转移的lst是一段后缀
\\设pp_i=能使f(i,j)合法的最大j,g_j=2S_j-S_{pp_j},能从j转移当且仅当g_j \le S_i
\\此时感受一下f(i)合法位置是递减的(合法位置不一定连续),这点我并不会证明,假定是对的话一定从f(j,pp_j)转移
\\猜到这个结论后就是f(i,pp_i=j)=\min_{g_j \le S_i} f(j,pp_j)+(S_i-S_j)^2
\\然后感受一下肯定在能选的里面选最大的j,单调队列优化就是线性了
$$
证明的话假如会了就补上,刚写的代码

1
2
3
4
5
6
fo(i,1,n)
{
while(tou<=wei and s[que[tou]]+s[que[tou]]-s[pp[que[tou]]]<=s[i]) now=que[tou++];
f[i]=f[now]+(s[i]-s[now])*(s[i]-s[now]);pp[i]=now;
while(tou<=wei and s[que[wei]]+s[que[wei]]-s[pp[que[wei]]]>=s[i]+s[i]-s[now]) wei--;que[++wei]=i;
}write(f[n]);

upd:myy的题解考场代码

upd:卡常并修锅后代码

t3

重心的显然结论1:一定满足$2(n-siz_x) \le n即2siz_x \ge n$,很明显满足这个的肯定是一条链(在根所在的重链上),重心一定是这条链上深度最大的,双重心的话一定是这个点的父亲且充要条件为$2siz_x=n$,我们先考虑怎么求出这个点,再去判其父亲

注意到求子树内重心其实是可以线性的,记录$f(x)=x的子树重心$,根据上面说的,$f(x)一定是f(x的重孩子)的祖先$,直接向上跳,复杂度等于所有重链长之和。因为下面只说怎么计算子树外

做法一:金华讲过故rose写的这个,直接线段树上维护siz二分找合法点中dfs序最大的节点,枚举每条边用树剖修改siz,log方

做法二:重心还有个结论,在一个点权为0/1的树上考虑带权重心,记下两个不重点集各自的任意一个重心,点集并的所有重心一定都在这两个重心的路径上;于是很容易想出log做法,假设已有函数$merg(a,b,al,ar,bl,br)=dfs序[al,ar]的重心为a,[bl,br]的重心为b$,那么预处理出dfs序前后缀点集的任意一个重心,直接枚举树边合并点集就好了。注意到任意一个点的带权siz可以$O(1)$计算,那么分别在a和b的链上倍增找到最深的合法点,并选两边中最深那个即可,常数为3*2需要小小卡个常才能在luogu过最后一个点(其实如果你把求前缀和后缀用dfs实现,记录当前处理的点,其每个祖先应该向哪个孩子跳,那么重心指针的移动是线性的,应该就不用卡常了,常数降低为2),code

upd:我的代码官方数据下loj能过uoj不行,而且被rose的log方做法教做人,乖乖学线性做法,好写得夸张

做法三:记整棵树的重心为r并作为树根(因此$\forall 2siz(son_r)<n$),记其重儿子为$w_r$

当删除不在$w_r$子树内的点的子树时,根的重链完全不变,对每个wt预处理出在那条重链上最深的$2siz(p_i)\le wt$,$O(1)$回答询问

当删除在$w_r$子树内的点的子树时,可能影响较小根的重孩子还是$w_r$,然而考虑到一定满足$2siz(w_r-now)<n-now$,新的重心为r;当删除子树影响较大,重孩子变为次大的$v_r$,注意到$v_r$所在重链也完全不变,这个也预处理一次,也是$O(1)$回答

后记

总之估分就是100+100+(0~25)+100+100+75=475~500,E=476

为什么每次比赛完回到机房写游记的时候都是我一个人啊

upd:D2T2高精度写得有点丑,被真实地卡了8分(本机4s少爷机并跑不过去,太高估了),最后467

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/1634d012.html
转载请注明出处,谢谢!