CSP2019总结

CSP2019总结

前言

赛前停课集训了两个星期,自认为已经准备充分了,结果...

不知道有没有写挂分,即使一分没挂,满打满算也只有400出头,还是太菜了。

Day0

晚上复习了一会,打了会游戏就睡了。

睡得特别香。

Day1

这次早早地到了考场,但是被告知不能试机,就补了一会觉。

然后就开题了。

T1

题目有点长。看完之后发现是一道水题。

从高位开始放,递归一下就好了。

由于不知道怎么读入usigned long long,就打了一个快读。

T2

感觉好神仙的样子。

维护一个栈表示根到当前节点的括号序列,左括号用1表示,右括号用-1表示,维护栈的前缀和。

然后发现,对于一个点,设它的前缀和为x,它对答案的贡献就是,从栈中第一个等于x的数开始,往后的等于x+1的数的个数。

找起点用线段树,找个数用主席树。

打到十一点半。

忘记开大栈的编译选项怎么打的,大样例没测。

T3

没时间想了,拿了10分的暴力分走人。

心态小崩。

赛后

似乎没几个人T3拿到高于10分的成绩,所以似乎局面对我很有利?

T2我想复杂了。线段树可以用倍增来代替;由于确定了起点,需要在后面查找的数也确定了,所以主席树可以用桶来代替。

太naive了。

下午打游戏,背了一下开大栈的编译选项。

Day2

T1

我讨厌计数。

想了很久,怎么把m的指数去掉,结果发现选的次数大于k/2的最多只有一个。那就好办多了。枚举t不合法,设f[i][s1][s2]表示t选了s1次,剩下的数选s2次的方案数,84分到手。

然后就不会优化了。

T2

一看数据范围就知道正解肯定是O(n)的贪心,但是想不到怎么贪。

开始想\(n^3\)的dp,设f[i][j]表示选的最后一段首位,转移显然。绝望地发现这样只有36分。

然后发现f有单调性可以优化掉一维,多了28分。

T3

\(n^2\)暴力很显然,好歹我也是打过点分治的。

链的也很显然。

然后就没时间了。

赛后

T1可以把状态改为s1-s2,这样就可以切了。

T2其实考场上我发现的那个单调性就是正解用的那个原理。

T3的满二叉树的20分其实比较简单。

小结

这次比赛应该没有出现太大的问题,没有出现像上一次NOIP的时候那样的策略失误。其实我已经把能拿的分拿完了。

但是也暴露出我的实力的不足。两天的T2都没有想到很好的做法。

等分数出再写

上一篇:通过C#中的位掩码存储多个值


下一篇:致后来者——长梅Oiers