【化学】固定模式答法合集
由于博主高Ň …
作者： KSkun
![[NOIP2017普及]跳房子 题解](https://ksmeow.moe/wp-content/uploads/2018/09/180926a.jpg "180926a")
[NOIP2017普及]跳房子 题解
题目地址：洛谷：【P3957】跳房子 – 洛谷
题目描述
跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。跳房子的游戏规则如下：
在地面上确定一个起点，然后在起点右侧画n个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。
现在小R研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的d。小R希望改进他的机器人，如果他花g个金币改进他的机器人，那么他的机器人灵活性就能增加g，但是需要注意的是，每次弹跳的距离至少为1。具体而言，当g<d时，他的机器人每次可以选择向右弹跳的距离为d-g，d-g+1，d-g+2，…，d+g-2，d+g-1，d+g；否则（当g≥d时），他的机器人每次可以选择向右弹跳的距离为1，2，3，…，d+g-2，d+g-1，d+g。
现在小R希望获得至少k分，请问他至少要花多少金币来改造他的机器人。
输入输出格式
输入格式：
第一行三个正整数 n ， d ， k ，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。
接下来 n 行，每行两个正整数 xi, si ，分别表示起点到第 i 个格子的距离以及第 i 个格子的分数。两个数之间用一个空格隔开。保证 xi 按递增顺序输入。
输出格式：
共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k 分，输出 -1 。
输入输出样例
输入样例#1：
7 4 10 2 6 5 -3 10 3 11 -3 13 1 17 6 20 2
输出样例#1：
2
输入样例#2：
7 4 20 2 6 5 -3 10 3 11 -3 13 1 17 6 20 2
输出样例#2：
-1
说明
![jump data - [NOIP2017普及]跳房子 题解](https://ksmeow.moe/wp-content/uploads/2018/09/jump_data.png "[NOIP2017普及]跳房子 题解")
题解
很容易看出来这应该是一个二分答案验证的套路，我们二分花费金币的数量，通过这个值确定跳跃的长度范围，可以用这样的DP来计算到每个位置为终点的最大路径和。
$$ dp[i] = \max_{\text{在跳跃范围内}} \{ dp[j] \} + val[i] $$
由于跳跃范围是定长区间，我们想到了滑动窗口，显然可以用单调队列来维护定长区间最大值，从而完成$O(1)$的转移。这样，复杂度就降为$O(n \log n)$，可以通过本题。
吐槽：好久没写代码了手都生成什么样子了QAQ，这破题还花了半小时……
代码
// Code by KSkun, 2018/8
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
return res * neg;
}
inline char readsingle() {
register char c;
while(!isgraph(c = fgc())) {}
return c;
}
const int MAXN = 5000005;
int n, d, k, dis[MAXN], val[MAXN], que[MAXN], ql, qr;
LL dp[MAXN], sum;
inline bool check(int mid) {
memset(dp, 0xc0, sizeof(dp));
dp[0] = 0;
int dl = std::max(1, d - mid), dr = d + mid, now = 0;
ql = qr = 0;
for(int i = 1; i <= n; i++) {
while(dis[i] - dis[now] >= dl && now < i) {
while(ql < qr && dp[que[qr - 1]] <= dp[now]) qr--;
que[qr++] = now; now++;
}
while(ql < qr && dis[i] - dis[que[ql]] > dr) ql++;
if(ql < qr) dp[i] = dp[que[ql]] + val[i];
if(dp[i] >= k) return true;
}
return false;
}
int main() {
n = readint(); d = readint(); k = readint();
for(int i = 1; i <= n; i++) {
dis[i] = readint(); val[i] = readint();
if(dis[i] > 0) sum += dis[i];
}
if(sum < k) {
puts("-1"); return 0;
}
int l = 0, r = dis[n] + 5, mid;
while(r - l > 1) {
mid = (l + r) >> 1;
if(check(mid)) r = mid; else l = mid;
}
printf("%d", r);
return 0;
}
![[HNOI2013]游走 题解](https://ksmeow.moe/wp-content/uploads/2018/07/180725a.jpg "180725a")
NOI2018游记
一年OI一场空，exCRT见祖宗
人生的第一次，也是最后一次的NOI，就这么结束了。
留下了D类Cu的优秀成绩，以及签了张废约的记录。
谨以此文献给我的OI人生……我学过OI吗？
Day -1 7月15日
跟APIO一样，整理行李整理到了半夜。带的东西比APIO要多一点，因为呆的时间更长了。
发现自己计划还咕了一大堆，感觉要凉，计划着剩的几天的空闲时间都补起来。
晚上跟panda_2134大爷聊了会，他的计划也咕了，不过至少他整理了板子而我没整理完，而且在这个时候我还不会生成函数和多项式算法，似乎是凉透的预感。
Day 0 7月16日 路上
起的特别早，因为要赶7点的火车，明明没睡几个小时却很精神。D5222去武汉，我NOIP、省选都坐的是它，算是陪伴了我OI人生的一趟列车了吧。
先小睡了2小时，过了襄阳以后没多少隧道了，手机信号良好，就把NOI17的裸2-SAT题游戏拿出来打。打了两个小时总算是打完了，快5K的代码，头疼的是好像锅了，然后就没什么时间打了。
下车以后跟教练随便吃了点面条，然后等接续换乘的D2378。这里用了很皮的操作，从汉口站坐动车去武汉站，虽然贵一点但是比地铁快，而且教练说这个能报销挺好的。不过他吐槽我说你这样时间全花在上下车上了，反而候车没怎么等。
在武汉站路遇了本省的Anoxiacxy大爷和高一红太阳Edgration，他们的车比我的早半小时，所以就跑了。我坐的是G83，特地查了下是复兴号的车底CR400AF，内部挺漂亮的。
由于到站时间靠的太近可能接站坐同一班班车去洋湖。车上1小时把游戏那题调出来了，交了一发美滋滋。
好像寝室跟HN的rank 1和2安排到一起了，好紧张，怎么在神仙包围的寝室里存活下来啊，挺急的，在线等。
果真和前面提到的大爷在同一辆班车上，去洋湖还有一段时间，路上分享了一下近段时间的坑爹经历，以及cxy大爷std::random_shuffle优秀做法AC游戏的神仙操作。
长沙热炸了，根本不想在这样的太阳下多待一秒钟。领了狗牌、饭卡、衣服，吐槽一下今年居然没有印成“nol”的书包，差评。然后开始思考怎么合适地在签到处签到得到事情，因为那块板子已经被各路神仙占领了，我等蒟蒻应该无法存活。在cxy大爷的名字后面签了个小小的“KSkun”，成功签上了到。
考虑到跟女325的其他神仙交流遭不住，决定将来只回去睡觉，讨论的时间就呆在我省红太阳所在的女322寝室好了。考虑到太阳太毒，窝在寝室什么都没干，不知道自己在颓什么。
想起了之前立的flag们：
Flag #1: NOI开始之前Codeforces上紫名（candidate master）
Flag #2: NOI开始之前题解博客用完lxl的珂朵莉
凸包图包
Flag #3: NOI开始之前日膜cxy
还有一个
Flag #4: Au女装
到这一天为止，Flag #1已经实现不了了，最后一场Codeforces Round #497 (Div. 2)体验极差，5个题里能做的就3个，拼的就是不fst和手速，没涨多少rating。另外Flag #2的图包还有10张，可能需要肝一肝才可以实现了。而且这个#4肯定是实现不了的啦，我这么菜怎么Au啊。
下午跑去开幕式彩排，好像果真要进行所谓的“选手风采展示”。每个省队要被集体爆照还要站起来尬打招呼尬喊口号，整场都尴尬的1B，真不知道在搞什么。三楼的空调并不是很足，坐久了挺热的，浑身都是汗。偶然发现直播开幕式应该挺多人看的，就开了一发直播彩排，反响不错。
食堂好评，各种菜和饮料都有，味道不错。
晚上当然是愉快地被各路神仙鄙视背笔试啦。评测鸭的背笔试功能真好用www
听说rqy那边遇到了一点问题，希望他不要出事。
Day 1 7月17日 开幕式
上午开幕式和下午练习赛换了一下，于是一早上就在跟F4 F9 F6 F8奋战（Anjuta和Lazarus的快捷键）。
进考场的时候就虚虚虚虚虚虚虚，想着笔试不能锅，锅了就出事了。打开题一看，跟想象中的差别不大，开始往下做，十几分钟做完。本来想着就着检查一遍，不小心把浏览器页面关了，没保存答案，GG。又花了几分钟重新填，保存，继续检查。查了一发成绩，100/100，没出事，算是个好的开头？
练习赛给的题目是省选Day 1，我都没订正不会做怎么办啊。于是跟cxy比较了一下各自用的快读，就早早地溜了。溜之前看到身后就是stdcall，打了个招呼，stdcall本人好帅呀！
下午跑去开幕式，比昨天还热。又被拎起来爆照尬喊口号，湖北的口号是钦定的“心怀梦想，砥砺前行，赛出风采，超越自我，湖北加油”，没什么新意，不过如果真的能做到也是一件好事，另外某个省口号养苟，在场所有人的生命受到了威胁。本来准备只在qwq圣殿给大家看的直播被发去了WC建的NOI2018交友群，还被继续传播到了UOJ和LOJ等群，最后甚至跑去了NOI2018@YALI这个群，人气值甚至破天荒的达到了7k，上了B站直播第一页，太可怕了。开幕式总的来说没啥可以看的，这也包括一部分HB位置靠后的原因。€€￡的dzd秘书长的讲话倒是很有看头：
我以前一家11口人很穷，所以就立志要搞一个能吸金的组织
于是就有了这个什么CCF
一做就是22年，期间啊国家没有给我们一分钱，全靠我们自己骗钱，资本主义吃枣药丸
我们就弄了个CCF会员，每年定期交钱，只有一年参加所有的赛事才能回本
那个2004年啊，我记得NOI在长郡中学举办，那个时候还没有ABCD类名额，每个省只去了4个
我就觉得要让更多的人来交钱，CCF快速膨胀
于是就有了B
之后又有了CD
今年啊又有了5k/人的吃瓜团
哎呀太热了我先不讲了骗钱要紧，总之现在的CCF已经能够自给自足啦，希望大家积极给CCF交钱，我只想在退休的时候，能有更多的钱。
不对，我怎么能够退休呢？！我要骗钱！！！
谢谢大家（大雾——摘自匿名知乎回答
以及
震惊！开幕式被推迟的真正原因竟然是。。。
zbzy一定要灭亡，，，让后排的港澳同胞怎么想
我们还有一个 D
秉公执法
含金量最高
太热了不讲了（考题肯定有模拟退火）
DDF主席多赚D——摘自匿名知乎回答2
一瞬间各大讨论群就炸了，我直播间人气值也疯长233333。不过也是多亏了€€￡，让我这种爆零垃圾有机会以会走路的2w2的身份参加NOI2018，有了这篇游记（flag）。笑完开幕式就回寝室写题了。
Flag #5: 怼€€￡（小声BB，心里怼一怼，我怂不敢说出来）
一下午就打了一道强连通水题，其他的时间都在跟dalao们扯淡，大家都好强，聊些多项式神仙算法，我这种菜鸡根本不敢插嘴。然后把GitHub上的模板全读了一遍，晚上就这么过完了。
去跑了一发步，回寝室的时候拍了这张照片。
9点了仍灯火通明的考场，里面的工作人员还在做最后的调试和检查以及分发试题。明天就考Day 1了呀，明明学OI才一年多，从停课到现在也才半年，怎么NOI就开始了呢。
晚上翻空间，翻到了这样的说说
歌唱节目《Hot Chocolate》中途钢琴出现了几次失误，因此他们可能是故意让我们听出这是Live演奏，暗示强制在线；
同时后面左方大屏幕卡了几秒钟，暗示卡常数；
舞蹈节目《梅逐剑影》多次出现换位、变换队形和个人旋转，暗示Link-Cut Tree；
杜子德主席说了“太热，不讲了！”暗示模拟退火。
明天的NOI考题已经剧透完了√——摘自空间某不认识的选手的说说
天秀哈哈哈哈哈哈哈哈哈，笑了半天。
NOI2018爆零退役记·Day2
早上笔试非常愉快。
笔试完了紧接着试机也非常愉快。
试完机去黑网吧颓前十分钟也非常愉快。
然后听说今年试机题第一页都点不太对劲。
吓得我专门跑回去看了一眼，题目首页”测试点/包数目”和”每个测试点是否等分”两栏顿时十分显眼。
NOI打包预定？我开始慌了。。
不过仔细想想还是不慌，你CCF可以打包，我还可以打铁呀。这样一来不就扯平了吗（大雾
下午开幕式就不说了。。体验极差。给差评。
省队入场式有多智障参见昨天说说。
明天考试日。有点绝望。。。
希望别炸。——摘自空间RE丨MegaOwIer的说说
居然Subtask打包测试了？这不是我要凉的节奏？
Flag #6: 可能会有的打包测试
转了迷信yql帅照，希望可以rp++。
晚上听了一遍WC文艺汇演的OI金曲系列。嘛，别想太多，先睡觉就是了。也许把我和神犇分在一个寝室也是涨rp的操作呢。
Day 2 7月18日 考试Day 1
起了个早去吃饭，和HB的各路神仙互膜rp++。跟panda大爷一起走的，进考场的时候开玩笑说“我们踏入爆零之门辣”，其实内心无比慌张。
Flag #7: 爆零之门
居然纸质电子题面都给了一份，好评。
出了一堆锅，包括
- T2写错了的冒泡排序
- T2数据范围里$q_i$写成了$p_i$
- T3并没下发的样例2
上来读T1，读完以后发现很可做，对着数据YY了一发算法。花了半个小时YY了一种$O(n \log n)$的优秀算法，就是在每个点记录历史并查集代表元，在每个代表元记录历史连通块最小值，查询的时候std::lower_bound一下时间查就好。简单地证明了一下时间和空间复杂度，发现没大问题，然后1h写完。写完居然没怎么调就过大样例了，然后决定先不管继续看题，一会有时间再跟暴力拍一下。
写完T1就想去个厕所，然后没注意要排队进，尴尬了。考场提供了咖啡，好评，弄一杯回去喝提提神。后面的时间安排本来是半小时打T2T3暴力然后看哪个题可做分2个小时刚一下。
观察了一下T2，发现并不是很可做，于是跳了先看T3。先试试SA，然后试试SAM，然后发现这俩我都跟这个题连接不起来了啊，感觉要凉。然后想到了AC自动机跑暴力的方法，暴力把每个$S$的后缀扔进去枚举子串跑匹配统计答案，然后用hash去重。似乎复杂度是$O(n^2)$的，可以过掉几个点？但是调到死调不出大样例，迷得很，扔了。
回去玩T2，先想个暴力，$逆序对数=\frac{1}{2} \sum |i – p_i|$就可以计入答案，DFS边搜边维护权值BIT，减小统计逆序对数的常数，复杂度$O(n! \cdot n \log n)$，这个暴力可以获得12分的好成绩。然后发现好的排列中的数字要满足它之前的比它大的数字个数不大于它到它应该在的位置的差值，可以状压DP了，能多过几个点。写出来跑了一发中样例发现WA了，然后那个样例就把我的做法hack了。回头看了一眼T1的大样例，似乎很强不需要拍了，于是接下来的1小时全在刚T2。试图修正我的结论失败，Day 1就这么结束了。
出了考场以后才知道T3是SAM的经典应用有68分，T2的结论是最长下降子序列长度不超过2，T1是Kruskal重构树裸题。但是写了112分我感觉也不算太差。听说T2的爆搜点卡常，突然虚了起来。
查分，果然是100+12+0，T2的爆搜优化了下常数跑过去了。围观了一下本省其他人，似乎有点惨。看到了不少200+的神仙。
讲题，T2神仙结论猜不到啊，T3神仙SAM不会写啊。还在后悔T3的68分。据dzd说Day 2有最简单的和最难的题，如果这句话是真的，大概我Day 2不AC最简单的题就会GG。
Flag #8: AC最简单的题
cxy神仙160+，其他人基本在120上下。对于一个省来说这个分可能有点惨？下午放飞自我，随便玩点啥，水群看番啥的。就很虚，因为Day 2要达到50%线以上，不然就真的没学上了。
rqy好像Day 1爆炸了，多组数据没清空数组。好像不少人栽在这里了。祝他Day 2 AK顺利进队。
晚上吃瓜看题，因为明天社会活动的事情各个大群都爆炸了，集体怼雅礼和€€￡，看戏看到好晚。
Day 3 7月19日 社会活动
果然好热，跑去吃个饭就跑了。顺了两瓶藿香正气水防中暑。
跟SX的dkw、poorpool和SD的pb见了一面。跟HA和GZ的dalao们同车，感受到了dalao的气息。
韶山热到炸裂，进去XJB玩一下手机，出来XJB玩一下手机，就逛完了一个地方，然后跟丢了队没进故居，在外面XJB玩一下手机，就自己跑去吃饭了。饭还不错，就是有点辣。
出去一趟什么都没看到，甚至没留下照片，然后就跑回寝室了。一下午磕一个SAM模板（TJOI弦论）没磕会，晚上才差不多看懂的，怕是要凉。
Flag #9: SAM模板题没看懂
晚上照例出去跑步，回来拍了这张东西。
对我又拍糊了。明天能怎么办呢，Day 1已经低于50%线了，Day 2希望能超回来啊。
晚上听歌，又听了一遍OI金曲。
Flag #10: 场场考试前的晚上都听退役金曲
睡前发的说说：
祝……
什么也说不出了。
还有几个小时退役，以及确定有没有学上。
各位玩的开心，感谢一路相伴。
Last Night, Good Night
分享初音ミク的单曲《Last Night,Good Night》: 网页链接 (来自@网易云音乐)
Day 4 7月20日 考试Day 2
比Day 1前平静多了，也方多了。真的不知道怎么面对考完试后的结果。
Day 2没什么锅，补充的pdf里也只是一些关于题意的补充说明，没有明显的错误。
开T1，推了会式子发现exgcd好像做不了。又看了一眼，woc这不是裸的exCRT？打打打。诶exCRT怎么打来着，完蛋，现场推式子。
下面是我推式子的心路历程：
$$ \begin{cases} x \equiv a_1 \pmod{p_1} \\ x \equiv a_2 \pmod{p_2} \end{cases} \Rightarrow \begin{cases} x = a_1 + p_1t \\ x = a_2 + p_2t’ \end{cases} \Rightarrow a_1+p_1t=a_2+p_2t’ \Rightarrow a_1-a_2=p_1t+p_2t’ $$
诶可以exgcd了，写一发。判定有无解怎么搞来着？$a_1-a_2=\gcd(p_1, p_2)$？完蛋我忘了，试一下。试不出，完蛋了，其中能过小样例的做法不知道有多少分，总之先放着吧先看后面的题。
T2只会爆枚树剖求链并的$O(n^2 \log^2 n)$的差劲做法，凉了。
T3只会爆搜。九莲题怎么可能可做啊。
打完了所有的暴力，不过T3没过样例，也没调出来，不指望这个暴力能拿分了。
回去刚T1，什么都没搞出来，然后比赛就结束了。所以我刚T1得到了什么？一定要AC最简单的一题这样一个想法干预了我的安排，让这一天的计划全搞乱了，于是我就光荣退役了。
自己想了想T1的瞎搞，似乎还有个几十分，不算特别惨。中午一起吐槽exCRT卡科技，希望T1分差大把Ag线拉下来啊。看了一眼exCRT的板子，发现自己整除判断反了，我居然没有发现，看来我数论还是很差。
查分，35+5+0。似乎是爆long long然后还有一些地方挂了，但是也不想看哪个地方挂了。写了个对的exCRT，发现能补救回来20多分，有点凉啊。
讲题，照例直播。今天吐槽题目的人挺多的啊，松松松表示自己看不懂T2解法，于是让猫锟远程讲题，被点名了好紧张。吉老师的题果然是防AK好题，跟我的判断差不多。
听高校宣讲。很无聊，陪xlj听完以后跟他一起去跑学校。这也是我人生中犯的最大的一个错误，我这一下午讲题和宣讲都不该听，不然可能能进人大面试。
根据计划先去显然不要我的高校。上交复旦南大浙大都没DCu的事，很快就转完了。转的过程中在楼道里看到了复旦的老师：
老师：同学你有约吗
我：我是D类铜牌
老师：……
我：……
溜了溜了……
果然是这样的结果，直接去人大看看。填了张表交过去，xlj 280+等了两个小时就进面试了，只是因为高一没签。我等了一个小时，什么都没等到，于是问了下人大的老师，溜去别的学校了。
武大不要D这个是已知的消息。
北航、哈工、天津也不要，但是天津给了我一张表填起来，说留个信息可以再联系。
北理直接进面试，大概讲了下自己是怎么翻车了，然后就登记上了，说9点左右给消息。
电科的老师比较厉害，居然还能聊起来算法方面的事情，问了我的竞赛成绩和Codeforces Rating，很尴尬的是我没上紫。听到我是基本靠自学他也有点惊讶，可惜他们没有D的现场签约计划，留了我的信息说9月跟招办商量一下再考虑。
去西北工大，半小时听老师洗了一波脑，说自招给-50，然而这个学校我好像能裸分。登记了信息就溜了。
不想去吉大，就剩北邮了。又在人大那坐了一会，没到我，就跑去北邮等着了。北邮说给一本，然而要我排在队尾等着。等了一会以后已经9点多了，跑去北理签了个约就跑下来继续等。一查北邮只让签两所，我整理了一下，决定咕了北邮去人大
- 人大是我能签到的最好的学校
- 北邮我可以裸分上
- 看北邮不太顺眼（？）
人大晚一点的时候清了一波250以下的，还好我252留住了。然后等啊等啊等到了0点最后一批面试结束以后还是没有我，这个时候我已经凉到最低点了。等他们出来宣布签约名单的时候，所有人都炸了，因为最后一批没有人签约。我也顺便求了一波情，可惜并没有卵用。
0点多的时候，我在NOI2018的所有工作就以这样悲剧的方式结束了。自己一个人提着包走在无人的街上。经过考场的时候又拍了张。
又渴又饿，但是超市已经关门了，并没有办法满足我此时想暴饮暴食的欲望。回去以后发现322的神仙们还没睡，跑去玩。直接喝掉一整瓶水，鬼知道我今天晚上经历了什么啊。
成果：北理自招-40/30/20，其他一概没有。
panda大爷翻得比我还惨，签约的时候放弃了，并没拿到约……本校的wayne也没达到期望，但是有学上；wxg也有学上；anoxiacxy不用说肯定是有学上的；队长barrin Day 2翻盘，蹭进了Ag。strangers可能是最惨的……什么都没拿到就退役了。
想哭又哭不出来的感觉，回去以后根本不知道有什么可以做的，只好刷空间。看到了不少人的退役感想。
曾经，我觉得自己肯定至少有银牌水平。
结果第一天开错题，没写送的68；第二天被卡科技，心态完全爆炸，75分炸成10分。 然后现在没学上。
确实啊，竞赛这东西不仅要水平，更要运气。
一年后高考见吧，希望文化课不要再让我失望。——摘自空间panda_2134的说说
获得成就：成为老年退役选手
——摘自空间Anoxiacxy的说说
列表里个个都是集训队。。。
说实话我根本没想好退役该怎么过。
满脑子都是进队之后丰富多彩的生活。
我可能要花时间冷静冷静，想想高考该怎么学。——摘自空间__stdcall的说说
对啊，我退役了。但是我应该干点啥？什么都不想干，干脆去洛谷开个题写算了。
睡得很晚。
Day 5 7月21日 闭幕式
9点才起床，没吃早饭，去买了点东西就去文艺汇演了。
所谓的文艺汇演不就是聚众传教嘛2333（公开放LL的MV还行）
在某交友群里发起了μ’s合唱企划，然而只募集到了4个人，毁了首《愛してるばんざーい！》，然后就溜了。
达成成就: 在大庭广众之下唱歌丢人
中午不知道干啥，安慰了下panda。继续看昨晚开的那个题，看懂了可以开始打了。然后和其他人颓颓颓。
联系了一下Wahacer，成功加入了传销组织，计划着高三结束以后去骗钱。
下午跑去闭幕式。好无聊啊，dzd的讲话也没什么亮点。HB的好多选手和老师闭幕式没结束就溜了，把我的证书也带跑了。
晚上和panda大爷颓，然后和HA的王冠大爷聊天，进行非对称信息博弈（斗地主）。收拾了东西，准备第二天一早跑路。
考崩了还莫名其妙的开心？
想起来了vfk博客中的话。
我不觉得我比集训队中某些人水平低。
可是进队的是他们，不是我。
为什么呢？为什么呢？。。我大概想清楚了。
OI的本质其实也是在赌博。
水平越高，赢的概率越高，可是这终究只是个概率。
我获胜的概率比较大，但是最后还是输了。
我曾经以为我看透了OI的本质，就是比谁稳，比谁暴力打得好，比谁不挂题。
我还是错了，因为我以前总是站在获胜一方的角度看问题的。
考场上的状态，写题时候脑子的清醒程度，遇到什么样的题，这些真的不是能用水平来衡量的。
不只是我，还有非常非常非常多比我强的多的秒天秒地的人，这次也挂下去了。我这次终于亲身体会到了，什么叫“卧槽他这么强为啥没进队？”。
这时候回头看看，发现其实自己运气已经够好了，2017-2018两个赛季八场比赛，我只有这一次运气差，只有这一次挂了题，只有这一次被卡科技，只有这一次比自己预估的分低了几十到一百，我曾经可是以码力爆强，从不挂题自豪的。
再回头看看，我们其实也是踩着很多人的尸骨爬上来的，同样是很多秒天秒地的人，他们挂的更早，可能在NOIp，可能在省选，甚至可能是因为文化课太差被劝退出OI，他们退役的时候，肯定比我有着更多的不甘和委屈吧。。。
把人生寄托在这种比赛上面，真的靠谱吗？。。
我当时入OI的时候就没有了解到这残酷的一切，因为没什么人带我。所以我没有做好任何退役的准备，自认为水平够了就没问题的，根本没想好退役之后该怎么过。
所以我希望想要入OI的，和还没退役的OIer，虽然这里面有相当一部分的人比我强，但是我还是想提醒大家，做好心理准备，即使你再强，也有可能因为不知道什么原因就被刷下去了，这真的不是玩笑。
当然，wyy说过，他曾经以为只要足够强，强到见题秒题，比赛策略和状态什么的就都不是问题了，然而这样的人用两只手就数的过来吧。。他们是真正的神仙，我感觉是必须要同时拥有天赋和几倍于常人的努力的。。。
咽不下这口气，但是还是就这样退役了。
大概过不了多久就会被遗忘吧。。。在OI圈混不下去了。。——摘自空间__stdcall的说说
深有感触。只是，stdcall比我好一点，毕竟我是从NOIP挂到NOI的人啊。
这是空间一条说说的配图。
垃圾竞赛，毁我青春。
Day 6 7月22日 返程
和SX的选手一起走的，路上跟dkw聊了聊。卡Ag线也是件挺烦恼的事情。
跟panda买了同一趟高铁，一起上的车，可惜车厢不同。车上打出来了开的虚树题，快到武汉的时候没调出，下一班车上继续。
来的时候经过了这里，回去的时候又要经过这里。NOI过的真快啊，还来不及反应，就打铜滚粗了。
下车之前跟panda告别，跑去永和大王吃个饭。永和大王的乌龙茶豆浆差评，那么苦怎么喝啊，不过还算解暑，凑合着喝吧。中午在KFC呆着吹空调，水水群。在回十堰的路上调出了那个题并写好了题解，然后电脑就刚好没电了。
cxy错把我的充电头带走了，他今天去邮了一发估计明天才能到。
到家了，好累。回外公家吃个饭，没控制住跟外公吵了一架，整个人瞬间就崩溃了，哭成傻逼。
上次这么哭还是省选爆零的时候，不过也算痛快。
就是可能会面临更严重的经济问题就是。
说起来，我搞OI花了一年时间几万钱，最后又得到了什么呢，我为什么要搞OI呢。
玩到很晚才睡。
Day 7 7月23日
居然开始写题了。连写了3个题，把珂朵莉图包用完了，拔了个flag。
说起来这种行为应该算在“逃避现实”的一类，毕竟我校22日就开学了，我却在家玩。也好，用完图包我也就AFO了，少了重心事。
思考怎么开这篇游记的头，晚上撑着写完了一半。困过头了所以还是睡了。
Day 8 7月24日
我妈跟我说咕两天，今天她查了下天气说借着感冒等彻底好了再返校，我也就继续咕着。
从中午起床开始写游记，写到中间心情都是很沉重的。现在总算是写完了吧。
非常非常非常感谢一路上陪伴和关照过我的同学和学长们。OI让我认识了各位，留下了那么多回忆，这也是我舍不得AFO的原因之一啊。
也终于能够理解为什么看到的OI故事差别都不大了。因为NOI考崩的人（比如我）大多都不愿意记录OI故事或者直接回去拼了命的高考了，也没什么人像我一样现在还在水。
NOI完了，很多认识的人的博客就这样死了，看着有一种心疼的感觉。希望我的博客能不要死掉。
KS
2018/7/24
![[ZJOI2007]时态同步 题解](https://ksmeow.moe/wp-content/uploads/2018/07/180723c.jpg "180723c")
![[NOI2016]区间 题解](https://ksmeow.moe/wp-content/uploads/2018/07/180723b.jpg "180723b")
![[HNOI2012]永无乡 题解](https://ksmeow.moe/wp-content/uploads/2018/07/180723a.jpg "180723a")
[HNOI2012]永无乡 题解
题目地址：洛谷：【P3224】[HNOI2012]永无乡 – 洛谷、BZOJ：Problem 2733. — [HNOI2012]永无乡
题目描述
永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连通的。
现在有两种操作：
B x y 表示在岛 x 与岛 y 之间修建一座新桥。
Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座，请你输出那个岛的编号。
题意简述
给你一个$n$个点有点权的图，两种操作：
- 加边
- 询问连通块$k$小点
输入输出格式
输入格式：
输入文件第一行是用空格隔开的两个正整数 n 和 m，分别表示岛的个数以及一开始存在的桥数。
接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。
随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存在一座连接岛 ai 和岛 bi 的桥。
后面剩下的部分描述操作，该部分的第一行是一个正整数 q，表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或 B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。
输出格式：
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出-1。
输入输出样例
输入样例#1：
5 1 4 3 2 5 1 1 2 7 Q 3 2 Q 2 1 B 2 3 B 1 5 Q 2 1 Q 2 4 Q 2 3
输出样例#1：
-1 2 5 1 2
说明
对于 20% 的数据 n≤1000, q≤1000
对于 100% 的数据 n≤100000, m≤n, q≤300000
题解
其实把图上的连通块看成集合就是个裸题了。我们考虑使用Splay维护集合，加边等价于合并两个集合，启发式合并即可，询问$k$小直接做就好。注意已经是一个集合内的情况不需要加边，而且加边存在数据不合法（即$a_i, b_i < 1$或$a_i, b_i > n$的情况），需要把这些边忽略。
复杂度$O(n \log n)$。
代码
// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
return res * neg;
}
inline char readsingle() {
register char c;
while(!isgraph(c = fgc())) {}
return c;
}
const int MAXN = 100005;
int n, m, q;
struct Node {
int ch[2], fa, val, siz;
} tr[MAXN];
int tot;
inline bool isleft(int p) {
return tr[tr[p].fa].ch[0] == p;
}
inline void update(int p) {
if(!p) return;
tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + 1;
}
inline void rotate(int p) {
bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
tr[p].fa = ffa; if(ffa) tr[ffa].ch[!isleft(fa)] = p;
tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
tr[p].ch[!t] = fa; tr[fa].fa = p;
update(fa);
}
inline void splay(int p) {
for(int fa = tr[p].fa; fa; rotate(p), fa = tr[p].fa) {
if(tr[fa].fa) rotate(isleft(fa) == isleft(p) ? fa : p);
}
update(p);
}
inline int insert(int rt, int q) {
int p = rt;
for(;;) {
bool t = tr[q].val > tr[p].val;
if(!tr[p].ch[t]) {
tr[p].ch[t] = q; tr[q].fa = p; tr[q].ch[0] = 0; tr[q].ch[1] = 0;
splay(q); return q;
}
p = tr[p].ch[t];
}
}
inline int queryk(int rt, int k) {
int p = rt;
for(;;) {
if(k <= tr[tr[p].ch[0]].siz) {
p = tr[p].ch[0];
} else if(k == tr[tr[p].ch[0]].siz + 1) {
splay(p); return p;
} else {
k -= tr[tr[p].ch[0]].siz + 1;
p = tr[p].ch[1];
}
}
}
int sta[MAXN], stop;
void dfs(int p) {
sta[stop++] = p;
if(tr[p].ch[0]) dfs(tr[p].ch[0]);
if(tr[p].ch[1]) dfs(tr[p].ch[1]);
}
inline void merge(int x, int y) {
splay(x); splay(y);
if(tr[x].fa || tr[y].fa || x == y) return;
if(tr[x].siz > tr[y].siz) std::swap(x, y);
stop = 0; dfs(x);
for(int i = 0; i < stop; i++) {
splay(y); insert(y, sta[i]);
}
}
int main() {
n = readint(); m = readint();
for(int i = 1; i <= n; i++) {
tr[i].val = readint();
tr[i].siz = 1;
}
for(int i = 1, a, b; i <= m; i++) {
a = readint(); b = readint();
if(a < 1 || a > n || b < 1 || b > n) continue;
merge(a, b);
}
q = readint();
while(q--) {
char op = readsingle();
int a = readint(), b = readint();
if(op == 'B') {
merge(a, b);
} else {
splay(a);
if(b > tr[a].siz) puts("-1");
else printf("%d\n", queryk(a, b));
}
}
return 0;
}
![[SDOI2011]消耗战 题解](https://ksmeow.moe/wp-content/uploads/2018/07/180722a.jpg "180722a")
