Codeforces Round #402 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #402 (Div. 2)
过题数：4
排名：802/10360

A. Pupils Redistribution

题意

有两个班级的同学，每个班 $n$ 名同学，所有同学被分为 $5$ 个学术等级，但是这 $5$ 个等级的人数在两个班并不平均，在 $A$ 班中第 $i$ 个同学的等级为 $a_i$，$B$ 班中第 $i$ 个同学的等级为 $b_i$，校长想要通过交换使得同一个等级的同学在两个班的人数相等，如果可以，则输出最少的交换次数，否则输出 $-1$。

数据范围

$1\leq n\leq100\\1\leq a_i,b_i\leq5$

题解

统计 $a_i$ 和 $b_i$ 中 $1$ ~ $5$ 的数字个数，如果为存在一个数字个数为奇数，则输出 $-1$，否则输出交换次数。

过题代码

#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 = 220;
int n;
bool flag;
int a[maxn], b[maxn];
int num[maxn], numa[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", &n) != EOF) {
        int ans = 0;
        flag = true;
        memset(num, 0, sizeof(num));
        memset(numa, 0, sizeof(numa));
        for(int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            ++num[a[i]];
            ++numa[a[i]];
        }
        for(int i = 0; i < n; ++i) {
            scanf("%d", &b[i]);
            ++num[b[i]];
        }
        for(int i = 1; i <= 5; ++i) {
            if(num[i] % 2 != 0) {
                flag = false;
                break;
            }
            ans += abs(num[i] / 2 - numa[i]);
        }
        if(!flag) {
            printf("-1\n");
            continue;
        }
        printf("%d\n", ans / 2);
    }
    return 0;
}

B. Weird Rounding

题意

给定两个整数 $n$ 和 $k$，判断能否通过删掉 $n$ 中的某些位上的数字，使得 $n$ 没有前导零且能够被 $10^k$ 整除，题目保证数据有解。

数据范围

$0\le n\leq2\times10^9,1\leq k\leq9$

题解

从低位到高位统计在 $k$ 个 $0$ 之前存在多少个非零数字，如果数字中 $0$ 的个数少于 $k$ 个，则需要删掉 $n-1$ 个数字，使得 $n$ 变为 $0$。

过题代码

#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 k, ans;
char str[100];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%s%d", str, &k) != EOF) {
        ans = 0;
        int cnt = 0;
        int len = strlen(str);
        for(int i = len - 1; i >= 0; --i) {
            if(str[i] == '0') {
                ++cnt;
            } else {
                ++ans;
            }
            if(cnt == k) {
                break;
            }
        }
        if(cnt == k) {
            printf("%d\n", ans);
        } else {
            printf("%d\n", len - 1);
        }
    }
    return 0;
}

C. Dishonest Sellers

题意

商家在一周内做打折活动，但是这一周内的价格 $a_i$ 不一定都比原价 $b_i$ 便宜，$Igor$ 想要买其中的 $n$ 件商品，但是他必须在一周内购买其中的至少 $k$ 件商品，输出 $Igor$ 需要付的最少的费用。

数据范围

$1\leq n\leq2\times10^5,0\leq k\leq n\\1\leq a_i,b_i\leq10^4$

题解

假设 $Igor$ 所有商品都在一周后买，然后再挑选 $k$ 件商品换到一周内购买，设 $d_i=a_i-b_i$，则只要在 $d_i$ 中选最小的 $k$ 个数字加到 $\sum_i^nb_i$ 即可，因为至少买 $k$ 件商品，所以如果有大于 $k$ 个 $d_i$ 都小于 $0$，则也可以将这些商品在一周内购买。

过题代码

#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 = 200000 + 100;
int n, k;
LL a[maxn], b[maxn], d[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", &n, &k) != EOF) {
        LL ans = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &a[i]);
        }
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &b[i]);
            d[i] = a[i] - b[i];
            ans += b[i];
        }
        sort(d, d + n);
        for(int i = 0; i < n; ++i) {
            if(d[i] <= 0 || i < k) {
                ans += d[i];
            } else {
                break;
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

D. String Game

题意

有一个字符串 $t$ 要通过消去其中的一些字符，使得这个字符串变为 $p$ 字符串，$Nastya$ 只会按序列 $a_i$ 的顺序消除字符，但是并不知道这样能不能让 $t$ 字符串变为 $p$ 字符串，为了达到这个目的，他的哥哥 $Sergey$ 将会在某一步阻止她，然后自己消除字符。问 $Nastya$ 最多可以消除到第几个字符。题目保证 $t$ 字符串能够消除成 $p$ 字符串，且每消除一个字符，其他字符的位置不变。

数据范围

$1\leq\left|p\right|<\left|t\right|\leq2\times10^5\\1\leq a_i\leq\left|t\right|$

题解

二分答案，对于每次二分，$O(n)$ 判断字符串 $p$ 是否是剩下的字符串的子序列。

过题代码

#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 = 200000 + 100;
int n;
char str1[maxn], str2[maxn];
int tmp[maxn];
int num[maxn];
char stmp[maxn];
bool is(char *s1, char *s2) {
    int Index = 1;
    for(int i = 1; s1[i]; ++i) {
        if(s1[i] == s2[Index]) {
            ++Index;
        }
    }
    return s2[Index] == '\0';
}
bool judge(int x) {
    int cnt = 1;
    for(int i = x + 1; i <= n; ++i) {
        tmp[cnt++] = num[i];
    }
    sort(tmp + 1, tmp + cnt);
    for(int i = 1; i < cnt; ++i) {
        stmp[i] = str1[tmp[i]];
    }
    stmp[cnt] = '\0';
    return is(stmp, str2);
}
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 + 1, str2 + 1) != EOF) {
        n = strlen(str1 + 1);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
        }
        int low = 0;
        int high = n + 1;
        int mid;
        while(high - low > 1) {
            mid = (low + high) / 2;
            if(judge(mid)) {
                low = mid;
            } else {
                high = mid;
            }
        }
        printf("%d\n", low);
    }
    return 0;
}