Codeforces Round 1089 (Div. 2)
A. A Simple Sequence
大致题意
要求你生成一个排列，满足
$a_1 \space mod \space a_2 \geq a_2 \space mod \space a_3 \dots a_{n-2} \space mod \space a_{n-1} \geq a_{n-1} \space mod \space a_n$
思路
由于这里可以是 $\geq$，而 $n \space n-1 = 1$，是一个显然的等式，所以直接倒序输出即可
AC code
1 | |
B. Simply Sitting on Chairs
大致题意
有一个 $n$ 的排列 $p$，然后需要完成如下操作：
从第一个值开始往后逐个选择，如果选择了这个值 $i$，那么接下来就不能选择 $p_i$
问最多可以选多少个值
思路
其实也非常简单，只要选择的 $i \geq p_i$ 就行了
AC code
1 | |
C2. A Simple GCD Problem
大致题意
有两个数组 $a, b$，都是长度 $n$，现在希望生成一个新的数组 $a’$，满足
$a’_i \in \Set{a_i, [1, b_i]}, \forall \Set{l, r} (1 \leq l < r \leq n), gcd(a_l, a_{l+1}, a_{l+2}, \dots, a_{r}) = gcd(a’_l, a’_{l+1}, a’_{l+2}, \dots, a’_{r})$
问最多可以同时存在多少个 $a’_i$ 满足 $a’_i \neq a_i$
思路
首先先分析题目中提到的 $gcd(a_l, a_{l+1}, a_{l+2}, \dots, a_{r}) = gcd(a’_l, a’_{l+1}, a’_{l+2}, \dots, a’_{r})$
看起来很吓人，实际上根据 $gcd$ 的性质，可以得到 $gcd(gcd(a, b), gcd(b, c)) = gcd(a, b, c)$
而题目中提到的是$\forall \Set{l, r} (1 \leq l < r \leq n)$，由于任意区间的 $gcd$ 等于这个区间里的相邻值的 $gcd$ 再做 $gcd$
所以要求条件可以转为: $\forall i (1 \leq i < n), gcd(a_i, a_{i+1}) = gcd(a’_i, a’_{i+1})$
要满足这条，我们需要先找出一个数组 $c$，满足 $c_i = gcd(a_i, a_{i+1})$，这不是什么难事
显然我们可以得到，最终的 $a’$ 满足: $gcd(a’_i, a’_{i-1}) = c_{i-1}, gcd(a’_i, a’_{i+1}) = c_{i+1}$
根据 $gcd$ 的性质，我们可以得到 $a’_i = x \times lcm(c_{i-1}, c_i), x \geq 1$
由此我们可以得到 $a’$ 数组的每一项的最小可选值，即 $a’_i = lcm(c_{i-1}, c_i)$
至此，我们已经完成了 Easy Version 的题解。由于 $b_i = a_i$，所以如果 $lcm(c_{i-1}, c_i) = a_i$，那么就不可能存在 $a’_{i} \neq a_{i}$
接下来是讨论 Hard 部分的解决方案
显然，如果 $lcm(c_{i-1}, c_i) \neq a_i$ 的话，我们就可以选择令 $a’_{i} = lcm(c_{i-1}, c_i)$，因为再乘上任何值都有可能让 $gcd$ 发生变化（变大）
接下来核心是要处理这些不满足的值，也就是 $lcm(c_{i-1}, c_i) = a_i$ 的值，尝试找到一个 $x$ 使得 $x \times lcm(c_{i-1}, c_i) \neq a_i$ 且不改变 $gcd$ 关系
由于不能改变 $gcd$ 关系，假定 $a’_i = x_i \times lcm(c_{i-1}, c_i)$，那么 $gcd(x_i, a’_{i-1}) = gcd(x_i, a’_{i+1}) = 1$
扩展后可以得到：
$gcd(x_i, x_{i-1}) = gcd(x_i, x_{i+1}) = gcd(x_i, lcm(c_{i-2}, c_{i-1})) = gcd(x_i, lcm(c_{i}, c_{i+1}))$
即有很多很多的互质
显然我们很容易想到用素数，因为任意两个素数之间肯定互质，由于本身是乘法，且只需要找到相互互质的值即可，所以只需要限制在较小的值内即可
我用了 100 以内的素数，通过 dp 的方式，枚举每一位乘上每一种素数的情况
我的 dp 算法里，下标 $x$ 表示第几个素数，其中 $0$ 表示 $lcm(c_{i-1}, c_i)$ 本体，而 $max(x)$ 表示 $a_i$ 本身
AC code
1 | |
