Codeforces Round #900 (Div. 3)

EternalEpic · 2023-09-27 11:04:49 · 个人记录

三年之后第一次打比赛，用小号打了场 Div.3 ，居然没有AK，感觉实力退步到小学了。

A. How Much Does Daytona Cost?

若只判断题，只要判断 \{ a_n \} 中是否存在 k 即可。

B. Aleksa and Stack

构造方法不唯一，我直接输出奇数列，显然正确。

C. Vasilije in Cacak

若只判断题，只要判断前 k 个数的和会不会超过 x ，以及后 k 个数的和会不会小于 x 就行了。

D. Reverse Madness

易知 \{ r_n \} 单调增， 故可以二分 x 的位置。至于调换操作直接用一颗平衡树解决就行了。

const int Maxn = 2e5 + 5;
int T, n, k, q, l[Maxn], r[Maxn], x[Maxn];
char str[Maxn];

struct FHQTreap {
    int lson[Maxn], rson[Maxn], data[Maxn], tag[Maxn];
    int rnd[Maxn], sze[Maxn], seed, root, tot;

    FHQTreap(void) {
        Ms(lson, 0), Ms(data, 0), Ms(tag, 0);
        Ms(sze, 0), Ms(rnd, 0), root = 0;
        Ms(rson, 0), tot = 0, seed = 1;
    }

    void clear(void) {
        root = 0, tot = 0, seed = 1;
    } 

    inline int _rand(void) { return seed *= 482711; }
    inline int newnode(int val) { tot++; data[tot] = val, rnd[tot] = _rand(), sze[tot] = 1, lson[tot] = rson[tot] = 0, tag[tot] = 0; return tot; }
    inline void pushup(int pos) { sze[pos] = sze[lson[pos]] + sze[rson[pos]] + 1; }
    inline void pushdown(int pos) {
        if (!pos || !tag[pos]) return;
        swap(lson[pos], rson[pos]);
        tag[lson[pos]] ^= 1, tag[rson[pos]] ^= 1;
        tag[pos] = 0; return;
    }

    inline void split(int pos, int val, int &x, int &y) {
        if (!pos) { x = y = 0; return; } pushdown(pos);
        if (sze[lson[pos]] + 1 <= val) x = pos, split(rson[pos], val - sze[lson[pos]] - 1, rson[pos], y);
        else y = pos, split(lson[pos], val, x, lson[pos]); pushup(pos);
    }

    inline int merge(int x, int y) {
        if (!x || !y) return x + y; pushdown(x), pushdown(y);
        if (rnd[x] < rnd[y]) return rson[x] = merge(rson[x], y), pushup(x), x;
        else return lson[y] = merge(x, lson[y]), pushup(y), y;
    }

    inline void insert(int val) {
        int x, y, pos = newnode(val);
        split(root, val, x, y);
        root = merge(merge(x, pos), y);
    }

    inline void remove(int val) {
        int x, y, z;
        split(root, val - 1, x, y);
        split(y, val, y, z); if (!y) return;
        y = merge(lson[y], rson[y]);
        root = merge(merge(x, y), z);
    }

    inline void reverse(int l, int r) {
        int x, y, z;
        split(root, r, x, y);
        split(x, l - 1, x, z);
        tag[z] ^= 1; root = merge(merge(x, z), y);
    }

    inline void search(int pos) {
        if (!pos) return;
        pushdown(pos);
        search(lson[pos]);
        putchar(str[data[pos]]);
        search(rson[pos]);
    }
} treap;

signed main(void) {
//  ios :: sync_with_stdio(false);
    read(T); while (T--) {
        read(n), read(k); readstr(str + 1);
        treap.clear(); for (int i = 1; i <= n; i++) treap.insert(i);
        for (int i = 1; i <= k; i++) read(l[i]);
        for (int i = 1; i <= k; i++) read(r[i]);
        read(q);
        for (int i = 1; i <= q; i++) {
            read(x[i]);
            int m = lower_bound(r + 1, r + k + 1, x[i]) - r;
            int L = min(x[i], l[m] + r[m] - x[i]),
                R = max(x[i], l[m] + r[m] - x[i]);
            treap.reverse(L, R);
//          reverse(str + L, str + R + 1);
        }
        treap.search(treap.root); putchar('\n');
    }
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

当然更简单的方法是打交换标记，贴一段 jiangly 的代码：

void solve() {
    int n, k;
    std::cin >> n >> k;

    std::string s;
    std::cin >> s;

    std::vector<int> l(k), r(k);
    for (int i = 0; i < k; i++) {
        std::cin >> l[i];
        l[i]--;
    }
    for (int i = 0; i < k; i++) {
        std::cin >> r[i];
        r[i]--;
    }

    int q;
    std::cin >> q;

    std::vector<int> f(n);

    while (q--) {
        int x;
        std::cin >> x;
        x--;
        f[x] ^= 1;
    }

    for (int i = 0; i < k; i++) {
        int rev = 0;
        for (int j = l[i]; j <= l[i] + r[i] - j; j++) {
            rev ^= f[j] ^ f[l[i] + r[i] - j];
            if (rev) {
                std::swap(s[j], s[l[i] + r[i] - j]);
            }
        }
    }
    std::cout << s << "\n";
}

E. Iva & Pav

考试时候脑子坏了，写了两个log的做法。实际上用ST表维护区间按位与和就行。 贴一段脑残二分线段树做法：

const int Maxn = 2e5 + 5;
int T, n, a[Maxn], q, k;

struct SegmentTree {
    int t[Maxn << 2];
    SegmentTree(void) { Ms(t, 0); }
    void clear(void) { Ms(t, 0); }
    inline void pushup(int pos) { t[pos] = t[pos << 1] & t[pos << 1 | 1]; }

    inline void build(int pos, int l, int r) {
        if (l == r) return (void) (t[pos] = a[l]);
        int mid = l + r >> 1;
        build(pos << 1, l, mid);
        build(pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }

    inline int query(int pos, int l, int r, int L, int R) {
        if (L <= l && R >= r) return t[pos];
        int mid = l + r >> 1, ret = INT_MAX;
        if (L <= mid) ret &= query(pos << 1, l, mid, L, R);
        if (R > mid) ret &= query(pos << 1 | 1, mid + 1, r, L, R);
        return ret;
    }
} sgt;

inline int check(int x, int y) {
    int l = x, r = y, ans = x;
    while (l <= r) {
        int mid = l + r >> 1;
        if (sgt.query(1, 1, n, x, mid) >= k) l = mid + 1, ans = mid;
        else r = mid - 1;
    } return ans;
}

signed main(void) {
    int l;
    for (read(T); T; T--) {
        read(n);
        for (int i = 1; i <= n; i++) read(a[i]);
        sgt.build(1, 1, n); read(q);
        for (int i = 1; i <= q; i++) {
            read(l), read(k);
            if (a[l] < k) {
                writeln(-1, i == q ? '\n' : ' ');
            } else {
                int r = check(l, n);
                writeln(r, i == q ? '\n' : ' ');
            }
        }
    }
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

F. Vasilije Loves Number Theory

由题意知只要满足 n \equiv 0 \pmod{d(n)} 就存在满足条件的 a 可是累乘 x 会导致 n 爆炸，所以记录当前的唯一分解的指数，并时刻保持取余运算：

int T, q, n;

const int Maxn = 1e6 + 5; 
int prime[80000], cnt;
int vis[Maxn], d, sum[Maxn];

inline void doit(int x, int t = 1) {
    while (x > 1) {
        int p = vis[x];
        x /= p;
        d /= sum[p] + 1;
        sum[p] += t;
        d *= sum[p] + 1;
    }
}

vector <int> vec;

signed main(void) {
    vis[1] = 0; d = 1;
    for (int i = 2, upEdge = 1e6 + 1; i <= upEdge; i++) {
        if (!vis[i]) prime[++cnt] = i, vis[i] = i;
        for (int j = 1; j <= cnt; j++) {
            if (i > upEdge / prime[j]) break;
            vis[i * prime[j]] = prime[j];
            if (prime[j] == vis[i]) break;
        }
    }

    for (read(T); T; T--) {
        read(n), read(q); vec.push_back(n); doit(n);
        for (int opt, x; q; q--) {
            read(opt);
            if (opt == 1) {
                read(x); vec.push_back(x); doit(x);
                int ret = 1;
                for (auto v : vec) ret = 1ll * ret * v % d;
                if (ret != 0) {
                    puts("NO");
                } else {
                    puts("YES");
                }
            } else {
                while (vec.size() > 1) doit(vec.back(), -1), vec.pop_back();
                puts("");
            }
        }
        while (!vec.empty()) doit(vec.back(), -1), vec.pop_back();
    }
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

G. wxhtzdy ORO Tree

赛时没来得及想出来，先鸽了，咕咕咕。