CSP-J/S 2020 游记

小柯

2020-11-08 12:04:47

Personal

# 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\} )$ 的情况下的最大价值,然后就来了个``『优先队列』``乱搞...(最后似乎有``AC``有``WA``有``TLE``...) # 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{继续}}}$