Day -35
提高组初赛。
竟然只有一道 Linux 命令题。(巴不得全考 Linux 命令)
base64 其实不难理解,然而自己实在是不想模拟解码 (实际忘了 ASCII 码表),随便蒙答案。
从来没接触过笛卡尔树,然而还是勉强看懂了。
Day -3?
出成绩了。89.5pts。
Day 0
wyz,gc,Eason 打摆被抓(默哀)。
我不会说是 wyz 问我 super mario 在哪里能玩的
幸好只是看了些文字类的东西,幸免于难。
高情商:看学术文章 低情商:看知乎娱乐
Day 1
睡得还不错。
下午来到湖大。
在候考室打量了一下机器,Pentium CPU,2013年(跟我家 G630 有得一拼),难道这就是我们要用的机器?/jk
然而,到了四楼,竟然是工作站!虽然比较老了 (E3-1220v2 (4C4T),8GB),但显示器竟然是 1080p 的(比我们学校机房好不知道多少倍)
顿时信心十足。
14:30 ~ 15:30
先看 T1。一个单增,一个单降,加起来应该是个凸函数。
30min 码完三分,对拍,成功 WA on 1。
后来仔细想了想发现这貌似不能三分,好像不是凸的。
然后有点慌了,通过告诉自己“这是 T1,不会那么难”稳住心态(忘记儒略日了吗)。
自己手动模拟,猜了个结论,然后居然过了样例,对拍 \(10^4\) 也没出错。
总算 100pts 了。
15:30 ~ 17:00
看到括号序列,再看数据范围,显然是区间 DP。
但是它的定义比较复杂,于是直接设 \(f(l,r)\) 开干。
发现是 \(O(n^4)\),但好像可以后缀和优化,先写了再说。
写写写,发现第二个样例过不去。
发现 \(\texttt{()()()}\) 会重复算,于是枚举第一个括号配对的哪一个括号。
发现还是过不去,貌似还要设个 \(g(l,r)\)。
调调调,总算把 \(O(n^4)\) 调了出来。
最后加了个后缀和优化。
17:00 ~ 17:45
T3 一开始没什么思路,但后来发现似乎有些性质。
假设选出了最终在 \(i\) 和 \(2n-i+1\) 位置上的数,那么要求 \(i+1\) 和 \(2n-i\) 位置上的数与前一个数在 \(a\) 序列中相邻。
然后貌似是会被卡的,但还是好写。
预计 \(O(2^n)\),最多也就 40pts 吧。
17:45 ~ 18:20
T4 这个模型,一开始以为是贪心什么的,但越看越感觉是文理分科。
手玩了一个网络流模型,这最小割不是 \(0\) 吗?好像哪里不对……
结果发现没有附加点时本来答案就是 \(0\)…… (喷血)
赶快码码码,有前人的事迹激励(指 wyz 模拟考激情 10min 网络流),一测,\(\texttt{global-buffer-overflow}\)…… 哦没有初始化,那没事了。
样例一遍过,还好,虽然最后一个样例跑了 18s。
18:20 ~ 18:30
检查文件,又测了一遍样例。
结束了。
Day 2
心血来潮,测一波代码。
幸好这次没有像上次一样重蹈覆辙,(似乎)没有挂分。
估分:\(100+100+40+60=300\)
InfOJ:\(100+100+88+80=368\)
洛谷(民间):\(100+100+92+60=352\)
CCF:\(?+?+?+?=?\)
(我 T3 怎么骗了这么多分?感觉 rp 被提前用光,NOIP 危)
等官方成绩出来了再更。