Day 5

说实话，在这五天当中，我也常常思索着Day 5以及本次集训会是怎么样迎来尾声的。然而此刻坐在G1128上的我内心竟没有什么大的波动== 那么这篇博客——

当然是要继续轻松愉快地说说今天在机房的被吊打经历啦！！！

首先是日常的吐槽酒店早餐环节！今天毒瘤酒店居然把超好吃的河粉换成了炒方便面？？锤爆酒店厨师！我超喜欢酒店的炒河粉的！（不过听说昨天的炒河粉炒的很淡？Nerlci_:不管。）不过今天的面似乎没有那么辣了，果然老天还是给咱留了一条活路的==

然后就是五天以来博客的重要内容——毒瘤题讲解！

T1 相遇

怎么第一题题目名字就这么奇怪==

这道题目描述是给定数轴上的两个点n与k，每次操作可以使n变为2n、n+1或n-1中的任意一个，求需要多少次操作才能使n变为k。

首先，我们可以发现，使n变为2n的操作只能让n向数轴正方向移动，那么，若n \gt k的话，直接输出n-k即可。

接下来考虑其他情况。除去上面的情况后，每次操作可以让n的值增加n或增减1。此处我的处理方法是对k进行改变，每次若k \mod 2 = 1，就将答案加一，若此时k \gt n，则将k/2，答案加一，直到k \leq n为止。此时若k=n，则答案已经计算出来，若k \gt n，则计算除二前后距n那个较近，最近的距离加上上面统计的答案既是要求的答案。但是存在一种情况，若开始向右走一步更优，则取开始先向右走一步得出的答案。

但是！这个算法是存在问题的（只是没找到）。正解的解法是将每一步三种走法都处理成有向图的一个节点，求出最短路。由于每条边的边权为1,使用BFS处理即可。

T2 加密信件

好的，现在我们可以确定这5天考察逆序对的次数了——3次！（Day 1 T3、Day 4 T3、Day5 T2）这个毒瘤出题人到底是多喜欢逆序对啊==

读完题目，我们可以发现，若按原文的字母顺序对信件中的字母进行离散化（不如说是密集化或是映射？）后，对于信件中每一个字母离散化后的值，交换一次都会减少一对逆序对，则求出逆序对个数即可。

然而！出题人显然不是普及组随便抓来的。在这种处理方法中，对于相同的字母处理会出现问题。那么，如何解决呢？

注意到相同的字母交换后对打乱后的信件向原信件变化没有贡献，那么，每一次对相同的字母进行的交换是白白浪费的，不做这次操作答案会变得更优。那么，我们让映射后的相同字母在打乱后的信件中的值单调递增即可，这样可以避免相同字母间的交换。在实现上，则是让每一个字母映射的值是原信件中第一个没有被使用的该字母的下标即可。实现上可以使用队列来进行处理。

T3 小乔

这个题面是什么鬼啊

惯例超纲题。注意到每个n \lt 10^{5}，那么，我们可以对每一个划分后的扇形区域进行枚举计算。因为要求的是被覆盖至少k次的面积，我们对于扇形进行分析，发现该扇形中半径第k大的范围之内全都被至少覆盖了k次，那么我们需要一个能够快速修改及求出区间第k大的数据结构。显然，平衡树和主席树可解此题。

下午与天泽龟愉快地颓了很久的slay，接着就是看题解打正解。看完最后一题题解后十分好奇是否有dalao能够考场手打平衡树，结果误打误撞发现了卡评测机AK的MDz2。lemon的防卡还是做得不够好啊==

下午四点最后一次走出长沙一中的校门（忘了拍照留念了啊好可惜)，人生中第一次坐黑车到了长沙南站（真的好远呐），结果很惨的把手机丢了！！我超爱的黑莓啊！！（不过似乎是个换Q20的机会）

18:05坐上G1128次，写完了这篇博文。

最后感谢长沙一中主办的这次集训，让我学到了太多太多。感谢出题人的毒瘤题目，让咱每天都充满了生活的希望，同样也要感谢教练给咱的这次机会，以及母上大人万忙之中抽出时间陪咱到长沙照顾我（要是咱腿没坏就好了Qw)。

那么，再见了长沙一中！我们2020年再见！

NOIP2018::rp++;