Educational Codeforces Round 93 题解

A

找到两条最小的边,与最大的边比较一下即可。

B

贪心易得先砍最长的 1 段。

C

$$\sum\limits_{i=l}^r a_i = r-l+1\\\sum\limits_{i=l}^r (a_i - 1)= 0$$

$$s_i = \sum _{j=1}^i (a_i-1)$$

答案相当于求

$$\sum_{i = 1}^n \sum_{j = 0 }^{i-1}[s_i -s_j = 0]= \sum_{i = 1}^n \sum_{j = 0 }^{i-1} [s_i = s_j]$$

就相当于求 $i$ 的时候,求 $cnt[s_i]$ 的个数。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#define ll long long 

using namespace std;

const int N = 1e5 +5;

char a[N];int cnt[N * 10];
int sum[N];
int main() {
    int T; scanf("%d", &T); while (T--) {
        int n; scanf("%d", &n); ll ans = 0; sum[0] = 0;
        scanf("%s", a + 1);
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i] - 49;
        for (int i = 1; i <= n; ++i) sum[i] += 100000; memset (cnt ,0 ,sizeof cnt); 
        cnt[100000] = 1;
        for (int i = 1; i <= n; ++i) {
            ans += cnt[sum[i]]; 
            ++cnt[sum[i]];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

D

首先一个贪心,大的和大的匹配。

之后从大到小排序,进行dp。

const int N = 1e5 +5;
 
int q[3][N];// l[3], r[3];
 
ll f[205][205][205];
 
int main() {
        int R, G, B; scanf("%d%d%d", &R, &G, &B);
        
        for (int i = 1; i <= R; ++i)
            scanf("%d", &q[0][i]);
        sort(q[0] + 1, q[0] + R +1); reverse(q[0] + 1, q[0] + R +1);
        
        for (int i = 1; i <= G; ++i)
            scanf("%d", &q[1][i]);
        sort(q[1] + 1, q[1] + G +1); reverse(q[1] + 1, q[1] + G +1);
        
        for (int i = 1; i <= B; ++i)
            scanf("%d", &q[2][i]);
        sort(q[2] + 1, q[2] + B +1); reverse(q[2] + 1, q[2] + B +1);
        
        memset(f, 0xcf, sizeof f);
        f[0][0][0] = 0; ll ans = 0;
        
        for (int i = 0; i <= R; ++i)
            for (int j = 0; j <= G; ++j) 
                for (int z = 0; z <= B; ++z) if (f[i][j][z] != 0xcfcfcfcfcfcfcfcf) {
                    if (i < R && j < G) f[i + 1][j + 1][z] = max(f[i + 1][j + 1][z], f[i][j][z] + q[0][i + 1] * q[1][j + 1]);
                    if (i < R && z < B) f[i + 1][j][z + 1] = max(f[i + 1][j][z + 1], f[i][j][z] + q[0][i + 1] * q[2][z + 1]);
                    if (j < G && z < B) f[i][j + 1][z + 1] = max(f[i][j + 1][z + 1], f[i][j][z] + q[1][j + 1] * q[2][z + 1]);
                }
        for (int i = 0; i <= R; ++i)
            for (int j = 0; j <= G; ++j) 
                for (int z = 0; z <= B; ++z) if (f[i][j][z] != 0xcfcfcfcfcfcfcfcf) ans = max(ans, f[i][j][z]);            
        printf("%lld\n", ans);
    return 0;
}

E

贪心选前 $k$ 大的数翻倍,$k$ 为翻倍卡的数量。

需要注意前 $k$ 大的数可能都是翻倍卡,需要将最小的翻倍卡置换成 $k+1$ 大的数。

这个实现可以用权值线段树来维护。

const int N = 2e5 + 5;
 
template<class o> il void qr(o &x) {
    x = 0; char c = gc; int f = 1; 
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = gc; }
    while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = gc; }
    x *= f;
}
 
template<class o> il void qw(o x) {
    if (x < 0) x = -x; if (x/10) qw(x/10); 
    putchar(x % 10 + 48); 
}
 
struct node { int i, val, op; node(int i = 0, int val = 0, int op = 0): i(i), val(val), op(op){} } a[N];
 
int arr[N], len;
 
int get(int d) {
    int l = 1, r = len;
    while (l < r) {
        int mid = l + r >> 1;
        if (arr[mid] > d) l = mid + 1;
        else r = mid;
    }
    return l;
}
 
struct Hseg { int w[2], s; ll sum;} t[N << 2];
 
struct vec { int s; ll d; vec(int s = 0, int d = 0ll): s(s), d(d){} };
 
void build(int x, int l, int r) {
    t[x].w[0] = t[x].w[1] = t[x].s = t[x].sum = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
}
 
void upd(int x, int l, int r, int pos, int i, int op) {
    t[x].w[i] += op; t[x].s += op; t[x].sum += op * arr[pos];
    if (l == r) return;
    int mid = l + r >> 1; 
    if (pos <= mid) upd(x << 1, l, mid, pos, i, op);
    else upd (x << 1 | 1, mid + 1, r, pos, i, op);
}
 
vec solve(int x, int l, int r, int k) {
    if (l == r) return vec(t[x].w[1], t[x].sum);
    int mid = l + r >> 1, s = t[x << 1].s;
    if (s >= k) return solve(x << 1, l, mid, k);
    vec val = solve(x << 1 | 1, mid + 1, r, k - s);
    val.s += t[x << 1].w[1], val.d += t[x << 1].sum;
    return val;
}
 
int ask(int x, int l, int r, int k) {
    if (l == r) return l;
    int mid = l + r >> 1, s = t[x << 1].s;
    if (s >= k) return ask(x << 1, l, mid, k);
    return ask(x << 1 | 1, mid + 1, r, k - s);
}
int main() {
    int n; qr(n);
    for (int i = 1; i <= n; ++i) {
        int p, val; qr(p), qr(val);
        if (val < 0) a[i] = node(p, -val, -1), val = -val;
        else a[i] = node(p, val, 1);
        arr[i] = val;
    }
    
    sort(arr + 1, arr + n + 1); reverse(arr + 1, arr + n + 1); len = 0;
    for (int i = 1; i <= n; ++i) if (i == 1 || arr[i - 1] != arr[i]) arr[++len] = arr[i];
    for (int i = 1; i <= n; ++i) a[i].val = get(a[i].val);
    
    ll sum = 0; int k = 0, num = 0;
    for (int i = 1; i <= n; ++i) {
        sum += arr[a[i].val] * a[i].op; num += a[i].op;
        if (a[i].i) k += a[i].op;
        upd(1, 1, len, a[i].val, a[i].i, a[i].op);
        vec now = vec(0, 0ll);
        if (k) now = solve(1, 1, len, k);
        if (now.s == k && k) { 
            int p = 0, q;
            q = ask(1, 1, len, k); if (num != k) p = ask(1, 1, len, k + 1);
            ll val = now.d - arr[q]; if (num != k) val += arr[p];
            qw(val + sum); puts("");
        }
        else qw(now.d + sum), puts("");
    }        
    return 0;
}

F

挺妙的贪心。

若现在进行 $x$ 长度的决策。

假如我们选择到了 $i$ 位置,我们肯定是优先考虑离我最近的合法位置在哪,因为这样才能尽可能地产生贡献。

也就是要找到 $nxt[0][i]$ 表示 $i$ 位置后第一个 $0$ 的位置与 $i$ 位置的距离。

如果 $nxt[0][i]\ge x$ 则可行; 对于 $nxt[1][i]$ 也如此;

如果存在上述两个任一合法,那么则可以继承到 $i + x$ 这个位置。

否则,则需要找到最近的一段合法长度为 $x$ 的区间。

这个可以线性解决,具体解决方式可以参照下面的代码。

const int N = 1e6 + 5;
 
int nxt[2][N];
vector<int> p[2][N];
int prv[2]; char s[N];
 
int main() {
    int n; scanf("%d%s", &n, s + 1);
 
    for (int i = n; i; --i) { 
        if (s[i] != '0') nxt[0][i] = nxt[0][i + 1] + 1;
        if (s[i] != '1') nxt[1][i] = nxt[1][i + 1] + 1; 
    }
 
    for (int i = 0; i <= 1; ++i) {
        int l = 1, r;
        while (l <= n) {
            if (s[l] == '0' + i) {
                ++l; continue; 
            }
            int r = l + 1; 
            while (r <= n && s[r] != '0' + i) ++r;
            int k = r - l;
            for (int len = 1; len <= k; ++len) 
                p[i][len].push_back(l);
            l = r;
        }
    }
    
    for (int len = 1; len <= n; ++len) {
        prv[0] = prv[1] = 0; int pos = 0, res = 0;
        while (pos <= n) {
            int npos = 0x3f3f3f3f;
            for (int i = 0; i <= 1; ++i) {// 这里
                if (nxt[i][pos] >= len) npos = min(npos, pos + len);
                while (prv[i] < p[i][len].size() && p[i][len][prv[i]] < pos) ++prv[i];
                if (prv[i] < p[i][len].size()) npos = min(npos, p[i][len][prv[i]] + len);
            }
            if (npos != 0x3f3f3f3f) ++res;
            pos = npos;
        }
        printf("%d ", res);
    }
    
    return 0;
}

G

题目转化成是否存在一个区间长度 $l$,使得 $L_i \text{ mod } l = 0 $, 若存在 ,请输出最大的 $l$ .

考虑到区间可以转化成前缀和减,直接 $s_i- s_j$ ,这是一个可卷积形式,直接上模板就好了。

const int mod = 998244353, N = 4e5 + 5, G = 3, W = mod - 1;
 
template<class o> il void qr(o &x) {
    x = 0; char c = gc; int f = 1;
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = gc; }
    while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = gc; }
    x *= f;
}
 
template<class o> void qw(o x) {
    if (x < 0) x = -x; if (x/10) qw(x/10);
    putchar(x % 10 + 48);
}
 
int w[N << 1], tr[N << 1], inv[N << 1], cnt, _g1[N << 1];
 
il int ksm(int a, int b = mod - 2) { 
    int ans = 1; 
    for(; b; b >>= 1, a = 1ll * a * a % mod) 
        if (b & 1) ans = 1ll * ans * a % mod; 
    return ans;
}
 
void init(int m) {
    int n = 1; for (; n < (m << 1); n <<= 1);
    inv[0] = inv[1] = 1; for (int i = 2; i <= n; ++i) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) %mod;
    int wn = ksm(G, W / n); w[n >> 1] = 1; for (int i = (n >> 1) + 1; i < n; ++i) w[i] = 1ll * w[i - 1] * wn % mod;
    for (int i = (n >> 1) - 1; i; --i) w[i] = w[i << 1];
}
 
il void rev(int n) { 
    if (cnt == n) return ; cnt = n;
    for (int i = 1; i < n; ++i) tr[i] = (tr[i >> 1] >> 1 | ((i & 1) ? n >> 1 : 0));
}
 
void dft(int *g, int op, int n) { 
    rev(n); if (op) for (int i = 1; i < n; ++i) if (n - i < i) swap(g[n - i], g[i]);
    static ull f[N << 1]; for (int i = 0; i < n; ++i) f[i] = ((1ll * mod << 5) + g[tr[i]])%mod;
    for (int p = 2, l = 1; p <= n; l = p, p <<= 1) {
        for (int i = 0; i < n; i += p) for(int j = 0, t; j < l; ++j) 
            t = w[j|l] * f[i|j|l] % mod, f[i|j|l] = f[i|j] + mod - t, f[i|j] += t;
        if (l == (1 << 10)) for (int i = 0; i < n; ++i) f[i] %= mod;
    }
    if (op) for (int i = 0, t = inv[n]; i < n; ++i) g[i] = f[i] % mod * t % mod;
    else for (int i = 0; i < n; ++i) g[i] = f[i] % mod; 
}
    
il void px(int *f, int *g, int n) { for (int i = 0; i < n; ++i) f[i] = 1ll * f[i] * g[i] % mod; }
 
#define sav _g1
 
void times(int *f, int *g, int l1, int l2, int limit) { 
    int n = 1, m = l1 + l2 - 1; for (; n < m; n <<= 1);
    cpy(sav, g, l2); clr(sav + l2, n - l2); 
    dft(f, 0, n); dft(sav, 0, n); px(f, sav, n); dft(f, 1, n);
    clr(f + limit, n - limit); clr(sav, n);
}
 
#undef sav
 
int a[N], f[N << 1], g[N << 1];
int ans[1000005];
 
 
int main() {
    int n, X, Y; qr(n), qr(X), qr(Y); memset(f, 0, sizeof f);
    for (int i = 0; i <= n; ++i) qr(a[i]), f[a[i]] = 1;
    //for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i], f[sum[i]] = 1;
    int m = X;
    for (int i = 0; i <= n; ++i) g[m - a[i]] = 1;
    ++m; init(m);
    times(f, g, m, m, (m << 1) - 1);
    int mx = 1e6;
    for (int i = m; i < (m << 1) - 1; ++i) {
        if ((i - X) * 2 + Y * 2 > mx) break;
        int x = i - X;
        if (f[i]) ans[(x + Y) * 2] = (x + Y) * 2;
    }
    for (int i = 1; i <= mx; ++i) 
        for (int j = i << 1; j <= mx; j += i) 
            ans[j] = max(ans[j], ans[i]);
    int Q; qr(Q);
    while (Q--) {
        int l; qr(l);
        printf("%d ", ans[l] == 0 ? -1 : ans[l]);
    }
    return 0;
}