CSP-J/S 2020 游记

DAY 0

天边云卷云舒,散去了期中考前的紧张气氛。

收拾完了所有卷子,踏着夕阳回到家,忘记了板子,忘记了算法,忘记了一切,倒头就睡,希望第二天能够不爆零

DAY 1 Morning

城市清晨的雾气弥漫在街上,随着旭日的东升渐渐退散。

草草的吃了早饭,来到考场。

窗外阳光正好,但是电脑屏幕上的反光让我很难受

题目下发了,解压出来一看,我:哈哈哈哈哈哈...(你看他在狂笑!),肯定又要爆零了...

花了十多分钟的样子大概弄清了这套题,然后决定一道一道切。

第一道题还是蛮友好的,但是似乎对xxs们就不那么善良了...(幂的性质和二进制是小学几年级学得来着?)。 总之,『位运算』什么的瞎搞就行了...

第二题也还好,动态插入元素的第 $k$ 大,$k$ 还是递增的,元素还是不超过 $600$ 的,当然,用什么 『平衡树』『权值线段树』『权值树状数组』『对顶堆』什么的都可以搞定,不过还是有点大材小用了,其实只要开个 $600$ 的『桶』,然后暴力维护就可以了,也没啥好说的...

(P.S:途中脚不小心碰到了插头,万幸的是只是碰到了显示器的插头,所以没有出啥大事。)

第三题难度就瞬间飙升。后缀表达式?什么鬼?早忘了...当空的艳阳洒进考场,带来了温暖与焦虑。所幸的是曾经 $qty$ 巨佬曾教过我后缀表达式转成一棵树,然后沿着这个思路探了探,似乎有戏,于是就做出来了...

做法 (建议跳过)

建出原后缀表达式对应的树,对于每一个节点维护 $f[u][0/1]$ 表示当该字表达式的值为 $0/1$ 时,整个表达式的值为多少。显然,$f[root][0/1]=0/1$ ,然后自顶向下地『树形dp』即可。

第四题...没啥好讲的,没看出来『dp』,就乱写了半个多小时的『BFS』,大概思路是不经过重复格子等价于不走回头路,那就维护 $d[i][j][k]$ 表示走到 $(i,j)$,并且来时的方向是 $k(k\in\{0,1,2\} )$ 的情况下的最大价值,然后就来了个『优先队列』乱搞...(最后似乎有ACWATLE...)

DAY 1 Noon

中午随随便便找了一家饭馆吃了午饭,然后偶然乘兴,提前到考场,碰到了 $zyw$ 学长,如今在七中高新。聊过之后又碰到教练,然后就没有然后了...

DAY 1 Afternoon

因为桌子比较高,所以敲键盘的时候手挺难受的,我就在考试前在桌子上趴了一会儿。

题目发下来了,我又笑了:哈哈哈哈哈哈...(你看他在狂笑!),肯定又要爆零了...

T1大模拟,没啥好说的,但是耐心和体力是个问题,所以我果断放弃。最后一个小时的时候才开始写这道题...

T2是个挺普通的组合计数问题,因为每个二进制位之间没有直接的关联,所以直接按位乘法原理求出所有可以养的动物有多少,再减掉已经养了的动物就好了。但是可恶的 $k\leq64$,于是我开了 $unsigned\ long\ long$,然后,还自己造了一个 $%ulld$ 的输出,然后完美爆零...

T3题目看懂了,但就是不会,于是建了个图,跑了一遍每个点的等效操作,然后就跳过了...

天色渐晚,终于开始做T4了...感觉还是不是特别难想,部分分还是好拿。

做法

模拟一遍所有蛇全部都选择吃下去的过程,再来考虑哪些蛇会后悔。显然,最后剩下的那只一定不会后悔,因为它吃了尽量多,而且还没被吃掉。但是其他被吃掉的而且还有能选择的机会的蛇肯定会后悔,因为它们被吃掉了。所以当轮到某条蛇做选择时,给它打个标记;某条蛇被吃时,若它有标记,则证明它会后悔,加入一个栈。结束后从栈顶开始考虑,若它已经安全了,则跳过,若它还未安全,则将它吃的最后一条蛇置为安全,更新最终答案为它最后一次吃蛇的时候还剩的蛇的数量。最后答案就是最后剩下的蛇的数目。

但是这样做的时间复杂度为 $O(Tnlogn)$,显然过不了所有数据,但是作为tgT4来讲,我能拿到这70pts已经足够了。

DAY 1 Evening

橘黄色的路灯也抚慰不了我慌张的心,回家再次倒头就睡...

DAY 2

拿到代码测了以后,感觉天都黑了...

pj:310pts tg:130pts

$\colorbox{gray}{\colorbox{lightgray}{\texttt{退役}}}$$\colorbox{gray}{\colorbox{white}{\texttt{继续}}}$


发表于 2020-11-08 12:04:47 in 未分类