2022.9.18icpc网赛
https://pintia.cn/problem-sets/1571150153619189760
第一次参加正式的icpc比赛,尽管最近一直在打abc练手,但感觉还是力不从心.一是对icpc没有部分分的模式还不太熟悉,二是和队友的配合不够默契,三是码力下降不少,有两个本来可过的题寄了.幸亏队友还给力,一起口胡最后A掉4题.
L
开的第一个题,第一眼就是sam之类的字符串转移,直接跑了.后来和老哥一起分析时又口胡建图,猜了一手结论:每个点只用向最近的同一字母转移.
建图的思路没错,但是连边的可行条件分析没分析到位,直接判是否在t串中相邻,实际上应该把t串中前后全部字母组合ban掉.于是痛挂一题.
H
倒序开题没有思路,跟榜去做签到题.直接用栈模拟操作,1发A.
A
乍一看毫无头绪,不过数学大佬点明了关键性质,一块连续的1只有$(len+1)/2$个”有效1”.每一个”有效1”能消掉3个元素,若一个串中”有效1”不足$1/3$,z则需要操作补1.区间染色,前缀和求和,复杂度$O(q)$.第一发T了,加了个快读就直接过了
C
考场上队友切掉的.答案就是叶子节点个数.
这个做法的正确性:对于所有的叶子节点,只能采用delete.考虑整棵树对每个节点只留下一个叶子,其余的全部删掉,然后shrink所有的单链,不断重复这个过程,可以发现所有的非叶子节点都可以被shrink.可以得到需要delete的只有叶节点
D
在考试时看假了题,以为是01个数相等,还差点误导了队友,最后s大佬切了.
考完再看这题才发觉是水题,直接dfs预处理,二分答案即可.
K
由于太菜只会$n^3$dp,于是想到了记搜剪枝.但是剪枝的条件并没有思考完备,白白的写了半个小时的假题,不仅没想出怎么优化,最后甚至正确性都没有.似乎有神仙乱剪过了,后面再找std看看吧
G
同样,由于太菜,只能想到裸暴力dp.一直在纠结$n^5$的复杂度,却忽视了选取多个连续时实际状态并不算多,写完心虚不敢久调,又浪费时间写了假题.
这场满打满算可以切掉7题,尽管第一次正式赛失误无可避免,但只搞掉4题还是有遗憾.根据最近打的3场比赛,目前最主要的目的并不是复习一些高级算法的用法,毕竟几乎用不到,而是多做一些dp,搜索之类的需要处理边界条件的题目,很久没做题带来的生疏大概就体现在细节不会写了吧.