思路
因为是零和博弈，所以和是零，所以输出所有元素之和的负数即可
代码
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 namespace std;
void solve(){
int n;
cin >> n;
int sum = 0;
for(int i = 0; i < n - 1; i++){
int x;
cin >> x;
sum += x;
}
int ans = -sum;
cout << ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 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
| #include<bits/stdc++.h>
using namespace std;
void solve(){
string s;
cin >> s;
map<char, int> mp;
for(auto x: s){
mp[x]++;
}
vector<int> cnt(s.size() + 1, 0);
for(auto [key, value]: mp){
cnt[value]++;
}
for(auto x: cnt){
if(x != 0 && x != 2){
cout << "No";
return;
}
}
cout << "Yes";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
|
思路
首先将字符串T转为小写，然后贪心地去做。对于当前需要的字符，当然是越早出现越好，同时判断当字符串为2时，初始的T的结尾是否为x，或者判断是否已经选取到三个字符即可。
代码
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
| #include<bits/stdc++.h>
using namespace std;
void solve(){
string s, T;
cin >> s >> T;
transform(T.begin(), T.end(), T.begin(), ::tolower);
int ti = 0;
for(auto x: s){
if(x == T[ti]){
ti++;
if(ti == 3 || (ti == 2 && T.back() == 'x')){
cout << "Yes";
return;
}
}
}
cout << "No";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
|
思路
同样也是贪心的做。题目提示了次数最少的做法，所做的操作一定是相同的。
设当前的数字为$num$，那么一定有$num = 2^i * j, i,j \in N$，所以可以直接枚举$i$的值，直到$i$不合法，或者$num + 2^i > R$为止。之后不断更新$num = num + 2^i$，直到$num = R$即可。
代码
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
| #include<bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve(){
i64 L, R;
cin >> L >> R;
vector<array<i64,2>> ans;
i64 num = L;
while(num < R){
i64 step = 1;
i64 tmp = num;
while(tmp % 2 == 0 && num + step <= R){
step *= 2;
tmp /= 2;
}
if(num + step > R){
step /= 2;
}
i64 nxt = num + step;
ans.push_back({num, nxt});
num = nxt;
}
cout << ans.size() << "\n";
for(auto [l, r]: ans){
cout << l << " " << r << "\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
|
思路
VP的时候写完以为自己是错的，结果居然是对的，只是因为一个无伤大雅的错误让结果跑错了而已。
简单来说，就是搜索当前状态下，让对手随意下棋有哪些结果，如果对手的所有结果都能让自己赢，那么自己就是必赢的了，否则，只要有一种结果能让对手赢，那么对手一定会选择这种状态，所以自己当前的状态就会返回输的结果。
搜索的终止条件是当有人以井字棋的规则赢了，或者棋盘已经下满了，第二种情况下再判断一下谁的得分高即可。
有两版代码，一版是赛时代码，另一半是看了别人的实现后写的新的代码。
代码1
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include<bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve(){
i64 INF = 1e18;
const int n = 3;
vector<vector<i64>> grid(3, vector<i64>(3));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> grid[i][j];
}
}
vector<vector<i64>> status(n, vector<i64>(n, 0));
function<i64(int)> dfs = [&](int step){
vector<int> cnt(4, 0);
for(int i = 0; i < n; i++){
cnt[0] = cnt[1] = 0;
for(int j = 0; j < n; j++){
cnt[0] += status[i][j];
cnt[1] += status[j][i];
}
cnt[2] += status[i][i];
cnt[3] += status[i][n - 1 -i];
for(auto x: cnt){
if(x == 3){
return INF;
}
if(x == -3){
return -INF;
}
}
}
for(auto x: cnt){
if(x == 3){
return INF;
}
if(x == -3){
return -INF;
}
}
vector<i64> rets;
bool full = true;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(status[i][j] == 0){
full = false;
status[i][j] = (step % 2 == 0? 1: -1);
i64 res = dfs(step + 1);
rets.push_back(res);
status[i][j] = 0;
}
}
}
if(full){
i64 sum = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(status[i][j] == 1){
sum += grid[i][j];
}
}
}
return sum;
}
if(step % 2 == 0){
return *max_element(rets.begin(), rets.end());
}
else{
return *min_element(rets.begin(), rets.end());
}
};
i64 t_score = dfs(0);
i64 sum = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
sum += grid[i][j];
}
}
if(t_score > sum / 2){
cout << "Takahashi";
}
else{
cout << "Aoki";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
|
代码2
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int WHITE = 0;
const int RED = 1;
const int BLUE = -1;
const int n = 3;
void solve(){
vector<vector<i64>> score(n, vector<i64>(n));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> score[i][j];
}
}
vector status(n, vector<int>(n, WHITE));
auto win = [&](int color){
vector<int> cnt(4, 0);
for(int i = 0; i < n; i++){
cnt[0] = cnt[1] = 0;
for(int j = 0; j < n; j++){
cnt[0] += status[i][j] == color;
cnt[1] += status[j][i] == color;
}
if(cnt[0] == 3 || cnt[1] == 3){
return true;
}
cnt[2] += status[i][i] == color;
cnt[3] += status[i][n - 1 - i] == color;
}
if(cnt[2] == 3 || cnt[3] == 3){
return true;
}
return false;
};
auto check = [&](){
i64 score_blue = 0, score_red = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(status[i][j] == BLUE){
score_blue += score[i][j];
}
else if(status[i][j] == RED){
score_red += score[i][j];
}
}
}
return (score_blue > score_red? BLUE: RED);
};
function<int(int, int)> dfs = [&](int color, int step){
if(win(-color)){
return -color;
}
if(step == n * n){
return check();
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(status[i][j] == WHITE){
status[i][j] = color;
int res = dfs(-color, step + 1);
status[i][j] = WHITE;
if(res == color){
return color;
}
}
}
}
return -color;
};
cout << (dfs(RED, 0) == RED? "Takahashi": "Aoki");
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
|
