NOTE
比赛链接：Atcoder Beginner Contest 461

A - Armor#

关键词：签到

Code#

1
// Problem: AT ABC461 A
2
// Contest: AtCoder - AtCoder Beginner Contest 461
3
// URL: https://atcoder.jp/contests/abc461/tasks/abc461_a
4
// Time: 2026-06-06 20:00:07
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int a, d;
29
    cin >> a >> d;
30

31
    cout << (a <= d ? "Yes" : "No") << endl;
32
}
33

34
int main()
35
{
36
    fastio();
37

38
    int T = 1;
39
    // cin >> T;
40

41
    while (T--)
42
        solve();
43

44
    return 0;
45
}

B - The Honest Woodcutters#

关键词：签到

Code#

1
// Problem: AT ABC461 B
2
// Contest: AtCoder - AtCoder Beginner Contest 461
3
// URL: https://atcoder.jp/contests/abc461/tasks/abc461_b
4
// Time: 2026-06-06 20:00:08
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    vector<int> a(n + 1), b(n + 1);
32
    map<int, int> mp;
33

34
    for (int i = 1; i <= n; ++i)
35
    {
36
        cin >> a[i];
37
        mp[a[i]] = i;
38
    }
39

40
    for (int i = 1; i <= n; ++i)
41
    {
42
        cin >> b[i];
43
        if (mp[i] != b[i])
44
        {
45
            cout << "No" << endl;
46
            return;
47
        }
48
    }
49

50
    cout << "Yes" << endl;
51
}
52

53
int main()
54
{
55
    fastio();
56

57
    int T = 1;
58
    // cin >> T;
59

60
    while (T--)
61
        solve();
62

63
    return 0;
64
}

C - Variety#

关键词：贪心

思路#

首先这不是一个dp题。

考虑首先把所有的宝石按价值从大到小排序，贪心地拿最大的前 $k$ 个宝石，并且记录不同颜色的数量。

当不同的颜色不够 $m$ 种时，我们就要继续拿其他颜色的最大价值的宝石，由于前面排序过，如果当前宝石是一种尚未出现的新颜色，那么它一定是这种颜色中价值最大的宝石，就应该直接把它加进来，那我们怎么从现有的宝石里找一个去掉呢？

对于当前已经选中的宝石：

如果某颗宝石是其颜色唯一的一颗，那么删除它会使颜色种类减少 $1$ ，不能随意删除；
如果某颗宝石的颜色已经出现过，那么它是重复颜色的宝石，删除它不会减少颜色种类。

因此，只有重复颜色宝石可以被替换。为了使损失尽可能小，我们应当优先删除价值最小的重复颜色宝石。

可以使用一个小根堆，维护所有可删除宝石的价值。

Code#

1
// Problem: AT ABC461 C
2
// Contest: AtCoder - AtCoder Beginner Contest 461
3
// URL: https://atcoder.jp/contests/abc461/tasks/abc461_c
4
// Time: 2026-06-06 20:00:09
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 2e5 + 10;
25

26
struct Gems
27
{
28
    int c;
29
    ll v;
30

31
    bool operator<(const Gems &other) const
32
    {
33
        return v > other.v;
34
    }
35
} g[N];
36

37
void solve()
38
{
39
    int n, k, m;
40
    cin >> n >> k >> m;
41

42
    for (int i = 0; i < n; ++i)
43
        cin >> g[i].c >> g[i].v;
44

45
    sort(g, g + n);
46

47
    vector<bool> st(n + 1, false);
48

49
    priority_queue<ll, vector<ll>, greater<ll>> heap;
50

51
    ll res = 0;
52
    int colors = 0;
53

54
    for (int i = 0; i < k; ++i)
55
    {
56
        auto &[c, v] = g[i];
57
        res += v;
58

59
        if (!st[c])
60
            st[c] = true, colors++;
61
        else
62
            heap.push(v);
63
    }
64

65
    for (int i = k; i < n && colors < m; ++i)
66
    {
67
        auto &[c, v] = g[i];
68

69
        if (st[c])
70
            continue;
71

72
        res -= heap.top();
73
        heap.pop();
74

75
        res += v;
76
        st[c] = true;
77
        colors++;
78
    }
79

80
    cout << res << endl;
81
}
82

83
int main()
84
{
85
    fastio();
86

87
    int T = 1;
88
    // cin >> T;
89

90
    while (T--)
91
        solve();
92

93
    return 0;
94
}

D - Count Subgrid Sum = K#

关键词：暴力

思路#

这里是天堂吗？为什么在D题出现了一个可以用 $O(n^4)$ 来过的算法？

二维前缀和暴力算即可。自己都没想到过了。

好吧，时限竟然是4s，为什么过的人这么少？

Code#

1
// Problem: AT ABC461 D
2
// Contest: AtCoder - AtCoder Beginner Contest 461
3
// URL: https://atcoder.jp/contests/abc461/tasks/abc461_d
4
// Time: 2026-06-06 20:00:10
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 510;
25

26
int g[N][N], s[N][N];
27

28
void solve()
29
{
30
    int h, w, k;
31
    cin >> h >> w >> k;
32

33
    for (int i = 1; i <= h; ++i)
34
        for (int j = 1; j <= w; ++j)
35
        {
36
            char ch;
37
            cin >> ch;
38

39
            g[i][j] = ch - '0';
40
        }
41

42
    for (int i = 1; i <= h; ++i)
43
        for (int j = 1; j <= w; ++j)
44
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + g[i][j];
45

46
    ll res = 0;
47
    for (int x1 = 1; x1 <= h; x1++)
48
        for (int x2 = x1; x2 <= h; x2++)
49
            for (int y1 = 1; y1 <= w; y1++)
50
                for (int y2 = y1; y2 <= w; y2++)
51
                    if (s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] == k)
52
                        res++;
53
    cout << res << endl;
54
}
55

56
int main()
57
{
58
    fastio();
59

60
    int T = 1;
61
    // cin >> T;
62

63
    while (T--)
64
        solve();
65

66
    return 0;
67
}

E - E-liter#

关键词：树状数组

思路#

转化题意#

注意到行永远只会被染成黑色，列永远只会被染成白色。

这意味着，对于网格中的任意一个细胞 $(r, c)$ ，我们根本不需要知道它经历了多少次反复横跳。它的最终颜色只取决于一件事：行 $r$ 和列 $c$ 谁最后被操作过。

可以使用时间戳来记录。定义 $row_r$ 为第 $r$ 行最后一次被涂黑的时间， $col_c$ 为第 $c$ 列最后一次被涂白的时间。

初始时所有格子为白色，可以让 $row_r=col_c=0$ ，当第 $i$ 次操作发生时，将它的时间记为 $i$ 。

对于格子 $(r,c)$ ：

若 $row_r > col_c$ ，说明最近一次相关操作是行涂黑，格子为黑色；
若 $row_r \leq col_c$ ，说明列涂白操作更新，或者从未被染黑，格子为白色。

因此： $(r,c) \text{ 为黑色} \iff row_r > col_c$

考虑单次操作如何修改答案：关键在于每次操作只需要计算这一行或这一列原来有多少个黑色格子。

操作 $1$ ：将第 $R$ 行涂黑。执行操作前，第 $R$ 行中的格子 $(R, c)$ 为黑色，当且仅当 $col_c < row_R$ ，因此这一行原本的黑色格子数量为： $old = \#\{c \mid col_c < row_R\}$ 。即统计所有满足 $col_c < row_R$ 的格子 $c$ 的数量。执行操作后，第 $R$ 行的所有 $N$ 个格子都会变成黑色，所以答案增加 $N-old$ ，随后更新时间戳。

操作 $2$ ：将第 $C$ 列涂白。执行操作前，第 $C$ 行中的格子 $(r, C)$ 为黑色，当且仅当 $row_r > col_C$ ，因此这一列原本的黑色格子数量为： $old = \#\{c \mid row_r > col_C\}$ ，执行操作后，这一列的所有格子都会变成白色。所以答案减少 $old$ ，随后更新时间戳。

维护信息#

每次查询需要快速回答两类问题：

有多少个 $col_c < x$ ？
有多少个 $row_r > x$ ？

可以使用树状数组维护每一种时间戳出现了多少次。

建立两个树状数组， $bitr$ 表示每一种时间戳对应多少行， $bitc$ 表示每一种时间戳对应多少列。

总结#

NOTE
这类题目的关键特征是：

对整行、整列、区间或区域执行覆盖操作；

后执行的操作会覆盖先执行的操作；

需要实时统计满足某种条件的元素数量。

此时可以优先考虑：将覆盖关系转换为最后操作时间的大小比较。

Code#

NOTE
代码实现方面：由于树状数组不能使用下标 $0$ ，所以初始时间戳都设置为 $1$ ，第一次查询对应时间戳 $2$ 。

1
// Problem: AT ABC461 E
2
// Contest: AtCoder - AtCoder Beginner Contest 461
3
// URL: https://atcoder.jp/contests/abc461/tasks/abc461_e
4
// Time: 2026-06-06 20:00:11
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 3e5 + 10;
25

26
struct Fenwick
27
{
28
    int n;
29
    vector<ll> tr;
30

31
    Fenwick()
32
    {
33
    }
34

35
    Fenwick(int n)
36
    {
37
        init(n);
38
    }
39

40
    Fenwick(const vector<ll> &a)
41
    {
42
        build(a);
43
    }
44

45
    void init(int n)
46
    {
47
        this->n = n;
48
        tr.assign(n + 1, 0);
49
    }
50

51
    int lowbit(int x)
52
    {
53
        return x & -x;
54
    }
55

56
    void build(const vector<ll> &a)
57
    {
58
        init(static_cast<int>(a.size()) - 1);
59

60
        for (int i = 1; i <= n; i++)
61
        {
62
            tr[i] += a[i];
63

64
            int j = i + lowbit(i);
65

66
            if (j <= n)
67
                tr[j] += tr[i];
68
        }
69
    }
70

71
    void add(int x, ll val)
72
    {
73
        for (int i = x; i <= n; i += lowbit(i))
74
            tr[i] += val;
75
    }
76

77
    ll sum(int x)
78
    {
79
        ll res = 0;
80

81
        for (int i = x; i > 0; i -= lowbit(i))
82
            res += tr[i];
83

84
        return res;
85
    }
86

87
    ll range_sum(int l, int r)
88
    {
89
        return sum(r) - sum(l - 1);
90
    }
91
};
92

93
void solve()
94
{
95
    int n, q;
96
    cin >> n >> q;
97

98
    vector<int> row(n + 1, 1), col(n + 1, 1);
99
    Fenwick bitr(q + 1), bitc(q + 1);
100

101
    bitr.add(1, n), bitc.add(1, n);
102

103
    ll res = 0;
104

105
    for (int t = 2; t <= q + 1; t++)
106
    {
107
        ll op, x;
108
        cin >> op >> x;
109

110
        if (op == 1)
111
        {
112
            int old = bitc.sum(row[x] - 1);
113
            res += n - old;
114

115
            bitr.add(row[x], -1);
116
            row[x] = t;
117
            bitr.add(row[x], 1);
118
        }
119
        else
120
        {
121
            int old = n - bitr.sum(col[x]);
122
            res -= old;
123

124
            bitc.add(col[x], -1);
125
            col[x] = t;
126
            bitc.add(col[x], 1);
127
        }
128
        cout << res << endl;
129
    }
130
}
131

132
int main()
133
{
134
    fastio();
135

136
    int T = 1;
137
    // cin >> T;
138

139
    while (T--)
140
        solve();
141

142
    return 0;
143
}

A - Armor#

Code#

B - The Honest Woodcutters#

Code#

C - Variety#

思路#

Code#

D - Count Subgrid Sum = K#

思路#

Code#

E - E-liter#

思路#

转化题意#

维护信息#

总结#

Code#

评论