AtCoder Begginer Contest 377 A~D

· · 题解

A - Rearranging ABC

洛谷链接

AtCoder链接

题目

给你一个长度为 3 的字符串 S，由大写英文字母组成。

请判断是否有可能重新排列 S 中的字符，使其与字符串 ABC 匹配。

代码

#include <bits/stdc++.h>

using namespace std;

string s;

int main()
{
    cin >> s;
    sort(s.begin(), s.end());
    if (s == "ABC")
        puts("Yes");
    else
        puts("No");
    return 0;
}

B - Avoid Rook Attack

洛谷链接

AtCoder链接

题目

有一个由 64 个正方形组成的网格，网格中有 8 行和 8 列。(i,j) 表示从上面 (1 \le i \le 8) 起第 i 行，从左边 (1 \le j \le 8) 起第 j 列的正方形。

每个方格要么是空的，要么有棋子放在上面。方格的状态由长度为 8 的 8 字符串序列 (S_1,S_2,S_3, \ldots ,S_8) 表示。如果 S_i 的第 j 的字符是 .，则 (1 \le i \le 8,1 \le j \le 8) 为空；如果是 #，则有棋子。

您要将棋子放在空方格上，使它不能被任何现有棋子吃掉。

放置在方格 (i,j) 上的棋子可以吃掉满足以下任一条件的棋子：

例如，位于 (4,4) 位置上的棋子可以吃掉位于下图中蓝色所示位置上的棋子：

您可以将棋子放在几个位置上？

代码

#include <bits/stdc++.h>

using namespace std;

string ip;
int rt, pi[10], pj[10];

int main()
{
    for (int i = 1; i <= 8; i ++ )
    {
        cin >> ip;
        for (int j = 0; j < 8; j ++ )
        {
            if (ip[j] == '#')
            {
                pi[i] = 1;
                pj[j + 1] = 1;
            }
        }
    }
    for (int i = 1; i <= 8; i ++ )
    {
        for (int j = 1; j <= 8; j ++ )
        {
            if (pi[i] + pj[j] == 0)
                rt += 1;
        }
    }
    cout << rt << '\n';
    return 0;
}

C - Avoid Knight Attack

洛谷链接

AtCoder链接

题目

有一个由 N^2 个正方形组成的网格，网格中有 N 行和 N 列。让 (i,j) 表示从上面 (1 \le i \le N) 起第 i 行，从左边 (1 \le j \le N) 起第 j 列的正方形。

每个方格要么是空的，要么放了一颗棋子。网格上有 M 个棋子，而第 k(1 \le k \le M) 个棋子被放置在 (a_k,b_k) 个方格上。

您想要将棋子放在空方格上，使其不能被任何现有棋子吃掉。

放置在位置 (i,j) 上的棋子可以吃掉满足以下任何条件的棋子：

在这里，涉及不存在的正方形的条件被认为是不满足的。

例如，放在 (4,4) 位置上的棋子可以吃掉下图中蓝色所示位置上的棋子：

您可以将棋子放在几个位置上？

思路

可用方格的数量可达 10^{18}-3，数量庞大；而不可用方格的数量不超过 9M，完全可以维持。

通过在类似哈希集的数据结构中对不可用方格进行重复管理，可以找到所需的方格数。

时间复杂度约为 O(M) 或 O(M \log M)。

代码

#include <bits/stdc++.h>

using namespace std;

int n, m, x, y;
set<pair<int, int> > bad_cell;
vector<pair<int, int> > knight_move{{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i ++ )
    {
        scanf("%d %d", &x, &y);
        bad_cell.emplace(x, y);
        for (const auto& [dx, dy] : knight_move)
        {
            if (1 <= x + dx && x + dx <= n && 1 <= y + dy && y + dy <= n)
                bad_cell.emplace(x + dx, y + dy);
        }
    }
    cout << static_cast<long>(n) * n - size(bad_cell) << '\n';
    return 0;
}

D - Many Segments 2

洛谷链接

AtCoder链接

题目

给你两个长度分别为 N、L=(L_1,L_2, \ldots ,L_N) 和 R=(R_1,R_2, \ldots ,R_N) 的正整数序列，以及一个整数 M。

求满足以下两个条件的整数对 (l,r) 的个数：

思路

这个题要倒着做，我们先统计出有多少个是不符合要求的，再用总数减去。（总数怎么算就不说了，从所有的选两个点做为左右端点，再加上一个的）。

不符合要求，即包含了某一个区间，如果只有一个区间是好做的，我们只要把左端点及左边点的个数和右端点及右边点的个数匹配（乘起来）即可，那么如果有多个区间，就有重复问题（其实和一个区间没什么关系）。

那么如何解决重复问题呢？那么我们要定住一个端点，右端点，那么对于每个右端点，我们该如何统计有多少个以这个点结尾的区间是不合法的呢？

那就是有几个左端点是不合法的。而我们知道如果一个区间 \lbrack l,r \rbrack 是不合法的那么区间 \lbrack l-1,r \rbrack 一定也是不合法的，因为区间 \lbrack l-1,r \rbrack 包含区间 \lbrack l,r \rbrack，那么它一定包含区间 \lbrack l,r \rbrack 包含的那个给出区间，即可得出它也不合法。

那么有了这个性质，我们就只需要对于每个右端点把最靠后（最大）的使得它不合法的左端点存下来，前面的就都不合法了，即可求出前面的问题。

那么这个问题怎么做呢？如果个右端点和某些给出区间的右端点重合，那么就是要包含这些区间中的一个，肯定包含那个左端点最靠后的合适，那么对这些所有的取个最大值即可。

但是给出区间的右端点不一定非要恰好在这个点上，给出区间的右端点在当前点的前面即可，那么如果把这种也算上，其实也就是对第一种情况的数做一个从 1 到当前的取最大值（最靠后）即可，因为到前面已经不合法了，到当前这个一定更不合法，而我们又想让 l 更靠后，所以是这样。

最后统计一下答案即可。

代码

#include <bits/stdc++.h>

using namespace std;

long long n, m, f[200010], l[200010], r[200010], ans;

int main()
{
    scanf("%lld %lld", &n, &m);
    ans = m * (m - 1) / 2 + m;
    for (long long i = 1; i <= n; i ++ )
    {
        scanf("%lld %lld", &l[i], &r[i]);
        f[r[i]] = max(f[r[i]], l[i]);
    }
    for (long long i = 1; i <= m; i ++ )
    {
        f[i] = max(f[i - 1], f[i]);
        ans -= f[i];
    }
    cout << ans << '\n';
    return 0;
}