ABC474

比赛链接： ABC474 。

A. Not X

题目描述：

给一个 $X\in\{1,2,3\}$ 。

输出一个 $\{1,2,3\}$ 内与 $X$ 不同的整数。

未识别到题目。

B. Exit Order

题目描述：

给一个排列 $p$ ，将排列 $10$ 个一分组之后，判断是否每一组都满足他们是对应下标的排列。

未识别到题目。

C. Remove and Append

题目描述：

给一个排列 $p$ ， $Q$ 次操作，每次将一个元素 $x$ 移到最后。求最终排列。

记录每一个元素最后一次出现的位置即可。

D. Outweigh

题目描述：

构造一个序列 $w$ ，满足 $\sum\limits_{i=1}^n a_iw_i>\sum\limits_{i=1}^n b_iw_i$ 。

或输出无解。

$w_i\in[1,10^{18}]$ 。

很显然 $10^{18}$ 很大，所以只要有一个 $i$ 满足 $a_i>b_i$ 就有解。对于每一个 $w_i$ 满足 $w_i=[a_i>b_i]10^{18}+[a_i\le b_i]$ 就行。

E. One Time Coupon

题目描述：

有 $n$ 个商品，第 $i$ 个商品价格为 $a_i$ ，优惠后为 $b_i$ 。

你可以进行任意次操作：

• 使用优惠卷购买商品 $i$ 。
• 直接购买商品 $i$ ，然后获得一个优惠卷。

求购买了所有商品至少的费用。

显然我们应该通过 $a$ 最少的那个商品搞优惠卷。然后将 $a_i-b_i$ 顺序排序使用就行。

F. Increment All Divisors

题目描述：

给一个长度为 $n$ 的序列，你可以进行下列操作任意多次：

• 将一个数所有因数的位置 $+1$ 。

求是否有可能使得所有元素相等。若可能，求最少次数。

$n\le 2\times 10^5$ 。

莫比乌斯反演模板题。略。

G. LRUD Moving 2

神秘构造

题目描述：

$n*n$ 的方格，要求从 $(1,1)$ 开始， $(n,n)$ 结束。结束时必须经过所有方格恰好一次。求向右走恰好为 $K$ 的走法的存在性以及具体方案。

$n\le10^3$ 。

显然 $n$ 为奇数， $K$ 为偶数为有解充要条件。

问题是怎么构造。

容易发现我们的构造大概是类似这样的：

############
*###########
***#########
****########
****########
****########
****########
*****#######
*****#######
********###
********###
***********

其中 * 表示竖着搞， # 表示横着搞。

但是这样不一定有解。

容易发现 $n*m$ 的方格的有解充要条件为 $n$ 或 $m$ 中有一个为奇数。为了方便不妨让两个都为奇数。

所以每次我们应该一次搞两行或两列。

然后就做完了。证明可以考虑归纳。