题目链接：https://atcoder.jp/contests/abc461/tasks

A - Armor#

按照题意判断输出即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8
typedef pair<int, int> pii;
9

10
void solved(){
11
    int a, d;
12
    cin >> a >> d;
13
    if(a > d) cout << "No" << endl;
14
    else cout << "Yes" << endl;
15
}
16

17
int main() {
18
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
19
    int _ = 1;
20
    // cin >> _;
21
    while(_--){
22
        solved();
23
    }
24
    return 0;
25
}

B - The Honest Woodcutters#

我们判断每个伐木工 $i$ 拥有的斧头是否是他自己的（ $b[a[i]]$ 是否等于 $i$ ）即可，如果有一个不是那就输出 $no$ ，否则就 $yes$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8
typedef pair<int, int> pii;
9
int a[110];
10
int b[110];
11

12
void solved(){
13
    int n;
14
    cin >> n;
15
    for(int i = 1; i <= n;i++) cin >> a[i];
16
    for(int i = 1; i <= n;i++) cin >> b[i];
17
    for(int i = 1; i <= n;i++){
18
        if(b[a[i]] != i){
19
            cout << "No" << endl;
20
            return;
21
        }
22
    }
23
    cout << "Yes" << endl;
24
}
25

26
int main() {
27
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
28
    int _ = 1;
29
    // cin >> _;
30
    while(_--){
31
        solved();
32
    }
33
    return 0;
34
}

C - Variety#

这里的思路是将每个颜色宝石中价值最大的放入数组 $max\_vals$ ，然后取最大的 $m$ 个计入总价值，也就是满足了 $m$ 个颜色种类这个条件。然后 $max\_vals$ 里面没选到的元素就放入 $other\_vals$ 。和其他宝石一起排序，然后再取价值最大的 $k$ - $m$ 个宝石取够 $k$ 个宝石计入总价值即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8
typedef pair<int, int> pii;
9

10
map<ll, vector<ll>> mp;
11
vector<ll> max_vals;
12
vector<ll> other_vals;
13

14
void solved(){
15
    int n, k, m;
16
    cin >> n >> k >> m;
17
    for(int i = 1; i <= n;i++){
18
        ll c, v;
19
        cin >> c >> v;
20
        mp[c].push_back(v); //用二维数组计入对应颜色c含有的所有价值v
21
    }
22
    //将map中的数组元素从大到小排序
23
    for(auto &c : mp){
24
        sort(c.second.begin(), c.second.end(), greater<ll>());
25
    }
26
    for(auto it1 : mp){
27
        ll cnt = 1;
28
        for(auto it2 : it1.second){
29
            if(cnt){max_vals.push_back(it2),cnt--;continue;} //max_vals只取每个颜色的第一个
30
            other_vals.push_back(it2);  //其他就加入other_vals
31
        }
32
    }
33
    //排序之后取前m个
34
    sort(max_vals.begin(), max_vals.end(), greater<ll>());
35

36
    ll cnt = 0;
37
    ll ans = 0;
38
    for(auto it : max_vals){
39
        if(cnt < m){
40
            ans += it;
41
            cnt++;
42
        }
43
        else other_vals.push_back(it);
44
    }
45
    //排序之后取前k - m个
46
    sort(other_vals.begin(), other_vals.end(), greater<ll>());
47

48
    for(auto it : other_vals){
49
        if(cnt != k){
50
            ans += it;
51
            cnt++;
52
        }
53
    }
54
    cout << ans << endl;
55
}
56

57
int main() {
58
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
59
    int _ = 1;
60
    // cin >> _;
61
    while(_--){
62
        solved();
63
    }
64
    return 0;
65
}

D - Count Subgrid Sum = K#

这题直接暴力的复杂度会达到 $O(H^2 W^2)$ ，没办法通过这题。思路是通过给定确定的矩阵上界和下界，然后再在上下界里取左右边界，然后统计矩阵内计数之和为 $k$ 的个数即为答案。这个原理的复杂度大概为 $O(H^2 W)$ ，足够通过本题。
这里上下界的循环仍然有 $H^2$ 的复杂度，优化的地方是在给定上下界的每一列中计算整一列的整数之和，然后将 $W$ 个列压成了一维数组 $column$ ，求连续子序列之和为 $k$ 的数量有多少个。这里的解法是利用前缀和变式。我们知道 $pre[r + 1] - pre[l] = k$ 时 $[l, r]$ 就是满足条件的区间。我们不妨改变一下式子。变成 $pre[l] = pre[r + 1] - k$ ，也就是说，对于目前遍历到的前缀和 $prefix(pre[r + 1])$ ，满足条件的区间的数量就是 $pre[l]$ 的出现频率 $(prefixL\_cnt)$ 。所以每次遍历时我们累加对应的 $prefixL\_cnt$ 即可。不过这里要注意 $prefixL\_cnt[0]$ 要设置成 $1$ ，以正确统计区间左端点 $l$ 为 $0$ 的区间。(这里的 $prefixL\_cnt$ 数组是 $base-0$ 的)
这里的 $touched$ 是为了记录每一次给定上下界的循环内使用到的 $prefixL\_cnt[i]$ ，然后一一对应清零，供下一次循环使用。（如果使用直接将 $prefixL\_cnt[i]$ 全部覆写为 $0$ 的话需要写入 $H \cdot W$ 次，可能超时，所以只把用到清零即可）

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8
typedef pair<int, int> pii;
9

10
vector<string> grid;
11
vector<int> column, prefixL_cnt, touched;
12

13
void solved(){
14
    int h, w, k;
15
    ll ans = 0;
16
    cin >> h >> w >> k;
17
    grid.resize(h + 1);
18
    column.resize(w + 1);
19
    prefixL_cnt.resize(h * w + 10);
20

21

22
    for(int i = 1; i <= h;i++){
23
        cin >> grid[i];
24
        grid[i] = " " + grid[i];
25
    }
26

27
    //上界
28
    for(int i = 1; i <= h;i++){
29
        //清空column
30
        fill(column.begin(), column.end(), 0);
31

32
        //下界
33
        for (int j = i; j <= h;j++){
34
            //压缩为一维数组
35
            for(int l = 1; l <= w;l++){
36
                column[l] += grid[j][l] - '0';
37
            }
38
            //当前的前缀和
39
            int prefix = 0;
40
            prefixL_cnt[0] = 1;
41
            touched.push_back(0);
42

43
            for(int i = 1; i <= w;i++){
44
                prefix += column[i];
45
                if(prefix >= k) ans += prefixL_cnt[prefix - k];    //统计满足条件的区间
46
                if(prefixL_cnt[prefix] == 0) touched.push_back(prefix); //第一次出现时计入touched中
47
                prefixL_cnt[prefix]++;
48
            }
49
            //只清空用过的prefixL_cnt[x]
50
            for(int x : touched){
51
                prefixL_cnt[x] = 0;
52
            }
53
            touched.clear();
54
        }
55
    }
56
    cout << ans << endl;
57
}
58

59
int main() {
60
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
61
    int _ = 1;
62
    // cin >> _;
63
    while(_--){
64
        solved();
65
    }
66
    return 0;
67
}

Mkrari的个人博客

A - Armor#

B - The Honest Woodcutters#

C - Variety#

D - Count Subgrid Sum = K#