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

Codeforces

Contests 链接：Codeforces Round #474 (Div. 1 + Div. 2)
过题数：2
排名：1055/8670

A. Check the string

题意

一个只包含有 a，b，c 三种字符的字符串，字符串分为三段，依次为连续的 a 字符、连续的 b 字符和连续的 c 字符，其中 c 字符的个数等于 a 字符或者 b 字符的个数，问给定的字符串是否满足以上条件。

输入

输入为一个字符串 $S~(1\leq|S|\leq5000)$，字符串中只包含 a，b，c 三种字符。

输出

如果满足条件，则输出 $YES$，否则输出 $NO$。

样例

题解

按题意检查格式。

过题代码

#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 = 5000 + 100;
int Count[3];
char str[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%s", str) != EOF) {
        bool flag = true;
        int cnt = 0;
        memset(Count, 0, sizeof(Count));
        for(int i = 0; str[i]; ++i) {
            int w = str[i] - 'a';
            ++Count[w];
            if(cnt + 1 == w) {
                ++cnt;
            } else if(cnt != w) {
                flag = false;
                break;
            }
        }
        for(int i = 0; i < 3; ++i) {
            if(Count[i] == 0) {
                flag = false;
                break;
            }
        }
        if(!flag) {
            printf("NO\n");
            continue;
        }
        if(Count[2] == Count[0] || Count[1] == Count[2]) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

B. Minimize the error

题意

给定两个长度为 $n$ 的序列 $A$ 和 $B$，定义两个序列的误差 $E=\sum_{i=1}^n(a_i-b_i)^2$，可以对 $A$ 序列进行 $k_1$ 次操作，对 $B$ 序列进行$k_2$ 次操作，每次操作可以选择序列中任意一个字符，将它的值加 $1$ 或减 $1$，问两个序列分别经过 $k_1$ 次和 $k_2$ 次操作后的最小误差值。

输入

第一行为三个整数 $n,k_1,k_2~(1\leq n\leq10^3,0\leq k_1+k_2\leq10^3,k_1,k_2\geq0)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n$，第三行为 $n$ 个整数 $b_1,b_2,\cdots,b_n$，其中 $-10^6\leq a_i,b_i\leq10^6$。

输出

输出修改后两个序列的最小误差值。

样例

题解

由于对其中一个序列的元素 $+1$ 或 $-1$ 等价于对另一个序列相同位置上的数字 $-1$ 或 $+1$，因此相当于直接对其中一个序列做 $k_1+k_2$ 次操作，每次贪心地对两个序列对应位置上绝对值最大的数字进行一次操作，往减小它们绝对值的方向操作，若序列中对应位置的最大绝对值为 $0$，则只能将绝对值 $+1$，否则 $-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 = 1000 + 100;
int n, k1, k2;
int a[maxn], b[maxn];
priority_queue<int> que;
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", &n, &k1, &k2) != EOF) {
        while(!que.empty()) {
            que.pop();
        }
        for(int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        for(int i = 0; i < n; ++i) {
            scanf("%d", &b[i]);
            que.push(abs(a[i] - b[i]));
        }
        k1 += k2;
        for(int i = 0; i < k1; ++i) {
            int tmp = que.top();
            que.pop();
            if(tmp != 0) {
                --tmp;
            } else {
                ++tmp;
            }
            que.push(tmp);
        }
        LL ans = 0;
        while(!que.empty()) {
            LL tmp = que.top();
            que.pop();
            ans += tmp * tmp;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

C. Subsequence Counting

题意

给定整数 $X$ 和 $d$，构造一个长度为 $n$ 的序列，这个序列总共有 $2^n-1$ 个非空子序列，要求将所有非空子序列中的子序列最大值减最小值大于等于 $d$ 的所有子序列删去后，剩下 $X$ 个子序列。

输入

输入包含两个整数 $X,d~(1\leq X,d\leq10^9)$。

输出

第一行输出一个整数 $n~(1\leq n\leq10^4)$，表示构造出来的序列长度，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^{18})$，如果无法构造出满足条件的序列，输出 $-1$。

样例

题解

将 $X$ 分解成 $\sum_{k=0}^{32}(2^k-1)\times c_k$，其中 $c_k\in[0,1]$，$k$ 个相同的数字就可以得到 $2^k-1$ 个非空子序列，对于每个 $k$ 输出 $k\times c_k$ 个相同的数字，让任意两个不同的数字间隔为 $d$，就可以构造出合法的序列，不存在无法构造数列的情况。

过题代码

#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 = 70;
int cnt;
LL x, d;
LL two[maxn];
LL *it;
LL ans[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    two[0] = 1;
    for(int i = 1; i < 63; ++i) {
        two[i] = two[i - 1] * 2;
    }
    for(int i = 0; i < 63; ++i) {
        --two[i];
    }
    while(scanf("%I64d%I64d", &x, &d) != EOF) {
        bool flag = false;
        cnt = 0;
        LL n = 0;
        while(x != 0) {
            it = upper_bound(two, two + 63, x);
            --it;
            x -= *it;
            ans[cnt++] = it - two;
            n += ans[cnt - 1];
        }
        printf("%I64d\n", n);
        for(int i = 0; i < cnt; ++i) {
            for(int j = 0; j < ans[i]; ++j) {
                if(flag) {
                    printf(" ");
                }
                printf("%I64d", i * d + 1);
                flag = true;
            }
        }
        printf("\n");
    }
    return 0;
}