AtCoder Beginner Contest 178

官方题解链接: AtCoder Beginner Contest 178 Editorial

A - Not

ABC 178 A

输入 $x$ ,输出 $1-x$ 。

B - Product Max

ABC 178 B

$\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

ABC 178 C

计数长度为 $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

ABC 178 D

将整数 $S$ 划分成数列 $A$ ,长度不限,每项最少为 $3$,求方案数。

满足 $S\le 2000$

Solution

开始想着整数拆分的 DP ,但是很难解决多重集的排列问题。

换个思路,设 $f[i]$ 表示当前已经划分走 $i$ 的方案数,则 $f[i]=\sum_{j=3}^if[i - j]$ 。

1
2
3
f[0] = 1;
for (int i = 3; i <= n; ++i)
for (int j = 3; j <= i; ++j) f[i] = (f[i] + f[i - j]) % mod;

E - Dist Max

ABC 178 E

求 $n$ 个点两两曼哈顿距离的最大值。

满足 $2\le n \le 2\times 10^5$ , $1\le x_i,y_i\le 10^9$

Solution

分讨。

  1. $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)$

  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)$

  3. $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)$

  4. $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

ABC 178 F

给定两个长度为 $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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
reverse(b + 1, b + 1 + n);
int x, l = 0, r, L, R;
for (int i = 1; i <= n; ++i)
if (a[i] == b[i]) l ? ++r : l = r = i;
x = a[l];
if (!l) {print(); return 0;}
for (int i = 1; i <= n; ++i)
if (a[i] == x || b[i] == x) {L = i; break;}
for (int i = n; i; --i)
if (a[i] == x || b[i] == x) {R = i; break;}
if (L - 1 + n - R < (r - l + 1)) {puts("No"); return 0;}
int lim = min(L - 1, r - l + 1);
for (int i = 1; i <= lim; ++i) swap(b[i], b[l + i - 1]);
lim = r - l + 1 - lim;
for (int i = 1; i <= lim; ++i) swap(b[n - i + 1], b[r - i + 1]);

(挖坑 感觉字典序最小有搞头)