Educational Codeforces Round 75 (Rated for Div. 2)lyh's blog

Educational Codeforces Round 75 (Rated for Div. 2)题解。

A. Broken Keyboard

水题了。只要连续的一段字母是奇数个，它一定在答案里。

#include <bits/stdc++.h>
using namespace std;
char op[100005];
int dp[100005];
set<char> s;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int len;
        scanf("%s", op);
        s.clear();
        len = strlen(op);
        for (int i = 0; i < len;) {
            int at = i;
            while (at + 1 < len && op[at + 1] == op[at])
                ++at;
            if ((at - i + 1) % 2) {
                s.insert(op[i]);
            }
            i = at + 1;
        }
        for (char e : s) {
            printf("%c", e);
        }
        printf("\n");
    }
    // PAUSE;
    return 0;
}

B. Binary Palindromes

        统计0和1的数量，固定每一个串的长度，给它们做分配。
        将串按照长度排序，依次分配。易知，除了最后一个串，其余的串一定可以全分配为0或者全分配为1。这样的话，我们可以保证前面所有的串都是回文串。
        对于最后一个，如果它的长度是奇数个，由于奇数只能为奇数和偶数的和，因此它一定可以分配成回文串，此时答案就是$n$。
        如果最后一个是偶数长度，要考虑0和1剩余数量的奇偶性质。若都为偶数，则最后一个串仍然可以为回文串。但是当两者都为奇数时，情况则不然。这种情况下，需要考察前面的串中有没有奇数串，若有，我们可以交换其中心的数，使得最后剩余的0和1的数量都为偶数。如果前面没有奇数串，那么答案只能为$n-1$。

#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
char op[55];
int n, z0, z1;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        z0 = z1 = 0;
        vec.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%s", op);
            int len = strlen(op);
            vec.push_back(len);
            for (int j = 0; j < len; j++) {
                if (op[j] == '0')
                    ++z0;
                else
                    ++z1;
            }
        }
        int ans = 0, num = 0;
        sort(vec.begin(), vec.end());
        for (int i = 0; i < vec.size() - 1; i++) {
            if (vec[i] % 2)
                ++num;
        }
        for (int i = 0; i < vec.size(); i++) {
            if (z0 > vec[i]) {
                z0 -= vec[i];
                ++ans;
            }
            else if (z1 > vec[i]) {
                z1 -= vec[i];
                ++ans;
            }
            else {
                if (vec[i] % 2) {
                    ++ans;
                }
                else if (z0 % 2 == 0 && z1 % 2 == 0) {
                    ++ans;
                }
                else if (num) {
                    ++ans;
                }
            }
        }
        printf("%d\n", ans);
    }
    // PAUSE;
    return 0;
}

C. Minimize The Integer

由于奇数和偶数是不能交换的，因此所有奇数和所有偶数的相对位置保持不变。我们用两个队列维护这种相对关系，然后贪心即可。

#include <bits/stdc++.h>
using namespace std;
queue<char> j, o;
char op[300005];
vector<char> vec;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s", op);
        vec.clear();
        int len = strlen(op);
        for (int i = 0; op[i]; i++) {
            if ((op[i] - '0') % 2)
                j.push(op[i]);
            else
                o.push(op[i]);
        }
        while (!j.empty() && !o.empty()) {
            if (j.front() < o.front()) {
                vec.push_back(j.front());
                j.pop();
            }
            else {
                vec.push_back(o.front());
                o.pop();
            }
        }
        if (j.empty()) {
            while (!o.empty()) {
                vec.push_back(o.front());
                o.pop();
            }
        }
        else {
            while (!j.empty()) {
                vec.push_back(j.front());
                j.pop();
            }
        }
        for (int i = 0; i < vec.size(); i++)
            printf("%c", vec[i]);
        printf("\n");
    }
    // PAUSE;
    return 0;
}

D. Salary Changing

        考虑二分答案。
        二分出一个答案，然后贪心判断其正确性。假设答案为$p$。
        找出所有$r< p$的区间，它们一定在中位数$p$的左侧，为了使总和最小，取其$l$值计入答案。然后找出所有$l >p$的区间，它们一定在右侧，同样地，将$l$计入答案。
        对于包含$p$的区间，我们用它对答案进行调节。注意到如果小于$p$的区间或者大于$p$的区间数量多于$\frac {n-1} {2}$个，那么一定是不合法的。
        接下来，我们调节左侧区间的数量。将包含$p$的区间按照左端点$l$升序排列，依次遍历。若左侧的区间不足$\frac {n-1}{2}$，则将当前遍历到的区间加入左侧，答案计入$l$，否则为了最小化总和，之后的区间都计入$p$。
        最后对比总和和$s$的大小关系，即可判断出答案的正确性。

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int l, r;
    bool operator<(Node s)
    {
        return l < s.l;
    }
} nd[200005];
vector<Node> vec;
vector<int> tmp;
int n, ps;
long long S;
bool check(int x)
{
    long long s = 0;
    int ll = 0, rr = 0;
    vec.clear();
    for (int i = 1; i <= n; i++) {
        if (nd[i].r < x) {
            s += nd[i].l;
            ++ll;
        }
        else if (nd[i].l > x) {
            s += nd[i].l;
            ++rr;
        }
    }
    if (ll > ps || rr > ps)
        return false;
    for (int i = 1; i <= n; i++) {
        if (nd[i].l <= x && nd[i].r >= x)
            vec.push_back(nd[i]);
    }
    sort(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++) {
        if (ll < ps) {
            s += vec[i].l;
            ++ll;
        }
        else {
            s += x;
        }
    }
    if (s <= S)
        return true;
    else
        return false;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%lld", &n, &S);
        tmp.clear();
        ps = n >> 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &nd[i].l, &nd[i].r);
            tmp.push_back(nd[i].l);
        }
        sort(tmp.begin(), tmp.end());
        int l = tmp[(tmp.size() - 1) >> 1], r = 1000000001, mid;
        while (l < r) {  //[,)
            if (r == l + 1) {
                printf("%d\n", l);
                goto to;
            }
            mid = (l + r) >> 1;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }
    to:;
    }
    // PAUSE;
    return 0;
}

E. Voting

        思维题。
        考虑如何选取votes来最小化答案。它们一定是这样的：选了一些并且支付$p_i$硬币后，数量达到一定要求，使得最后所有人都加入vote的集合。
        将所有人按照其$m$值分组。对于$m_i=n$的组，假设他有$s$个人，那么有下面的一些思考：

若$n-s<m_i$，这说明选取了除了这个组的所有人都不能使他们免费，这就是说这一个组内的人至少有一个需要收费。
若$n-s\geq m_i$，说明我们可以暂且不对这个组的人付费。

上面的思考带来了一个思路。倒序枚举$m$的值，将该组的人统一加入一个集合，计算集合元素的数量$s$与$n$和$m$的关系。若$n-s< m$则说明这个集合中必有人需要付费，那么我们就对其中$m+s-n$个人付费，为了最小化代价，当然选取最小的那一部分，这样集合就是一个优先队列。
用优先队列维护就可以了。

#include <bits/stdc++.h>
using namespace std;
vector<int> vec[200005];
int n, m[200005], p[200005];
struct cmp
{
    bool operator()(int a, int b)
    {
        return p[a] > p[b];
    }
};
priority_queue<int, vector<int>, greater<int>> pq;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        while (!pq.empty())
            pq.pop();
        for (int i = 1; i <= n; i++)
            vec[i].clear();
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", m + i, p + i);
            vec[m[i]].push_back(i);
        }
        long long s = 0;
        for (int i = n; i >= 1; i--) {
            for (int j = 0; j < vec[i].size(); j++)
                pq.push(p[vec[i][j]]);
            while (i > n - pq.size()) {
                s += pq.top();
                pq.pop();
            }
        }
        printf("%lld\n", s);
    }
    // PAUSE;
    return 0;
}

F. Red-White Fence

先统计白板的数量，对于数量多于2的白板，可以将其看做2（因为只能放到两侧），我们用$a_i$和$b_i$来表示用数量为1的白板构造长度为$i$的方案数，$b_i$表示用数量多于1的白板构造长度为$i$的方案数。
假设数量为一的白板有$na$个，数量多于1的有$nb$个（计入重数，重数最多为2），那么，有下面的结论：

$a_i=C_{na}^i2^i\\ b_i=C_{nb}^i$

$a_i$的$2_i$是对两侧的枚举，$b_i$是不需要的，因为它本身已经包含了这一信息。
那么构造长度为$m$的白板的方案数为：

$\sum_{i=0}^ma_ib_{m-i}$

这是一个卷积，可以用$NTT$优化。
由于有最多$k$个红板，需要有$k$个多项式。由于$k$很小，查询时暴力查即可。

#include <bits/stdc++.h>
using namespace std;
#define N 300005
#define MOD 998244353
#define G 3 
int tr[N << 2];
struct Pol
{               
    int l, op[N << 2];
} pol[6], t1, t2;
int fac[N], inv[N], n, k, a[N], b[6], q, cnt[N];
 
int qPow(int a, int b)
{
    int ans = 1, x = a;
    while (b) {
        if (b & 1)
            ans = 1ll * ans * x % MOD;
        x = 1ll * x * x % MOD, b >>= 1;
    }
    return ans;
}
 
void NTT(int l, int* c, int type)
{
    for (int i = 0; i < l; i++)
        if (i < tr[i])
            swap(c[i], c[tr[i]]);
    for (int mid = 1; mid < l; mid <<= 1) {
        int wn = qPow(G, (MOD - 1) / (mid << 1));
        if (type == -1)
            wn = qPow(wn, MOD - 2);
        for (int len = mid << 1, j = 0; j < l; j += len) {
            int w = 1;
            for (int k = 0; k < mid; k++, w = 1ll * w * wn % MOD) {
                int x = c[j + k], y = 1ll * w * c[j + mid + k] % MOD;
                c[j + k] = (1ll * x + y) % MOD, c[j + mid + k] = (1ll * x - y) % MOD;
            }
        }
    }
}
 
inline void multiple(Pol* ans, Pol* a, Pol* b)
{
    int l = 1, le = 0;
    while (l <= a->l + b->l)
        l <<= 1, ++le;
    for (int i = 0; i < l; i++) {
        tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (le - 1));
        if (i > a->l)
            a->op[i] = 0;
        if (i > b->l)
            b->op[i] = 0;
    }
    NTT(l, a->op, 1), NTT(l, b->op, 1);
    for (int i = 0; i < l; i++)
        a->op[i] = 1ll * a->op[i] * b->op[i] % MOD;
    NTT(l, a->op, -1), l = qPow(l, MOD - 2), ans->l = a->l + b->l;
    for (int i = 0; i <= ans->l; i++)
        ans->op[i] = 1ll * a->op[i] * l % MOD;
}
inline int C(int x, int y)
{
    if (x == 0)
        return y == 0;
    return 1ll * fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    for (int i = 1; i <= k; i++)
        scanf("%d", b + i);
    for (int i = 1; i <= n; i++)
        ++cnt[a[i]];
    sort(a + 1, a + n + 1);
    fac[0] = 1, inv[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = 1ll * i * fac[i - 1] % MOD;
        inv[i] = qPow(fac[i], MOD - 2);
    }
    for (int i = 1; i <= k; i++) {
        int na = 0, nb = 0;
        for (int j = 1; j < b[i]; j++) {
            if (cnt[j] >= 2)
                nb += 2;
            else if (cnt[j] == 1)
                ++na;
        }
        t1.l = na, t2.l = nb;
        for (int j = 0; j <= t1.l; j++)
            t1.op[j] = 1ll * C(na, j) * qPow(2, j) % MOD;
        for (int j = 0; j <= t2.l; j++)
            t2.op[j] = 1ll * C(nb, j) % MOD;
        multiple(pol + i, &t1, &t2);
    }
    scanf("%d", &q);
    while (q--) {
        int Q, ans = 0;
        scanf("%d", &Q);
        for (int i = 1; i <= k; i++) {
            int sv = ((Q - 2 * b[i]) / 2) - 1;
            if (sv >= 0) {
                ans += pol[i].op[sv];
                ans %= MOD;
            }
        }
        printf("%d\n", (ans + MOD) % MOD);
    }
    return 0;
}