当前位置：首页 > article >正文

AtCoder Beginner Contest 370 Solution

article 2024/11/13 10:06:39

A

void solve() {
    int a, b;
    qr(a, b);
    if(a + b != 1) cout << "Invalid\n";
    else Yes(a);
}

B

模拟

void solve() {
    qr(n);
    int x = 1;
    FOR(i, n) FOR(j, i) qr(a[i][j]);
    FOR(i, n) x = x >= i ? a[x][i]: a[i][x];
    pr2(x);
}

C

首先先考虑能变小的位置, 此时选择更前面的位置对字典序的改变更优. 反之, 先选后面的位置更优.

void solve() {
    string s, t;
    qr(s, t);
    n = SZ(s);
    VT<int> v[2];
    m = 0;
    rep(i, 0, n - 1) 
        if(s[i] != t[i])
            v[s[i] < t[i]].pb(i);
    pr2(SZ(v[0]) + SZ(v[1]));
    reverse(v[1]);
    rep(i, 0, 1) {
        for(int j: v[i]) s[j] = t[j], pr2(s);
    }
}

D

维护 $n + m$ 个set,用内置函数查找. 需要注意的时,先删除 prev(it), 再删除 it. 否则迭代器可能异常.

void solve() {
    qr(n, m, q);
    VT r(n + 1, set<int>()), c(m + 1, set<int>());
    FOR(i, n) FOR(j, m) r[i].insert(j), c[j].insert(i);
    int x, y;
    auto del = [&](int x, int y) {
        r[x].erase(y); 
        c[y].erase(x);
    };
    while(q--) {
        qr(x, y);
        if(r[x].contains(y)) {
            del(x, y);
            continue;
        }
        if(SZ(c[y])) {
            auto jt = c[y].upper_bound(x);
            if(jt != c[y].begin()) del(*prev(jt), y);
            if(jt != c[y].end()) del(*jt, y);
        }
        if(SZ(r[x])) {
            auto jt = r[x].upper_bound(y);
            if(jt != r[x].begin()) del(x, *prev(jt));
            if(jt != r[x].end()) del(x, *jt);
        }
    }
    int ans = 0;
    FOR(i, n) ans += SZ(r[i]);
    pr2(ans);
}

E

简单容斥+dp, 每次把以 $i$ 末尾段中和为 $k$ 的段去掉即可.

const int N = 2e5 + 10, inf = 0x3f3f3f3f;
const ll INF = 4E18;
int n;
ll s[N], m, f[N];

void solve() {
    qr(n, m);
    FOR(i, n) qr(s[i]), s[i] += s[i - 1];
    ll sum = f[0] = 1;
    map<ll, int> g;
    g[0] = 1;
    FOR(i, n) {
        f[i] = sum;
        dl(f[i], g[s[i] - m]);
        ad(g[s[i]], f[i]);
        ad(sum, f[i]);
    }
    pr2(f[n]);
}

F

看到最小值最大,显然二分 $x$ ,判断是否可以每段都 $\ge x$ .
然后环的处理就是断环为链(复制一次在后面).
然后每个位置求一下最大的前驱,满足对应区间和 $\ge x$ .
然后就是倍增选择跳 $m$ 次前驱, 如果跳完坐标差 $\le n$ , 则合法.

考虑第二个输出, 不被砍,说明不能以它结尾, 所以统计不合法的 $e n d p o in t$ 数量即可. 复杂度 $O(n\log m \log (\sum a[i] / n))$ .

当然把倍增去掉,改成 $df s$ 即可省去一个 $\log m$ .

const int N = 4e5 + 10, inf = 0x3f3f3f3f;
const ll INF = 4E18;
int n, m, a[N], sum;

int p[N], f[N][20], out;
bool check(int x, int o = 1) {
    int st = 1, s = 0;
    int lg = __lg(m);
    out = 0;
    FOR(i, 2 * n) {
        s += a[i];
        while(st < i && s - a[st] >= x) s -= a[st++];
        p[i] = st - 1;
        f[i][0] = p[i];
        rep(j, 1, lg) f[i][j] = f[f[i][j - 1]][j - 1];
        if(i > n) {
            int j = i;
            rep(k, 0, lg) if(m >> k & 1) j = f[j][k];
            if(i - j <= n) {
                if(o) return 1;
            }
            else out++;
        }
    }
    return 0;
}

void solve() {
    qr(n, m);
    FOR(i, n) qr(a[i]), a[i + n] = a[i], sum += a[i];
    int l = *min_element(a + 1, a + n + 1), r = sum / m, mid;
    while(l < r) {
        mid = (l + r + 1) >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    check(l, 0);
    pr1(l, out);
}