CF1554简要题解

\(\text{Problem A}:\)​Cherry

\(\text{Solution}:\)

考虑取 \(a_{i}\times a_{i+1}\) 肯定最优。可以通过加入一个 \(a_{i-1}\) 来证明。

\(\text{Code}:\)Link


\(\text{Problem B}:\)Cobb

\(\text{Solution}:\)

对于这类题目,首先考虑怎么减少需要计算的状态数。

可以发现,\(k(a_{i}\mid a_{j})\leq 2nk,i\times j\leq j(j-1)\)​​。考虑极端的情况,令 \(j=n\)​​,则解得 \(i\geq n-1-2k\)​​。同理,对于 \(j\not=n\)​​,可以解得 \(i\geq j-1-\dfrac{2k\times n}{j}\)​​。但考虑 \(i\times j\)​ 的值大小后,不难发现也只需枚举 \(i\geq j-1-2k\) 即可。时间复杂度 \(O(nk)\)。

\(\text{Code}:\)Link


\(\text{Problem C}:\)​Mikasa

\(\text{Solution}:\)

即找出最小的 \(k\),满足对于 \(\forall i\in[0,m]\),\(n\oplus i\not=k\)​。

考虑异或的性质,即对于 \(\forall i\in[0,m]\),\(n\oplus k\not=i\)。则 \(n\oplus k\geq m+1\)。然后按位构造即可。

\(\text{Code}:\)Link


\(\text{Problem D}:\)Diane

\(\text{Solution}:\)

找到两段长度分别为 \(x,y\) 的连续 \(a\)​,可以发现当 \(x-y\equiv 1\pmod 2\)​ 时,这两段的所有回文子串出现次数都是奇数。

以此构造,只要构造两段长度奇偶性不同的 \(a\) 即可。中间随便填一些字符。

\(\text{Code}:\)Link


\(\text{Problem E}:\)You

\(\text{Solution}:\)

考虑总方案数。给每条边定向后按照拓扑排序来删点,且答案一定不会重复。故为 \(2^{n-1}\)。

当 \(k>1\) 时,如何确定当前 \(k\) 的可行性?

首先显然有 \(k\mid (n-1)\),然后 DFS 整棵树,如果当前子树 \(x\) 恰有 \(p\) 个结点满足 \(k\mid p\),说明删 \(x\) 是合法的;若 \(k\mid (p+1)\),则删 \(fa_{x}\)​ 是合法的;否则,无解。

考虑方案数至多是 \(1\)。当 \(k>1\) 时,不能直接删叶子结点。根据 DFS 删点的步骤,不难发现每个点是否会被删除是唯一的。故方案数与可行性等价。

求出来的是 \(k\mid \gcd(a_{1},a_{2},...,a_{n})\)。最后筛去每个数的倍数的贡献即可。

\(\text{Code}:\)Link

上一篇:Linux—查看内核版本、系统版本、系统位数


下一篇:TS接口