Codeforces Round #414 (Div. 1 + Div. 2)

Codeforces

Contests 链接：Codeforces Round #414 (Div. 1 + Div. 2)
过题数：2
排名：911/6157

A. Bank Robbery

题意

有 $n$ 个保险箱，第 $i$ 个保险箱内有 $x_i$ 的钱，一个小偷在位置 $a$，有两个保安在位置 $b$ 和 $c$，要求小偷不能走到保安的位置，且能够偷到的最多的钱。

数据范围

$1\leq n\leq10^5,1\leq b<a<c\leq10^9\\ 1\leq x_i\leq10^9$

题解

计算出 $\sum_{i=b+1}^{c-1}x_i$，就是结果。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n;
int a, b, c;
int l, r;
LL ans;
int num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &a, &b, &c) != EOF) {
        scanf("%d", &n);
        ans = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            if(num[i] > b && num[i] < c) {
                ++ans;
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

B. Cutting Carrot

题意

将一个高为 $h$ 的等腰三角形切成面积相等的 $n$ 段，输出 $n-1$ 个数字，表示每次切的位置。

数据范围

$2\leq n\leq1000,1\leq h\leq10^5$

题解

推出公式 $h_i=h\times \sqrt{\frac{i}{n}}$，输出结果。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n;
double h;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%lf", &n, &h) != EOF) {
        for(int i = 1; i < n; ++i) {
            if(i != 1) {
                printf(" ");
            }
            printf("%.10f", h * sqrt((double)i / n));
        }
        printf("\n");
    }
    return 0;
}

C. Naming Company

题意

$Oleg$ 和 $Igor$ 两人玩一个游戏，$Oleg$ 先开始，两个人各有一个长度为 $n$ 的字符串，最开始有一个长度为 $n$ 的只包含 $?$ 的字符串，两人轮流从自己的字符串中选一个字符替换其中的一个 $?$，$Oleg$ 想让这个结果字符的字典序最小，$Igor$ 想让这个字符的字典序最大，如果两人都采取最优策略，输出所有 $?$ 字符都被替换之后的字符串。

数据范围

$1\le n\leq3\times10^5$

题解

将 $Oleg$ 的字符串按从小到大排序，$Igor$ 的字符串从大到小排序，如果 $Oleg$ 最小的字符小于 $Igor$ 最大的字符，就将这个最小的字符替换最前面的问号，如果 $Oleg$ 最小的字符大于等于 $Igor$ 最大的字符，就从后面往前面放，但是仍然要使字典序最小，所以他会先放自己最后要放下的，最大的字符。$Igor$ 就与 $Oleg$ 相反。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 3000000 + 100;
int n;
char str1[maxn], str2[maxn];
char ans[maxn];
bool cmp(const char &a, const char &b) {
    return a > b;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%s%s", str1, str2) != EOF) {
        int n = strlen(str1);
        sort(str1, str1 + n);
        sort(str2, str2 + n, cmp);
        int who = 1;
        int cnt = n;
        int l = 0;
        int r = n - 1;
        int l2 = 0, r2 = n / 2;
        int l1 = 0, r1 = n - r2;
        --r1;
        --r2;
        memset(ans, 0, sizeof(ans));
        while(cnt != 0) {
            if(who == 1) {
                if(str1[l1] < str2[l2]) {
                    ans[l++] = str1[l1++];
                } else {
                    ans[r--] = str1[r1--];
                }
            } else {
                if(str2[l2] > str1[l1]) {
                    ans[l++] = str2[l2++];
                } else {
                    ans[r--] = str2[r2--];
                }
            }
            who = 3 - who;
            --cnt;
        }
        printf("%s\n", ans);
    }
    return 0;
}