AtCoder Beginner Contest 299

A - Treasure Chest

题目大意

给定一个包含 |*.的字符串，其中|两个，*一个，问*是否在两个|之间。

解题思路

找到两个|的下标l，r以及*的下标mid，看看是否满足 l< mid < r即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
 
int main (){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int a = s.find('|');
    int b = s.find('|',a + 1);
    int c = s.find('*');
    if(c > a && c < b) cout << "in";
    else cout << "out";
    return 0;
}

B - Trick Taking

题目大意

给定n个人的卡片，颜色为 c[i] ，数字为 r[i] 。

如果其中有颜色为 T 的牌，则该颜色中数字最大的卡片对应的人赢。如果没有，则颜色为第一个人的卡牌颜（ 即c[0] ）中数字最大的卡片对应的人赢。问谁赢。

解题思路

分两种情况模拟即可。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
 
const int N = 2*1e5*10;;
int c[N],r[N];
int n, t;
 
void solve(){
    int res1 = 0;
    bool flag = false;
    for (int i = 0; i < n; i++)
    {
        if (c[i] == t)
        {
            res1 = max(res1, r[i]);
            flag = true;
        }
    }
 
    if (flag)
    {
        for (int i = 0; i < n; i++)
        {
            if (res1 == r[i])
            {
                cout << i + 1;
                break;
            }
        }
    }
    else
    {
        int res2 = r[0];
 
        for (int i = 1; i < n; i++)
        {
            if (c[i] == c[0])
            {
                res2 = max(res2, r[i]);
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (res2 == r[i])
            {
                cout << i + 1;
                break;
            }
        }
    }
}
int main (){
    cin >> n >> t;
    for(int i = 0; i < n; i++)  cin >> c[i];
    for(int i = 0; i < n; i++)  cin >> r[i];
    solve();
    return 0;
}

C - Dango

题目大意

定义一种字符串s的等级X是一个正整数），满足仅包含-o，且头或尾仅一处为-，其余都为o。其等级X为o的数量。给定一个字符串T，问其子串的最大等级。

解题思路

依次遍历字符串T，遇到两个-时期间就有一个等级。

然后再考虑从头到第一个-的子串，从最后一个-到尾的子串的等级。

注意单纯的一个-并不是合法的（0不是正整数）。

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
N = int(input())
S = input()
 
S = S + '-'
ans = -1
j = -1
for i in range(N+1) :
    if S[i] == '-' :
        l = i - j - 1
        if l > 0 and (j >= 0 or i < N) :
            ans = max(ans, l)
        j = i
print(ans)

D - Find by Query (abc299 d)

题目大意

交互题。这里有个长度为n的01字符串 s，其中$s1=0$，$sn=1$。你可以询问$si$的值。输出一个位置$p$满足$sp≠sp+1$。给定字符串长度n，你最多问20次。 $n<=2×10^5$。

解题思路

感觉好像和某次 cf的交互题很像。

注意题意保证了$s1=0，sn=1$。

首先询问中间位置$mid=\frac{n}{2}$，如果$s{mid}=1$，由于sn=1，最坏情况很有可能这后半部份都是 1，显然我们不该去问。但因为$s_1=0，s_{mid}=1$，所以前半部份必定有一处$s_p=0,s_{p+1}=1$。 反之$s_{mid}=0$的情况同理。

这样，通过一次询问，我们可以把答案保证存在的区间砍半了。那最多砍$logn$次就找到结果了。由于 $n≤2×10^5$，所以不会超过20次。

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
#include <bits/stdc++.h>
 
using i64 = long long;
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;
    
    int l = 1, r = N;
    while (l < r - 1) {
        int m = (l + r) / 2;
        std::cout << "? " << m << std::endl;
        int res;
        std::cin >> res;
        if (res == 1) {
            r = m;
        } else {
            l = m;
        }
    }
    std::cout << "! " << l << std::endl;
    
    return 0;
}

解题思路

E - Nearest Black Vertex

题目大意

给定一张图，要求给点涂黑白色，要求至少有一个黑点，且满足k个要求。

每个要求 $(p_i,d_i)$表示点 pi距离黑点的最近距离恰好为 $d_i$。

点数、边数 $≤2000$

解题思路

注意边数只有2000。

我们可以对每个要求的$p_i$进行BFS，把距离其小于d的点都标记为白色。

然后再对每个要求的 $p_i$进行 BFS，把距离其为d的且未被标记为白色的点标记为黑色。

如果有个要求没有找到可以被涂黑色的点，就无解了。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
 
using i64 = long long;
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M;
    std::cin >> N >> M;
    
    std::vector<std::vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    std::vector<bool> black(N, true);
    int K;
    std::cin >> K;
    
    std::vector<int> p(K), d(K);
    for (int i = 0; i < K; i++) {
        std::cin >> p[i] >> d[i];
        p[i]--;
        
        std::vector<int> dis(N, -1);
        std::queue<int> q;
        dis[p[i]] = 0;
        q.push(p[i]);
        
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            
            if (dis[x] < d[i]) {
                black[x] = false;
            }
            for (auto y : adj[x]) {
                if (dis[y] == -1) {
                    dis[y] = dis[x] + 1;
                    q.push(y);
                }
            }
        }
    }
    
    std::queue<int> q;
    std::vector<int> dis(N, -1);
    for (int i = 0; i < N; i++) {
        if (black[i]) {
            q.push(i);
            dis[i] = 0;
        }
    }
    
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        
        for (auto y : adj[x]) {
            if (dis[y] == -1) {
                dis[y] = dis[x] + 1;
                q.push(y);
            }
        }
    }
    
    for (int i = 0; i < K; i++) {
        if (dis[p[i]] != d[i]) {
            std::cout << "No\n";
            return 0;
        }
    }
    
    std::cout << "Yes\n";
    for (int i = 0; i < N; i++) {
        std::cout << black[i];
    }
    std::cout << "\n";
    
    return 0;
}

F - Square Subsequence

不会

G - Minimum Permutation

不会

Ex - Dice Sum Infinity

不会