Loge编程生活头像
打卡信奥刷题(3704)用C++实现信奥题 P12505 「ROI 2025 Day2」充实的假期封面图

打卡信奥刷题(3704)用C++实现信奥题 P12505 「ROI 2025 Day2」充实的假期

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

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--