JXOI2020 游记

前排提醒：JX 用 B 卷。 ## Day1 早上大约 8:00 到了考场，8:10 进去，打了个缺省源感觉良好。 8:30 开始考试，先看了眼题目名称。 > `card` > > `message` > > `icefire` 看起来似乎海星。 于是开 T1。 > 给定一个 $n$ 项数列，每次选取其**最前面至少两项**，计算其和 $a$，获得 $a$ 分，然后将这些数换成一个数 $a$，可以随时停止，求最大得分。$n\le 10^5$，1s，256MB 补充，由于有人觉得我说得不太清楚，这里补个样例及解释 > 假如 $a=[2,-1,-1,2,-4]$ 选择前两个，加一分，$a$ 变成 $[1,-1,2,-4]$ 选择前三个，加二分，$a$ 变成 $[2,-4]$ 结束游戏，最终得分 $3$ 然后发现是个大思博题，秒了。 然后看 T2。 > 给定一颗 $n$ 个点的树，$m$ 次询问到 $x$ 最短路为 $k$ 的点的个数。$n,m\le 10^5$，2s，256MB 一脸懵逼，于是先打了个 $O(nm)$ 的暴力，$\text{30 pts}$ 到手。 然后就想能不能换根 dp 啥的，于是就推出来了： $a_{u,0}=1,a_{u,k}=\sum\limits_{f_v=u}a_{v,k-1}$ $b_{1,k}=a_{1,k},b_{u,k}=a_{u,k}+b_{f_u,k-1}-a_{u,k-2}$ 就拿到了 $k\le 20$ 的 $\text{30 pts}$。 想了一下正解，发现不会了，就先开 T3。 （B 组 D1T3 与 [A 组 D1T1](https://www.luogu.com.cn/problem/P6619) 完全相同） 发现就是求 $2\times\min\{ice,fire\}$。 首先肯定离散化温度，然后想到了树状数组维护。 由于 $ice$ 随 $T$ 不减，$fire$ 随 $T$ 不增，其 $\min$ 显然单峰，所以可以三分？ 打了一下，调了一下，发现自己一直过不了大样例。 然后突然反应过来它不是严格单峰，可以有相等，然后三分就炸了…… 于是换了下思路，发现可以找到 $ice\le fire$ 和 $ice \ge fire$ 的交界点，而这个是可二分的；然后再二分找出最远的峰顶就好了。 然后写了一发过了大样例。 时间复杂度 $O(n\log^2n)$，大概能 $\text{60 pts}$？ 此时大约 10:50，我感觉接下来 2h 似乎没啥事干，正解又想不出来，于是就去写对拍。 11:30 左右，T2 $k\le 20$ 的部分分拍的没问题，就去拍 T3。 然后拍了 1h 发现暴力写挂了……一直输出 `Peace`……最后发现是变量重名的锅…… 总之最终发现自己写的没有问题，反倒是暴力出了 114514 个锅 大约 12:50 监考员提示上交到网上？？？ 不怕又丢一次吗.jpg 然后才发现，上传到网上的是备份，事实上是以监考员亲自收的为准。 哦那没事了，看来还是吸取了教训.jpg 大约 12:55 我就交好了，监考员示意我离开。 出来以后，发现我大概是拿了个大众分 100+60+60。 我：你们估分多少，我 220 tyq：220 zmy：220，本来似乎能写完 260 的 Hansue：190，我裂开了 LHQ：220~260 我：你 260 哪来的 LHQ：我 T3 写了 $O(n\log^2n)$，本地极限数据 6s，我觉得能过 我&tyq&zmy：？？？？？？？你在想桃子 LHQ：我不管它肯定能过 我&tyq&zmy：¿¿¿¿¿¿¿¿ 那它给 $q\le 2\times10^5$ 的部分分是干嘛，肯定会卡死你的 LHQ：它肯定不会卡啊，它不是卡根号的吗 我：$\log^2n=\sqrt n$ LHQ：反正它就是能过 （no fxxk to say） 然后我就回到机房来~~打雀~~写游记了 /kk 晚上测了下 LHQ 造的数据，100+60+60 应该稳了 ## Day2 进入考场，老师说我们昨天的文件没有清空，再做备份 /fad 于是就把昨天打的缺省源又拉了出来。 突然老师意识到一个问题，桌面上两个 `JX-00xx` 会重名，于是就叫我们把昨天的扔进 `0620` 文件夹，然后再新建一个 `JX-00xx`。 大约 8:27 拿到题目，照例先看了下名称。 > `lucky` > > `transfer` > > `lilac` 诶 `lilac` 是啥啊？哦是丁香的意思啊。 然后开 T1。 > 给定 $n$ 个条件，每个条件形如 $x=A$ 或 $x\neq A$ 或 $L\le x\le R$，你可以选择一个数 $x$，令 $w=0$，如满足第 $i$ 个条件则令 $w$ 异或上 $w_i$，求 $w$ 的最大值以及此时 $x$ 的取值，满足条件的 $x$ 如果有多个输出绝对值最小的，如还有多个输出最大的。$n\le 10^5,|A|,|L|,|R|,w_i \le 10^9$，1s，256MB。 然后发现是离散化+前缀和的思博题，写了大约 10min 一发过大样例就去开 T2 了。 （B 组 D2T2 和 [A 组 D2T1](https://www.luogu.com.cn/problem/P6622) 完全相同） 一脸懵逼，数据范围看起来像是状压 $O(2^m)$，但是想了半天只会 $m\le 8$ 的 $O(m^2m!)$ 算法，于是骗到了 $\text{30 pts}$，然后想了半天的状压发现怎么想都是假的，于是放弃去开 T3。 > 有一个 $n$ 个点的无向图，编号为 $i,j$ 的点之间恰有一条边，其长度为 $|i-j|$。给定 $m$ 条必须经过的边，求 $s$ 到每个点的最短路。$n\le 2500$，2s，512MB。 一脸懵逼 \*2，然后看了看数据范围，就先把 $m=0$ 的 $\text{5 pts}$ 骗了。 接下来，看到 $m=1$ 的 $\text{15 pts}$ 也马上骗到了。 之后想了一段时间 $n\le 50,m=9$ 怎么做，然后想到一个 $O(m!nm)$ 的算法，然后想了一会发现似乎是假的，保证正确性可能需要 $O(nm2^mm!)$（然而事实上不用），就自闭了。 思考了一会发现可以状压，然后就写了一波过了样例，于是就又有了 $\text{30 pts}$。 此时大约 11:00，然后我又没事干了。 然而我懒得写对拍，于是就开始摸鱼（ 在想了很久 T2 无果以后，就开始玩 python（ 最后 15min 又测了波样例，确定莫得问题以后就交了。 出来以后，发现我的 100+30+50 似乎又是大众分…… 我：你们估分多少，我 180 tyq：你 180 怎么来的？我 170 我：100+30+50 tyq：啊你 T3 50 怎么写的？ 我：1~6 状压，11~14 显然 tyq：啊这 我：LHQ 你多少？ LHQ：100+30+50 zmy：我只有 105，我彻底裂开 我&tyq&Hansue&LHQ：啊这 zmy：你们 T1 怎么做的啊 我&LHQ&tyq：?#/&@!?#/&#? zmy：哦哦哦哦哦原来如此 然后我单独去找 tommy 问 tommy：100+30+50 我：我也是 我&tommy：真就考了两天大众分啊艹 然后下午被拉去做物竞实验，然后就回来鸽游记了 /kk ## Day3 学了一天的文化课真爽啊。 ## Day4 又学了一上午的文化课。 一看成绩出来了，就查了下我的分数。 100+60+60+95+30+50=395 为啥 `lucky` 炸了 5pts 啊 >\_< 然后 tommy 把 JX 完整表发给了我，发现我是 rk6，开心，应该能进 E 了。 看了看其他人的分数 tyq：100+30+0+0+35+0=165 为啥 tyq 炸了这么多分啊 /fad LHQ：100+60+60+90+30+35=375 似乎也能进 E 队 tommy：100+30+10+50+30+35=255 听说炸了 70pts，默哀 zmy：100+60+60+25+30+35=310 正好 rk10，去掉我和 LHQ 和另外一个初三的应该是能进 A 的 Hansue：100+30+10+20+0+20=180 为啥也炸了这么多分啊 /fad/fad 然后算完加权平均分数以后，发现我是 rk7，LHQ 是 rk8，zmy 是 rk10，我们学校三个省队稳了 /cy 下午继续乖乖 whk 去啦 ## Day6 官网公布成绩了，成功水入 E 队 /cy