AtCoder Beginner Contest 222 (E~G)

闲着的时候 vp 的一场 abc,vp 完之后发现自己居然 FG 都会/fad

为什么这场 abc 我没打/fn/fn/fn

ABC222E Red and Blue Tree

首先我们对每个 \(1\le i<n\),将 \(A_i\to A_{i+1}\) 中间的这些边的边权都加一。

设最后的边权序列为 \(x_{1\cdots n-1}\),把红边看做系数 \(c_i=+1\),蓝边看做系数 \(c_i=-1\),那么只需要最后所有 \(\sum x_ic_i=K\)。

\(f(i,j)\) 表示前 \(i\) 个数和为 \(j\) 的方案数,转移枚举最后一个填 \(+1\) 还是 \(-1\) 随便做。

注意 \(j\) 可以是负数,因此需要平移一波值域。

边权之和最大可以是 \(O(nm)\),因此总的时间复杂度为 \(O(n^2m)\)。

AC Code

ABC222F Expensive Expense

一开始想的是 dp,然后发现我好像不太会写 up-down tree dp......

突然发现好像可以点分治:先把根节点 \(\text{rt}\) 子树内所有节点 \(u\) 的 \(\text{dist}(u)+D_u\) 扔进一个 multiset,然后处理一棵子树的时候就把这棵子树内的点都从 multiset 里扔掉,不断更新答案,最后再扔进去。

时间复杂度 \(O(n\log ^2n)\),最慢的点跑了 \(\text{1886ms}\)(限时是 \(\text{4s}\)),海星。

AC Code

ABC222G 222

套路题。

注意到 \(x\) 个 \(2\) 连起来其实就是 \(\dfrac{2}{9}(10^x-1)\)。

那么我们就只需要找一个最小的 \(x\) 使得 \(9K\mid 2(10^x-1)\)。

如果 \(2\mid K\),那么相当于 \(\left.\dfrac{9K}{2}\right|10^x-1\);如果 \(2\nmid K\),那么就是 \(9K\mid 10^x-1\)。

总之,不论如何,我们都可以将其转化为

\[10^x\equiv1\quad(\bmod N) \]

其中 \(N=\dfrac{9K}{2}\) 或 \(9K\).

这个实际上就是 \(\bmod N\) 意义下 \(10\) 的阶,即 \(\text{ord}_{N}(10)\)。那么:

  • 如果 \(\gcd(10,N)>1\),则 \(\text{ord}_{N}(10)\) 不存在,答案为 \(-1\)。
  • 否则,\(\text{ord}_{N}(10)\) 必然为 \(\varphi(N)\) 的约数,枚举其约数并验证即可。

时间复杂度 \(O(T\sqrt{K}\log K)\),\(\log\) 来自快速幂。

上一篇:halcon-switch分子语句


下一篇:C语言笔记:2.分支与循环语句