CF1398B-Substring Removal Game
题目:
题目描述:
Alice and Bob play a game. They have a binary string $ s $ (a string such that each character in it is either $ 0 $ or $ 1 $ ). Alice moves first, then Bob, then Alice again, and so on.
During their move, the player can choose any number (not less than one) of consecutive equal characters in $ s $ and delete them.
For example, if the string is $ 10110 $ , there are $ 6 $ possible moves (deleted characters are bold):
- $ \textbf{1}0110 \to 0110 $ ;
- $ 1\textbf{0}110 \to 1110 $ ;
- $ 10\textbf{1}10 \to 1010 $ ;
- $ 101\textbf{1}0 \to 1010 $ ;
- $ 10\textbf{11}0 \to 100 $ ;
- $ 1011\textbf{0} \to 1011 $ .
After the characters are removed, the characters to the left and to the right of the removed block become adjacent. I. e. the following sequence of moves is valid: $ 10\textbf{11}0 \to 1\textbf{00} \to 1 $ .
The game ends when the string becomes empty, and the score of each player is the number of $ 1 $ -characters deleted by them.
Each player wants to maximize their score. Calculate the resulting score of Alice.
输入格式:
The first line contains one integer $ T $ ( $ 1 \le T \le 500 $ ) — the number of test cases.
Each test case contains exactly one line containing a binary string $ s $ ( $ 1 \le |s| \le 100 $ ).
输出格式:
For each test case, print one integer — the resulting score of Alice (the number of $ 1 $ -characters deleted by her).
样例:
样例输入 1:
1
2
3
4
5
6
| 5
01111001
0000
111111
101010101
011011110111
|
样例输出 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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
| /*
*User: ybw051114
*Time: 2020.08.14 22:35:09
*/
#include <bits/stdc++.h>
using namespace std;
#ifndef use_ios11
#define use_ios11
using namespace std;
struct ins
{
int ans;
ins() { ans = 1; }
#define endl '\n'
void read()
{
}
void read1(char &s)
{
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
s = c;
if (c == EOF)
ans = 0;
}
void read1(string &s)
{
s = "";
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
s += c;
if (c == EOF)
ans = 0;
}
template <typename T>
void read1(T &n)
{
T x = 0;
int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-')
f = -1;
if (c == EOF)
{
ans = 0;
return;
}
}
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
n = x * f;
if (c == EOF)
ans = 0;
if (c != '.')
return;
T l = 0.1;
while ((c = getchar()) <= '9' && c >= '0')
x = x + (c & 15) * l, l *= 0.1;
n = x * f;
if (c == EOF)
ans = 0;
}
void write() {}
void write1(string s)
{
int n = s.size();
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(const char *s)
{
int n = strlen(s);
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(char s) { putchar(s); }
void write1(float s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%df", x);
printf(y, s);
}
void write1(double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dlf", x);
printf(y, s);
}
void write1(long double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dLf", x);
printf(y, s);
}
template <typename T>
void write1(T n)
{
if (n < 0)
n = -n, putchar('-');
if (n > 9)
write1(n / 10);
putchar('0' + n % 10);
}
template <typename T>
friend ins operator>>(ins x, T &n);
template <typename T>
friend ins operator<<(ins x, T n);
operator bool() { return ans; }
};
template <typename T>
ins operator>>(ins x, T &n)
{
if (!x.ans)
return x;
x.read1(n);
return x;
}
template <typename T>
ins operator<<(ins x, T n)
{
x.write1(n);
return x;
}
ins yin;
ins yout;
#endif
int a[10001];
int main()
{
int TTT;
yin >> TTT;
while (TTT--)
{
string s;
yin >> s;
int tot, sum;
tot = sum = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '0')
{
if (sum)
a[++tot] = sum;
sum = 0;
}
else
sum++;
}
if (sum)
a[++tot] = sum;
sort(a + 1, a + tot + 1);
int ans = 0;
for (int i = tot; i >= 1; i -= 2)
ans += a[i];
yout << ans << endl;
}
return 0;
}
|