Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017

A：题意把“ogo”是连续x(x >= 0)个“go”的子串变成“***”,输出改变后的串

先搜到“ogo”然后再判断

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int MAXN = 200005;
 5 const int INF = 2e9;
 6 
 7 int main() {
 8 
 9     char s[105];
10     int n;
11     scanf("%d%s", &n, s);
12     for(int i = 0; i < n;){
13         if(s[i] == 'o' && s[i+1] == 'g' && s[i+2] == 'o'){
14             i += 3;
15             while(s[i] == 'g' && s[i+1] == 'o'){
16                 i += 2;
17             }
18             printf("***");
19         }else putchar(s[i++]);
20     }
21     return 0;
22 }

B：题意在一个舞台上n x m, 1代表演员，0代表空位子，你可以在一个空位子上放聚光灯，

聚光灯的放置方向有四种，问你有多少种方法，至少有一个演员在你放置聚光灯的方向上。

用四个数组分别储存前缀和，分别是从上到下，从下到上，从左到右，从右到左储存

然后枚举点，判断四个方向数组的前缀和是否大于0

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int MAXN = 1005;
 6 int a[MAXN][MAXN] = {};
 7 int righ[MAXN][MAXN] = {};
 8 int lef[MAXN][MAXN] = {};
 9 int up[MAXN][MAXN] = {};
10 int down[MAXN][MAXN] = {};
11 int n, m;
12 int per(int x, int y){
13     int cnt = 0;
14     if(down[x+1][y] > 0) cnt++;
15     if(up[x-1][y]> 0) cnt++;
16     if(righ[x][y-1] > 0) cnt++;
17     if(lef[x][y+1] > 0) cnt++;
18     return cnt;
19 }
20 int main()
21 {
22 
23     scanf("%d%d", &n, &m);
24     for(int i = 1; i <= n; i++){
25         for(int j = 1; j <= m; j++){
26             scanf("%d", &a[i][j]);
27         }
28     }
29     for(int i = 1; i <= n; i++){
30         for(int j = 1; j <= m; j++){
31             righ[i][j] = righ[i][j-1] + a[i][j];
32             up[i][j] = a[i][j] + up[i-1][j];
33         }
34     }
35     for(int j = m; j >= 1; j--){
36         for(int i = n; i >= 1; i--){
37             lef[i][j] = lef[i][j+1] + a[i][j];
38             down[i][j] = down[i+1][j] + a[i][j];
39         }
40     }
41     int sum = 0;
42     for(int i = 1; i <= n; i++){
43         for(int j = 1; j <= m; j++){
44             if(!a[i][j]){
45                 sum += per(i, j);
46             }
47         }
48     }
49     printf("%d
", sum);
50     return 0;
51 }

C：你需要在t时间内走完长度为s的路，到达电影院，这条路上有k个加油站

你需要租一辆汽车，去赶到电影院，这n辆汽车的油箱容纳量和价格也是不同，加油是不消耗时间和钱的

如果加速行驶，每1km消耗2单位的油，消耗1单位时间

如果平常速度，每1km消耗1单位的油，消耗2单位时间

问你最少需要租多少钱的汽车

二分需要消耗的汽油，找到最少需要多少油箱容纳量，然后枚举汽车，找到最低的价格

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int MAXN = 200005;
 5 const int INF = 2e9;
 6 struct car{
 7     int c, v;
 8 }s[MAXN];
 9 int g[MAXN];
10 
11 int n, k, ss, t;
12 
13 bool slove(int x){
14     int sum = 0;
15     for(int i = 1; i <= k+1; i++){
16         int len = g[i] - g[i-1];
17         if(2*len <= x){
18             sum += len;
19         }else if(len > x){
20         return false;
21         }else {
22             sum += (x - len) + 2*(2*len - x);
23         }
24     }
25     //printf(" %d %d
", x, sum);
26     if(sum <= t) return true;
27     return false;
28 }
29 
30 int main() {
31 
32     scanf("%d%d%d%d", &n, &k, &ss, &t);
33     for(int i = 0; i < n; i++) scanf("%d%d", &s[i].c, &s[i].v);
34 
35     for(int i = 1; i <= k; i++) scanf("%d", &g[i]);
36     g[0] = 0, g[k+1] = ss;
37     sort(g, g+k+1);
38     int l = 0, r = INF;
39     int cnt = 0;
40     while(l < r){
41         int mid = (l+r)>>1;
42         //printf("%d %d %d
",mid, l, r);
43         cnt++;
44         if(slove(mid)) r = mid;
45         else l = mid+1;
46         if(cnt > 100) break;
47     }
48     //if(slove(6)) printf("SDSDS
");
49     int res = INF;
50     for(int i = 0; i < n; i++){
51         if(s[i].v >= r) {
52             res = min(s[i].c, res);
53         }
54     }
55     if(res == INF) printf("-1
");
56     else printf("%d
", res);
57     return 0;
58 }

D:题意有一个1 x n 的“图”，图上有a艘长度为b的战舰，

有个人射了k发子弹没有打到战舰，这些打到的位置标记为1，0为未知区域

问你最少射几法，射哪几个位置才能至少射中一艘战舰

先计算出每段连续的0中最多能容纳几艘战舰，设其为x，根据鸽巢原理，最少要射x-a+1发子弹

如果你的运气差，你射了x-a次没有中，现在还有a个位置，那么随便射一发就会中

然后枚举出1的位置pos，射pos - b（= =猜的），直到不能容纳

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int MAXN = 200005;
 5 int que[MAXN];
 6 int sy[MAXN];
 7 int main() {
 8     int n, a, b, k;
 9     cin >>n >>  a >> b >> k;
10     string s;
11     cin >> s;
12 
13     int ans = 0;
14 
15     for(int i = 0; i < n; i++){
16         if(s[i] == '1') que[++ans] = (i+1);
17     }
18     que[0] = 0;
19 
20     que[++ans] = n+1;
21 
22     int sum = 0;
23 
24     for(int i = 1; i <= ans; i++){
25         int len = que[i] - que[i-1] - 1;
26         int num = len/b;
27         //printf("%d %d
", len, num);
28         sy[i] = num;
29         sum += num;
30     }
31     //printf("%d
", sum);
32     int res = sum - a + 1;
33 
34     printf("%d
", res);
35 
36     for(int i = 1; i <= ans && res > 0; i++){
37         while(sy[i] > 0 && res > 0){
38             sy[i]--;
39             res--;
40             que[i] -= b;
41             printf("%d%s", que[i], (res==0)?"
":" ");
42         }
43     }
44     return 0;
45 }

E ：一个公司中，去了经理以外，每个员工都有一个直接上司，这些人都有一个属于自己的id,

给你这个公司中经理的id s，以及这个公司每个人的上司数量，这个可能出点了错误

然后问你最少修改多少次能把它改为正常的

这个题很别扭，一句话讲不清。

大概方法就是用数组a储存上司数的数量
这个上司数必须是连续的一段 0 ~ m(m <= n-1)

也就是必须存在上司数为 0 1 2 3 4 ~ m的情况

如果有空缺必须补上，如果出现太多空缺，可以直接修改后面的

比如

8 1

0 1 1 2 3 3 7 7

你不会再补一个4、5、6吧，把两个7修改为m (m>= 1 || m <= 4)就很好了，只需要两步思路就是

枚举分割点，前部分补齐上司数a[i] = 0的情况，后部分直接修改

啰嗦这么多了

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int MAXN = 200005;
 5 int a[MAXN];
 6 int main() {
 7     int n, s, x, k = 0;
 8     scanf("%d%d", &n, &s);
 9     for(int i = 1; i <= n; i++) {
10         scanf("%d", &x);
11         if(i == s) {if(x) k++;}//1、如果经理的上司数不为0，当然要改
12         else a[x]++;
13     }
14     if(n == 1) return 0*printf("%d
", k);
15 
16     int mn = n, m = 0, c = 0;
17     for(int i = 1; i < n; i++){
18         m += a[i];
19         c += (a[i] == 0);
20         mn = min(mn, max(n-1-m, c));//把上司数 > i 改动, 把 上司数 <= i的， 都补一个
21     }
22     //printf("%d
", mn);
23     printf("%d
", mn+k);
24     return 0;
25 }