Educational Codeforces Round 93lyh's blog

Educational Codeforces Round 93。论刚刚上紫名是一种什么体验。

A. Bad Triangle

这。。把最小的两个加起来，与最大的一个比较大小即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 5;
typedef long long ll;
int n, op[N];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", op + i);
        if (op[1] + op[2] > op[n]) {
            printf("-1\n");
        } else {
            printf("1 2 %d\n", n);
        }
    }
    return 0;
}

B. Substring Removal Game

每一个人的最佳策略一定是拿当前最长的一段连续的1，不可能拿0。因为如果拿0，要么没有影响，要么使得两段原本不相邻的1相邻，这对对手是有利的，总之拿0不会使自己有任何优势，较小的一段1同理。于是我们统计有哪些连续的1，记录它们的数量，排序后隔项取。

#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 5;
typedef long long ll;
char op[500];
vector<int> vec;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", op), vec.clear();
        int n = strlen(op), l = 0, r;
        while (l < n) {
            if (op[l] == '0') {
                ++l;
            } else {
                r = l;
                while (r + 1 < n && op[r + 1] == '1') ++r;
                vec.push_back(r - l + 1), l = r + 1;
            }
        }
        sort(vec.begin(), vec.end(), greater<int>());
        int ans = 0;
        for (int i = 0; i < vec.size(); i += 2) ans += vec[i];
        printf("%d\n", ans);
    }
    return 0;
}

C. Good Subarrays

预处理前缀和，然后等价于$S(r)-S(l-1)=r-l+1$，即为$S(r)-r=S(l-1)-l+1$。然后我们对于一个$l$，统计有多少个$r$满足这个式子。统计的方法有很多，使用$map$是一个不错的策略，当然也可以用二分的方法。

#include <bits/stdc++.h>
 
#define N 200005
using namespace std;
 
int n, tmp[N], m;
char op[N];
int sum[N];
vector<int> vec[N];
set<int> ssp;
int fb(int l, int r, int s, int who)
{
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%s", &n, op + 1), ssp.clear();
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + op[i] - '0', tmp[i] = sum[i] - i;
            vec[i].clear();
        }
        sort(tmp + 1, tmp + n + 1), m = unique(tmp + 1, tmp + n + 1) - tmp - 1;
        for (int i = 1; i <= n; i++) {
            int what = lower_bound(tmp + 1, tmp + m + 1, sum[i] - i) - tmp;
            vec[what].push_back(i);
            ssp.insert(sum[i] - i);
        }
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            int ss = sum[i - 1] - i + 1;
            if (ssp.count(ss) == 0) continue;
            int at = lower_bound(tmp + 1, tmp + m + 1, ss) - tmp;
            int l = -1, r = vec[at].size() - 1, mid;
            while (l < r) {
                if (r == l + 1) break;
                mid = (l + r) >> 1;
                if (vec[at][mid] >= i)
                    r = mid;
                else
                    l = mid;
            }
            if (vec[at][r] >= i) ans += vec[at].size() - r;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

D. Colored Rectangles

首先贪心是不对的，考虑其它做法。
容易发现，对于$ab+cd$，如果$a>d$且$c>b$，则$ac+bd>ab+cd$，这说明我们应该尽可能地使较大的数乘在一起（如果只有两个序列，贪心是可以的），但是这里有三个序列，于是需要$DP$，$DP$方程很好列。

#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
vector<int> R, G, B;
int n, r, g, bb;
ll dp[201][201][201];
ll DP(int a, int b, int c)
{
    if (~dp[a][b][c]) return dp[a][b][c];
    if ((a == 0 && b == 0) || (a == 0 && c == 0) || (b == 0 && c == 0)) return 0;
    if (a > 0 && b > 0 && c > 0) {
        return dp[a][b][c] =
                   max(R[a] * G[b] + DP(a - 1, b - 1, c), max(R[a] * B[c] + DP(a - 1, b, c - 1), G[b] * B[c] + DP(a, b - 1, c - 1)));
    } else {
        if (a == 0) {
            return dp[a][b][c] = DP(a, b - 1, c - 1) + G[b] * B[c];
        } else if (b == 0) {
            return dp[a][b][c] = DP(a - 1, b, c - 1) + R[a] * B[c];
        } else {
            return dp[a][b][c] = DP(a - 1, b - 1, c) + R[a] * G[b];
        }
    }
}
int main()
{
    scanf("%d%d%d", &r, &g, &bb), memset(dp, -1, sizeof(dp));
    R.push_back(0), G.push_back(0), B.push_back(0);
    for (int i = 1, x; i <= r; i++) scanf("%d", &x), R.push_back(x);
    for (int i = 1, x; i <= g; i++) scanf("%d", &x), G.push_back(x);
    for (int i = 1, x; i <= bb; i++) scanf("%d", &x), B.push_back(x);
    sort(R.begin(), R.end());
    sort(B.begin(), B.end());
    sort(G.begin(), G.end());
    printf("%lld", DP(r, g, bb));
    return 0;
}

E. Two Types of Spells

        发现第二个$spell$的好处就是能把下一个卡的伤害乘个2，这给我们一个解题思路。假如现在有$x$个第二个$spell$，贪心地想，如果我们把最大的$x$个乘上二，这样显然是最优的。
        问题是一个二号$spell$可能也位于前$x$大中，这就需要分类讨论。如果前$x$个中有不到$x$个二号卡（假设$y$个），这样剩下的$x-y$个一号卡需要$x-y$个二号卡来做乘二的处理，刚好有$x-y$个二号卡不在前$x$大中，就拿它们来处理这$x-y$张一号卡，然后把$y$张二号卡全部插到某个二号卡和一号卡的间隙中（这个间隙是必然存在的，因为$x-y>0$），于是全部满足条件。也就是说$x>y$时，答案就是总的伤害加上前$x$大伤害。
        如果$x=y$，这样间隙就没有了，我们必须牺牲掉$x$张二号卡中的一张，当然是牺牲伤害最小的那一个，与此同时可以多出一个处理一号卡的名额，当然要处理一号卡中最大的那一个。即$x=y$时，答案就是总的伤害加上前$x-1$大伤害加上一号卡的最大值。
        由于有动态插入删除操作，用平衡树可以很好的解决这个问题，当然可以用动态开点线段树。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
struct Node
{
    int ch[2], v, num, key, type;
    ll sum, tn;
 
    Node()
        : num(0)
    {
        ch[0] = ch[1] = 0;
    }
} node[300005];
 
int root = 0, cnt = 0;
 
inline void update(int x)
{
    node[x].num = node[node[x].ch[0]].num + node[node[x].ch[1]].num + 1;
    node[x].tn = node[node[x].ch[0]].tn + node[node[x].ch[1]].tn + node[x].type;
    node[x].sum = node[node[x].ch[0]].sum + node[node[x].ch[1]].sum + node[x].v;
}
 
inline int addNode(int x, int type)
{
    node[++cnt].v = x, node[cnt].ch[0] = node[cnt].ch[1] = 0;
    node[cnt].num = 1, node[cnt].key = rand(), node[cnt].type = type;
    node[cnt].tn = type, node[cnt].sum = x;
    return cnt;
}
 
void split(int rt, int& a, int& b, int v)
{
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (node[node[rt].ch[0]].num < v)
        a = rt, split(node[rt].ch[1], node[a].ch[1], b, v - node[node[rt].ch[0]].num - 1);
    else
        b = rt, split(node[rt].ch[0], a, node[b].ch[0], v);
    update(rt);
}
 
void merge(int& rt, int a, int b)
{
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (node[a].key > node[b].key) {
        rt = a, merge(node[a].ch[1], node[a].ch[1], b);
    } else {
        rt = b, merge(node[b].ch[0], a, node[b].ch[0]);
    }
    update(rt);
}
 
void split2(int rt, int& a, int& b, int v)
{
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (node[rt].v <= v)
        a = rt, split2(node[rt].ch[1], node[a].ch[1], b, v);
    else
        b = rt, split2(node[rt].ch[0], a, node[b].ch[0], v);
    update(rt);
}
int n, num;
inline void add(int x, int tp)
{
    int a, b, c;
    split2(root, a, c, x);
    split2(a, a, b, x - 1);
    if (tp == 1)
        merge(b, b, addNode(x, tp));
    else
        merge(b, addNode(x, tp), b);
    merge(a, a, b), merge(root, a, c);
    ++num;
}
inline void del(int x, int tp)
{
    int a, b, c;
    split2(root, a, c, x);
    split2(a, a, b, x - 1);
    if (tp == 1) {
        if (node[b].type == 0)
            node[b].ch[1] = 0, update(b);
        else
            b = 0;
    } else if (tp == 0) {
        if (node[b].type == 1)
            node[b].ch[0] = 0, update(b);
        else
            b = 0;
    }
    merge(a, a, b), merge(root, a, c);
    --num;
}
int findR(int rt)
{
    if (rt == 0) return 0;
    if (node[rt].ch[1]) return findR(node[rt].ch[1]);
    return node[rt].v;
}
int main()
{
    srand(time(0));
    scanf("%d", &n);
    while (n--) {
        int tp, d;
        scanf("%d%d", &tp, &d);
        if (d > 0) {
            add(d, tp);
        } else {
            del(-d, tp);
        }
        ll ans = node[root].sum;
        // cout << ans << endl;
        int what = node[root].tn;
        if (what == 0) {
            printf("%lld\n", ans);
            continue;
        }
        int a, b;
        split(root, a, b, num - what);
        if (node[b].tn < what) {
            ans += node[b].sum;
        } else {
            ans += findR(a);
            merge(root, a, b);
            split(root, a, b, num - what + 1);
            ans += node[b].sum;
        }
        merge(root, a, b);
        printf("%lld\n", ans);
    }

F. Controversial Rounds

        本题很好，强烈建议一做。
        首先可以想到一个$dp$，设$dp(x)$为前$x$段的答案，长度为$len$时，如果可以将$[x-len+1,x]$化为全$0$或者全$1$，这样就可以转移到$dp(x-len)+1$，另一个转移即为$dp(x-1)$。
        可以发现，当可以转移的时候必然有$dp(x-len)+1\geq dp(x-1)$，这告诉我们只要能凑够$len$的区间，就尽可能凑，这就变成一个贪心问题了。
        既然可以贪心，就从左向右尽可能凑长度为$len$的区间。暴力做每一次都是$O(n)$的，这样就是$O(n^2)$不可取。
        解决这种需要枚举长度的区间问题有一个通用思路：打点法。我们每$len$个单位打一个点，显然每一个$len$长的段都必然会包括唯一的一个点。我们通过枚举这些点就能求出最多有多少个合法区间。具体来说我们从左到右枚举这些点，同时维护上一个长度为$len$的段的右端点，然后贪心地选下一个（能选就选）。
        复杂度是$O(\sum_{i=1}^n\frac{n}{i})=O(nlogn)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000000 + 5;
typedef long long ll;
int n, ltr[N][2], rtl[N][2];
char op[N];
inline int solve(int at, int last, int len, int who)
{
    if (op[at] != '?' && op[at] != who + '0') return 0x3f3f3f3f;
    int pre = max(last + 1, at - ltr[at][who] + 1);
    int nxt = at + rtl[at][who] - 1;
    if (nxt - pre + 1 < len) return 0x3f3f3f3f;
    return pre + len - 1;
}
int main()
{
    scanf("%d%s", &n, op + 1);
    for (int i = 1; i <= n; i++) {
        ltr[i][0] = op[i] == '1' ? 0 : ltr[i - 1][0] + 1;
        ltr[i][1] = op[i] == '0' ? 0 : ltr[i - 1][1] + 1;
    }
    for (int i = n; i >= 1; i--) {
        rtl[i][0] = op[i] == '1' ? 0 : rtl[i + 1][0] + 1;
        rtl[i][1] = op[i] == '0' ? 0 : rtl[i + 1][1] + 1;
    }
    for (int len = 1; len <= n; len++) {
        int last = 0, ans = 0;
        for (int i = len; i <= n; i += len) {
            int to = min(solve(i, last, len, 0), solve(i, last, len, 1));
            if (to != 0x3f3f3f3f) last = to, ++ans;
        }
        printf("%d ", ans);
    }
    return 0;
}

G. Running Competition

先考虑一个简单问题：给$n$个数，在给若干次询问，每次给一个数$x$，查询$x$是否可以表示成先前给的$n$个数中，某两个数的差。
当数的范围不很大时，我们可以使用$FFT/NTT$在$O(nlogn)$预处理，$O(1)$查询的复杂度下优雅地解决这个问题。具体来说，我们构造多项式：

$F(x)=\sum_{i=1}^nx^a_i\\ G(x)=\sum_{i=1}^nx^{-a_i}$

        其中$a_i$就是给定的第$i$个数。
        然后用$FFT/NTT$将两个多项式乘起来就可以很快地判断。
        本题中，每一个路径必然是一个矩形，长度可以表示成$2(a_j-a_i)+2y$，它需要是给定数的因子。
        枚举因子，然后判断它是否合法即可，预处理和判断即为上面的$FFT/NTT$思路。

#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct Complex
{
    double a, b;
 
    Complex(double a = 0, double b = 0)
        : a(a), b(b) {}
 
    Complex operator+(Complex c)
    {
        return {a + c.a, b + c.b};
    }
 
    Complex operator*(Complex c)
    {
        return {a * c.a - b * c.b, a * c.b + b * c.a};
    }
 
    Complex operator-(Complex c)
    {
        return {a - c.a, b - c.b};
    }
};
struct Pol
{
    int l;
    Complex op[N << 2];
} p1, p2, pa;
const double Pi = acos(-1.0);
int tr[N << 2];
 
inline void FFT(int l, Complex* 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) {
        Complex wn(cos(Pi / mid), type * sin(Pi / mid));
        for (int len = mid << 1, j = 0; j < l; j += len) {
            Complex w(1.0, 0);
            for (int k = 0; k < mid; k++, w = w * wn) {
                Complex x = c[j + k], y = w * c[j + mid + k];
                c[j + k] = x + y, c[j + mid + k] = x - y;
            }
        }
    }
}
 
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;
    }
    FFT(l, a->op, 1), FFT(l, b->op, 1);
    for (int i = 0; i < l; i++) a->op[i] = a->op[i] * b->op[i];
    FFT(l, a->op, -1), ans->l = a->l + b->l;
    for (int i = 0; i <= ans->l; i++) ans->op[i].a = a->op[i].a / l;
}
int n, x, y;
vector<int> yz;
int main()
{
    scanf("%d%d%d", &n, &x, &y);
    p1.l = x, p2.l = x;
    for (int i = 0, a; i <= n; i++) {
        scanf("%d", &a);
        // a = i;
        p1.op[a] = Complex(1, 0), p2.op[x - a] = Complex(1, 0);
    }
    multiple(&pa, &p1, &p2);
    // for (int i = 0; i <= pa.l; i++) cout << pa.op[i].a << " ";
    // cout << endl;
    int q;
    scanf("%d", &q);
    while (q--) {
        int L;
        scanf("%d", &L), yz.clear();
        for (int i = 1; 1ll * i * i <= L; i++) {
            if (L % i == 0) {
                yz.push_back(i);
                if (L / i != i) yz.push_back(L / i);
            }
        }
        sort(yz.begin(), yz.end());
        for (int i = yz.size() - 1; i >= 0; i--) {
            if (yz[i] & 1) continue;
            int sv = (yz[i] - 2 * y) >> 1;
            // cout << sv << endl;
            if (sv <= 0) continue;
            if (fabs(pa.op[sv + x].a) >= 0.5) {
                printf("%d ", yz[i]);
                goto tag;
            }
        }
        printf("-1 ");
    tag:;
    }
    return 0;
}