CSP2022游记
Assembly_line
·
·
个人记录
upd on 11.8:
感谢ccf送大分
85+85+65+44=279，省内rk79
Day -2
(10.26)
明天期中考，决定裸考
但愿不要因为疫情挂掉（
Day 1
(10.29)
早上7:20一些初一的还在拿准考证，很不爽
但是jy的神速车7:40就到了jz
在车上喝了一瓶咖啡，真不错
考前到处问中缀怎么转后缀
8:27开考，密码是mountain2022
T1签到，T2可以得出p+q，pq，想到可以二分
T3是表达式，直接蒙中。T4瞬间想到dp，看到n\leq500,k\leq100直接过
9:00开做，慢慢做到9:45，开始想T3，想到可以建出表达式树，然后直接做
但是想到不会建表达式树，只会转后缀表达式（考场推出来了）。想到可以通过后缀和中缀确定表达式树，于是先求后缀表达式再建树
慢慢码，码到10:40就全都过了，于是开始欢乐检查。11:40开始吃吃喝喝。感觉能AK
中午和pmx，mzx，zbh延续CSP传统，开始欢乐扑克
下午考前状态不好（蒙一下密码water2022）
14:26开题，密码是belief2022
看完题发现一道都不会做
首先T1不同的景点很难搞，想到可以维护每个C->D->1时D点权的最大值，次大值，次次大值，次次次大值，于是确定A,B,C后就可以O(1)算答案了，这样复杂度是O(n^3)的
然后T2n\leq1000的部分显然，可以看做每行中的最小值取最大，拿个线段树维护一下就行了。考虑特殊性质1，容易发现第二个人肯定取B的最小值，第一个人肯定取A的最大值，ST表维护即可。然后是特殊性质2，若l_1=r_1，也就是第一个人一定取A_{l_1}，若A_{l_1}<0，第二个人就取最大值，否则取最小值。l_2=r_2类似
然后直接去看T4，容易发现k=1的情况即为求两点间点值和，树上差分容易解决。考虑特殊性质，想起性质即为树高为O(logn)。又考虑k=2，玩一下可以发现经过的点必定在两点的路径上，于是可以设f_i为s走到i点的最小代价，简单转移和计算即可，对于满足特殊性质的测试点，可以每次O(logn)解决
回过头来看T3，两个条件即为：1.能走到环上，2.出度为1。想想发现满足条件的图必定长成这样：
也就是环上挂了一些节点（可能有很多个这样的环）
又发现只要满足了条件2就可以判断合法，大概感性证明了一下。也就是现在要维护每个点的出度，$n\leq1000$可以简单暴力
然后考虑后面的测试点，感觉可以用数据结构维护出度，莽了一下发现已经17:40了，感觉写不完。于是删了，把$t=1,t=3$写了，开始检查
结果就是一道正解都没写，但是task打满
估：70+85+50+44=249
赛后：
普及讨论了一下发现T3只有我一个人建了表达式树，别人都直接用后缀表达式做，不知道怎么做
T2发现知道p+q，pq可以O(1)算答案，$(p+q)^2-4pq=(p-q)^2$，于是知道p+q，p-q就可以得出p,q
提高发现很多人没写T3，但是本届有一个人说自己能过T3（害怕）。lyx说他爆切T1%%%，发现T4$k=3$直接跑最短路就能骗十多分了
看了一下网上的题解，发现T1差一点就想到正解了，可以枚举B,C，然后用最大值，次大值，次次大值，直接算答案
upd10:30:T2就是个分类讨论，感觉T4可以倍增做
感觉还可以多拿30多分
小图灵普及：400
infoj提高：85+75+40+44=244
坐等欧欧镑出成绩
upd on 10.31
上洛谷估分，普及400，提高85+85+40+44=254（感觉T1数据水了）
infoj提高：80+85+40+44=249
wzx和lmd普及都挂分了
总的来说，这次提高感觉一般，T1T2不难的正解没有深入去想，T3有一个task挂了，T4没有想到写最短路。也就是要加强简单题的过题能力和难题的骗分能力