AtCoder Beginner Contest 370

A - Raise Both Hands (abc370 A)

题目大意

给出Snuke举的左右手情况,如果只举左手,输出Yes,如果只举右手,输出No,否则输出Invalid

解题思路

逐一判断即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int l, r;
    cin >> l >> r;
    if (l == 1 && r == 0)
        cout << "Yes" << '\n';
    else if (l == 0 && r == 1)
        cout << "No" << '\n';
    else
        cout << "Invalid" << '\n';

    return 0;
}



B - Binary Alchemy (abc370 B)

题目大意

给定物品合成成分表\(a_{ij}\)表示物品 \(i\)和物品 \(j\)合成物品 \(a_{ij}\)

问物品 \(1\),依次与 \(1,2,3,..N\)物品合成,问最后的物品。

解题思路

按照题意查表,模拟合成即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> a(n);
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        for (auto& x : a[i]) {
            cin >> x;
            --x;
        }
    }
    int cur = 0;
    for (int i = 0; i < n; ++i) {
        int x = cur, y = i;
        if (x < y)
            swap(x, y);
        cur = a[x][y];
    }
    cout << cur + 1 << '\n';

    return 0;
}



C - Word Ladder (abc370 C)

题目大意

给定两个字符串\(s,t\)

用最小的次数,使得 \(s=t\),并且字符串\(x\)的字典序最小。

操作为,选择 \(s_i = c\),并且将修改后的 \(s\)放入 \(x\)的末尾。

解题思路

如何次数最小呢?

依次考虑\(s\)从左到右的每一位 \(i\),如果 \(s_i \neq t_i\),那我肯定要 \(s_i = t_i\),但这是我们此时要进行的操作吗?还是先放一放,改后面的字母后,再改当前位?

由于每次会将修改后的\(s\)放入 \(x\)的末尾,因此我们要优先考虑首先进行的操作,应该是:即刻进行,还是缓一缓在进行。

如果\(s_i > t_i\),那就优先更改当前位,这样改后的 \(s\)的字典序更小。

如果 \(s_i < t_i\),那就先更改后面位的,最后再改当前位,这样得到的 \(x\)的字典序最小。

这种回溯的感觉,可以用\(DFS\)实现上述操作。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s, t;
    cin >> s >> t;
    vector<string> ans;
    auto dfs = [&](auto dfs, int pos) {
        if (pos == s.size()) {
            return;
        }
        if (s[pos] == t[pos]) {
            dfs(dfs, pos + 1);
        } else if (s[pos] < t[pos]) {
            dfs(dfs, pos + 1);
            s[pos] = t[pos];
            ans.push_back(s);
        } else {
            s[pos] = t[pos];
            ans.push_back(s);
            dfs(dfs, pos + 1);
        }
    };
    dfs(dfs, 0);
    cout << ans.size() << '\n';
    for (auto& i : ans)
        cout << i << '\n';

    return 0;
}



D - Cross Explosion (abc370 D)

题目大意

二维网格,初始每个格子有墙。

依次进行\(q\)次放炸弹的操作,给定每次放炸弹的位置 \((i,j)\),如果该位置有墙,则该墙消失。

否则,炸弹会爆炸,会产生十字冲击波,该位置上下左右的各第一个墙都会消失。

问最后还存在的墙的数量。

解题思路

对于第一种情况,直接移除该位置的墙即可。

对于第二种情况,需要找到该列上下、该行左右最近的墙。

墙的数量\(hw \leq 4e5\),可以储存每个墙的坐标。

然后对于每行和每列,分别维护\(hset[i]\)表示第\(i\)行还有墙的列坐标,是个\(set\)\(wset[i]\)表示第 \(i\)列还有墙的行坐标 ,也是个\(set\)

这样,对于一个炸弹 \((i,j)\),如果该位置没有墙\((hset[i].find(j) == hset[i].end())\),则需要找到 \(< j\)的最大和 \(> j\) 的最小的数字。同理对于\(wset\)也要找对应的数字,然后 \(erase\)。这样每次操作的复杂度都是 \(O(\log)\),总的时间复杂度就是 \(O(q\log (h + w))\)

代码对于没有墙的逻辑是:

  • \(it = hset[i].lower\_bound(j)\), 由于没有墙,此时一定 \(*it > y\)(否则是 \(*it == y\)),如果 \(it != hset[i].end()\),那么它就是下面的第一个墙(这里认为左上是原点),要毁掉,于是\(it = hset[i].erase(it)\)\(erase\)返回值是移除了该 \(*it\)后的下一个元素。
  • 然后要找上面的第一个墙,此时 \(it\)\(>y\)的第一个位置(无论刚刚是否\(erase\)了),因此如果 \(it != hset[i].begin()\),那么 \(prev(it)\)就是上面的第一个墙,要毁掉,于是 \(hset[i].erase(prev(it))\)

同理的思路处理 \(wset\)即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w, q;
    cin >> h >> w >> q;
    vector<int> hh(h), ww(w);
    iota(hh.begin(), hh.end(), 0);
    iota(ww.begin(), ww.end(), 0);
    vector<set<int>> hset(h), wset(w);
    for (int i = 0; i < h; i++) {
        hset[i].insert(ww.begin(), ww.end());
    }
    for (int i = 0; i < w; i++) {
        wset[i].insert(hh.begin(), hh.end());
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        auto it = hset[x].lower_bound(y);
        if (it != hset[x].end() && *it == y) {
            hset[x].erase(y);
            wset[y].erase(x);
        } else {
            if (it != hset[x].end()) {
                wset[*it].erase(x);
                it = hset[x].erase(it);
            }
            if (it != hset[x].begin()) {
                it = prev(it);
                wset[*it].erase(x);
                hset[x].erase(it);
            }
            it = wset[y].lower_bound(x);
            if (it != wset[y].end()) {
                hset[*it].erase(y);
                it = wset[y].erase(it);
            }
            if (it != wset[y].begin()) {
                it = prev(it);
                hset[*it].erase(y);
                wset[y].erase(it);
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < h; i++) {
        cnt += hset[i].size();
    }
    cout << cnt << '\n';

    return 0;
}



E - Avoid K Partition (abc370 E)

题目大意

给定一个数组\(a\),划分成若干个子区间,使得没有子区间的和为 \(k\)

求划分方案数。

解题思路

朴素\(dp\)就是设 \(dp[i]\)表示前 \(i\)段划分满足条件的方案数。

转移则枚举最后一次的区间,然后 \(dp[i] = \sum_{1 \leq j \leq n, sum[j+1..i] \neq k} dp[j]\)

复杂度显然是 \(O(n^2)\)的。

棘手在条件 \(sum[j+1..i] \neq k\)上,如果没有这个条件,这个转移其实就是一个前缀和,用前缀和优化即为 \(O(n)\)

我们用前缀和相减代替区间和,即 \(sum[j+1..i] = sum[i] - sum[j]\),转移式即为\(dp[i] = \sum_{1 \leq j \leq n, sum[i] - sum[j] = k} dp[j]\)

换句话说,我们要对\(sum[j] \neq sum[i] - k\)\(dp[j]\)求和,这是个非常稀疏的条件,即如果设 \(cnt[i] = \sum_{sum[j] = i} dp[j]\),即前缀和为 \(i\)\(dp\)值,那上述转移式可改写成\(dp[i] = \sum_{1 \leq j < i} dp[j] - cnt[sum[i] - k]\)

即一个前缀和与一个数的差值,这样转移就是\(O(1)\)了,因此维护一个\(dp\)前缀和 \(\sum_{1 \leq j < i} dp[j]\)以及前缀和的\(dp\)\(cnt[i] = \sum_{sum[j] = i} dp[j]\)即可。

时间复杂度就是\(O(n \log n)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mo = 998244353;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    LL k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    map<LL, int> cnt;
    cnt[0] = 1;
    LL presum = 0;
    int precnt = 1;
    int ans = 0;
    for (auto& i : a) {
        presum += i;
        ans = (precnt - cnt[presum - k] + mo) % mo;
        cnt[presum] = (cnt[presum] + ans) % mo;
        precnt = (precnt + ans) % mo;
    };
    cout << ans << '\n';

    return 0;
}



F - Cake Division (abc370 F)

题目大意

给定一个环形数组,划分为\(k\)段,使得每段和的最小值最大。

在该最大值的各种划分方案中,求有多少位置,在所有划分方案中都不被分开。

解题思路

<++>

神奇的代码



G - Divisible by 3 (abc370 G)

题目大意

如果一个数是好的,说明它的因子和能被\(3\)整除。

给定 \(n,m\),问一个长度为 \(m\)的数组 \(a\)的数量,满足其各数的乘积不超过 \(n\),且是好数。

解题思路

<++>

神奇的代码