醉心代码无法自拔

程序员的自我修养(?)

0%

Atcoder Beginner Contest 370 题解

发表于 更新于 分类于
本文字数： 3.4k 阅读时长 ≈ 6 分钟

竞赛结果：Contestant,3202nd,Solved ABC,+22

todo

因为博主太困所以打算等下周空闲时间把这场和上场的题意补上。

A.Raise Both Hands

思路

打表（这能叫做一个表吗？）即可。

代码

1
2
3
4
5
6
7
8
9
10
11
void solve()
{
    int l, r;
    cin >> l >> r;
    if (l && !r)
        cout << "Yes" << endl;
    else if (!l && r)
        cout << "No" << endl;
    else
        cout << "Invalid" << endl;
}

B.Binary Alchemy

思路

按规则模拟即可，为了缩减代码量我直接采用了 max 和 min 来替代一层 if 判断，增加的复杂度无伤大雅。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve()
{
    int n;
    cin >> n;
    vector<vector<int>> vec(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> vec[i][j];
    int element = 1;
    for (int ele = 1; ele <= n; ele++)
        element = vec[max(element, ele)][min(ele, element)];
    cout << element << endl;
}

C.Word Ladder

思路

显然，因为修改本身没有限制，所以最少的修改次数必然是两个字符串不同字符的字符个数。

下面考虑如何让每次修改字典序最小。

显而易见，将一个字典序大的字符修改为一个字典序小的字符，字符串的整体字典序会下降，反之上升。而字典序的比较规则是从前往后比较，即为前面的字典序下降对整体字符串字典序的影响更大，而后面字符字典序上升对整体字符串字典序影响更小。

所以，为了让每次修改后的字典序是最优，我们首先正序修改会导致字典序下降的字符，让字典序“速降”，再倒序修改会导致字典序上升的字符，让字典序“缓升”。这样的解法就是最优的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve()
{
    string s, t;
    cin >> s >> t;
    vector<string> ans;
    vector<int> inc,dec;
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        if (s[i] < t[i])
            inc.push_back(i);
        else if (s[i] > t[i])
            dec.push_back(i);
    }
    for (auto &v : dec)
        s[v] = t[v], ans.push_back(s);
    reverse(all(inc));
    for (auto &v : inc)
        s[v] = t[v], ans.push_back(s);
    cout << ans.size() << endl;
    for (auto &s : ans)
        cout << s << endl;
}

以下为补题部分。

D.Cross Explosion

思路

朴素的暴力

直接根据题意暴力即可，开启O3优化后，对于本题会TLE两个点，但是大部分样例都能过，证明只要在暴力上进行优化即可。

暴力的优化

暴力的优化一共有两个方向，一种是用数组维护当前节点的相邻节点，另外一种是 set 记录目前剩余节点并二分查找相邻节点。

我赛时写的第一种优化，没优化出来。

但这种优化好像有些边界条件模糊，还真不如二分set好懂，于是干脆只写二分set了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void solve() // set + 二分
{
    int h, w, q;
    cin >> h >> w >> q;
    vector<set<int>> col(w + 1), row(h + 1);
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            row[i].insert(j), col[j].insert(i);
    for (int i = 1; i <= h; i++)
        row[i].insert(0), row[i].insert(w + 1);
    for (int i = 1; i <= w; i++)
        col[i].insert(0), col[i].insert(h + 1);
    int ans = h * w;
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        auto it = row[x].lower_bound(y), it2 = prev(it); // 搜行
        if (*it == y) // 只炸自己
        {
            ans--, row[x].erase(y), col[y].erase(x);
            continue;
        }
        if (*it <= w) // 搜索到的it不到边界
            ans--, row[x].erase(*it), col[*it].erase(x);
        if (*it2) // it的前一个不到边界
            ans--, row[x].erase(*it2), col[*it2].erase(x);
        it = col[y].lower_bound(x), it2 = prev(it); // 搜列
        if (*it <= h)
            ans--, row[*it].erase(y), col[y].erase(*it);
        if (*it2)
            ans--, row[*it2].erase(y), col[y].erase(*it2);
    }
    cout << ans << endl;
}

E.Avoid K Partition

思路

时间复杂度 $O(N^2)$

二维 dp，定义 $dp[i]$ 为在选定点 $i$ 的时候，从 $1$ 选到 $i$ 的方案的总和。

初始值： $dp[1] = 1$ ，终值取 $dp[n+1]$ ，过程中的推导式为 $dp[n] = \sum_{1 \leq m \lt n} \left(0\text{ if }\sum_{k=m}^{n-1} A_i = K \text{ else } dp[m] \right) $。

注意：虽然这个式子中的$\sum A_i$部分可以用前缀和，但是时间复杂度最坏是$N^2$，这个推导式过不了本题目，要对其进行优化。

优化正解

可以发现转移只会从 $\sum^i_j {A_i \neq k}$ 的区间来，所以分别记录目前的总方案数和上述区间的方案数，则 $dp[i] = sum-invalid$。

开一个 map 进行缓存，令 $mp[pref]$ 等价前缀和为 $pref$ 时的合法方案数，则 $invalid = mp[sum-k]$。答案得以求出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
constexpr int MOD = 998244353;
using i64 = long long;
void solve()
{
    int n;
    i64 k;
    cin >> n >> k;
    vector<int> vec(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> vec[i];
    vector<i64> dp(n + 1);
    dp[1] = 1;
    map<i64, int> mp;
    mp[0] = 1;
    i64 sum = 0, all = 1;
    for (int i = 1; i <= n; i++)
    {
        sum += vec[i];
        int invalid = mp[sum - k];
        dp[i] = (all - invalid + MOD) % MOD;
        all = (all + dp[i]) % MOD;
        mp[sum] = (mp[sum] + dp[i]) % MOD;
    }
    cout << dp[n] << endl;
}