• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

CF592D Super M(2200)

\(\mathcal O(n)\)暴力构建虚拟树,答案是\((n-1)\乘以2-mx\)(\(n\)是虚拟树的总数,(mx\)是虚拟树的直径),时间复杂度\(\mathcal O(n

CF601B Lipshitz Sequence(2100)

易,最大值只会出现在相邻两个数之间,不会跨数。因为需要区间分段的答案,所以一定不能破。考虑一个数可以有多少个子段作为最大值,可以用fhq \(\mathcal O(n \log n)\)或者monotonic stack \(\mathcal O(n)\)维护。时间复杂度\(\mathcal O(qn)\)。

CF601C Kleof and the n-thlon(2300)

设\(f_{i,j}\)代表在历次\(i\)比赛中获得总分\(j\)的期望人数。那么答案就是\(1 \ sum \ limits _ { I=1 } { sum-1 } f _ { n,i} \)(其中\(sum\)是所有\(c_i\)的和)。传递方程很明显:\ (f _ {i,j }=\ frac { \ sum \ limits _ { k=1 } { m } f _ { I-1,j-k} (k \ ne c _ i)} {m-1} \)。时移前缀和优化。时间复杂度\(\mathcal O(nm)\)。

CF1338A Powered Addition(1500)

如果这个数大于上一个数,那么保持这样显然是最优的。如果这个数小于前一个,我们二进制计算它至少需要几轮运算才能大于前一个。只取最大值,时间复杂度\(\mathcal O(n \log n)\)。

CF1338B Edge Weight Assignment(1800)

考虑第一个问题,如果树中所有叶节点之间的距离都是偶数,那么答案是\(1 \);否则可以按如下方式分布:当点\(1\)为根时,我们称到根节点距离为奇数的叶节点为奇点,类似于定义偶点。如果奇点的距离是\(2k 1\),我们从上到下填入\(2k\) \(3\)和\(1\)。如果偶数点之间的距离是\(2k\),我们从上到下分别填入\(2k-1\) \(3\)和\(2\)。很容易知道这是正确的,所以只需要\(3\)种颜色。

考虑第二个问题。如果几个叶子节点的父亲相同,那么这些节点的连通边的权重也一定相同。不然随便填,就满意了。只需要数一数每个点的叶子数。

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

CF1338C Perfect Triples(2200)

找到一个模式。

\(a\)的值将序列分成若干块,每个块中的\(a\)是从\ (2 k \)到\ (2 {k 1}-1 \)的连续整数。

在同一个块中,可以递归构造\(b\)的值。每次把大块分成四个小块,取最小值\(1,3,4,2\)。

在同一个块中,可以递归构造\(c\)的值。每次把大块分成四个小块,取最小值\(1,4,2,3\)。

CF842E Nikita and game(2800)

由于几个直径之间有相交部分,所以维护\(s1,s2\)分别表示相交部分周围的点。那么每个点的直径要么是常数,要么更大。如果没有变化,就在对应的集合上加点。如果改变,清除对应的集合,判断另一个集合的点,将距离加到新的直径上。容易证明复杂性是正确的。时间复杂度\(\mathcal O(n \log n)\)。

AT4754 [ABC126F] XOR Matching(1770)

结构简单。第一,如果\ (k \ ge2 m \),无解。其次,受\ (0 1 cdots (2 m-1)=0 \)启发,构造\ ((0,1,2,\ cdots,2 m-1)(排除\(k\)如下。时间复杂度\(\mathcal O(n)\)。

AT3884 [ARC090D] Number of Digits(2891)

分类讨论。

\ (s \ leq10 8 \)时,那么当\ (l10 7 \),\(r

= 23000000\),尺取即可。

当 \(l \ge 10^7\) 时,有 \(f(r)-f(l) \leq 1\),枚举区间长度 \(t\),假设 \(t\) 由 \(x\) 个数位 \(f(l)\) 的数和 \(y\) 个数位 \(f(l) + 1\) 的数组成,于是有:\(\begin{cases}x+y=t\\f(l)\times x+(f(l)+1)\times y=S\end{cases}\)。

整理得 \(f(l)\times t=S\)。然后枚举长度 \(t\)(\(t \leq \lfloor\frac{n}{8}\rfloor\)),分类讨论 \(f(r)-f(l)\) 的值即可。时间复杂度 \(\mathcal O(可过)\)。

CF770C Online Courses In BSU(1500)

如果必修课程在环内,则无解,否则有解,tarjan 判环加拓扑排序模拟即可。时间复杂度 \(\mathcal O(m)\)。

CF1421D Hexagons(1900)

暴力模拟到周围 \(6\) 点的最小花费,分类讨论即可。时间复杂度 \(\mathcal O(1)\)。

CF1421E Swedish Heroes(2700)

考虑到所有合法的分配方案都满足一个简单的性质:\(2 \times p+q \equiv 1 \pmod 3\)(其中 \(p\) 为 - 的个数,\(q\) 为 + 的个数)和至少存在一对相邻且符号相同的数。数学归纳易证。

由此,设 \(f_{i,j,0/1,0/1}\) 表示考虑了前 \(i\) 个数,\(2 \times p+q\equiv j \pmod 3\),第 \(i\) 个数的符号为 -+,否/是存在至少一对相邻且符号相同的数,的答案。

边界 \(f_{1,2,0,0}=-a_1\),\(f_{1,1,1,0}=a_1\)。

转移方程:

\[f_{i+1,(j+2)\pmod 3,0,t|(k==0)} \leftarrow f_{i,j,k,t}-a_{i+1}\\ f_{i+1,(j+2)\pmod 3,1,t|(k==1)} \leftarrow f_{i,j,k,t}+a_{i+1} \]

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

CF855E Salazar Slytherin's Locket(2200)

数位 dp 板子。模板 可看这。

先差分,再记 \(f_{i,j,k}\) 表示在 \(i\) 进制下有 \(j\) 位,并且每个数字出现次数的奇偶性是 \(k\) 的数的个数。

转移方程:\(f_{i,j,k}=\sum\limits_{m=0}^{i - 1}f_{i,j-1,k⊕2^{m}}\)。

时间复杂度 \(\mathcal O(\log_b(r)2^bb^2)\)。

CF711C Coloring Trees(1700)

记 \(f_{i,j,k}\) 表示前 \(i\) 个点,第 \(i\) 个点染为 \(j\),分成 \(k\) 段的最小花费。

转移方程:

  • 第 \(i\) 个点已被染色:\(f_{i,col_i,k}=\min(f_{i,col_i,k},f_{i-1,lst,k-(lst==col_i?0:1)})\)。
  • 第 \(i\) 个点未被染色:\(f_{i,j,k}=\min(f_{i,j,k},f_{i-1,lst,k-(lst==j?0:1)}+cost_{i,j})\)。

时间复杂度 \(\mathcal O(nkm^2)\),可用 st 表优化到 \(\mathcal O(nkm\log m)\)。

CF710D Two Arithmetic Progressions(2500)

直接分治。

  • 若 \(\max(a1,a2) < 10^3\),枚举 \(x \in [l,l+a1\times a2]\),对于符合条件的,答案累加 \(\lfloor\frac{r-x}{a1\times a2}\rfloor+1\),时间复杂度 \(\mathcal O(a1\times a2)\)。
  • 否则,暴力枚举所有满足第二个条件的数,判断一下是否可行即可,时间复杂度 \(\mathcal O(\frac{r-l}{a2})\)。

总时间复杂度 \(\mathcal O(可过)\)。

CF590C Three States(2200)

可以发现图只有一种情况:即可以找到一点与三个联通块相连。

那么对于每个点,bfs 计算它与三个联通块的距离之和,取最小值即可。

时间复杂度 \(\mathcal O(nm \alpha)\)。

CF1151F Sonya and Informatics(2300)

设有 \(m\) 个 \(0\),那么题意就是让 \(a[1,m]\) 均为 \(0\),\(a[m+1,n]\) 均为 \(1\)。

令 \(f_{i,j}\) 表示 \(i\) 个操作后,前 \(m\) 个数中有 \(j\) 个 \(0\) 的方案数,答案即为 \(\frac{f_{k,m}}{\sum\limits_{i=0}^{m}f_{k,i}}\),边界:\(f_{0,p}=1\),\(p\) 为原序列前 \(m\) 个数中 \(0\) 的个数。

对于 \(f_{i,j}\),考虑它是如何转移来的:

  • 之前有 \(j-1\) 个 \(0\),第 \(i\) 次交换换来一个 \(0\),由于前面 \(1\) 的个数与后面 \(0\) 的个数均为 \(m-j+1\),顾方案数为 \(f_{i-1,j-1}\times (m-j+1)^2\)。
  • 之前有 \(j + 1\) 个 \(0\),第 \(i\) 次交换换走一个 \(0\),由于前面有 \(j+1\) 个 \(0\),后面有 \(n-m-(m-j-1)=n-2m+j+1\) 个 \(1\),顾方案数为 \(f_{i-1,j+1}\times (j+1)(n-2m+j+1)\)。
  • 之前本来就有 \(j\) 个 \(0\),第 \(i\) 次操作没换走也没换来,四种情况:前面交换,后面交换,前后交换 \(0\),前后交换 \(1\),则方案数为 \(C_{m}^{2}+C_{n-m}^{2}+j(m-j)+(m-j)(n-2m+j)\)。

到这里差点结束了,总结:\(f_{i,j}=f_{i-1,j-1}\times (m-j+1)^2+f_{i-1,j+1}\times (j+1)(n-2m+j+1)+C_{m}^{2}+C_{n-m}^{2}+j(m-j)+(m-j)(n-2m+j)\)。

考虑到 \(k\leq 10^9\),经验告诉我们直接上矩阵快速幂,毕竟这转移无需判断。

\[\begin{bmatrix}c_0& b_1& 0 & 0&\cdots & 0\\ a_0 & c_1 & b_2 & 0&\cdots & 0\\ 0 & a_1 & c_2 & b_3 & \cdots & 0\\ 0&0&a_2&c_3&\cdots&0\\ 0&0&0&a_3&\cdots&0\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ 0&0&0&0&\cdots&c_m\end{bmatrix} \times \begin{bmatrix}f_{i-1,0}\\f_{i-1,1}\\f_{i-1,2}\\f_{i-1,3}\\f_{i-1,4}\\ \cdots \\f_{i-1,m}\end{bmatrix}=\begin{bmatrix}f_{i,0}\\f_{i,1}\\f_{i,2}\\f_{i,3}\\f_{i,4}\\ \cdots \\f_{i,m}\end{bmatrix} \]

其中 \(a_i=(m-i)^2\),\(b_i=i(n-2m+i)\),\(c_i=C_{m}^{2}+C_{n-m}^{2}+i(m-i)+(m-i)(n-2m+i)\)。

时间复杂度 \(\mathcal O(n^3\log k)\)。

Link to comment
Share on other sites