AtCoder Beginner Contest 178

比赛链接

C Ubiquity

Description

设 $A$ 为 $N$ 个 0~9 的数构成的序列。问存在 0 且存在 9 的序列有多少个。

Solution

方法 1：所求序列个数为总序列个数减去不含 0 或不含 9 的序列个数。

• 不含 0 和 9 的序列个数有 $8^n$ 个。
• 含 0 但不含 9 的序列个数有 $9^n - 8^n$ 个。（二项式去掉第 0 项可得）
• 含 9 但不含 0 的序列个数同上。

所以答案为 $10^n - 2 * 9^n + 8^n$

方法 2: DP

• $dp[n][0][0]$ 表示当前序列长度为 $n$，有 0 个 0, 0 个 9 的方案数
• $dp[n][1][0]$ 表示当前序列长度为 $n$，有至少 1 个 0, 0 个 9 的方案数
• $dp[n][0][1]$ 表示当前序列长度为 $n$，有 0 个 0, 至少 1 个 9 的方案数
• $dp[n][1][1]$ 表示当前序列长度为 $n$，有至少 1 个 0，至少 1 个 9 的方案数

Code

Ubiquity

#include <bits/stdc++.h>
#define int long long

int tc, n, m;
array<int, MAXN> a;

inline int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

signed main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    int res = qpow(10, n);
    int minus = qpow(8, n);
    (minus += 2LL * (qpow(9, n) - qpow(8, n))) %= MOD;
    (res -= minus) %= MOD;
    cout << (res + MOD) % MOD <<endl;
    return 0;
}

D Redistribution

Description

题目链接

Solution

首先，由于数列中每个数至少为 3，因此数列长度最大为 $L=\frac{S}{3}$。设 $dp[i][j]$ 表示构成长度为 $i$，和为 $j$ 的数列方案数，那么最后答案为 $\sum\limits_{i=1}^{L}dp[i][S]$。易得状态转移方程为 $dp[i][j]=\sum\limits_{k=(i-1)*3}^{j-3}dp[i-1][k],j∈[i*3,S]$。如果直接转移时间复杂度为$O(S^2L)$，但 $\sum\limits_{k=(i-1)*3}^{j-3}dp[i-1][k]$ 可以用利用前缀和 $O(1)$ 求得，同时 $dp[i][j]$ 第一维可以滚掉，因此复杂度可降至 $O(SL)$。

Code

Redistribution

#include <bits/stdc++.h>

using namespace std;
const int MOD = 1E9 + 7;
int dp[2005], sum[2005];
int len, s, ans;

template <class T>
void read(T &x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

int main() {
    cin >> s;
    len = s / 3;
    dp[0] = 1;
    for (int i = 0; i <= s; i++) sum[i] = 1;
    for (int i = 1; i <= len; i++) {
        for (int j = i * 3; j <= s; j++)
            dp[j] = (sum[j - 3] - (i > 1 ? sum[(i - 1) * 3 - 1] : 0)) % MOD;
        ans += dp[s], ans %= MOD;
        for (int j = 0; j <= s; j++) sum[j] = 0;
        for (int j = i * 3 - 1; j <= s; j++)
            sum[j] = (sum[j - 1] + dp[j]) % MOD;
    }
    cout << (ans + MOD) % MOD;
    return 0;
}

E Dist Max

Description

题目链接

Solution

$|x_1-x_2|+|y_1-y_2|$ 去绝对值后有以下四种情况：

• $x_1+y_1-(x_2+y_2)$
• $y_1-x_1-(y_2-x_2)$
• $x_2+y_2-(x_1+y_1)$
• $y_2-x_2-(y_1-x_1)$

要求 $|x_1-x_2|+|y_1-y_2|$ 最大值，只需要分别求出 $x_i+y_i$ 和 $y_i-x_i$ 最大值与最小值的差，对这两个差取 $max$ 即可。

Code

Dist Max

#include <bits/stdc++.h>

using namespace std;

int n, x, y;
int mxSum = INT_MIN, miSum = INT_MAX, mxSub = INT_MIN, miSub = INT_MAX;

template <class T>
void read(T &x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(x), read(y);
        mxSum = max(mxSum, x + y), miSum = min(miSum, x + y);
        mxSub = max(mxSub, y - x), miSub = min(miSub, y - x);
    }
    cout << max(mxSum - miSum, mxSub - miSub);
    return 0;
}

E Contrast

Description

题目链接

Solution

首先根据鸽巢原理，如果一个数在 $A$ 和 $B$ 的出现次数大于 $n$，那么一定无解。

对于有解的情况，设 $C_i$ 表示 $A$ 中小于等于 $i$ 的数的个数，设 $D_i$ 表示 $B$ 中小于等于 $i$ 的数的个数，$C_i$， $D_i$ 是单增的。

对于每一个 $x(0 \leq x \leq N)$，我们让 $B$ 的每个元素向右移动 $x$ 位(即将 $B_{i+1}$ 移动到 $B_{(i+x) \% n+1}$)。

要使结果合法，$x$ 需要满足对于所有 $i(1 \leq i \leq n)$，区间$(C_{i-1}, C_{i}]$，$(x + D_{i - 1}, x + D_{i}]$ 和 $(n + C_{i-1}, n + C_{i}]$ 没有交集(可以看作 $A$ 复制一倍，$B$ 右移 $x$，需满足同一位置没有相同的数)。即对于所有 $i$， $C_i - D_{i-1} \leq x \leq C_{i-1}+n-D_i$。

可以证明这样的 $x$ 是一定存在的Editorial。

由于对于每一个 $i$ 都要成立，则 $x$ 的取值范围一定在 $C_i - D_{i-1}$ 的最大值 与 $C_{i-1}+n-D_i$ 的最小值之间。故取 $x$ 为 $C_i - D_{i-1}$ 的最大值即可。

Code

Contrast

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 2e5 + 5;

int n, mx;
array<int, MAXN> a, b, c, d, cnt, ans;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], c[a[i]]++, cnt[a[i]]++;
    for (int i = 1; i <= n; i++) c[i] += c[i - 1];

    for (int i = 1; i <= n; i++) cin >> b[i], d[b[i]]++, cnt[b[i]]++;
    for (int i = 1; i <= n; i++) d[i] += d[i - 1];

    for (int i = 1; i <= n; i++)
        if (cnt[i] > n) {
            cout << "No" << endl;
            return 0;
        }
    
    for (int i = 1; i <= n; i++)
        mx = max(mx, c[i] - d[i - 1]);
    for (int i = 1; i <= n; i++)
        ans[(i + mx) % n == 0 ? n : (i + mx) % n] = b[i];

    cout << "Yes" << endl;
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    return 0;
}