CF 1900 选做

标签：字符 选做 log 复杂度 不选 CF 提交 mathcal 1900

by Duck.

CF1012B Chemical table

双倍经验 eJOI2018 同名题目。

经典套路题。

我们把行号和列号建成二分图，那么这个连边条件可以看作，\((r_1,c_1),(r_1,c_2),(r_2,c_2)\) 之间有边后就会自然导致 \(r_2,c_2\) 连通。最后的目标是让所有点联通。

并查集维护连通性，答案就是连通块数 \(-1\)。时间复杂度线性。

提交记录

CF1012C Hills

双倍经验 eJOI2018 同名题目。

考虑朴素的 dp。设 \(f(i,j,0/1,0/1)\) 表示前 \(i\) 个中有 \(j\) 个满足条件，且 \((i-1)\) 和 \(i\) 分别是否被选中。显然，不能存在 \(i,i+1\) 同时选中的情况。

转移稍微讨论一下。记将 \(x\) 提到 \(y\) 的操作次数为 \(g(x,y)=\max(0,y-x+1)\)。

• \(i,i-1\) 都不选。则有

\[f(i,j,0,0)\leftarrow \min\{f(i-1,j,1,0),f(i-1,j,0,0)\} \]

• \(i\) 选，\(i-1\) 不选。如果 \(i-2\) 选了就需要考虑 \(i-1\) 的大小，\(v_{i-1}=\min(a_{i-2}-1,a_{i-1})\)。可以得到

\[f(i,j,0,1)\leftarrow \min\{f(i-1,j-1,0,0)+g(a_i,a_{i-1}),f(i-1,j-1,1,0)+g(a_i,v_{i-1})\} \]

• \(i-1\) 选，\(i\) 不选。此时 \(a_{i-2}\) 只能不选，故有

\[f(i,j,1,0)\leftarrow f(i-1,j,0,1)+g(a_i,a_{i-1}) \]

时间复杂度 \(\mathcal{O}(n^2)\)。

提交记录

CF1119E Pavel and Triangles

因为 \(2^i\) 的条件卡得很死，从而三角形只可能有两种形状，等边三角形 \((2^i,2^i,2^i)\) 或着腰更长的等腰三角形 \((<2^i,2^i,2^i)\)。在这两种三角形中，我们优先匹配等腰。

开一个堆维护每种边的剩余数量，扫到 \(i\) 时找堆中的剩余边拿出来匹配等腰，剩下的匹配等边，多余的扔到堆里作为剩余。

时间复杂度 \(\mathcal{O}(n \log n)\)。

提交记录

CF1178E Archaeology

挺 tricky 的题目。

注意到题目给出的两个重要性质：相邻的字符不相同。字符集大小为 \(3\)。

由于只需要找长度为原串一半的回文子序列，考虑从头尾各拿出四个字符，根据抽屉原理和相邻字符不相等的性质，必然存在两个字符相等，且一个在头一个在尾。

我们只留下这两个字符，把不同的删掉。如此操作，就可以得到一个长度为一半的回文子序列。

时间复杂度 \(\mathcal{O}(n)\)。

提交记录

CF1205B Shortest Cycle

按位考虑，如果某一位上有 \(\geq 3\) 个数为 \(1\)，那么就直接形成了三元环。否则只有 \(\leq 2\) 个数能够在这一位上匹配，我们在这两个点之间连边。这样就把图简化成了 \(\mathcal{O}(\log V)\) 个点和边的图。

接下来只需要朴素地找一个最小环即可。可以用各种最短路算法实现。

这里采用 Floyd，时间复杂度 \(\mathcal{O}(n \log V+\log^3 V)\)。

提交记录

标签：字符,选做,log,复杂度,不选,CF,提交,mathcal,1900
From： https://www.cnblogs.com/duckqwq/p/18132122