12月做题记录
0x00. 前言
大家好，我是Ramen。
12月注定是很忙的一月，大作业验收+ACM新生杯，还有其他各种各样的事情。嘛，最后反正都能顺利解决的吧。
这个月也就打了很多比赛，感觉打比赛成为常态，学习停滞了，不是很好。下个月寒假，开始学习新的东西了！
GSoC 2018也要开始了，套词好像很难的样子，稍微准备准备吧。
我的答案仓库是 Click Me!。根据题号你能找到我的答案，但是我的答案有很大改进余地，欢迎与我探讨。
0x01. 模板题
很忙的一个月，没刷模板题，跳过了。
哎！
0x02. 趣题
思路有趣是做题最爽的，有趣的思路就是有趣的题目。有趣，也是我打ACM的本源动力嘛。
Another India Site. 印度人在这方面是比中国人走得远，各种专门的面试网站算法网站，GSoC也是组团去的，真的是十分团结。这个网站也是十分热心，注册了之后我做了一道水题就没管了，结果好几封邮件问我怎么不来。
扯远了，看题。一个$n\times m$的矩阵$A$，你可以进行四种操作：
- 选一行，把这一行全部加上$v1$；
- 选一行，这一行全部改成$v2$；
- 选一列，把这一列全部加上$v3$；
- 选一列，把这一列全部变成$v4$。
任意一种操作你可以执行无数次，但是每一个格子至多执行1种操作。也就是说，这个格子可以不执行操作，假如执行了，那就是上面的任意一种，也只能有这一种。
答案问的是最大的$F(x)$，其中$F(x)$我们这么定义：
$$ F(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}|a_{i,j}| $$
这个题其实深入分析题意，我们知道，一个格子要么是本行被改，要么本列被改。有什么问题吗？很简单，一改就涉及一行或者一列，任何不同方向上的操作都会导致至少1个格子操作了两次。那实际上，这个题就是针对每行，针对每列计算最大$F(x)$，然后比较对行对列操作的最大值修改即可。简单吧？
思路有点意思，一开始我以为需要状态压缩DP，后面再度分析才发现的确不难。
车祸题。出题人错误估计答案范围，结果答案范围超过了$10^{18}$，然后1k个人过的题目，hack phase开始之后就剩100+人了。
我的答案对了，C++一发没过，改成python准备一试结果实现完比赛结束了。题目本身是比较有趣的，给出序列，对所有数对求$d(x,y)$，其中$d(x,y)$这么定义：
$$d(x,y)=\begin{cases}y-x&|x-y|>1\\0&|x-y|\le1\end{cases}$$
其实一开始计算我想了很多办法，比如$d(x,y)+d(y,x)=0$，考虑用Manacher的方法去做，但是很明显的，这也是$\mathcal{O}(n^2)$。后面突然发现，假如单纯定义$d(x,y)=y-x$，这个题可以转化成一类求后缀和问题，对于每个数$x_i$，$\sum d(x_i,y)$就是$y_{sum}-k*x_i$。其中$k$是$x_i$后面数的个数，$y_{sum}$是$x_i$之后数的和，就是后缀和。那么现在问题就在于如何处理特殊情况。我们考虑顺序扫一遍，可以统计出任何一个数的出现次数，那么就好办了，考虑$x_i$之后有多少个$x_i-1$，答案自然加上这些数的差，显然是$1$，同理$x_i+1$也可以直接处理。那就是统计+后缀和+扫一遍，整体复杂度$\mathcal{O}(n)$。
这个题的后缀和做法让我还是记忆犹新，这也是难得我在比赛时思路能如此清晰的一次。
Chinese round again！
中国人的轮就是题目很有趣。
这一题很简单，给出基础字符串$f_0$，按照如下规则构造字符串：$f_n=s_0+f_{n-1}+s_1+f_{n-1}+s_2$。问$f_n$的$p$位置字符是什么。
这是一道无限生成字符串的题目，相似的题目很多，今年沈阳站A题也出过。
这一题如果就是耿直的下去做，一定会爆炸。因为$1\le n\le10^5$，同时一个点至多$10$次询问，那么整个时间直接抬走。这里第一步预处理考虑字符串长度，因为$|f_0|=75$，又知道$|s_0|=34,|s_1|=32,|s_2|=2$，我们使用递推公式$|f_n|=2\times |f_{n-1}|+68$可以很快得到整个字符串的长度。由于$1\le p\le10^{18}$，我们几乎立即解出这个字符串满足$n\le54$时需要对完整串搜索。那我们耿直一波？$10^{18}$个字符，抬走了。
这里做法其实应该是比较显然的，DFS。我们根据字符串长度，由于$f_n=s_0+f_{n-1}+s_1+f_{n-1}+s_2$，我们可以判断出这个位置是落在哪一节里面，然后不断DFS下去，可以找到独立的那一节，直接输出就行。
很有趣的题目，这个DFS可以说是很棒的题目了。
现场学习算法系列。
刚好是一个空缺。其实挺好的，前几个月停留在不知道要求什么，现在已经到要怎么求的状态了，是一种进步？
题目其实一看就是卡时间的。给出一个$n$长度的正整数排列，然后给出$m$组翻转，每组为$[l_i,r_i]$。问每一步的逆序数的奇偶性。
一上来就直接求逆序数。根据我们知道的，朴素算法$\mathcal{O}(n^2)$时间内能求，但是肯定会超时。
现场学习了树状数组求逆序数，树状数组就不讲了，主要是用树状数组怎么求，其实很简单，由于题目给出的是一个排列，那我们只需要单点更新同时统计。更新的时候我们把出现过的数置$1$，然后根据前缀和特性就可以求。这个方法核心在
pos-getsum(num)，pos就是当前有多少个数，getsum(num)就是这个数前面有多少个数，那其实很简单，就是现在有的数减去前面的数，自然就是后面的数，后面所有的数都和这个数构成一组逆序，那后面有几个就有几组逆序。根据树状数组特性，知道这样复杂度是$\mathcal{O}(nlogn)$。当然，这只是顺便一提，这个题根本不用这么做。首先考虑对于一个长度为$k$的序列会有几组逆序。我们考虑$4,3,2,1$，这就是完全逆序，所以我们得到了$\binom{k}{2}$，这也就是最多可出现的逆序对。那当我们整个翻转之后，整个顺序刚好颠倒，那假设前面占了$x$种，这里正好就是$\binom{k}{2}-x$。好了，小学数学time，偶数加偶数等于偶数，偶数加奇数等于奇数。所以这里根本不用管有几种，加上$\binom{k}{2}$万事大吉。所以这个题就解决了，甚至$\binom{n}{2}=\frac{n(n-1)}{n}$，$\mathcal{O}(m)$解决战斗。
这个题有点意思，我们可以抛弃一些看似需要其实不需要的属性，然后求解。
这个题，把$1,2,\cdots,n$划分成两个非空集合，让$|sum(s_l)-sum(s_r)|$尽可能的小。构造解问题。
这个其实很容易就能知道，这些数的和要不为奇数要不为偶数，那么两份均分后要不两份大小相等，要不这两份的差为1。接下来要考虑怎么切分，根据$\sum^{n}_{i=1}i=\frac{n(n-1)}{2}$，那么实际上可以观察出我们这个和的大小会均分成4份。这里很容易可以看出来，可以模拟试一下。那么我们知道对于连续的四个数$i,j,k,l\in{1,2,\cdots,n}$，这四个数必定满足$i+l=j+k$。那到这一步就简单了，挨个遍历四元集$(i,j,k,l)$，然后构造即可。
这个题难在拆分算法构造上，一开始很容易直接二分然后两头构造，但是并不是所有可行元素都是集中在两头和中间的。这里我们的做法是一种分治：按大小为4划分子块，保证每个子块的划分都满足题目要求，那完全划分完后的整个序列也满足题目要求。
0x03. 难题
这个月好像没什么让我印象深刻的难题……可能还是因为太忙了做题少……
That’s All.
1月要好好刷题啦！