Contest Info

date 2017.08.03 12:00-17:00

practice link

Solutions

A. Big Integer

题目大意：给你一个 \(01\) 矩阵 \(g\) ，问你满足下面要求的 \(k\) 进制数有多少种： 不出现数字 \(0\) ；设数字 \(i\) 出现 \(cnt_{i}\) 次，要求有 \(0\le cnt_{i}\le n, g_{i,cnt_{i}}=1\) 。在上述问题下进行 \(m\) 次修改操作，每次给出 \(u, v\) ，把 \(g_{u,v}\) 取反。最后问 \(\sum_{i=0}^{m}ans_{i}\) ，\(ans_{i}\) 表示第 \(i\) 次修改操作后的答案。

题解：易得答案为 \(\displaystyle ans=\sum_{i=1}i!\sum_{\sum_{j=1}^{k-1}cnt_{j}=i}\prod_{j=1}^{k-1}\frac{g_{j,cnt_{j}}}{cnt_{j}!}\) 。

这就成了我们熟悉的卷积形式， 可以用 \(NTT\) 加速，求出初始答案的这一部分的复杂度为 \(\mathcal{O}(nk^{2}\log nk)\) 。同时我们注意到只要求所有答案的和，所以可以先不 \(IDFT\) ，把每次修改得到的\(DFT\) 的乘积全部加起来以后再 \(IDFT\) 。

考虑每次修改操作，由于每次只修改矩阵的一个位置，也就是只改变一个多项式的一项的系数，而 \(c_{k}x^{k}DFT\) 后的多项式为 \(\sum_{i=0}^{d-1}c_{k}(g^{\frac{p-1}{d}})^{ik}x^{i}\) ，这个多项式容易在 \(\mathcal{O}(nk)\) 的时间内计算，然后把这个多项式加到原来那个\(DFT\) 后的多项式上，并重新计算一次答案就可以了。

这里有一个小优化，如果每次都把这个新多项式的一项 \(\mathcal{O}(k)\) 地和其它多项式相乘，总复杂度为 \(\mathcal{O}(nk^{2}m)\) ，不能通过本题。我们可以对每个位置记录所有非 \(0\) 数的乘积和 \(0\) 的个数，即可 \(\mathcal{O}(1)\) 修改一项的答案，复杂度为 \(\mathcal{O}(nkm)\) 即可满足时间限制。总复杂度 \(\mathcal{O}(nk^{2}\log nk+nkm)\) 。有个大坑是 \(0\) 位数不算。

tips： \(NTT\) 对加法和数乘也保持性质，虽然很显然，但是以前没有注意过，看起来有时候还是能用上的。如果这道题硬是每次询问都 \(IDFT\) ，复杂度就有 \(\mathcal{O}(nk^{2}\log nk+nkm\log nk)\) ，再加上 \(NTT\) 的常数，妥妥地 \(T\) 爆。

B. Classic Quotation

题目大意：给出两个字符串 \(S\) 和 \(T\)，长度分别为 \(n\) 和 \(m\)（\(n \leq 5 \times 10^4\), \(m \leq 100\)），现在有 \(k \leq 5 \times 10^4\) 次询问，每次询问给出 \(L\) 和 \(R\) （\(1 \leq L \leq R \leq n\)），问将 \(S\) 的一个前缀 \(S[1\cdots i]\) 和一个后缀 \(S[j\cdots n]\) 拼起来的串中，\(T\) 出现了多少次，求对于所有 \(i\leq L\) 且 \(R \leq j\) 的所有情况的和。

题解：考虑 \(T\) 在拼起来的串中出现的情况，分为三种：

• 在前缀 \(S[1\cdots i]\) 中出现
• 在后缀 \(S[j\cdots n]\) 中出现
• 在前缀 \(S[1\cdots i]\) 和后缀 \(S[j\cdots n]\) 的拼接部分出现

我们可以先跑一次 kmp 算法，算出 \(T\) 在 \(S\) 中出现的次数和出现位置的前缀和，分别记为 \(pre_i\) 和 \(sum_i\)。类似的也可以处理后缀的情况，同时再预处理出 \(f[i][k]=\sum\limits_{j=1}^{i} \left[S[(j-k+1) \cdots j]=T[1\cdots k] \right]\) 和 \(g[i][k] = \sum\limits_{j=i}^{n} \left[S[i\cdots (i+k-1)]=T[1\cdots k]\right]\)。那么对于询问\((L,R)\)，第一种情况的贡献为 \((pre_i \times (L+1) - sum_i) \times (n-R+1)\)，类似的可以去计算第二种情况的贡献，而第三种情况的贡献为 \(\sum\limits_{k=1}^{m-1} f[L][k] \times g[R][m-k]\)。

C. Counting Divisors

题目大意：求 \(\sum_{i=l}^{r}\sigma(i^{k})\) 。

题解：由于 \(r-l\le 10^{6}\) ，我们考虑暴力把每个 \(i\) 质因数分解，注意到 \([l,r]\) 中的数不会有超过 \(1\) 个大于 \(\sqrt{r}\) 的质因子，所以我们用 \([2,\sqrt{r}]\) 中的质数筛一遍就好了。

D. Dirt Ratio

题目大意：给你一个数列 \(\{ a_i\}(1\leq a_i\leq n)\)，定义一个区间的价值为：区间内数的种类除以区间长度。求所有区间中的最小价值。

题解：二分答案。二分一个答案 \(ans\)，我们需要验证是否存在一个区间 \([l, r]\) 满足 \(\displaystyle \frac{cnt[l, r]}{r-l+1}\leq ans\)。稍微做一下变形： \(cnt[l,r]+ans\cdot l\leq ans\cdot (r+1)\)。

我们从小到大枚举 \(r\)，对于给定的 \(r\)，左边可以被看做是以 \(l\) 为变量的一个函数 \(f(l)\)。在 \(r\) 从 \(r-1\) 移动而来的时候，显然 \(next[r]+1, \dots, r\) 的 \(f\) 值都会增加 \(1\)。其中 \(next[i]\) 是上一个 \(a_i\) 出现的位置。用线段树维护区间修改和区间最值即可。复杂度 \(O(n\log n\log w)\)。

E. Lazy Running

题目大意：给你一个四元环，求从点 \(2\) 出发回到点 \(2\) ，长度大于等于 \(k\) 的最短路。

题解：找到任意一个从 \(2\) 出发的环，设环长为 \(w\) ，显然若有一条长度为 \(L\) 的路，那么长度为 \(L + w\) 的路也存在。于是我们可以在模 \(w\) 的剩余系中讨论。

设 \(dis[i][j]\)表示从 \(2\) 出发，到 \(i\) 结束，长度模 \(w\) 为 \(j\) 的最短路 ，则 \(ans =\mathrm{min}_{i\geq k,dis[2][i\%w]\leq i}i\) 。而求 \(dis[i][j]\) 我们只需要跑一次最短路即可。另外一个显然的事实是，为了提高时间效率， \(w\) 应取最小环长，在本题中就是 \(\mathrm{min}(2d_{12}, 2d_{23})\) 。

F. Logical Chain

题目大意：给你一个 \(n(1\leq n\leq 250)\) 个点的无自环无重边的有向图 \(G\) 的邻接矩阵 \(\{g_{ij}\}\)。\(m(1\leq m\leq 25000)\) 次修改，每次修改将 \(k_i\) 个 \(g_{uv}\) 的值取反。每次修改之后输出 \(\displaystyle \sum {cnt_i \choose 2}\)，其中 \(cnt_i\) 是第 \(i\) 个 \(SCC\) 的点的个数。

题解：利用 Kosaraju 算法求强连通分量，只需要正反图各做一次 dfs 即可。但是对稠密图来说，每次的复杂度是 \(O(n^2)\) 。

Kosaraju 在稠密图中的瓶颈在于每次寻找与点 \(u\) 相连且未访问过的点。我们用 bitset 来保存边表 \(g_u\) 和未访问过的点集 \(S\)，每次从 \(g_x\land S\) 中取出 \(1\) 即可在 \(O(\frac{n^2}{64})\) 的时间内求解。对于每次修改之后的图暴力求解。注意取出 \(1\) 的操作在內建的 bitset 中并没有对应操作，需要手写压位。

G. Matching In Multiplication

题目大意：给你一个二分图，\(U, V\) 两部的点数相同，\(U\) 中每个点的度数恰为 \(2\)，\(V\) 中每个点度数至少为 \(1\)。定义一个完备匹配的价值为所有边权的乘积。求所有完备匹配的价值之和。

题解：从 \(V\) 部中依次找到度为 \(1\) 的点，显然它们关联的边一定在匹配中，我们可以不断地去掉这样的点和边。那么剩下的图中两部的点数各有 \(m\) 个点，每个点的度数都不小于 \(2\)。并且 \(U\) 部中总点数为 \(2m\)，因此 \(V\) 部中也只能是每个点度数都是 \(2\)。说明剩余图中每个联通块是一个环。环的完备匹配对边染色即可，一共两种方案。

H. Phone Call

题目大意：给你一棵树和 \(m\) 条线路。每条线路是一个五元组 \((a, b, c, d, w)\)，表示任意两个不同的点 \(u, v\in S(a, b)\cup S(c, d)\) 使用这条线路连通的代价为 \(w\)。其中 \(S(u,v)\) 表示从点 \(u\) 到点 \(v\) 路径上的所有点的点集。先从点 \(1\) 出发，使用一些线路与某些点连通。然后再从已经与 \(1\) 连通的点出发，使用线路与其他点连通。不断重复上述过程，问点 \(1\) 最多能与多少个点连通，在此基础上，最小代价是多少。

题解：显然题目描述就是用 Prim 算法求最小生成树的过程。我们用 Kruskal 算法同样正确。我们将所有线路按代价从小到大排序。对于每条线路 \((a, b, c, d, w)\)，我们先把 \(S(a, b)\) 中的每条边的两端点合并，这等价于每个点合并到 \(\text{LCA}_{ab}\)， \(S(c,d)\) 同理，最后再合并 \(\text{LCA}_{ab}\) 和 \(\text{LCA}_{cd}\)。

为了避免每条边被合并多次，我们可以用另外一个并查集进行树上缩点，每次先跳到该点到根的路径上最深的还未合并的点进行合并。

I. Questionnaire

签到题

J. Security Check

题目大意：给出两个队列 \(A\) 和 \(B\) ，\(A\) 和 \(B\) 都是 \(1\) 到 \(n(n \leq 10^5)\) 的排列。我们可以花 \(1\) 的时间让 \(A\) 或者 \(B\) 的队首出队，如果某个时刻 \(A\) 和 \(B\) 的队首相差超过一个给定的正整数 \(k(k\leq 10)\)，那么我们可以花 \(1\) 的时间让它们同时出队。问至少要多少时间才能让两个队列都为空。

题解：考虑一个\(dp\) ，\(f(i,j)\) 为队列 \(A\) 中前 \(i\) 个和队列 \(B\) 中前 \(j\) 个都出队的最小时间，则有 \[f(i,j)= \begin{cases} f(i-1,j-1)+1,&\left|A_i-B_j\right|>k\\ \min\{f(i-1,j),f(i,j-1)\}+1,&\left|A_i-B_j\right|\leq k \end{cases} \] 显然，第二种情况只会出现 \(O(nk)\) 次，直接暴力转移即可。

而对于第一种情况，我们可以直接二分找到一个最小的 \(t\) ，满足对 \(\forall i\in [1, x-t]\) 都有 \(\left| A_{t+i} - B_{y-x+t+i}\right| > k\)。也即最小的 \(t\) 满足 \(\left| A_t - B_{y-x+t}\right| \leq k\)。这样就可以加速 \(f(x,y)\) 的转移：

\[f(x,y) = f(t, y-x+t) + (x-t)\]

因为断点（第二种情况）很少，所以我们也只需要二分转移 \(O(nk)\) 次。我们在预处理的时候，将不能由第一种转移的状态 \((x,y)\) 按照 \(x-y\) 的值分类，对于每一个不同的 \(x-y\) 的值用一个 vector 顺序存储所有的 \(x\)。询问的时候，只需要去 \(x-y\) 对应的 vector 中找到最大的小于 \(x\) 的 \(t\) 即可。

最终复杂度为 \(O(nk\log n)\)。具体实现的时候，用记忆化搜索会方便很多。

tls 有个 nk 的算法

K. Time To Get Up

签到题

L. Wavel Sequence

题目大意：序列 \(\{a_i\}\) 是一个 wavel，当且仅当满足 \(a_1 < a_2 > a_3 < a_4 > a_5 < a_6 \dots\)。给定两个长度分别为 \(n,m\) 的序列 \(\{a_i \}\) 和 \(\{b_i \}\)。求有多少个是 wavel 的公共子序列。

题解：

法一：定义 \(dp[i][j][0/1]\) 表示一定以 \(a_i\) 和 \(b_j\) 结尾的，接下来要下降/上升的 wavel 的公共子序列个数。初值 \(dp[i][j][1] = 1\) 对于满足 \(a_i=b_j\) 的 \((i,j)\)。那么很容易写出转移方程：

\[ dp[i][j][0/1] = \sum_{i'<i} \sum_{j'<j}dp[i'][j'][1/0] \]

其中 \(a_i=b_j=x, a_{i'}=b_{j'}=y\)。\(x,y\) 满足对应的大小关系。那么我们可以从小到大枚举 \(i\)，然后用二维树状数组维护 \(j, x\) 这两维，时间复杂度 \(\mathcal{O}(nm\log ^2 2000)\)。实际加一些剪枝可以跑得很快。

法二：（tls队的做法）令 \(g[i][j][0/1] = \sum_{k=1}^j dp[i][k][0/1]\)。那么我们可以得出转移方程：

\[ dp[i][j][0/1] = \sum_{i'<i} g[i'][j-1][1/0] \]

且满足 \(a_i > a_{i'} (0)\) 和 \(a_i < a_{i'} (1)\)。我们只需要对每个 \((j, 0/1)\) 维护一个关于 \(a_i\) 的树状数组即可。

时间复杂度 \(\mathcal{O}(nm\log 2000)\)。实际上我写出来比法一慢了很多，要加一些常数优化才能通过。原因主要是 \(g\) 数组是一个前缀和，非零的元素比较多，每个元素都要在树状数组中进行插入。

法三：（题解的做法）令 \(g[i][j][0/1] = \sum_{k=1}^i dp[k][j][0/1]\)。我们最外层枚举 \(i\)，内层枚举 \(j\)。用两个变量分别记录 \(a_i < b_j\) 和 \(a_i > b_j\) 的 \(g[i-1][j][1/0]\) 的前缀和，在 \(a_i = b_j\) 的时候累加上去。时间复杂度 \(\mathcal{O}(nm)\)。

M. Yuno And Claris

unsolved

Replay and Summary

Replay

慌得一批，不知道在慌什么。W 一来就看了 M 题，跟 D 讨论了一下，W 感觉完全不可做，然而 D 说可以怎么两个树状数组套在一起做一下，就去写了。结果写到后面发现算法错了，浪费了很多时间，很伤。

然后就是把签到题 I 和 K 做了。期间 Z 来做 C 题，常数比较大，TLE 了两发。把常数优化之后交到了 M 题去，可以看出当时有点慌。

做完三题之后就一直在卡题。W 想了一个错误的 G 的结论，写到一半发现写不下去了，然后过了一会儿发现其实应该先确定一定能匹配到的边，然后剩下的就全是环了，然后 A 了这题。

D 题的话想二分答案没有想出来，但是标程就是二分答案。后来看数据范围比较小，而且时限比较大，就随便搞了一个固定左端点跳右端点的做法，也过掉了。

L 题一开始就想了一个 \(O(n^2\log ^2n)\) 的做法，觉得过不了但是后来还是写了一发，数据比较弱就水过了，以后还是得先写一下。

最后阶段 W 和 D 一起重新看了看 B，然后花了十几分钟讨论，就交给 D 去做了，一发 ac，非常鼓舞人心。

很难受的是 W 和 D 一直在想 H，而 Z 一直再想 E，都没有想出来。

coldwater

这场一开始有点僵硬，三题的状态持续了很长时间。D 和 L 拿在手上很长时间，感觉都有点想法，但是都不是很确定。最后瞎搞了一个 D 过了，L 用很不优秀的复杂度也过掉了，感动于数据的弱。G 题做的时候有点着急，一开始想了一个错误的想法占用了很久键盘。最后一小时和 D 讨论了一下 B 的做法，很快想到了正解，但是有点不敢写，让 D 去写了。写完之后一发 ac，很开心。最后 40mins 完全不能像 tls 他们一样每次都翻盘 a 两题，以后还是得多开一些题。

ShinriiTin

非常蠢，一开始脑子秀逗了写 M，浪费 2h+ 写了 200+ 行代码终于发现自己算法错了。一开始写了一道签到题，之后又和 W 讨论了一会儿 B 就写了过掉了。最后一直在想 H，想要改 Prim 算法做，但是一直想不到好的从点找到覆盖它的链的方法，由于时间不够也没有往 Kruskal 的方向去想。 不应该这样没仔细想清楚就写很长的代码，如果方向错了就是白白浪费了大量时间，以后要特别注意。

zhongzihao

这场完全在划水，只写了一道做过一万遍的筛法 C ，然后就卡了 4 个小时 E 。感觉问题出在纯数学题只有 A 和 C ，而 A 太难现场没人过，结果直接就没题可做了。说明分到的题目类型还不够多，个人感觉其它的一些类似于 E 的思维题，和 J L 这样的 DP 题也应该要会。之后可能要视情况稍微增加一些这样题目的练习。