2026多校冲刺省选模拟赛5
Link
A. 粉兔的冰红茶(icetea)
比较牛的题
设一颗完全二叉树的节点 \(x\) 以及他的左儿子 \(ls\) 和右儿子 \(rs\)，\(f_a(x)\) 是以 \(x\) 为根当前位置放 \(a\) 的不和谐值的最小值。
则有 \(f_a(x) = f_b(ls) + f_c(rs) + (a - b)^2 + (a - c) ^ 2\) ，发现 \(f_a(x)\) 是一个二次函数的形式，可以线段树维护，然后就可以做了，据zxkqwq说十分卡常熟。
说说我的赛时唐诗做法。
手推了样例之后发现可以转化成 \((Sum_{rs} - Sum_{ls}) ^ 2\) 乘上一个系数，然后这个系数和层数有关。
然后考虑系数是多少。手推的前 \(4\) 项是 \(1, 2, 12, 44\)。实际上是假的。
然后放到OEIS上发现啥也没用。
赛后kinggojianofyue用打表程序打出了是 \(2^i \times (2^i - 1)\)，然后可以轻松做。因为是完全二叉树，暴力的复杂度是对的。
还是贴一下代码吧。
signed main(){cin >> n >> q; int N = (1 << n) - 1;for(int i = (N + 1) >> 1; i <= N; ++i) cin >> a[i];for(int i = 1; i <= 100; ++i) f[i] = qpow(2, i - 1) * (qpow(2, i - 1) - 1) % mod; for(int i = 1; i <= 100; ++i) f[i] = qpow(f[i], mod - 2);for(int i = 1; i <= (N >> 1); ++i) c[i] = f[n - __lg(i)];for(int i = ((N + 1) >> 1) - 1; i >= 1; --i){a[i] = (a[i << 1] + a[i << 1 | 1]) % mod;ans += (a[i << 1] - a[i << 1 | 1]) * (a[i << 1] - a[i << 1 | 1]) % mod * c[i] % mod; ans %= mod; }cout << ans << '\n';while(q--){int p, hp; cin >> p >> hp;int now = p >> 1; while(now) ans = (ans - (a[now << 1] - a[now << 1 | 1]) * (a[now << 1] - a[now << 1 | 1]) % mod * c[now] % mod + mod) % mod, now >>= 1; a[p] = hp; now = p >> 1;while(now){ans = (ans + (a[now << 1] - a[now << 1 | 1]) * (a[now << 1] - a[now << 1 | 1]) % mod * c[now] % mod) % mod; a[now] = (a[now << 1] + a[now << 1 | 1]) % mod;now >>= 1;} cout << ans << '\n';}return 0;
}
B. 粉兔的原神(genshin)
发现对于每个点只有 \(k\) 个点的 \(dist_{i,j}\) 是未知的。
考虑仅仅对这些点跑最短路，我们可以算出每对没有连边的点，求出他们之间的最小距离，这样边数很少，然后直接跑dij即可。
常数极大无比。
inline ll qpow(ll a, ll b){ll res = 1;while(b){if(b & 1) res = res * a % mod;a = a * a % mod, b >>= 1;}return res;
}
struct node{ll u, d;bool operator < (const node &a) const{return d > a.d;}
};
signed main(){freopen("genshin.in","r",stdin);freopen("genshin.out","w",stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> B;for(int i = 1, k; i <= n; ++i){cin >> t[i] >> k, mp[{i, i}] = 1; id[i] = i;for(int j = 1, x; j <= k; ++j){cin >> x; mp[{i, x}] = 1; G[i].pb(x), q[x].emp(i), w.emp(x);}}sort(id + 1, id + 1 + n, [](int x, int y){ return t[x] < t[y];});for(int i = 1; i <= n; ++i){vector<int> vec;for(auto p : w){vector<int> tmp;for(int j : q[p]) if(!mp.count(mkp(id[i], p)) && !mp.count(mkp(j, id[i]))) val[{j, p}] = t[id[i]], tmp.pb(j);for(int j : tmp) q[p].erase(j);if(!q[p].size()) vec.pb(p);}for(int p : vec) w.erase(p);}pw[0] = 1; for(int i = 1; i <= n; i++) pw[i] = pw[i - 1] * B % mod;for(int i = 2; i <= n; i++) (pw[i] += pw[i - 1]) %= mod;ll ans = 0;for(int i = 1; i <= n; ++i){ans = (ans + (t[i] * pw[n] % mod * qpow(B, (i - 1) * n) % mod + mod - t[i] * qpow(B, (i - 1) * n + i) % mod))% mod;priority_queue<node> q;int tot = 0;vector<ll> dis;dis.resize(G[i].size() + 1);for(int j : G[i]){d[j] = ++tot, (ans += (mod - t[i] * qpow(B, (i - 1) * n + j) % mod) % mod) %= mod, dis[tot] = inf;if(val[{i, j}]) q.push({j, val[{i, j}] + t[i]}), dis[d[j]] = val[{i, j}] + t[i];}while(!q.empty()){node u = q.top(); q.pop();if(u.d > dis[d[u.u]] || u.d >= inf)continue;for(int j : G[i])if((!mp.count(mkp(u.u,j))) && dis[d[u.u]] + t[u.u] < dis[d[j]])dis[d[j]] = dis[d[u.u]] + t[u.u], q.push({j, dis[d[j]]});}for(auto v : G[i])if(dis[d[v]] >= inf) (ans += V * qpow(B, (i - 1) * n + v) % mod) %= mod;else (ans += dis[d[v]] * qpow(B, (i - 1) * n + v) % mod) %= mod;} cout << ans << '\n';return 0;
}
C. 粉兔的牛拉(ramen)
计算几何我不会，咕咕咕。