AtCoder Beginner Contest 366 (opens new window)

A - Election 2

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, A , B ; cin >> N >> A >> B;
    int A_ = N - (A + B) + A;
    if (A_ < B) {
        cout << "Yes" << endl;
        return 0;
    }
    int B_ = N - (A + B) + B;
    if (B_ < A) {
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
    return 0;
}

B - Vertical Writing

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N; cin >> N;
    vector<string> S(N);
    int M = -1;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        M = max(M, (int)S[i].size());
    }
    vector<vector<char>> A(N, vector<char>(M, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < S[i].size(); j++) {
            A[i][j] = S[i][j];
        }
        for (int j = S[i].size(); j < M; j++) {
            A[i][j] = '*';
        }
    }
    for (int j = 0; j < M; j++) {
        for (int i = 0; i < N; i++) {
            if (A[i][j] == '*') A[i][j] = ' ';
            else break;
        }
    }
    for (int j = 0; j < M; j++) {
        for (int i = N - 1; i >= 0; i--) {
            cout << A[i][j];
        }
        cout << endl;
    }
    return 0;
}

C - Balls and Bag Query

Solution

使用 p 数组记录一个数出现了几次，用 $cnt$ 维护答案

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int main() {
    int Q; cin >> Q;
    vector<int> p(maxn, 0);
    int cnt = 0;
    while (Q--) {
        int op; cin >> op;
        if (op == 1) {
            int x; cin >> x;
            if (p[x]++ == 0) cnt += 1;
        }
        else if (op == 2) {
            int x; cin >> x;
            if (--p[x] == 0) cnt -= 1;
        }
        else {
            cout << cnt << endl;
        }
    }
}

D - Cuboid Sum Query

Solution

三维容斥

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    ios::sync_with_stdio(0);
    int n; cin >> n;
    vector<vector<vector<int>>> a(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) {
                cin >> a[i][j][k];
            }
    vector<vector<vector<int>>> s(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) {
                s[i][j][k] = s[i - 1][j][k] + s[i][j - 1][k] + s[i][j][k - 1] - s[i - 1][j - 1][k] - s[i - 1][j][k - 1] - s[i][j - 1][k - 1] + s[i - 1][j - 1][k - 1] + a[i][j][k];
            }
    int Q; cin >> Q;
    while (Q--) {
        int x1, y1, z1, x2, y2, z2; cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        cout << s[x2][y2][z2] - s[x1 - 1][y2][z2] - s[x2][y1 - 1][z2] - s[x2][y2][z1 - 1] + s[x1 - 1][y1 - 1][z2] + s[x1 - 1][y2][z1 - 1] + s[x2][y1 - 1][z1 - 1] - s[x1 - 1][y1 - 1][z1 - 1] << endl;
    }
    return 0;
}

E - Manhattan Multifocal Ellipse

Question

给定 $N$ 个点 $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$ 在二维平面上，以及非负整数 $D$。

找出满足 $\displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D$ 的整数对 $(x, y)$ 的数量。

Solution

先把 $x,y$ 分开，其实可以独立的来看这个问题

设 $f(x)=\sum\limits_{i=1}^N|x-x_i|,g(y)=\sum\limits_{i=1}^N|y-y_i|$，那么答案就是满足 $f(x)+g(y) \le D$ 的 $(x,y)$ 数对的数量

首先，我们发现值域其实不大，我们需要对序列中的每个 $x\in\{-(M+D),M+D\}$，都求出其 $f(x)$，我们可以用递推来计算，假设我们已知 $f(x-1)$，并且知道比 $x$ 小的 $x_i$ 有 $k$ 个，那么有 $k$ 个的距离需要增加 $1$，有 $N-k$ 个的距离需要减少 $1$，所以，$f(x)=f(x-1)+k-(N-k)=f(x-1)+2\times k-N$

同理，我们也能算出 $g(y)$

算出了 $f(x),g(y)$ 由于是 $(x,y)$ 是独立的，所以可以把 $f(x),g(y)$ 都从小到大排序，然后用一种所谓 "尺取法" 的东西（Atcoder题解叫这个，我感觉就是指针）

我们需要满足 $f(x)+g(y)\le D$，我们把 $x$ 从大到小枚举，然后令指针 $j=0$ 指向 $g(y)$ 最小的节点，找到满足 $f(x)+g(y)\le D$ 最大的 $y_j'$，那么对于这个 $x_i$，就有 $j$ 个 $y$ 满足条件

Code

N, D = map(int, input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
M = 2 * 10 ** 6


def calc(x):
    xsum = [0] * (2 * M + 1)
    x.sort()
    i = 0
    xsum[-M] = sum(x) + N * M
    for j in range(-M + 1, M + 1):
        while i < N and x[i] < j:
            i += 1
        xsum[j] = xsum[j - 1] + 2 * i - N
    return xsum

xsum = calc(x)
ysum = calc(y)
ans = 0
xsum.sort()
ysum.sort()
j = 0
for i in range(2 * M + 1)[::-1]:
    while j < 2 * M + 1 and xsum[i] + ysum[j] <= D:
        j += 1
    ans += j
print(ans)

F - Maximum Composition

Question

给定 $N$ 条线性函数 $f_1, f_2, \ldots, f_N$，其中 $f_i(x) = A_i x + B_i$。

对于一个由 $K$ 个 不同的 整数 $p = (p_1, p_2, \ldots, p_K)$ 组成的序列，计算 $f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots ))$ 的最大可能值，其中 $p_i$ 的取值范围为 $1$ 到 $N$。

Solution

先考虑 $f_i(f_j(x))>f_j(f_i(x))$ 的等价条件

$\begin{aligned} & f_i(f_j(x))>f_j(f_i(x))\\ \Leftrightarrow \ & A_i(A_j x+B_j)+B_i>A_j(A_ix+B_i)+B_j\\ \Leftrightarrow \ & A_iA_jx+A_iB_j+B_i>A_iA_jx+A_jB_i+B_j\\ \Leftrightarrow \ & A_iB_j-B_j>A_jB_i-B_i\\ \Leftrightarrow \ & (A_i-1)B_j>(A_j-1)B_i\\ \Leftrightarrow \ & \frac{(A_i-1)}{B_i}>\frac{(A_j-1)}{B_j} \end{aligned}$

所以，我们按照 $\frac{(A_i-1)}{B_i}>\frac{(A_j-1)}{B_j}$ 的标准，把 $(A,B)$ 排序

现在我们排完序后有 $N$ 个 $(A,B)$ 我们需要从中选 $K$ 个，这个就是一个很朴素的 DP 问题了

定义 $f[i][j]$ 对于前 $i$，已经选了 $j$ 个的最优解，那么转移方程就是

$f[i][j]=\max f[i-1][j],f[i-1][j-1] \times A_j+B_j$

答案就是 $f[N][K]$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    vector<int> ord(n);
    for (int i = 0; i < n; i++) ord[i] = i;
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return b[i] * (a[j] - 1) > b[j] * (a[i] - 1);
    });
    vector<ll> dp(k + 1, -INF);
    dp[0] = 1;
    for (auto i : ord) {
        auto ndp = dp;
        for (int j = 0; j < k; j++) {
            if (dp[j] != -INF) {
                ndp[j + 1] = max(ndp[j + 1], dp[j] * a[i] + b[i]);
            }
        }
        dp = ndp;
    }
    cout << dp[k] << endl;
    return 0;
}