A. Red Versus Blue
思路
计算出最多可以分成几段，多余的 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
| #include<bits/stdc++.h>
void solve() {
int n,r,b;
std::cin >> n >> r >> b;
int x = r / (b + 1), y = r % (b + 1);
int pos = 1;
while(pos <= n) {
int t = 1;
while(pos <= n && t <= x) {
std::cout << "R";
pos++;
t++;
}
if(pos > n) break;
if(y) {
std::cout << "RB";
pos +=2;
y--;
}
else {
std::cout << "B";
pos ++;
}
}
std::cout << '\n';
}
int main() {
}
|
B. Bit Flipping
思路
将总次数分为奇数与偶数考虑
总次数为奇数时，每一个位置都会变号，如果选择一次，那么该位置不变号
总次数为偶数时，每个位置不变号，如果选择一次，那么该位置变号
从高位向低位依次判断
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>
void solve() {
int n,k;
std::cin >> n >> k;
std::string s;
std::cin >> s;
int len = s.length();
std::vector<int> f(n);
int pos = k;
for(int i = 0; i < len; i++) {
if(k & 1) {
if(s[i] == '1') {
if(pos) {
f[i] = 1;
pos--;
}
else s[i] = '0';
}
else {
s[i] = '1';
}
}
else {
if(s[i] == '0') {
if(pos) {
f[i] = 1;
s[i] = '1';
pos--;
}
}
}
}
if(pos) {
f[len - 1] += pos;
if(pos & 1) {
if(s[len - 1] == '1') s[len - 1] = '0';
else s[len - 1] = '1';
}
}
std::cout << s << '\n';
for(int x : f)
std::cout << x << ' ';
std::cout << '\n';
}
int main() {
}
|
C. Line Empire
思路
简单贪心，考虑相邻两个城堡之间路的代价
如果移动，那么代价为
如果不移动，那么代价为 ，即后面有多少个城堡经过这条路
取较小值
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>
void solve() {
int n,a,b;
std::cin >> n >> a >> b;
std::vector<int> x(n + 1);
for(int i = 1; i <= n; i++)
std::cin >> x[i];
long long sum = 0;
for(int i = 1; i <= n; i++)
sum += x[i];
long long ans = 0;
int pos = 0;
for(int i = 1; i <= n; i++) {
ans += 1ll * b * (x[i] - pos);
sum -= (x[i] - pos);
if(i == n) break;
if(sum * b >=
1ll * (sum - 1ll * (n - i) * (x[i] - pos)) * b
+ 1ll * a * (x[i] - pos)) {
ans += 1ll * a * (x[i] - pos);
pos = x[i];
}
}
std::cout << ans << '\n';
}
int main() {
}
|
D. Reverse Sort Sum
思路
想了一个小时没想出来。。。
裂开
根据输入，可以计算出一共有多少个 ，即 应该是什么样子的
从 往前推，考虑 中的最后一个 有没有可能是一直存在的，即考虑前 个回合，第 个点的贡献是不是等于
我们已知第 个点在 个回合中的总贡献为 ，把 轮中，第 个点的贡献去掉即可
区间减法使用差分的方式优化时间
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
| #include<bits/stdc++.h>
void solve() {
int n;
std::cin >> n;
std::vector<int> f(n + 1),g(n + 1);
std::vector<int> ans(n + 1);
long long sum = 0;
for(int i = 1; i <= n; i++)
std::cin >> f[i];
for(int i = 1; i <= n; i++) sum += f[i];
int k = sum / n,del = 0;
for(int i = n; i >= 1; i--) {
f[i] += del;
del = del + g[i];
if(k > 1) {
del--;
g[i - k + 1] ++;
}
if(f[i] == i) {
ans[i] = 1;
k--;
}
}
for(int i = 1; i <= n; i++)
std::cout << ans[i] << ' ';
std::cout << '\n';
}
int main() {
}
|
E. AND-MEX Walk
挖坑
F. Tree and Permutation Game
挖坑
总结 & 吐槽
Rating 变化：
表现分：
Rank:
题在一些奇怪的地方卡住了，样例二没看清楚， 了一次，花了十七分钟分钟
题 题比较显然，各花了十五分钟
题构造题没想出来，卡了一个小时
看群友说 比较显然，或许我应该跳过 ？
还得加练QAQ
