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 完全相同）

发现就是求 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 完全相同）

一脸懵逼，数据范围看起来像是状压 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