CSP2019 游记

作者: xht37 分类: 游记 发布时间: 2019-11-15 14:12

点击数:2436

one last chance

Day 0

一觉睡到中午,感觉明天早上要起不来了。

吃过午饭,带着 wjyyy/ouuan/EternalAlexander 的 XR 抱枕冲到华科。

由于到的比较早,所以试机的地方还没有多少人,随便找了一排坐下。

然后华一和外校的到了,面了 ustze/EternalAlexander,然后惊奇的发现没几个认识的人了。

突然想到这是我参加的第一场没有 wjyyy/Dew/lbw/hyf/Vixbob/Edt 的 OI 比赛,有些伤感。

随便敲了点板子,对拍了一下,感觉没啥问题,除了键盘极其不习惯以及好久没用 Win7 了很自闭。

走的时候叫 EternalAlexander 把 ouuan 和他的抱枕都拿走了,zgjjj 带走了 wjyyy 的抱枕。

然后就回家了。

今晚要早点睡,大概十点?虽然好久没有用这么早躺下过了,鬼知道睡不睡得着。

CSP2019 rp++!

Day 1

果然混到两点还没睡着。

但是早上六点爬起来感觉精神状态还不错。

吃完早饭冲到华科,面到了 quank 和 KS。

然后就进场了。

进场之后先检查机器,打了板子码了快读,然后拿快读和 cin 的 a+b 拍了半天,感觉没啥问题。

然后发密码 Ren2Zhen0Si1Kao9?

认真思考 2019?

奶一口明天 Zi9Xi1Da0Ti2!,好像短了点 2333。

然后看题:http://www.xht37.com/wp-content/uploads/2019/11/CSP2019-S2-day1.pdf

T1 读完大概就知道是个简单模拟了,看了看数据范围,$n \le 64$,感觉有坑。

码码码,一测大样例,果然挂了,发现是 1 << n 的锅,改成 1llu << n 就过了。

然后造了一组最大极限数据一测,没挂,很稳,扔了。

开 T2,咋 T2 就来树啊。

读完题,感觉上就不太难,大概想了几分钟就会了:

考虑以每个节点为结尾的合法括号子串有多少个。

( 为 $1$ ) 为 $-1$ 做一个树上前缀和,设点 $x$ 的前缀和为 $s_x$。

则以 $x$ 结尾的合法括号子串的开头 $v$ 需要满足:

  1. $s_u = s_v$。
  2. $v \to u$ 的路径上所有点的 $s \ge s_u$。

遍历一遍树,用一个 $c$ 数组记录从根节点到当前节点的所有 $s$ 出现的个数,同时用一个 $p$ 数组记录每一个 $s$ 上一次出现的位置。

那么对于一个点 $u$,以 $u$ 结尾的合法括号子串的个数应该为,在点 $u$ 的时候 $c[s_u]$ 的值(去掉 $s_u$ 本身)减去在点 $p[s_u-1]$ 的时候 $c[s_u]$ 的值。

前者可以直接加到 $ans_u$ 中,后者则需要等到回溯到 $p[s_u-1]$ 再从 $ans_u$ 减掉,用一个 vector 记录即可。

其中,更新 $p$ 数组时,需要用一个额外的变量记录更新前的值。

总时间复杂度 $\mathcal O(n)$。

思路理清后,代码很快就打完了,然而一测过不了样例一。

一查,最开始的时候要将 $c_0$ 设为 $1$,因为本质上这是个差分。

然后顺利过了样例一二,再测第三个样例的时候爆栈了。

举手问了下监考给不给开栈命令,发现不给,然后使劲回忆,好像是 -stack,--Wl=1073741824

一开,CE 了。

然后慌了改成 -Wl,--stack=1073741824 就 ok 了(大雾。

嗯,大样例过了,很稳,扔了。

这个时候才过去不到一个小时,还有 2.5h 刚 T3?嗯,很稳。

然后就自闭了,T3 只能拿个 10 分。

出来的时候感觉要凉,这个 Day1 怕不是全场 AK,就我 210 T3 暴力滚粗。

然后一出来,感觉好像似乎或许这个 T3 没几个人 A 掉?

这样的吗…

这还是 NOIP 吗…

哦不是,这是 CSP…

吃饭的时候,C 的题解出来了:https://www.zhihu.com/question/351347604/answer/896344216

啊,神仙贪心。

话说贪心怎么一年比一年考得难啊,想想曾经的「国王游戏」。

然后 T1 OI-wiki 上居然有:https://oi-wiki.org/misc/gray-code/

看群里都在讨论 T2,据说那个大样例水得一匹,于是开始慌,我为啥不对拍一下啊,懒惰死了。

结果下午拿到了程序,牛客、信奥题库、洛谷、CSP.ac 都测了一下,都是 210,嗯,很稳。

顺便测了一下别人的程序,emmm…

Day1 考得还可以,但想到去年 NOI 的时候,也是 Day1 海星,Day2 就爆炸,心里还是有点虚的…

希望明天自己能够正常发挥吧。

CSP2019 day2 rp++!

Day 2

密码是「抓紧时间」。

题目:http://www.xht37.com/wp-content/uploads/2019/11/CSP2019-S2-day2.pdf

开 T1,想了一会儿发现没啥正解思路,打了 64 就扔了。

开 T2,想了一会儿发现没啥正解思路,打了 36,输出了一下转移发现了些性质,就改成 64,然后又扔了。

开 T3,想了一会儿发现没啥正解思路,打了 75,然后又扔了。

这个时候过了不到 3h。

然后就开始在 T1T2 剩下的分中纠结。

然后考试就结束了。

下午测,还是那四个地方,$64+64+75=203$,一分没挂,一分也没多得。

问了下别人的分数,感觉全世界都吊打我。

这个 T1 就是一个极度简单的容斥,可是我脑抽了。

唉,还是技不如人吧。

两天加起来 $413$,没去年高,不知道能不能去 THUWC。

我已经高二了。

Day 3

中午才爬起来…

听说马上要合格考了,考政史地,全省前 $98\%$ 能过关。

看起来快要没学上喽。

测了下全湖北的代码,没测完,只测了一半,就感觉很凉…

jxl 535,ouuan 也铁定比我高。

某神仙和 ylh 看上去大概率比我高,如果 T1 数据不强的话。

一半就把我搞到第五去了。

我想去 THUWC,想上 THU;我想湖北前四,我想省队拿 A。

可能,就,都没了吧。

心情很糟,不写了。

4条评论
  • 万弘

    2019年11月17日 下午9:05

    D2T1一眼看去就嘴巴道”容斥”,然后得到了1h0分的好成绩.

    1. xht37

      2019年11月17日 下午9:08

      Orz

  • OrientalHorizon

    2019年11月25日 下午9:02

    请问(unsigned long long)11ull还是1llu呀,Dev 都会高亮,但是 LOJ 的编辑器上只会高亮1ull

    1. xht37

      2019年11月26日 上午1:25

      都可以

发表评论

电子邮件地址不会被公开。 必填项已用*标注