AtCoder Beginner Contest 413 A~G 题解

Tip. 简便起见，所有代码省略头文件、命名空间、关键字替换、常量和 I/O 优化.

A - Content Too Large

题目大意

给定 $N$ 个物品和背包容量 $M$，判断物品大小之和是否超过背包容量.

解法分析

不断从背包容量中减去物品大小，全部放完后判断容量是否非负.

代码实现

int n, m;

int main() {
    cin >> n >> m;
    while(n--) { int a; cin >> a; m -= a; }
    puts(m >= 0 ? "Yes" : "No");
    return 0;
}

B - cat 2

题目大意

给定 $N$ 个字符串 $S_{1...n}$，求选择两个不同的字符串拼接能得到多少种不同的结果.

• $2 \le N \le 100$

• $|S_i| \le 10$

解法分析

枚举两个字符串，拼接后记录，可使用 std::set 等方式去重.

代码实现

int n;
string s[N];
unordered_set<string> res;

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> s[i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(i != j) res.insert(s[i] + s[j]);
    cout << res.size() << endl;
    return 0;
}

C - Large Queue

题目大意

维护一个初始为空的整数序列 $A$，处理 $Q$ 个操作：

1. 添加：向序列末尾添加 $c$ 个值为 $x$ 的元素；

2. 删除：从序列开头移除 $k$ 个元素（$k \le |A|$），输出被移除元素的和.

• $1 \le Q \le 2\times10^5$
• 添加操作中, $1 \le c \le 10^9$

解法分析

如果直接将 $c$ 个元素 $x$ 压入，则空间和时间开销都不可接受.

考虑将每一次添加 $(c, x)$ 直接压入，每次处理时从 $k$ 中不断减去头部添加操作的元素个数，并将和累加，直到 $k = 0$.

由于每个添加操作被移除完最多产生一次操作，每次删除最多产生一次未移除完的操作，因此该算法时间复杂度为 $\mathrm O(Q + Q) = \mathrm O(Q)$.

代码实现

int q;
queue<pair<int, int>> Q;

int main() {
    cin >> q;
    while(q--) {
        int op;
        cin >> op;
        if(op == 1) {
            int c, x;
            cin >> c >> x;
            Q.push({c, x});
        } else {
            int k;
            cin >> k;
            long long res = 0;
            while(k) {
                int c = Q.front().first, x = Q.front().second, p = min(c, k);
                k -= p, res += 1ll * p * x;
                Q.front().first -= p;
                if(!Q.front().first) Q.pop();
            }
            cout << res << "\n";
        }
    }
    return 0;
}

D - Make Geometric Sequence

题目大意

$T$ 个测试用例. 每个包含一个长度为 $N$ 的非零数列 $A$，判断 $A$ 是否存在为等比数列的排列.

解法分析

若 $A$ 的某排列 $B$ 为等比数列，令 $r$ 为公比.

若 $|r| \neq 1$，则 $|B_i|$ 与 $|B_{i + 1}| = |r|\cdot|B_i|$ 的大小关系恒定，因此可按 $|A_i|$ 对 $A$ 进行排序，则 $A$ 存在等比数列排列当且仅当如此排序后为等比数列.

若 $|r| = 1$，则 $|A_i|$ 应为定值，记为 $a$，那么 $A$ 存在等比数列排列当且仅当 $A_i = a$（$r = 1$）或 $a$ 和 $-a$ 在 $A$ 中出现次数差值不大于 $1$（$r = -1$）.

时间复杂度瓶颈在于排序，因此该算法时间复杂度为 $O(N \log N)$.

代码实现

int n;
vector<int> a;

#define all(x) a.begin(), a.end()
#define Count(x) count(all(a), x)

bool solve() {
    cin >> n;
    a.assign(n, 0);
    unordered_set<int> Abs;
    for(int &i : a) cin >> i, Abs.insert(abs(i));
    if(Count(a[0]) == n) return true;
    if(Abs.size() == 1)
        return abs((Count(*Abs.begin())) - Count(-*Abs.begin())) <= 1;
    sort(all(a), [](int a, int b) { return abs(a) < abs(b); });
    for(int i = 2; i < n; i++)
        if(1ll * a[i - 1] * a[1] != 1ll * a[i] * a[0]) return false;
    return true;
}

int main() {
    int T;
    cin >> T;
    while(T--) puts(solve() ? "Yes" : "No");
    return 0;
}

E - Reverse 2^i

题目大意

$T$ 个测试用例. 每个包含一个长度为 $2^N$ 的排列 $A$，可无限次将 $A$ 分为 $2^n~(n \le N)$ 段并将其中一段反转，使 $A$ 的字典序最小.

• $1 \le T \le 10^5$
• $1 \le N \le 18$，$\sum 2^N \le 3 \times 10^5$

解法分析

容易发现 $A$ 长为 $2^n$ 的段恰包含 $2$ 个长为 $2^{n-1}$ 的段，也即 $A$ 长为 $2^n$ 的段可拆分为 $2$ 个长为 $2^{n-1}$ 的段；考虑这两段字典序已经最小后，若前段大于后段，则将他们交换可以实现字典序最小.

为什么可以交换？

$(A^\mathrm{rev}B^\mathrm{rev})^\mathrm{rev} = BA$

递归实现，对于长度 $2^n~(n \le N)$ 的段，最多处理所有 $2^N$ 个元素，因此该算法时间复杂度为 $\mathrm O(N \cdot 2^N)$.

代码实现

int n;
long long a[N];

void dfs(int l, int len) {
    if(len == 1) return;
    int m = l + (len /= 2);
    dfs(l, len), dfs(m, len);
    if(a[l] > a[m]) for(int i = 0; i < len; i++) swap(a[l + i], a[m + i]);
}
void solve() {
    cin >> n;
    for(int i = 0; i < 1 << n; i++) cin >> a[i];
    dfs(0, 1 << n);
    for(int i = 0; i < 1 << n; i++) cout << a[i] << " \n"[i + 1 == 1 << n];
}

int main() {
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}

F - No Passage

题目大意

小 A 和 小 T 在 $H \times W$ 的网格上弈棋，有 $K$ 个目标格子.

小 A 每次在四个方向中选择一个禁止小 T 移动，以使最大化小 T 到达目标格子的步数.

求从所有格子出发，小 T 到达目标格子最小步数之和；特别的，如果小 T 不能到达目标格子，那么将最小步数记为 $0$.

• $2 \le H \le 3000$
• $2 \le W \le 3000$
• $1 \le K \le \mathrm{min}(HW,3000)$

解法分析

我们称小 T 从该格子出发可以到达目标格的格子为「必达格」. 容易发现由于小 A 非此只能在一个方向上阻挡，与两个「必达格」相邻的格子也必定为「必达格」；并且在小 A 必然挡在路径最短的方向上，迫使使小 T 走路径次短的方向，因此该格的路径应为四个方向上次短的路径${}+1$.

容易用 BFS 算法实现，以所有目标格为源点开始搜索，第一次访问某点时打上一个标记，第二次访问时从来源更新答案并更新标记. 搜索结束后未被访问不少于两次的点即为无法到达的点.

考虑每格最多被访问 $4$ 次，该算法时间复杂度为 $\mathrm O(HW+K) = O(HW)$.

代码实现

int h, w, k, f[N][N], res[N][N], dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
queue<pair<int, int>> q;

int main() {
    cin >> h >> w >> k;
    while(k--) {
        int x, y;
        cin >> x >> y;
        f[x][y] = -1, q.push({x, y});
    }
    while(q.size()) {
        auto [x, y] = q.front(); q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if(!~f[nx][ny]) continue;
            if(!f[nx][ny]) f[nx][ny] = 1;
            else f[nx][ny] = -1, res[nx][ny] = res[x][y] + 1, q.push({nx, ny});
        }
    }
    cout << accumulate(&res[0][0], &res[0][0] + N * N, 0ll) << endl;
    return 0;
}

G - Big Banned Grid

题目大意

给定一个 $H \times W$ 的网格，其中 $K$ 个格子为障碍。从 $(1,1)$ 开始，每次可向四个方向的非障碍格子移动. 判断是否存在一条从 $(1,1)$ 到 $(H,W)$ 的路径.

• $1 \le H \le 2 \times 10^5$
• $1 \le W \le 2 \times 10^5$
• $0 \le K \le 2 \times 10^5$

解法分析

考虑讲边相邻和角相邻的障碍格合成一堵「墙」，判断是否存在墙可以在横向、纵向或斜向上撑满整个网格即可.

容易想到用并查集维护「墙」及其 $x,y$ 坐标极值，如仅使用路径压缩优化，该算法时间复杂度为 $\mathrm O(K\log K)$.

代码实现

int h, w, k;
map<LL, int> x_mn, x_mx, y_mn, y_mx;
map<LL, LL> fa;

LL P(int x, int y) { return 1ll * x * N + y + 2; }

LL find(LL x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(LL x, LL y) {
    x = find(x), y = find(y);
    x_mn[y] = min(x_mn[x], x_mn[y]), x_mx[y] = max(x_mx[x], x_mx[y]);
    y_mn[y] = min(y_mn[x], y_mn[y]), y_mx[y] = max(y_mx[x], y_mx[y]);
    fa[x] = y;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> h >> w >> k;
    while(k--) {
        int x, y;
        cin >> x >> y;
        fa[P(x, y)] = P(x, y);
        x_mn[P(x, y)] = x_mx[P(x, y)] = x;
        y_mn[P(x, y)] = y_mx[P(x, y)] = y;
        for(int dx = -1; dx <= 1; dx++)
            for(int dy = -1; dy <= 1; dy++)
                if((dx || dy) && fa.find(P(x + dx, y + dy)) != fa.end())
                    merge(P(x, y), P(x + dx, y + dy));
    }
    for(auto [p, v] : fa)
        if(x_mn[p] == 1 && x_mx[p] == h || y_mn[p] == 1 && y_mx[p] == w
        || x_mn[p] == 1 && y_mn[p] == 1 || x_mx[p] == h && y_mx[p] == w)
            puts("No"), exit(0);    
    puts("Yes");
    return 0;
}

$\cdot~~\text{THE END}~~\cdot$