ARC vp

ARC165

\(\rm Performance\ 2691\)，\(4\) 题。

打得比较正常，唯一缺憾是 \(\rm E\) 不会。

A - Sum equals LCM

略。

B - Sliding Window Sort 2

略。

C - Social Distance on Graph

把边排序之后直接判断当前是否是二分图，如果不是就寄了，算一下答案即可。

D - Substring Comparison

我们尽可能让限制在比较短的地方合法。

那么直接枚举合法的长度，建边之后缩点，不同 \(\rm scc\) 之间已经合法，同一个 \(\rm scc\) 内的限制则直接加入下一个长度，如果所有条件均合法直接退出。

需要注意的是每次建图要在缩点之后的图上建，不过我直接在原图上建边也过了。

E - Random Isolation

单独考虑每个连通块的贡献，发现如果这个连通块的大小 \(\ge k\) 则一定要被删一次，设 \(U\) 为连通块集合，\(P(T)\) 为连通块 \(T\) 出现的概率，则答案就是 \(\sum_{T \in U} P(T)\)。

考虑固定 \(T\) 如何计算 \(P(T)\)，设 \(n\) 为 \(T\) 的大小，\(m\) 为与 \(T\) 直接相连的点个数，那么最终要形成连通块 \(T\)，显然要先把 \(m\) 个点删完，并且这 \(n\) 个点必须没被删，所以概率是 \(\dfrac{n!m!}{(n+m)!}\)。

然后直接树形 DP 就行了。

F - Make Adjacent

感觉是个很套路的题。

考虑什么情况下 \(x\) 一定要在 \(y\) 前面，设 \(l_i,r_i\) 为 \(i\) 的两个出现位置，那么条件是 \(l_x<l_y\) 且 \(r_x<r_y\)。

于是直接主席树优化建图即可。

ARC162

\(\rm performance \ 2195\)，\(3\) 题，打得非常唐。

不光手速很慢还四发罚时，并且 \(\rm D\) 在硬 DP，没往 \(\rm prufer\) 序列上考虑，最终搞出了一个很阴间的 \(\Theta(n^4)\) DP。

A - Ekiden Race

略。

B - Insertion Sort 2

直接插排，\(\rm NO\) 写成 \(\rm -1\) 罚了一发。

C - Mex Game on Tree

不难发现如果后手在某个点塞个 \(k\)，那么这个点到根的链上的所有点都废了。

并且如果先手需要走两步，后手一定可以在先手走一步之后塞个 \(k\)。

所以先手必胜仅当一步取胜。

直接判断就行了，不知道为什么罚了三发！！！！

D - Smallest Vertices

先考虑如何计数合法树个数，直接在 \(\rm prufer\) 序列上考虑，答案显然是 \(\dfrac{(n-2)!}{\prod (d_i-1)!}\)。

然后固定 \(x\) 计数 \(x\) 对答案的贡献。

直接 DP 就行了，由于上面那个式子所以只关心一个连通块的出度之和以及点数，都加到状态里就行了。

E - Strange Constraints

具有启发意义的题。

首先题目看上去非常难做，这个“\(B_i\) 的出现次数最多为 \(A_i\)“的限制条件直接导致了按照 \(A_i\) 的顺序填与 \(B_i\) 的顺序填都无法做到多项式复杂度，因为信息难以记录。

考虑换一种顺序填，按照个数从大到小填。

为什么这样是对的呢？假设我们当前在填次数为 \(i\) 的数。那么我们需要知道：

• 当前序列中有几个 \(j\) 满足 \(A_j \ge i\)，并且值为 \(j\) 的数没被填过。
• 当前序列中有几个 \(j\) 满足 \(A_j \ge i\)，并且位置 \(j\) 上没有数。

我们发现现在的信息都是“个数”，换句话说，都是 \(\Theta(n)\) 级别的，至少能够轻松做到多项式复杂度。

如果你已经知道了填入顺序，这题自然也变成了一道基础 DP 题，直接设 \(dp_{i,x,y}\) 表示填到次数 \(i\)，有 \(x\) 个值被填了，\(y\) 个位置被填了。

转移可以直接来，复杂度稍微分析一下就能发现是 \(\Theta(n^3)\) 的。

F - Montage

具有启发意义的题。

考虑将空行和空列都缩起来之后再计数。

不难发现此时每行的 \(1\) 都是一个区间并且从上到下左右端点都单调不升，而且任意两个 \(1\) 都八连通。

于是直接 DP 计算即可。

ARC179

打得同样很唐，主要原因是出题人放了 \(\rm D\) 这个答辩题，并且我不会调题。

A - Partition

赛时 \(+\) 看成 \(\times\) 了，浪费了一点时间。

只要排个序就做完了。

B - Between B and B

暴力状压。

C - Beware of Overflow

比较显然的是在题目的约束条件下若每次都取最大值和最小值那一定合法。

于是可以用线段树维护全局 \(\max\) 和 \(\min\)，注意询问需要记忆化，而且细节一车（我只会想恶心做法）。

D - Portable Gate

赛后又调了 \(1h\) 才过 /oh

如果没有传送，那答案就是 \(2 \times (n-1)\)。

枚举根，然后是一个普及组 DP，设 \(dp_{x,0/1}\) 表示在点 \(x\)，是否需要回到根的最大减少的遍历次数，转移直接来，能轻松做到 \(\Theta(n^2)\)。

然后换根一下就做完了，但是细节令人上头。

E - Rectangle Concatenation

感觉是好题。

用一个二元组 \((x,y)\) 表示当前遍历到 \(x\)，\(x\) 的方向是竖着还是横着。

那我们考虑 \((x,0)\) 和 \((x,1)\) 是否能转移到 \((x+1,0)\) 和 \((x+1,1)\)。

比较显然的是如果 \(h_x=h_{x+1}\) 那么 \((x,0) \rightarrow (x+1,0)\)，如果 \(w_x=w_{x+1}\)，那么 \((x,1) \rightarrow (x+1,1)\)。

现在需要解决的问题是 \((x,y)\) 与 \((x+1,1-y)\) 之间的转移。

我们可以发现一个性质：若 \((x,y)\) 能转移到 \((x+1,1-y)\)，那从 \(l\) 遍历到 \(x\) 的矩形面积是确定的，于是 \(l\) 就确定了，我们将这条转移边放到点 \(l\) 上，等到遍历到 \(l\) 时加入这条边即可。

现在我们已经可以维护出这张图了，考虑计算答案。

比较显然的是对于一个 \(l\)，符合条件的 \(r\) 是一段区间，于是线段树上二分一下即可。