目录

12月做题记录

0x00. 前言

大家好,我是Ramen。

12月注定是很忙的一月,大作业验收+ACM新生杯,还有其他各种各样的事情。嘛,最后反正都能顺利解决的吧。

这个月也就打了很多比赛,感觉打比赛成为常态,学习停滞了,不是很好。下个月寒假,开始学习新的东西了!

GSoC 2018也要开始了,套词好像很难的样子,稍微准备准备吧。

我的答案仓库是 Click Me!。根据题号你能找到我的答案,但是我的答案有很大改进余地,欢迎与我探讨。

0x01. 模板题

很忙的一个月,没刷模板题,跳过了。

哎!

0x02. 趣题

思路有趣是做题最爽的,有趣的思路就是有趣的题目。有趣,也是我打ACM的本源动力嘛。

  1. Monk and Operations

    Another India Site. 印度人在这方面是比中国人走得远,各种专门的面试网站算法网站,GSoC也是组团去的,真的是十分团结。这个网站也是十分热心,注册了之后我做了一道水题就没管了,结果好几封邮件问我怎么不来。

    扯远了,看题。一个$n\times m$的矩阵$A$,你可以进行四种操作:

    1. 选一行,把这一行全部加上$v1$;
    2. 选一行,这一行全部改成$v2$;
    3. 选一列,把这一列全部加上$v3$;
    4. 选一列,把这一列全部变成$v4$。

    任意一种操作你可以执行无数次,但是每一个格子至多执行1种操作。也就是说,这个格子可以不执行操作,假如执行了,那就是上面的任意一种,也只能有这一种。

    答案问的是最大的$F(x)$,其中$F(x)$我们这么定义:

    $$ F(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}|a_{i,j}| $$

    这个题其实深入分析题意,我们知道,一个格子要么是本行被改,要么本列被改。有什么问题吗?很简单,一改就涉及一行或者一列,任何不同方向上的操作都会导致至少1个格子操作了两次。那实际上,这个题就是针对每行,针对每列计算最大$F(x)$,然后比较对行对列操作的最大值修改即可。简单吧?

    思路有点意思,一开始我以为需要状态压缩DP,后面再度分析才发现的确不难。

  2. Almost Difference

    车祸题。出题人错误估计答案范围,结果答案范围超过了$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)$。

    这个题的后缀和做法让我还是记忆犹新,这也是难得我在比赛时思路能如此清晰的一次。

  3. Nephren gives a riddle

    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可以说是很棒的题目了。

  4. Inversion Counting

    现场学习算法系列。

    刚好是一个空缺。其实挺好的,前几个月停留在不知道要求什么,现在已经到要怎么求的状态了,是一种进步?

    题目其实一看就是卡时间的。给出一个$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)$解决战斗。

    这个题有点意思,我们可以抛弃一些看似需要其实不需要的属性,然后求解。

  5. Dividing the numbers

    这个题,把$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月要好好刷题啦!