AtCoder Beginner Contest 337
A
思路
直接累加总分即可
Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
void solve()
{
int n, X, Y, x = 0, y = 0;
cin >> n;
while (n--)
{
cin >> X >> Y;
x += X, y += Y;
}
if (x > y)
cout << "Takahashi";
else if (x < y)
cout << "Aoki";
else
cout << "Draw";
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}B
思路
将长度和字符串 \(S\) 的所有扩展 \(ABC\) 字符串构造出来，看是否出现和 \(S\) 相同的字符串
Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
void solve()
{
string s;
cin >> s;
bool flag = false;
for (int i = 0; i <= s.size(); i++)
{
for (int j = 0; j <= s.size() - i; j++)
{
string tmp;
tmp = string(i, 'A') + string(j, 'B') + string(s.size() - i - j, 'C');
flag |= (tmp == s);
}
}
if (flag)
cout << "Yes";
else
cout << "No";
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}C
思路
新开数组 \(b\) 存数组 \(a\) 中每个数的下标，顺着数组 \(b\) 输出即可
Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
int now;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] == -1)
now = i;
else
b[a[i]] = i;
}
for (int i = 0; i < n; i++)
{
cout << now << " ";
now = b[now];
}
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}D
思路
分别遍历每行和每列，用前缀和分别记录 . 和 x 出现的次数，如果这段出现过 x 则不考虑，如果没出现过就看出现了多少 . ，最少即为答案。
Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 2e5 + 10;
void solve()
{
int n, m, k;
cin >> n >> m >> k;
vector<vector<char>> mp(n + 1, vector<char>(m + 1));
vector<int> a(N), b(N);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> mp[i][j];
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; i++)
{
a[0] = 0, b[0] = 0;
for (int j = 1; j <= m; j++)
{
a[j] = a[j - 1] + (mp[i][j] == '.');
b[j] = b[j - 1] + (mp[i][j] == 'x');
}
for (int j = k; j <= m; j++)
{
if (b[j] - b[j - k] == 0)
ans = min(ans, a[j] - a[j - k]);
}
}
for (int i = 1; i <= m; i++)
{
a[0] = 0, b[0] = 0;
for (int j = 1; j <= n; j++)
{
a[j] = a[j - 1] + (mp[j][i] == '.');
b[j] = b[j - 1] + (mp[j][i] == 'x');
}
for (int j = k; j <= n; j++)
{
if (b[j] - b[j - k] == 0)
ans = min(ans, a[j] - a[j - k]);
}
}
if (ans == 0x3f3f3f3f)
cout << -1;
else
cout << ans;
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}E
思路
经典老鼠喝药问题（筛选特例问题）
对输入的 \(N\) 求 \(N - 1\) 的二进制位数，位数即为需要的人数
将朋友排成一排，按编号喝对应二进制位为 \(1\) 的饮料，如：对于编号为 \(2\) 的朋友，他需要喝第 \(3\) 和第 \(6\) 杯，因为 \(3\) 的二进制数为 \(11\) ，\(6\) 的二进制数为 \(110\) 他们的第二位都是 \(1\) 。以此类推。需要注意的是，此时饮料的编号是从 \(0\) 开始的，因为 \(0\) 号饮料并不需要有人喝，但是题目中的饮料编号是从 \(1\) 开始的。
对于题目返回的一个 \(01\) 串 \(s\) ，我们将其转化为十进制即为坏掉的饮料的编号，此时的编号是从 \(0\) 开始的，题目的编号是从 \(1\) 开始的，所以需要 \(+1\)
Code
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
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
int m = 0, t = n - 1;
while (t)
{
m++;
t /= 2;
}
cout << m << endl;
vector<vector<int>> v(m + 1);
for (int i = 1; i < n; i++)
{
int p = 1, tmp = 1;
while (tmp < n)
{
if (i & tmp)
v[p].push_back(i);
p++;
tmp *= 2;
}
}
for (int i = 1; i <= m; i++)
{
cout << v[i].size() << " ";
for (auto j : v[i])
cout << j + 1 << " ";
cout << endl;
}
string s;
cin >> s;
int ans = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '1')
{
int tmp = 1;
for (int j = 0; j < i; j++)
{
tmp *= 2;
}
ans += tmp;
}
}
cout << ans + 1;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}AtCoder Beginner Contest 337
http://xiaowhang.github.io/archives/3994262799/