P12505 「ROI 2025 Day2」充实的假期
题目描述
译自 ROI 2025 Day2 T1. Качественный отдых
小明正在一家 IT 公司进行为期 n n n 天的实习,担任技术支持的角色。他的实习日程安排颇为复杂,工作日和休息日交织在一起。除了固定的休息日,小明还有一些调休日——他可以选择在任意工作日额外休息一天。
不过,小明觉得单独一天的休息远远不够,只有连续两天或以上的休息日才能让他真正放松,称之为充实休假日。
你会收到 q q q 个关于调休日数量的询问,每个询问对应一个不同的调休天数。你的任务是根据小明的实习日程,计算出在每种调休天数下,小明最多能获得多少个充实休假日。
输入格式
第一行包含两个整数 n n n 和 q q q ( 1 ≤ n ≤ 100 000 , 1 ≤ q ≤ n + 1 ) (1 \le n \le 100\,000, 1 \le q \le n+1) (1≤n≤100000,1≤q≤n+1),分别表示实习天数和询问数量。
第二行包含一个长度为
n
n
n 的字符串
s
s
s,由字符 0 和 1 组成,表示实习日程。其中,0 表示工作日,1 表示休息日。
接下来的 q q q 行,每行包含一个整数 k i k_i ki ( 0 ≤ k i ≤ n ) (0 \leq k_i \leq n) (0≤ki≤n),表示第 i i i 个询问中可用的调休天数。保证每个 k i k_i ki 不超过日程中的工作日总数。
输出格式
输出 q q q 个整数,分别表示在每个 k i k_i ki 调休天数下,小明通过选择 k i k_i ki 个额外休息日,最多能获得的充实休假日数量。
输入输出样例 #1
输入 #1
3 4
000
0
1
2
3
输出 #1
0
0
2
3
输入输出样例 #2
输入 #2
4 3
1010
0
1
2
输出 #2
0
3
4
输入输出样例 #3
输入 #3
11 6
11010101001
5
2
0
1
4
3
输出 #3
11
7
2
5
10
9
说明/提示
样例解释 1
在第一个样例中,实习的 3 3 3 天全是工作日。如果调休少于 2 2 2 天,无法获得充实休假日。对于 k 3 = 2 k_3 = 2 k3=2 或 k 4 = 3 k_4 = 3 k4=3,可以选择前 k j k_j kj 天作为调休日,这些天都将成为充实休假日。
样例解释 2
在第二个样例中,最优策略是将调休日安排在第二天,这样前三天都将成为充实休假日。
详细子任务附加限制及分值如下表所示。其中子任务 0 0 0 是样例。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 0 0 0 | 0 0 0 | 样例 |
| 1 1 1 | 6 6 6 | 所有日程均为工作日 |
| 2 2 2 | 11 11 11 | 工作日与休息日交替,首日为休息日 |
| 3 3 3 | 12 12 12 | q = 1 q = 1 q=1, k 1 = 0 k_1 = 0 k1=0 |
| 4 4 4 | 19 19 19 | q = 1 q = 1 q=1, k 1 = 1 k_1 = 1 k1=1 |
| 5 5 5 | 11 11 11 | n ≤ 15 n \le 15 n≤15 |
| 6 6 6 | 17 17 17 | n ≤ 1000 n \le 1000 n≤1000 |
| 7 7 7 | 13 13 13 | 日程中无连续休息日 |
| 8 8 8 | 11 11 11 | 无附加限制 |
C++实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, a[N], q, ans[N], pos[N], cnt, cnt_0, add_2, add_3;
vector<int> que[N];
string s;
signed main(void) {
cin >> n >> q >> s; s = " " + s;
for (int i = 1; i <= q; i ++ ) {
int k; cin >> k;
que[k].push_back(i);
}
int res = 0;
for (int i = 1; i <= n; i ++ ) {
if (s[i] == '1') {
int j = i;
while (j < n && s[j + 1] == '1')
j ++ ;
if (j - i + 1 >= 2)
res += j - i + 1;
else if (j == i)
pos[++ cnt] = i;
i = j;
} else cnt_0 ++ ;
}
for (int i = 1; i <= cnt; i ++ ) {
if (pos[i] == pos[i + 1] - 2)
add_3 ++ , i ++ ;
else if (s[pos[i] + 1] != '1' && s[pos[i] - 1] != '1')
add_2 ++ ;
}
for (auto it : que[0]) ans[it] = res;
for (int i = 1; i <= cnt_0; i ++ ) {
if (add_3) add_3 -- , res += 3;
else if (add_2) add_2 -- , res += 2;
else res += 1;
for (auto it : que[i]) ans[it] = res;
if (cnt_0 == n && i == 1) for (auto it : que[i]) ans[it] = 0;
}
for (int i = cnt_0 + 1; i <= n; i ++ )
for (auto it : que[i]) ans[it] = res;
for (int i = 1; i <= q; i ++ ) cout << ans[i] << '\n';
return 0;
}

后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现,记录日常的编程生活、比赛心得,感兴趣的请关注,我后续将继续分享相关内容
转载自 CSDN-专业IT技术社区
原文链接:https://blog.csdn.net/rogeliu/article/details/171080347




