Tips

仅含题解,代码详见github喜欢的话点个star

1002. Ch’s gift

首先考虑序列上的问题。

$a$ 是一个二维数组,如果第 $i$ 位置的值为 $j$,就在 $a_{i,j}$上加上 $j$ 。那么某个询问 $x,y,a,b$ 的答案就是子矩阵的和。如果一开始就把二维前缀和算出来的话就可以回答$O(1)$,答案等于 $(Sum(y,b)-Sum(y,a-1))-(Sum(x,b)-Sum(x,a-1))$ 。

考虑到 $a,b$ 的范围非常大,可以把所有询问离散化。当然就算离散化,预处理二维前缀和还是不行的,我们发现前缀和相当于把 $[a,b]$ 拆成 $[1,b]-[1,a-1]$,联想到扫描线,把 $a,b$ 这一维的每个区间拆成两条线,用扫描线从小到大扫这一维,$x,y$ 这一维直接预处理一下前缀和每次 $O(1)$ 查就行了。

再搬到树上,直接套一个树链剖分就行了,树状数组就能维护。

ps: 可持久化线段树可以在线回答,等写出来了更新

1005. FFF at Valentine

强连通缩点加拓扑序判分叉,不多说了。

1006. Senior Pan

这题主要是题意有点不清楚。。。大小为 $k$ 的端点集合,题目的意思是起点终点不能是同一个【不过也是有道理的。。。

拆点,加超级源超级汇,再跑一下dij 。这个限制可以每个点维护一下被谁松弛过,比如现在想用 $i$ 松弛 $j’$,如果 $j$ 松弛过 $i’$,直接不让松弛就行了。一个点被松弛的次数小于总点数,复杂度也就是多个 $logn$,具体表现可能比20次dij好一点吧。

1008. Numbers

从小到大取,$O(n^2logm)$,$n$ 是 $\sqrt{m}$ 级别。

1010. Two strings

主要还是题意比较坑。。。匹配.*是要把.先变成某个字符再处理*。。。

队友(wenwenla)写了一种dp,先预处理pattern,dp[i]保存pattern前i个字符为止可以匹配到text的最左和最右,可以证明这个界里面的每一个都是可取的。

具体实现加一维表示最左最右,然后发现第一维可以去掉。

1010.cpp

时间0ms,就是容易写错。。。比赛的时候前面WA的都交上去了,最后一次AC的代码却没交上去[cry]。。。而且我们亲眼看到点了submit以后页面跳转了。。。结果连提交记录都没有??

后来有人说了才发现这样直接正则就能过。这题出得真好??

1010_regex.cpp