题解 | 练习赛 Round 153
|
14
|
0
|
牛客,练习赛,题解

2019 字
|
24 分钟

A 字符插入

知识点：子序列计数、贡献、贪心

插入的字符固定为 $\texttt{6}$ ，原串中已有的 $\texttt{2026}$ 数量与插入位置无关，因此只需最大化新产生的 $\texttt{2026}$ 数量。若把 $\texttt{6}$ 插在前 $i$ 个字符之后，那么新增贡献正好等于前缀 $s_1\sim s_i$ 中子序列 $\texttt{202}$ 的个数。

随着 $i$ 从左到右增大，前缀中的 $\texttt{202}$ 数量不会减少，因此最优位置一定可以取 $i=|s|$，即插在最后。

时间复杂度 $\mathcal{O}(1)$。

void solve() {
    string s;
    cin >> s;
    cout << s.size() << endl;
}

B 前缀和

知识点：贡献拆分、前缀和、贪心

原序列中 $a_j$ 对所有前缀和总和的贡献系数为 $n-j+1$。若删除第 $i$ 个数：

  • $i$ 前面的每个数贡献系数都会少 $1$，总损失为 $\sum_{j<i} a_j$；
  • $a_i$ 本身被删除，损失为 $(n-i+1)a_i$；
  • $i$ 后面的数虽然位置前移，但贡献系数不变。

因此删除第 $i$ 个位置后的答案等于原答案减去
$$
\sum_{j<i} a_j+(n-i+1)a_i
$$
要让剩余前缀和总和最大，只需找到上式最小的位置。扫描时维护前缀和即可。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int S = 0, mn = INF, loc = -1;
    for (int i = 0; i < n; ++i) {
        S += a[i];
        if (S + (n - i - 1) * a[i] < mn) mn = S + (n - i - 1) * a[i], loc = i;
    }
    cout << loc + 1 << endl;
}

C 博弈

知识点：奇偶性、最大子段和、分类讨论

一次操作中，第 $l,l+2,l+4,\dots$ 个被选中的位置会改变奇偶性，其他位置奇偶性不变。也就是说，Alice 实际上可以在原数组下标奇偶性相同的一类位置中，选择一段连续子段并翻转这些位置的奇偶性。

设当前奇数个数为 $x$。对每个会被翻转的位置，若原来是偶数，则奇数个数增加 $1$；若原来是奇数，则奇数个数减少 $1$。于是把同奇偶下标上的元素看成一个序列，偶数记为 $+1$，奇数记为 $-1$，问题变为在两类下标中取最大子段和，得到最大增量 $g$。

若 $2(x+g)>n$，则 $\texttt{Alice}$ 可以使奇数严格多于偶数，输出 $\texttt{Alice}$；否则输出 $\texttt{Alice}$。不操作相当于增量为 $0$，最大子段和取非负即可。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int x = 0;
    for (int i = 0; i < n; ++i) x += a[i] & 1;
    auto ssolve = [&](int st) {
        int cur = 0, mx = 0;
        for (int i = st; i < n; i += 2) {
            cur += (a[i] & 1) ? -1 : 1;
            cur = max(cur, 0LL);
            mx = max(mx, cur);
        }
        return mx;
    };
    if (2 * (x + max(ssolve(0), ssolve(1))) > n)
        cout << "Alice" << endl;
    else
        cout << "Bob" << endl;
}

D 异或和I

知识点：动态规划、前缀异或、计数 DP

记前缀异或为 $pre_i$。若最后一段异或和为 $x$，上一段结束位置的前缀异或必须是 $pre_i\oplus x$；同时为了满足非降，上一段的最后一段异或和必须不超过 $x$。

设 $best[p][v]$ 表示：在已经处理过的某个前缀中，前缀异或为 $p$，且最后一段异或和不超过 $v$ 时，能得到的最多段数；$ways[p][v]$ 表示达到该段数的方案数。初始空前缀满足 $best[0][v]=0$。

处理到当前位置、当前前缀异或为 $pre$ 时，枚举新最后一段的异或和 $x$：
$$
elen[x]=best[pre\oplus x][x]+1
$$
这表示接上一段异或和不超过 $x$ 的最优划分。随后对 $elen$ 做前缀最大值及方案数累加，得到“最后一段异或和不超过 $v$”的状态，再用当前前缀异或更新 $best[pre][v]$。最后 $v$ 取异或值上界即可得到答案。

由于 $a_i\le 3000$，所有异或值都小于 $4096$。

时间复杂度 $\mathcal{O}(4096n)$。

array<int, 4096> best[4096], clen, elen;
array<Z, 4096> ways[4096], ccnt, ecnt;

void solve() {
    int n, _;
    cin >> n >> _;
    Z::setMod(_);
    for (int i = 0; i < 4096; ++i) best[i].fill(-INF), ways[i].fill(0);
    best[0].fill(0), ways[0].fill(1);
    int pre = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        pre ^= a;
        elen.fill(-INF), ecnt.fill(0);
        for (int j = 0; j < 4096; ++j) {
            int ps = pre ^ j;
            if (best[ps][j] == -INF) continue;
            elen[j] = best[ps][j] + 1, ecnt[j] = ways[ps][j];
        }

        int mx = -INF;
        Z cnt = 0;
        for (int j = 0; j < 4096; ++j) {
            if (elen[j] > mx)
                mx = elen[j], cnt = ecnt[j];
            else if (elen[j] == mx && mx != -INF)
                cnt += ecnt[j];
            clen[j] = mx, ccnt[j] = cnt;
        }

        for (int j = 0; j < 4096; ++j) {
            if (clen[j] > best[pre][j])
                best[pre][j] = clen[j], ways[pre][j] = ccnt[j];
            else if (clen[j] == best[pre][j])
                ways[pre][j] += ccnt[j];
        }
    }
    cout << clen[4095] << " " << ccnt[4095] << endl;
}

E 异或和II

知识点：$\texttt{Lucas}$ 定理、组合数奇偶性、按位贡献

异或答案可以逐位考虑。某一位为 $1$ 的子序列 $\texttt{OR}$ 值会对答案这一位贡献一次，因此只关心这类子序列数量的奇偶性。

设当前有 $n$ 个数，其中第 $b$ 位为 $0$ 的数有 $z$ 个。长度不超过 $k$ 的非空子序列总数奇偶性记为 $F(n,k)$，其中第 $b$ 位 $\texttt{OR}$ 为 $0$ 的子序列只能从这 $z$ 个数中选，数量奇偶性为 $F(z,k)$。所以答案第 $b$ 位为
$$
F(n,k)\oplus F(z,k)
$$

利用恒等式
$$
\sum_{i=1}^{k}\binom{n}{i}\equiv \binom{n-1}{k}-1 \pmod 2
$$
再由 $\texttt{Lucas}$ 定理，$\binom{n-1}{k}$ 为奇数当且仅当 $k$ 的每个二进制 $1$ 位都包含在 $n-1$ 中，即 $(k\ \&\ \sim(n-1))=0$。因此 $F(n,k)$ 可以 $\mathcal{O}(1)$ 求出。

维护每一位当前为 $1$ 的个数即可支持单点修改。每次询问枚举 $0\sim 30$ 位计算答案。

时间复杂度： $\mathcal{O}(31(n+q))$ 。

void solve() {
    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    array<int, 31> cnt{};

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        for (int j = 0; j < 31; ++j)
            if ((a[i] >> j) & 1) cnt[j]++;
    }

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            int old = a[x];
            if (old == y) continue;

            for (int i = 0; i < 31; ++i) {
                int o = (old >> i) & 1, ne = (y >> i) & 1;
                cnt[i] += ne - o;
            }
            a[x] = y;
        } else {
            int k;
            cin >> k;
            using ull = unsigned long long;
            auto F = [&](ull n, ull k) -> int { return 1 ^ ((k & (~(n - 1))) == 0); };
            int A = F(n, k), ans = 0;
            for (int i = 0; i < 31; ++i)
                if (A ^ F(n - cnt[i], k)) ans |= (1 << i);
            cout << ans << endl;
        }
    }
}

F 下棋

知识点：离线动态连通性、线段树分治、可回滚并查集

固定一种颜色 $c$ 计算其得分。只看所有状态不等于 $c$ 的格子，它们按四联通形成若干连通块；若某个连通块不接触边界，则其中颜色为 $3-c$ 的棋子都会被 $c$ 提走。于是对每个连通块，只需维护两个信息：是否接触边界、其中对方棋子的数量。颜色 $c$ 的得分就是所有“不接触边界”的连通块权值之和。

由于有修改操作，直接在线维护删边很困难。把时间看成 $0\sim q$，离线处理每个对象的存在区间：

  • 若某个格子在一段时间内颜色为 $3-c$，则在这段时间给该格子所在连通块增加权值 $1$；
  • 若相邻两个格子在一段时间内都不等于 $c$，则在这段时间加入这条边。

把这些区间加入时间线段树，DFS 线段树时用可回滚并查集维护当前时间段内的连通性和权值和。进入节点时加入该节点上的所有点权和边，离开节点时回滚；到叶子时即可得到该时刻颜色 $c$ 的得分。分别对 $c=1,2$ 做一遍，得到黑白双方在每个时刻的分数并比较输出即可。

时间复杂度 $\mathcal{O}((nm+q)\log q\log(nm))$。

struct DSU {
    struct Chg {
        int a, b, sa, wa, wb, ba, bb, dead;
    };

    int n, m, dead = 0;
    vector<int> f, siz, w, bd;
    vector<Chg> st;

    DSU() {}
    DSU(int N, int nn, int mm) {
        init(N, nn, mm);
    }

    void init(int N, int nn, int mm) {
        n = nn, m = mm;
        f.resize(N);
        iota(all(f), 0);
        siz.assign(N, 1);
        w.assign(N, 0);
        bd.assign(N, 0);
        st.clear();
        dead = 0;
        FOR(i, 0, N - 1) {
            int x = i / m, y = i % m;
            bd[i] = (x == 0 || x == n - 1 || y == 0 || y == m - 1);
        }
    }

    int find(int x) {
        while (f[x] != x) x = f[x];
        return x;
    }

    int snap() {
        return st.size();
    }

    void rollback(int t) {
        while (st.size() > t) {
            auto c = st.back();
            st.pop_back();
            dead = c.dead;
            if (c.b == -1) {
                w[c.a] = c.wa;
            } else {
                f[c.b] = c.b;
                siz[c.a] = c.sa;
                w[c.a] = c.wa;
                w[c.b] = c.wb;
                bd[c.a] = c.ba;
                bd[c.b] = c.bb;
            }
        }
    }

    void addw(int x) {
        x = find(x);
        st.pb({x, -1, 0, w[x], 0, 0, 0, dead});
        if (!bd[x]) ++dead;
        ++w[x];
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (siz[x] < siz[y]) swap(x, y);
        st.pb({x, y, siz[x], w[x], w[y], bd[x], bd[y], dead});
        if (!bd[x]) dead -= w[x];
        if (!bd[y]) dead -= w[y];
        f[y] = x;
        siz[x] += siz[y];
        w[x] += w[y];
        bd[x] |= bd[y];
        if (!bd[x]) dead += w[x];
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    int N = n * m;
    vector<int> a(N);
    vector<vector<PII>> his(N);

    string s;
    for (int i = 0; i < n; ++i) {
        cin >> s;
        for (int j = 0; j < m; ++j) a[i * m + j] = s[j] - '0';
    }

    for (int i = 1; i <= q; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        --x, --y;
        int id = x * m + y;
        his[id].pb({i, c});
    }

    vector<int> b, w;

    for (int c : {1, 2}) {
        vector<vector<int>> seg(4 * (q + 1) + 5);
        vector<int> ans(q + 1);

        auto add = [&](auto self, int p, int l, int r, int ql, int qr, int v) -> void {
            if (ql > qr) return;
            if (ql <= l && r <= qr) {
                seg[p].pb(v);
                return;
            }
            int mid = (l + r) >> 1;
            if (ql <= mid) self(self, p << 1, l, mid, ql, qr, v);
            if (qr > mid) self(self, p << 1 | 1, mid + 1, r, ql, qr, v);
        };
        auto ins = [&](int l, int r, int v) {
            if (l <= r) add(add, 1, 0, q, l, r, v);
        };

        int o = 3 - c;
        for (int u = 0; u < N; ++u) {
            if (his[u].empty()) {
                if (a[u] == o) ins(0, q, -u - 1);
                continue;
            }
            int cur = 0, val = a[u];
            for (auto [t, nv] : his[u]) {
                if (val == o) ins(cur, t - 1, -u - 1);
                val = nv;
                cur = t;
            }
            if (val == o) ins(cur, q, -u - 1);
        }

        auto build = [&](int u, int v, int d) {
            if (his[u].empty() && his[v].empty()) {
                if (a[u] != c && a[v] != c) ins(0, q, ((u << 2) | d) + 1);
                return;
            }

            auto &A = his[u], &B = his[v];
            int i = 0, j = 0, cur = 0, x = a[u], y = a[v];
            while (i < A.sz || j < B.sz) {
                int nt = q + 1;
                if (i < A.sz) cmin(nt, A[i].fi);
                if (j < B.sz) cmin(nt, B[j].fi);
                if (x != c && y != c) ins(cur, nt - 1, ((u << 2) | d) + 1);
                while (i < A.sz && A[i].fi == nt) x = A[i++].se;
                while (j < B.sz && B[j].fi == nt) y = B[j++].se;
                cur = nt;
            }
            if (x != c && y != c) ins(cur, q, ((u << 2) | d) + 1);
        };

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int u = i * m + j;
                if (j + 1 < m) build(u, u + 1, 0);
                if (i + 1 < n) build(u, u + m, 1);
            }
        }

        DSU dsu(N, n, m);
        auto dfs = [&](auto self, int p, int l, int r) -> void {
            int t = dsu.snap();
            for (auto v : seg[p]) {
                if (v < 0) {
                    dsu.addw(-v - 1);
                } else {
                    --v;
                    int u = v >> 2, d = v & 3;
                    dsu.merge(u, u + (d == 0 ? 1 : m));
                }
            }
            if (l == r) {
                ans[l] = dsu.dead;
            } else {
                int mid = (l + r) >> 1;
                self(self, p << 1, l, mid);
                self(self, p << 1 | 1, mid + 1, r);
            }
            dsu.rollback(t);
        };
        dfs(dfs, 1, 0, q);

        if (c == 1) {
            b = ans;
        } else {
            w = ans;
        }
    }

    for (int i = 0; i <= q; ++i) {
        if (b[i] > w[i]) {
            cout << "Black" << endl;
        } else if (b[i] < w[i]) {
            cout << "White" << endl;
        } else {
            cout << "Draw" << endl;
        }
    }
}

约定

#define int long long
#define pb push_back
using PII = pair<int, int>;
const int INF = numeric_limits<int>::max();
int __INIT__ = []() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout << fixed << setprecision(15);
    return 0;
}();
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇