题解 | 练习赛 Round 156
|
12
|
0
|
牛客,练习赛,题解

2406 字
|
29 分钟

A Flower_Rainbow_and_Honey

知识点：枚举、模拟、绝对值

初始坐标的候选只有 $21$ 个。枚举每个 $X$，按 $s$ 依次模拟两步，设当前位置为 $p$、移动后为 $q$；当且仅当 $|q|<|p|$ 时，本步 GPS 信号应为 $\texttt{C}$，否则应为 $\texttt{F}$。只要有一步信号不匹配，就放弃当前的 $X$；找到一个完整匹配的坐标即可输出。

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

void solve() {
    string s, t;
    cin >> s >> t;
    for (int x = -10; x <= 10; ++x) {
        int p = x;
        bool ok = 1;
        for (int i = 0; i < 2; ++i) {
            int q = p + (s[i] == 'L' ? -1 : 1);
            char c = abs(q) < abs(p) ? 'C' : 'F';
            if (q < -10 || q > 10 || c != t[i]) {
                ok = 0;
                break;
            }
            p = q;
        }
        if (ok) return cout << x << endl, void();
    }
    cout << "T_T" << endl;
}

B Flower_Rainbow_and_Victory

知识点：极小极大、分类计数、博弈

四种牌型中，$\texttt{0B}$ 只对 $\texttt{Rainbow}$ 有效，$\texttt{1R}$ 只对 $\texttt{Flower}$ 有效，$\texttt{0R}$ 和 $\texttt{1B}$ 对双方都有效。记三类牌的数量分别为 $A,B,C$。

把分差定义为 $\texttt{Rainbow}$ 得分减 $\texttt{Flower}$ 得分。设 $V_R(A,B,C)$、$V_F(A,B,C)$ 分别表示轮到 $\texttt{Rainbow}$、$\texttt{Flower}$ 时的最优分差。对三类牌分别枚举“当前玩家取走哪一类”，并按取牌者对分差的影响加上 $1$ 或减去 $1$，对牌数归纳可得。
具体地，轮到 $\texttt{Rainbow}$ 时，取 $\texttt{0B}$、$\texttt{1R}$、双方有效牌的候选值依次为

$$1+V_F(A-1,B,C), V_F(A,B-1,C), 1+V_F(A,B,C-1);$$

轮到 $\texttt{Flower}$ 时对应为

$$V_R(A-1,B,C)、-1+V_R(A,B-1,C)、-1+V_R(A,B,C-1)$$

取其中最小值。将这组递推代入归纳即可得到

$$V_R(A,B,C)=\left\lceil\frac{A+B+C}{2}\right\rceil-B-\left\lfloor\frac{C}{2}\right\rfloor\\V_F(A,B,C)=\left\lfloor\frac{A+B+C}{2}\right\rfloor-B-\left\lceil\frac{C}{2}\right\rceil$$

初始轮到 $\texttt{Rainbow}$，所以只需计算

$$d=\left\lceil\frac n2\right\rceil-B-\left\lfloor\frac C2\right\rfloor .$$

$d$ 的正负分别对应 $\texttt{Rainbow}$ 获胜、平局、$\texttt{Flower}$ 获胜。

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

void solve() {
    int n, b = 0, c = 0;
    string s, t;
    cin >> n >> s >> t;

    for (int i = 0; i < n; ++i) {
        if (s[i] == '0' && t[i] == 'B') continue;
        if (s[i] == '1' && t[i] == 'R')
            ++b;
        else
            ++c;
    }

    int d = (n + 1) / 2 - b - c / 2;

    if (d > 0)
        cout << "Rainbow" << endl;
    else if (d < 0)
        cout << "Flower" << endl;
    else
        cout << "Draw" << endl;
}

C Flower_Rainbow_and_Firework

知识点：树的直径、度数上界、构造

令
$$D=\min(d,n-1).$$
当 $n>2$ 且 $k=1$ 时，连通树的最大度数不可能为 $1$，直接无解。

先看容量上界。树的中心在直径为偶数时是一个点，在直径为奇数时是一条边；从中心向外扩展时，根最多有 $k$ 个孩子，其他节点最多有 $k-1$ 个孩子。因此直径不超过 $D$ 时，节点数至多为
$$M(2r)=1+k\sum_{i=0}^{r-1}(k-1)^i,\\M(2r+1)=2\sum_{i=0}^{r}(k-1)^i.$$
构造时先建立长度为 $D$ 的骨干路径 $1-2-\cdots-(D+1)$。对第 $i$ 个骨干节点设置
$$\operatorname{rem}_i=\min(i-1,D+1-i),$$
它表示从该点向骨干外侧还能延伸的最大层数；新挂出的子节点令 $\operatorname{rem}$ 减去 $1$。从骨干中心开始遍历，若当前节点仍有深度余量且度数小于 $k$，就不断挂接新节点，再继续处理这些节点和骨干上的邻居。这样会把每个可用的分支位置全部填满，正好实现上面的最大容量，同时始终保持直径不超过 $D$。

若所有可扩展位置都用完后仍有节点未接入，则 $n>M(D)$，由容量上界可知无解；否则输出构造出的边。

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

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

    if (n > 2 && k == 1) return cout << -1 << endl, void();

    int D = min(d, n - 1);
    int ptr = D + 2;

    vector<vector<int>> g(n + 1);
    vector<int> deg(n + 1), rem(n + 1, -1), vis(n + 1);
    vector<pii> edges;

    auto add = [&](int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
        ++deg[u];
        ++deg[v];
        edges.push_back({u, v});
    };

    for (int i = 1; i <= D; ++i) add(i, i + 1);

    for (int i = 1; i <= D + 1; ++i) rem[i] = min(i - 1, D + 1 - i);

    vector<pii> st{{D / 2 + 1, 0}};

    while (ptr <= n && !st.empty()) {
        auto [u, parent] = st.back();
        st.pop_back();

        if (vis[u]) continue;
        vis[u] = 1;

        int sz = g[u].size();

        while (rem[u] > 0 && deg[u] < k && ptr <= n) {
            int v = ptr++;
            add(u, v);
            rem[v] = rem[u] - 1;
            st.push_back({v, u});
        }

        for (int i = 0; i < sz; ++i) {
            int v = g[u][i];
            if (v != parent && !vis[v]) {
                st.push_back({v, u});
            }
        }
    }

    if (ptr <= n) return cout << -1 << endl, void();

    for (auto [u, v] : edges) cout << u << " " << v << endl;
}

D Flower_Rainbow_and_Cherish

知识点：树形 DP、按位拆分、子树统计、模运算

把原式按祖先关系展开，就是对所有满足 $v\in\operatorname{subtree}(u)$ 的有序对 $(u,v)$ 计入距离权重。先记总距离权重为
$$W=\sum_{u=1}^{n}\sum_{v\in\operatorname{subtree}(u)}\operatorname{dist}(u,v).$$
反向遍历根树，维护 $\operatorname{sz}_u$ 和 $\operatorname{sm}_u=\sum_{v\in\operatorname{subtree}(u)}\operatorname{dep}(v)$，即可用
$$\operatorname{sm}_u-\operatorname{dep}(u)\operatorname{sz}_u$$
累加出 $W$。

考虑权值的第 $k$ 位。对每个子树维护 $\texttt{cnt}[u][b]$（该位为 $b$ 的节点数）和 $\texttt{sumd}[u][b]$（这些节点的深度和）。若 $a_u$ 的第 $k$ 位为 $b$，则子树中与它该位不同的节点贡献
$$\operatorname{sumd}_u[1-b]-\operatorname{dep}(u)\operatorname{cnt}_u[1-b].$$
把所有 $u$ 相加记为 $one_k$，它就是这一位为 $1$ 的距离总权重；这一位为 $0$ 的权重则为 $W-one_k$。

异或的每一位互相独立，因此固定 $X$ 的第 $k$ 位后，这一位的代价为
$$2^k\begin{cases}one_k,&X_k=0,\\W-one_k,&X_k=1.\end{cases}$$
每一位取较小者即可。因为 $a_i<2^{31}$，只需处理位 $0$ 到位 $30$；更高位设为 $0$ 一定不劣。

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

using Z = MInt<mod>;

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

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> p(n + 1), d(n + 1), ord;

    vector<int> st = {1};
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        ord.push_back(u);

        for (int v : g[u]) {
            if (v == p[u]) continue;
            p[v] = u;
            d[v] = d[u] + 1;
            st.push_back(v);
        }
    }

    vector<int> sz(n + 1), sm(n + 1);
    int tot = 0;

    for (int i = n - 1; i >= 0; --i) {
        int u = ord[i];

        ++sz[u];
        sm[u] += d[u];

        tot += sm[u] - d[u] * sz[u];

        if (p[u]) {
            sz[p[u]] += sz[u];
            sm[p[u]] += sm[u];
        }
    }

    Z ans = 0, pw = 1;

    for (int k = 0; k <= 30; ++k) {
        vector<pii> cnt(n + 1), sumd(n + 1);
        int one = 0;

        for (int i = n - 1; i >= 0; --i) {
            int u = ord[i];
            int b = (a[u] >> k) & 1;

            ++cnt[u][b];
            sumd[u][b] += d[u];

            int o = b ^ 1;

            one += sumd[u][o] - d[u] * cnt[u][o];

            if (p[u]) {
                for (int j = 0; j < 2; ++j) {
                    cnt[p[u]][j] += cnt[u][j];
                    sumd[p[u]][j] += sumd[u][j];
                }
            }
        }

        ans += Z(min(one, tot - one)) * pw;
        pw += pw;
    }

    cout << ans << endl;
}

E Flower_Rainbow_and_Module

知识点：状态压缩 DP、连续段状态、路径重构

先记不扣奖励时的原始花费。若选择序列为 $b_1,b_2,\ldots,b_\ell$，则
$$\operatorname{raw}=\sum_{j=1}^{\ell}j\cdot a_{b_j}.$$
令 $\texttt{dp}[\texttt{mask}][\texttt{last}][\texttt{st}]$ 表示恰好选择 $\texttt{mask}$ 中的模块、最后一个是 $\texttt{last}$，且当前同色连续段长度为 $\texttt{st}$ 时的最小原始花费。$\texttt{st}=d$ 表示奖励已经触发，之后继续保持为 $d$ 即可。

从状态后面接入未选模块 $\texttt{nxt}$ 时，新增代价为
$$(|\texttt{mask}|+1)a_{\texttt{nxt}},$$
连续段状态按颜色是否相同转移；对已经达到 $d$ 的状态进行封顶，正好表达奖励最多触发一次。

最终若 $\texttt{st}=d$，实际花费为 $\max(0,\operatorname{raw}-W)$，否则为 $\operatorname{raw}$。可以只保留 $\operatorname{raw}\le m+W$ 的状态：未触发奖励时它必须不超过 $m$，触发奖励后也不可能通过扣除 $W$ 降到 $m$ 以下。枚举所有终态，先最大化已选模块数，再最小化实际花费；代码最后按转移等式反向寻找前驱，恢复一条序列。

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

constexpr int inf = 2e18 + 9;

void solve() {
    int n, m, d, w;
    cin >> n >> m >> d >> w;

    vector<int> a(n), c(n);
    for (auto &v : a) cin >> v;
    for (auto &v : c) cin >> v;

    int z = 1LL << n, lim = m + w;
    auto id = [&](int msk, int lst, int st) { return (msk * n + lst) * d + st - 1; };
    auto go = [&](int st, int lst, int nxt) {
        if (st == d) return d;
        return c[lst] == c[nxt] ? st + 1 : 1;
    };
    vector<int> pc(z);
    for (int msk = 1; msk < z; ++msk) pc[msk] = pc[msk >> 1] + (msk & 1);
    vector<int> dp(z * n * d, inf);

    for (int i = 0; i < n; ++i) {
        if (a[i] <= lim) {
            dp[id(1LL << i, i, 1)] = a[i];
        }
    }

    for (int msk = 1; msk < z; ++msk) {
        int cnt = pc[msk];

        for (int lst = 0; lst < n; ++lst) {
            if (!(msk >> lst & 1)) continue;

            for (int st = 1; st <= d; ++st) {
                int cur = dp[id(msk, lst, st)];
                if (cur == inf) continue;

                for (int nxt = 0; nxt < n; ++nxt) {
                    if (msk >> nxt & 1) continue;

                    int nst = go(st, lst, nxt);
                    int nms = msk | (1LL << nxt);
                    int val = cur + (cnt + 1) * a[nxt];

                    if (val > lim) continue;
                    dp[id(nms, nxt, nst)] = min(dp[id(nms, nxt, nst)], val);
                }
            }
        }
    }

    int bc = 0, res = inf;
    int bms = -1, bls = -1, bst = -1;

    for (int msk = 1; msk < z; ++msk) {
        for (int lst = 0; lst < n; ++lst) {
            if (!(msk >> lst & 1)) continue;

            for (int st = 1; st <= d; ++st) {
                int raw = dp[id(msk, lst, st)];
                if (raw == inf) continue;

                int cst = st == d ? max(0LL, raw - w) : raw;
                if (cst > m) continue;

                int cnt = pc[msk];
                if (cnt > bc || (cnt == bc && cst < res)) {
                    bc = cnt, res = cst, bms = msk;
                    bls = lst, bst = st;
                }
            }
        }
    }

    if (bms == -1) return cout << -1 << endl, void();

    vector<int> ans;
    int msk = bms, lst = bls, st = bst;

    while (msk) {
        ans.push_back(lst);

        int pms = msk ^ (1LL << lst);
        int cur = dp[id(msk, lst, st)];
        int add = pc[msk] * a[lst];
        bool ok = false;

        if (!pms) {
            ok = st == 1 && cur == a[lst];
        } else {
            for (int prv = 0; prv < n && !ok; ++prv) {
                if (!(pms >> prv & 1)) continue;

                for (int pst = 1; pst <= d; ++pst) {
                    int pv = dp[id(pms, prv, pst)];
                    if (pv == inf) continue;

                    if (go(pst, prv, lst) == st && pv + add == cur) {
                        msk = pms;
                        lst = prv;
                        st = pst;
                        ok = true;
                        break;
                    }
                }
            }
        }

        if (!ok) return;
        if (!pms) break;
    }
    reverse(ans.begin(), ans.end());
    cout << res << " " << ans.size() << endl;

    for (auto x : ans) cout << x + 1 << " ";
    cout << endl;
}

F Flower_Rainbow_and_Serenity

知识点：离线预处理、树状数组、前缀最值、区间聚合

固定四元组的外端点 $t=i_1$、$j=i_4$，再令 $p=i_3$。对固定的 $t,p$，第二个下标 $i_2$ 只影响第一条不等式，所以先取最优值
$$u_p=a_t-\min_{t<r<p}a_r.$$
于是固定外端点时能达到的最大阈值为
$$w_{t,j}=\min\left(a_j-a_t,\ \max_{t+2\le p<j}\min(u_p,a_p-a_j)\right).$$
若没有合法的 $p$，令 $w_{t,j}=-1$。

令 $z_p=a_p-u_p$，则
$$\min(u_p,a_p-a_j)=\begin{cases}u_p, & z_p\ge a_j,\\a_p-a_j, & z_p<a_j.\end{cases}$$
因此按 $z_p$ 离散化后，可以用一个树状数组维护满足 $z_p\ge a_j$ 的最大 $u_p$，另一个维护满足 $z_p<a_j$ 的最大 $a_p$；随着 $j$ 增大只需插入新出现的 $p=j-1$，每个固定的 $t$ 总共处理 $\mathcal{O}(n)$ 个候选。

设 $H_{L,R}$ 为区间内所有四元组可达到的最大 $K$：
$$H_{L,R}=\max_{\substack{L\le t<j\le R}}w_{t,j}.$$

扫描右端点 $R$ 时，先对当前 $R$ 做后缀最大值，得到所有 $t\ge L$ 的 $\texttt{w}[t][R]$；再与之前的 $\texttt{cur}[L]$ 取最大，就得到 $H_{L,R}$。收集全部区间的 $H$ 后排序，询问 $K$ 的答案就是其中不小于 $K$ 的元素个数，用 $\texttt{lower\_bound}$ 直接求出。

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

constexpr int inf = 2e18 + 9;

template <class T> struct BIT {...}; // 树状数组

struct P {
    int v = -inf;

    P() = default;
    P(int _v) : v(_v) {}

    P &operator+=(const P &o) {
        v = max(v, o.v);
        return *this;
    }
};

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

    vector<int> a(n);
    for (auto &x : a) cin >> x;

    vector<int> w(n * n, -1);

    for (int t = 0; t < n; ++t) {
        vector<int> u(n), z;
        int mn = inf;

        for (int p = t + 1; p + 1 < n; ++p) {
            if (p >= t + 2) {
                u[p] = a[t] - mn;
                z.push_back(a[p] - u[p]);
            }
            mn = min(mn, a[p]);
        }

        if (z.empty()) continue;

        sort(z.begin(), z.end());
        z.erase(unique(z.begin(), z.end()), z.end());

        int sz = z.size();
        BIT<P> bu(sz), bv(sz);

        for (int j = t + 3; j < n; ++j) {
            int p = j - 1;
            int rk = lower_bound(z.begin(), z.end(), a[p] - u[p]) - z.begin();

            bv.modify(rk + 1, P(a[p]));
            bu.modify(sz - rk, P(u[p]));

            int cut = lower_bound(z.begin(), z.end(), a[j]) - z.begin();

            int mid = max(bu.ask(sz - cut).v, bv.ask(cut).v - a[j]);

            int val = min(a[j] - a[t], mid);
            if (val >= 0) {
                w[t * n + j] = val;
            }
        }
    }

    vector<int> cur(n, -1), suf(n + 1, -1), all;

    for (int r = 0; r < n; ++r) {
        suf[n] = -1;

        for (int t = n - 1; t >= 0; --t) {
            int x = (t < r ? w[t * n + r] : -1);
            suf[t] = max(suf[t + 1], x);
        }

        for (int l = 0; l <= r; ++l) {
            cur[l] = max(cur[l], suf[l]);
            all.push_back(cur[l]);
        }
    }

    sort(all.begin(), all.end());

    while (q--) {
        int k;
        cin >> k;
        auto it = lower_bound(all.begin(), all.end(), k);
        cout << all.end() - it << endl;
    }
}

约定

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii array<int, 2>
#define endl "\n"

void solve() {
    
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout << fixed << setprecision(20);
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

使用到的算法模板见 $\texttt{github}$ 仓库 林月的XCPC模板库

暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

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

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇