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

A - Compromise#

我们直接判断是否存在大于等于 $0$ 的数，存在即说明幸福值可能为正数，输出 $No$ ，否则输出 $Yes$ 。

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

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

8
void solved(){
9
    int n; cin >> n;
10
    bool f = true;
11
    for (int i = 1; i <= n;i++){
12
        int x; cin >> x;
13
        if(x >= 0) f = false;
14
    }
15
    if(f) cout << "Yes" << endl;
16
    else cout << "No" << endl;
17
}
18

19
int main(){
20
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
21
    solved();
22
    return 0;
23
}

B - Representative Balls#

我们用一个二维数组来存储对应 $m$ 种的大小 $s$ 的球有哪些。然后遍历判断对应的颜色 $i$ 是否存在，存在则 $yes$ 设置为真，然后遍历 $A[i]$ 中球的大小 $s$ 找出最大值 $ma$ 输出。否则则 $yes$ 为假，直接输出 $-1$ 。

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

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

8
vector<vector<int>> A;
9

10
void solved(){
11
    int n, m; cin >> n >> m;
12
    A.resize(m + 1);
13
    for(int i = 1; i <= n;i++){
14
        int c, s; cin >> c >> s;
15
        A[c].push_back(s);
16
    }
17
    for(int i = 1; i <= m;i++){
18
        int ma = 0; bool yes = false;
19
        for(auto it : A[i]){
20
            yes = true;
21
            if(it > ma) ma = it;
22
        }
23
        if(yes) cout << ma << " ";
24
        else cout << -1 << " ";
25
    }
26
}
27

28
int main(){
29
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
30
    solved();
31
    return 0;
32
}

C - Count Close Pairs#

交互式问题，我们需要根据系统给出的输入来计算输出正确结果。这题我们需要用一个双指针来解决。我们每次可以询问两个点之间的距离是否大于 $1$ ，然后系统会给出 $Yes$ 或 $No$ 的答案。
我们用一个右指针 $j$ 来记录满足条件的区间的右端点。然后开始逐个判断左端点 $i$ 对应的最大的右端点 $j$ 是多少。也就是不断输出”? i j”，如果输入是 $Yes$ ，那么我们就继续右移右端点 $(j++)$ ，直到系统输入 $No$ ，则说明当前的 $j$ 和 $i$ 的距离已经超过了 $1$ ，那么我们就计入贡献 $ans$ ， $[i, j)$ 这个区间内共有 $j - i - 1$ 个合法的答案。因为两个指针一共最多移动 $2 \times n$ 次，所以不会超过 $2N$ 次询问就能得到答案，可以通过本题。
$tips：$ 注意本题要求每次询问都需要刷新标准输出，也就是每次输出都要使用 $endl$ 。

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

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

8
void solved(){
9
    int n; cin >> n;
10
    int j = 1;
11
    ll ans = 0;
12
    for(int i = 1; i <= n;i++){
13
        //如果右指针小于等于左指针就要将右指针移到左指针右边
14
        if(j < i + 1) j = i + 1;
15

16
        while(j <= n){
17
            cout << "? " << i << " " << j << endl;
18
            string resp;
19
            cin >> resp;
20
            if(resp == "Yes") j++;
21
            else break;
22
        }
23
        int r = j - 1;
24
        ans += (r - i);
25
    }
26
    cout << "! " << ans << endl;
27
}
28

29
int main(){
30
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
31
    solved();
32
    return 0;
33
}

D - Placing Rooks#

这题我们直接模拟会超时，这里的方法是通过记录判断每个棋子最终是否会被保留。
我们先用 $row[i], col[i]$ 记录下第 $i$ 次操作时的行和列。然后定义 $last\_ row$ 和 $last\_ col$ 来分别记录每行每列最后一次被操作是第几次。最后我们再遍历 $m$ 次，判断我们在操作中最终能被保留下来的棋子有多少个。
这里的遍历是判断当前次数 $i$ 对应行 $row[i]$ 和列 $col[i]$ 是否是最后一次操作(即 $last\_ row$ 和 $last\_ col$ 均为 $i$ )，如果是，则说明后续的操作都不会清空这个棋子对应的行和列，这个棋子就会被保留，我们 $ans$ 就加一。反之，如果 $last\_ row$ 和 $last\_ col$ 有一个不为 $i$ ，则说明后续这个棋子会被拿掉。最后我们输出 $ans$ 即为结果。

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

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

11
void solved() {
12
    int n, m;
13
    cin >> n >> m;
14

15
    vector<int> row(m + 1), col(m + 1);
16
    vector<int> last_row(n + 1, 0), last_col(n + 1, 0);
17
    for (int i = 1; i <= m; ++i) {
18
        cin >> row[i] >> col[i];
19
        last_row[row[i]] = i;
20
        last_col[col[i]] = i;
21
    }
22

23
    ll ans = 0;
24
    for (int i = 1; i <= m; ++i) {
25
        if (last_row[row[i]] == i && last_col[col[i]] == i)
26
            ans++;
27
    }
28
    cout << ans << endl;
29
}
30

31
int main() {
32
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
33
    int _ = 1;
34
    //cin >> _;
35
    while (_--) {
36
        solved();
37
    }
38
    return 0;
39
}

Mkrari的个人博客

A - Compromise#

B - Representative Balls#

C - Count Close Pairs#

D - Placing Rooks#