CCPC2023-Shenzhen

标签：CCPC2023 dfrac 复杂度 LARGE 枚举 textrm Problem Shenzhen

\[\LARGE \textrm{Problem A. A Good Problem} \]

• \(a_i\in[0, n]\)

分治，考虑做值域为 \([L,R)\) 的一部分，保证初始情况下所有数都是 \(L\)，然后把所有值域在 \([mid, R)\) 的数抬到 \(mid\)，再做分成的两部分。

---

\[\LARGE \textrm{Problem F. Gift} \]

基环树，枚举每一条环上的边删掉，不能出现度数大于等于 \(5\) 的点，度数等于 \(4\) 的点不能作根，计数即可。

---

\[\LARGE \textrm{Problem G. Gene} \]

考虑第 \(i\) 列，字符 \(c\) 没有出现的串组成的集合为 \(S(i, c)\)，用 bitset 维护。

每次询问的时候再利用 bitset 维护哪些串可能为答案，由于 \(k\) 很小，枚举列，bitset 求交后枚举每个未匹配的串。

时间复杂度 \(O\left(\dfrac{MN}{\omega}+QM\left(K+\dfrac N\omega\right)\right)\)，空间复杂度 \(O\left(\dfrac{NM|\Sigma|}\omega+(N+Q)M\right)\)

---

\[\LARGE \textrm{Problem I. Indeterminate Equation} \]

\(a^k-b^k = (a-b)\sum\limits_{i+j=k-1,i,j\in\mathbb N} a^ib_j\)，因此 \((a-b)|n\)。

不妨设 \(a = b+t\)，二项式展开后有 \((b+t)^k-b^k>t^k\)。因此 \(a-b\) 不大于 \(10^6\) 且为 \(n\) 的因数。枚举之，二分出 \(b\) 的值即可。

时间复杂度 \(O(\sqrt[k]N + d(N)\log N))\)

标签：CCPC2023,dfrac,复杂度,LARGE,枚举,textrm,Problem,Shenzhen
From： https://www.cnblogs.com/haze1231/p/18063782