首页 > 代码库 > Codeforces Round #409 (Div. 2)

Codeforces Round #409 (Div. 2)

2024-09-15 14:27:45   219人阅读

这是一次血崩的cf，脑子不好使了。读题读错...代码写错...查不出错...WAWAWA

这次题比较常规。前二题很简单，第三题二分，第四题数学。

 

A - Vicious Keyboard【暴力模拟】

题意：

改变最多一个字符，让字符串中出现最多的"VK"。

PS：

比赛时做法是先走一遍字符串找"VK“，标记已经构成"VK"的位置。再跑一遍字符串，

如果出现a[i]和a[i-1]都没标记过，而且a[i-1]==‘V‘ 或a[i]==‘K‘时，结果＋1并跳出循环。

结果 || 写成了&&，WA了，然后坚信C可做，就放弃检查了...

做法：

字符串长最多是100，直接O(n2)暴力最保险最容易写。

版本1：
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>
#define pii pair<int,int>
#define MEM(a,b) memset(a, b, sizeof(a))
#define ll long long
const double pi = acos(-1.0);
using namespace std;
int main() {
    string a;
    cin >> a;
    int len = a.size();
    bool flag = true;
    bool f[1000];
    memset(f, false, sizeof(f));
    int ans = 0;
    for(int i = 1; i < a.size(); i++) {
        if(a[i] == ‘K‘ && a[i-1] == ‘V‘) {
            ans++;
            f[i] = f[i-1] = true;
        }
    }
    for(int i = 1; i < a.size(); i++) {
        if(f[i] == true || f[i-1] == true) continue;
        if(a[i] == ‘K‘ || a[i-1] == ‘V‘) {
            ans++;
            break;
        }
    }
    cout << ans << endl;
}

 版本2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define pii pair<int,int>
#define MEM(a,b) memset(a, b, sizeof(a))
#define ll long long
const double pi = acos(-1.0);
using namespace std;
int solve(string a) {
    int ans = 0;
    for(int i = 1; i < a.size(); i++) {
        if(a[i] == ‘K‘ && a[i-1] == ‘V‘) ans++;
    }
    return ans;
}
int main() {
    string a;
    cin >> a;
    int ans = solve(a);
    for(int i = 0; i < a.size(); i++) {
        if(a[i] == ‘V‘) a[i] = ‘K‘; else a[i] = ‘V‘;  //改变一个字符
        ans = max(ans, solve(a));
        if(a[i] == ‘V‘) a[i] = ‘K‘; else a[i] = ‘V‘;  //改回来
    }
    cout << ans << endl;
}

 

B - Valued Keys【模拟】

题意：

a, b, c三个字符串等长， c = f(a,b) 。

函数的意义是取a, b对应字符的最小值 ( 即 c[i] = min ( a[i], b[i] )。

给你a和c，让你构造一个可行b，如果不存在输出-1。

做法:

两种情况:

1.存在则输出c，因为f(a,c)一定等于c

2.若不存在，即存在任意一个c[i] > a[i]，则输出-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main() {
    string a, b;
    cin >> a >> b;
    for(int i = 0; i < a.size(); i++) {
        if(b[i] > a[i]) {
            puts("-1");
            return 0;
        }
    }
    cout << b << endl;
}

 

C - Voltage Keepsake【二分求最大化结果】

 题意：

给你N个设备和1个充电器。充电器每单位时间可以冲p份电量。接下来给你N个设备每单位时间的耗电量和初始电量。

所有设备都要保持有电，问你怎么充电使得设备维持时间最长，如果可以无限使用，输出-1。

做法:

二分时间。根据judge算出每个设备维持mid时间的话，至少需要充多少电。

根据等式 y + t * p = mid * x 累加 t 值， 如果 t 值大于 mid 值说明充电时间不够，返回false。

如果最终结果超过1e17，说明无限长。

也能通过计算来判断是否无限长，累加所有设备的耗电量sum，如果 sum <= p，说明可以无限使用。

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
#include <bits/stdc++.h>
#define pii pair<int,int>
#define MEM(a,b) memset(a, b, sizeof(a))
#define ll long long
const double pi = acos(-1.0);
const double eps = 1e-9;
using namespace std;
struct Node {
    double x, y;
}node[100100];
int n;
double p;
bool judge(double mid) {
    double ans = 0;
    for(int i = 0; i < n; i++) {
        if(mid * node[i].x < node[i].y) continue;  // y > mid * x 说明不用充电
        double tp = (mid * node[i].x - node[i].y) / p; // y + t * p = mid * x  根据这个等式累加t
        ans += tp;
        if(ans > mid) return false;
    }
    return true;
}
int main() {
    scanf("%d%lf", &n, &p);
    for(int i = 0; i < n; i++) {
        scanf("%lf%lf",&node[i].x, &node[i].y);
    }
    double mid;
    double low = 0, high = 1e18; //注意极值
    for(int i = 0; i < 100; i++) {  //二分100次
        mid = (low + high) / 2;
        if(judge(mid)) low = mid;
        else high = mid;
    }
    if(mid > 1e17) puts("-1");
    else printf("%.10f\n", mid);
}

Codeforces Round #409 (Div. 2)


联系
我们