官方题解链接: AtCoder Beginner Contest 178 Editorial
A - Not
输入 $x$ ,输出 $1-x$ 。
B - Product Max
$\forall x\in [a, b],\forall y\in[c,d]$ ,求 $xy$ 最大值。
满足 $-10^9\le a\le b\le 10^9,\ -10^9\le c\le d\le 10^9$
Solution
答案显然是 $\max\{ac,ad,bc,bd\}$ 。
C - Ubiquity
计数长度为 $n$ 的整数数列 $A$ 的个数,满足:
- $0\le A_i\le 9$
- 保证数列中至少存在一个 $0$ 和一个 $9$
满足 $n\le 10^{6}$ ,答案对 $10^9 + 7$ 取模。
Solution
容斥,不考虑条件 $2$ 的方案数有 $10^n$ ,不满足条件 $2$ 的方案数为 $2\times 9^n - 8^n$ ,相减。
D - Redistribution
将整数 $S$ 划分成数列 $A$ ,长度不限,每项最少为 $3$,求方案数。
满足 $S\le 2000$
Solution
开始想着整数拆分的 DP ,但是很难解决多重集的排列问题。
换个思路,设 $f[i]$ 表示当前已经划分走 $i$ 的方案数,则 $f[i]=\sum_{j=3}^if[i - j]$ 。
1 | f[0] = 1; |
E - Dist Max
求 $n$ 个点两两曼哈顿距离的最大值。
满足 $2\le n \le 2\times 10^5$ , $1\le x_i,y_i\le 10^9$
Solution
分讨。
$x_1−x_2\ge 0,y_1−y_2\ge 0$
$|x_1−x_2|+|y_1−y_2|=x_1−x_2+y_1−y_2=(x_1+y_1)−(x_2+y_2)$
$x_1−x_2<0,y_1−y_2\ge 0$
$|x_1−x_2|+|y_1−y_2|=x_2−x_1+y_1−y_2=(x_2−y_2)−(x_1−y_1)$
$x_1−x_2\ge 0,y_1−y_2<0$
$|x_1−x_2|+|y_1−y_2|=x_1−x_2+y_2−y_1=(x_1−y_1)−(x_2−y_2)$
$x_1−x_2<0,y_1−y_2<0$
$|x_1−x_2|+|y_1−y_2|=x_2−x_1+y_2−y_1=(x_2+y_2)−(x_1+y_1)$
所以答案 $\max \big\{ \max \{x_i+y_i \}− \min \{x_i+y_i \}, \max \{x_i−y_i \} − \min \{x_i −y_i\} \big\}$ ,注意初始化。
F - Contrast
给定两个长度为 $n$ 的数列 $A,B$ ,保证两数列都是升序。
问是否能通过重排 $B$ ,使得不存在 $i\in [1,n]$ ,有 $A_i = B_i$ ,输出方案。
满足 $2\le n \le 2\times 10^5$ , $1\le A_i,B_i\le n$
Solution
At 的构造还是很有意思。
考虑把 $B$ 翻转,则 $A$ 升序, $B$ 降序 ,若有不合法位置,则相同的数字一定只有一个。
记相同的数字为 $x$ ,相同数字的区间为 $[l, r]$ 。
考虑 $B$ 中某一个换过来的位置 $i$ ,那么需要保证 $a[i] \ne x$ 且 $b[i] \ne x$ ,否则换后依然不合法。
记录 $A$ 和 $B$ (翻转后) 出现 $x$ 最靠左的位置 $L$ ,出现 $x$ 最靠右的位置 $R$ 。
则可以交换的位置 $i\in [L,R]$ ,有 $L - 1 + n - R$ 个,若这个数 $>r-l+1$ 则有解。
然后就和两侧交换就好了。
1 | reverse(b + 1, b + 1 + n); |
(挖坑 感觉字典序最小有搞头)