Codeforces Round #748 (Div. 3) 题解
A. Elections
题意
已知竞选中三个候选人的当前得票数
a
,
b
,
c
a,b,c
a,b,c，现在可以增加任何一个人的得票数，要求对于每个人，计算出能使得其得票数大于其余两人的最少增加票数。
思路
按照题意计算即可，假如要使得
a
a
a的票数最高，只需让
a
a
a加上
b
,
c
b,c
b,c中票数较高的人与
a
a
a的票数只差，再加上1即可。需要注意的是，如果某个人的得票数已经大于其余两人，应当输出0，而不是负数。
时间复杂度
O
(
1
)
O(1)
O(1)
AC代码
| Problem | Lang | Verdict | Time | Memory |
|---|
| A - Elections | GNU C++17 | Accepted | 15 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
void solve() {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
printf("%d %d %d\n", a > max(b, c) ? 0 : max(b, c) + 1 - a,
b > max(a, c) ? 0 : max(a, c) + 1 - b,
c > max(a, b) ? 0 : max(a, b) + 1 - c);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
B. Make it Divisible by 25
题意
给定一个十进制正整数，每次可以删除其中的任何一位，如果操作后会产生前导0，则会自动去除前导0。问至少删除多少位后，该数不i变成一个能被25整除的正整数。
思路
被25整除的正整数最大的特点是：十位和个位只有4种情况，即00、25、50、75。因此只需从后往前找，对于每种情况，找到第一个匹配的位置即可。
时间复杂度
O
(
n
)
O(n)
O(n)
AC代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
char s[22];
scanf("%s", s);
int n = strlen(s);
int a, b, p1, p2;
p1 = p2 = -1;
for (int i = n - 1; i >= 0; --i) {
if (p1 == -1 && s[i] == '5') {
p1 = i;
continue;
}
if (p1 != -1 && (s[i] == '2' || s[i] == '7')) {
p2 = i;
break;
}
}
a = n - 1 - p2 - 1;
p1 = p2 = -1;
for (int i = n - 1; i >= 0; --i) {
if (p1 == -1 && s[i] == '0') {
p1 = i;
continue;
}
if (p1 != -1 && (s[i] == '0' || s[i] == '5')) {
p2 = i;
break;
}
}
b = n - 1 - p2 - 1;
printf("%d\n", min(a, b));
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
C. Save More Mice
题意
在一个坐标轴上，有很多个老鼠，一只猫和一个洞，猫的起始位置是0，洞的位置是
n
n
n，所有老鼠的起始位置在0和
n
n
n之间，同一个位置可以有多个老鼠。每一个时刻，你可以将一个老鼠向右移动一个单位（坐标值+1），随后猫将向右移动一个单位，并吃掉这个位置上的所有老鼠。如果老鼠移动到了洞里，就不会再移动，也不会被吃掉。问最多能有多少个老鼠存活。
思路
在任何一个时刻，被选中的老鼠一定存活。在
n
n
n个时刻后，猫会吃掉所有能吃掉的老鼠。因此，我们只需尽可能多的将老鼠移动到洞里。采取贪心策略，排序后选择离洞最近的尽可能多的老鼠，使得它们与洞的距离之和小于
n
n
n。
时间复杂度
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2?n)
AC代码
#include <bits/stdc++.h>
using namespace std;
int a[400005];
void solve() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < k; ++i) {
scanf("%d", &a[i]);
}
sort(a, a + k, greater<int>());
int ans = 0, s = n;
for (int i = 0; i < k; ++i) {
if (s > n - a[i]) ++ans, s -= n - a[i];
else break;
}
printf("%d\n", ans);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
D1. All are Same
题意
给出一个序列，要求选定一个正整数
k
k
k，每次操作可以选择序列中的任何一个元素，并将其减少
k
k
k，这一操作可以进行任意次数。要求在经过若干操作之后，序列中的每一个元素都相等，求最大的可能的
k
k
k，若
k
k
k可以取任意大的值，输出-1。
思路
首先我们可以发现，当序列元素在初始状态下就已经相等时，
k
k
k可以任意大。
对于存在不同值的序列，在若干次操作后，序列中的元素一定可以变成序列最小值。
证明：设最终相等的值为
x
x
x，序列最小值为
m
m
m：若
x
>
m
x>m
x>m，由于
k
>
0
k>0
k>0，序列元素只减不增，则一定存在一项
m
′
≤
m
m'\le m
m′≤m，一定不能满足
m
′
=
x
m'=x
m′=x；若
x
<
m
x<m
x<m，则一定有
x
=
m
?
n
?
k
,
n
∈
N
?
x=m-n\cdot k,n\in N^*
x=m?n?k,n∈N?，因此取
x
′
=
m
x'=m
x′=m同样符合题意。
对于任意序列元素
a
i
=?
m
a_i\not=m
ai??=m，当满足
k
∣
(
a
i
?
m
)
k|(a_i-m)
k∣(ai??m)（|表示整除）时，可以经过若干次操作使
a
i
a_i
ai?变为
m
m
m。为了求出满足所所有序列元素的最大
k
k
k值，我们只要求出
a
i
?
m
a_i-m
ai??m的最大公因数即可。求最大公因数（gcd）可以手写欧几里得算法，也可以直接调用C++库函数__gcd(x,y)，该函数在<algorithm>头文件中。
时间复杂度
O
(
n
l
o
g
2
a
i
)
O(nlog_2a_i)
O(nlog2?ai?)
AC代码
#include <bits/stdc++.h>
using namespace std;
int a[100];
void solve() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
int minm = a[0], maxm = a[0];
for (int i = 1; i < n; ++i) {
minm = min(minm, a[i]);
maxm = max(maxm, a[i]);
}
if (minm == maxm) {
puts("-1");
return;
}
int ans = maxm - minm;
for (int i = 0; i < n; ++i) {
if (a[i] != minm) ans = __gcd(ans, a[i] - minm);
}
printf("%d\n", ans);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
D2. Half of Same
题意
给出一个序列，要求选定一个正整数
k
k
k，每次操作可以选择序列中的任何一个元素，并将其减少
k
k
k，这一操作可以进行任意次数。要求在经过若干操作之后，序列中的至少一半的元素相等，求最大的可能的
k
k
k，若
k
k
k可以取任意大的值，输出-1。
思路
这题和上一题的大致思路是相似的，但是难度大很多。观察发现序列长度
n
n
n的范围只有40，考虑枚举操作结束后相等元素的值（也就是枚举相当于上一题中最小值的那个元素），设计状态
d
p
[
i
]
dp[i]
dp[i]，表示在最终有
i
i
i个相等的数的情况下，可能的最大公因数值的集合，随后找出
i
≥
n
2
i\ge \frac{n}{2}
i≥2n?时的最大值。
时间复杂度
O
(
n
4
l
o
g
2
a
i
)
/
O
(
n
4
l
o
g
2
n
l
o
g
2
a
i
)
O(n^4log_2a_i)/O(n^4log_2nlog_2a_i)
O(n4log2?ai?)/O(n4log2?nlog2?ai?)
AC代码
#include <bits/stdc++.h>
using namespace std;
int a[100];
set<int> dp[100];
map<int, int> mp;
void solve() {
mp.clear();
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
++mp[a[i]];
}
for (auto &it: mp) {
if (it.second >= n / 2) {
puts("-1");
return;
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) dp[j].clear();
int num = 0;
for (int j = 0; j < n; ++j) if (a[j] == a[i]) ++num;
for (int j = 0; j < n; ++j) {
if (a[j] > a[i]) {
for (int k = n - 1; k > 0; --k) {
for (int l: dp[k]) {
dp[k + 1].insert(__gcd(l, a[j] - a[i]));
}
}
dp[1].insert(a[j] - a[i]);
}
}
for (int j = n / 2 - num; j <= n; ++j) {
if (!dp[j].empty()) ans = max(ans, *--dp[j].end());
}
}
printf("%d\n", ans);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
E. Gardener and Tree
题意
给出一棵树，每次操作删除树上的所有叶子节点，问经过
k
k
k次操作后，还剩多少节点。（树是无根树，空树经过操作后还是空树）
关于树和叶子节点，以及下面提到的度的概念，不理解者请自行找资料解决，在此不做说明。
思路
我们维护树上所有节点的度数，除了仅有一个节点的树以外，当且仅当节点的度数为1时，该节点是叶子节点。考虑类似拓扑排序的方法，使用bfs解决本题。初状态下将所有1度节点加入队列，然后处理队列中的所有节点，删除与之相连的边（只有一条），并检查与之相连的另一节点在删边后的度数，如果删边后该节点变为1度节点，则新增叶子节点，加入队列。另外需要记录节点的bfs层数，由于只操作
k
k
k次，当bfs层数达到
k
k
k后，就不需要再进行操作。
题目坑点：只有1个节点的情况需要特判！
时间复杂度
O
(
n
)
O(n)
O(n)
AC代码
#include <bits/stdc++.h>
using namespace std;
vector<int> g[400005];
int vis[400005], in[400005];
void solve() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) g[i].clear();
memset(vis, 0, (n + 5) << 2);
memset(in, 0, (n + 5) << 2);
int x, y;
for (int i = 0; i < n - 1; ++i) {
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
queue<int> q;
int ans = 0;
for (int i = 1; i <= n; ++i) {
in[i] = g[i].size();
if (in[i] <= 1) {
vis[i] = 1;
++ans;
q.push(i);
}
}
while (!q.empty()) {
int p = q.front();
q.pop();
if (vis[p] >= k) continue;
for (int i: g[p]) {
if (!vis[i]) {
--in[i];
if (in[i] == 1) {
vis[i] = vis[p] + 1;
++ans;
q.push(i);
}
}
}
}
printf("%d\n", n - ans);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
F. Red-Black Number
题意
给出一个位数为
n
n
n的十进制非负整数
x
x
x（可能有前导0），另给两个正整数
A
A
A和
B
B
B，要求将
x
x
x的每一位涂成红色或黑色，每种颜色都至少有一位数字，使得同种颜色的数字按原本顺序组合后，红色数字组成的数能被
A
A
A整除，黑色数字组成的数能被
B
B
B整除。答案输出使得红色数字个数与黑色数字个数最接近的一种涂色方式，若有多个答案可以输出任意一个，若无解，输出-1。
思路
观察发现
n
,
A
,
B
n,A,B
n,A,B的范围均只有40，考虑
n
4
n^4
n4的四维dp。设计状态
d
p
[
i
]
[
j
]
[
k
]
[
l
]
dp[i][j][k][l]
dp[i][j][k][l]：对于前
i
i
i个数字，红色数字组成的数模
A
A
A得
j
j
j，黑色数字组成的数模
B
B
B得
k
k
k，其中红色数字有
l
l
l个。初始状态为
d
p
[
0
]
[
0
]
[
0
]
[
0
]
dp[0][0][0][0]
dp[0][0][0][0]。
递推时，将
i
i
i进行迭代，每次迭代枚举每一个有效的
j
,
k
,
l
j,k,l
j,k,l，并枚举这一位涂的颜色（红或黑），记录操作（涂的颜色）以及来源路径（上一层中的位置），详见代码
完成递推后，枚举红色数字个数与黑色数字个数之差的绝对值，若存在有效状态
d
p
[
n
]
[
0
]
[
0
]
[
l
]
dp[n][0][0][l]
dp[n][0][0][l]，则说明该情况成立，通过前序dfs回溯路径，输出答案。
时间复杂度
O
(
n
4
)
O(n^4)
O(n4)
AC代码
#include <bits/stdc++.h>
using namespace std;
int x[50];
pair<int, int> dp[41][41][41][41];
int n, a, b;
void display(int i, int j, int k, int l) {
if (!i) return;
if (dp[i][j][k][l].first) display(i - 1, dp[i][j][k][l].second, k, l - 1);
else display(i - 1, j, dp[i][j][k][l].second, l);
printf("%c", dp[i][j][k][l].first ? 'R' : 'B');
}
void solve() {
scanf("%d%d%d", &n, &a, &b);
for (int i = 0; i < n; ++i) scanf("%1d", &x[i]);
memset(dp, -1, sizeof dp);
dp[0][0][0][0].first = -2;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < a; ++j) {
for (int k = 0; k < b; ++k) {
for (int l = 0; l <= i; ++l) {
if (dp[i][j][k][l].first != -1) {
if (dp[i + 1][(j * 10 + x[i]) % a][k][l + 1].first == -1)
dp[i + 1][(j * 10 + x[i]) % a][k][l + 1] = make_pair(1, j);
if (dp[i + 1][j][(k * 10 + x[i]) % b][l].first == -1)
dp[i + 1][j][(k * 10 + x[i]) % b][l] = make_pair(0, k);
}
}
}
}
}
for (int i = 0; i <= n / 2; ++i) {
if (n / 2 + i < n) {
if (dp[n][0][0][n / 2 + i].first != -1) {
display(n, 0, 0, n / 2 + i);
puts("");
return;
}
}
if (n / 2 - i > 0) {
if (dp[n][0][0][n / 2 - i].first != -1) {
display(n, 0, 0, n / 2 - i);
puts("");
return;
}
}
}
printf("-1\n");
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
G. Changing Brackets
题意
给出一个字符串
s
s
s，仅由字符’(’,’)’,’[’,’]‘组成，允许以0的代价翻转括号（也就是’(‘和’)‘互换，’[‘和’]'互换），允许以1的代价将任何形式的圆括号变成方括号，但不允许将方括号变成圆括号。
q
q
q次询问，每次询问，求对于给定的正整数
l
,
r
l,r
l,r，将子串
s
[
l
.
.
r
]
s[l..r]
s[l..r]转换为正则括号序列（括号完全匹配）的最小代价。
思路
Idea by REXWind
首先给出结论：统计奇数位置和偶数位置上方括号的个数，当且仅当子串中奇数位置的方括号数等于偶数位置的方括号数时，序列可以形成正则括号序列。
不难发现，括号的方向不影响答案（因为代价是0）。由于圆括号可以变成方括号，所以对答案造成影响的应当是方括号的位置和数量，圆括号根据方括号的需求进行变换。
假设有两个方括号，都位于奇数位置上（或都位于偶数位置上），那么这两个方括号之间的括号序列不可能形成正则序列。
证明：两个方括号之间的这段序列的长度是奇数，因此方括号和圆括号的个数中一定有一个是奇数，奇数个括号不可能完成匹配。
假设有两对方括号，其中两个在奇数位置，两个在偶数位置：
- 如果是嵌套关系（例如方括号位置是
1
,
5
,
8
,
10
1,5,8,10
1,5,8,10），如果仅考虑内层两个方括号之间的序列（
s
[
5..8
]
s[5..8]
s[5..8]），若该序列是正则序列，则整个序列也是正则序列（因为内外层之间的圆括号数（
s
[
2..4
]
+
s
[
9..9
]
s[2..4]+s[9..9]
s[2..4]+s[9..9]）是偶数，且中间没有插入单独的方括号，一定可以完成匹配）；
- 如果是并列关系（例如方括号位置是
1
,
4
,
7
,
12
1,4,7,12
1,4,7,12），如果两对方括号之内的序列（
s
[
1..4
]
s[1..4]
s[1..4]和
s
[
7..12
]
s[7..12]
s[7..12]）是正则序列，则整个序列也是正则序列（因为两个正则序列之间的圆括号数（
s
[
5..6
]
s[5..6]
s[5..6]）是偶数，且中间没有插入单独的方括号，一定可以完成匹配）。
使用归纳法可证，如果一个序列中奇数位置的方括号数和偶数位置的圆括号数相等，则序列是正则序列。
回到询问，暴力统计子序列中的奇数和偶数位置方括号数显然不可取，前缀和优化之。
每次询问，对前缀和作差，求出奇偶位置的方括号数，作差取绝对值，即是答案。
时间复杂度
O
(
n
+
q
)
O(n+q)
O(n+q)
AC代码
#include <bits/stdc++.h>
using namespace std;
char s[1000005];
int a[2][1000005];
void solve() {
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
if (s[i] == '[' || s[i] == ']') a[i & 1][i] = a[i & 1][i - 1] + 1;
else a[i & 1][i] = a[i & 1][i - 1];
a[i & 1 ^ 1][i] = a[i & 1 ^ 1][i - 1];
}
int q;
scanf("%d", &q);
while (q--) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", abs((a[0][r] - a[0][l - 1]) - (a[1][r] - a[1][l - 1])));
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
后记
本FW又双叒叕AK失败了呜呜呜。。
|