Visits: 359

【LGR-065】洛谷 11 月月赛 III Div.2

基础字符串练习题

前缀和 + 贪心。

注意「非空子串」。

const int N = 1e5 + 7;
int n, ans = -1;
char s[N];

int main() {
    rds(s, n);
    for (int i = 1, o = 0, k = 0; i <= n; i++) {
        k += (s[i] == '0' ? 1 : -1);
        ans = Max(ans, k - o);
        o = Min(o, k);
    }
    print(ans);
    return 0;
}

基础最短路练习题

由于「保证 $G$ 中不存在简单环使得边权异或和不为 $0$」，因此随便找一条路径即可。

const int N = 1e5 + 7;
int n, m, q, v[N], d[N];
vector< pi > e[N];

void dfs(int x) {
    v[x] = 1;
    for (ui i = 0; i < e[x].size(); i++) {
        int y = e[x][i].fi;
        if (v[y]) continue;
        d[y] = d[x] ^ e[x][i].se;
        dfs(y);
    }
}

int main() {
    rd(n), rd(m), rd(q);
    for (int i = 1, x, y, z; i <= m; i++) {
        rd(x), rd(y), rd(z);
        e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
    }
    dfs(1);
    for (int i = 1, x, y; i <= q; i++) {
        rd(x), rd(y);
        print(d[x] ^ d[y]);
    }
    return 0;
}

基础博弈练习题

首先只跟 $a$ 的奇偶性有关。

其次如果 $a_l$ 为偶数则先手必胜。

否则 $l \sim r$ 中最右边的一个先手必败的位置一定是最右边的奇数位置，而它上一个先手必败的位置一定是这个位置的 $m$ 个位置以前的最右边的奇数位置，依次类推。

可以发现这个关系形成一个树形结构，那么判断最右边的奇数位置在不在 $l$ 的子树中即可，可以用 dfs 序判断。

const ui N = 1e6 + 7;
int n, m, q, o, a[N], p[N], L[N], R[N], num, A, B, C, P;
ui ans;
vector< int > e[N];

inline int rnd() {
    return A = (A * B + C) % P;
}

void dfs(int x) {
    L[x] = ++num;
    for (ui i = 0; i < e[x].size(); i++) dfs(e[x][i]);
    R[x] = num;
}

int main() {
    rd(n), rd(m), ++m, rd(q), rd(o);
    for (int i = 1, j = 0; i <= n; i++) {
        rd(a[i]), a[i] &= 1;
        if (a[i]) {
            j = i;
            e[p[Max(0,i-m)]].pb(i);
        }
        p[i] = j;
    }
    dfs(0);
    if (o) rd(A), rd(B), rd(C), rd(P);
    for (int i = 1; i <= q; i++) {
        int l, r;
        if (o) {
            l = rnd() % n + 1, r = rnd() % n + 1;
            if (l > r) swap(l, r);
        } else rd(l), rd(r);
        if (!a[l] || L[l] > L[p[r]] || L[p[r]] > R[l]) ans += 1ll * i * i;
    }
    print(ans);
    return 0;
}

基础最优化练习题

首先不考虑 $a$ 的限制，那么一个位置是加是减取决于这个位置对答案的贡献是正是负，而对答案的贡献显然为 $w$ 的后缀和。

再考虑 $a$ 的限制，如果一个位置超出了限制，则应该不断地从之前贡献最小的位置减掉贡献，直到不超出，用一个堆维护即可。

时间复杂度 $\mathcal O(n \log n)$。

const int N = 1e6 + 7;
int n, k, a[N], now;
ll b[N], ans;
pq< pi > q;

int main() {
    rd(n), rd(k);
    for (int i = 1; i <= n; i++) rd(a[i]);
    for (int i = 1; i <= n; i++) rd(b[i]);
    for (int i = n; i; i--) b[i] += b[i+1];
    for (int i = 1; i <= n; i++) {
        if (b[i] >= 0) now += k, ans += k * b[i], q.push(mp(-b[i], k << 1));
        else now -= k, ans -= k * b[i];
        while (now > a[i]) {
            pi o = q.top();
            q.pop();
            int w = Min(o.se, now - a[i]);
            now -= w, ans += w * o.fi;
            if ((o.se -= w)) q.push(o);
        }
    }
    print(ans);
    return 0;
}