做題記錄
CF2008 G. Sakurako's Task
紀(jì)念第一次場(chǎng)上切的一道 G 題，想了 \(40\) 多分鐘。
題意
給定數(shù)組 \(a\)，可以進(jìn)行任意次操作：選定 \(i,j\), 可以操作 \(a_i \leftarrow a_i+a_j\) 或 \(a_i \leftarrow a_i-a_j\)。
問(wèn) 數(shù)組 a 中不存在的第 \(k\) 個(gè)非負(fù)整數(shù)的最大可能為多少。
思路
首先發(fā)現(xiàn)這個(gè)第 \(k\) 個(gè)非負(fù)整數(shù)比較奇怪，不太好入手。但是可以發(fā)現(xiàn)盡量把數(shù)往小了堆是更優(yōu)的。
轉(zhuǎn)變思路從操作入手，發(fā)現(xiàn)如果我們可以獲得一個(gè)很小的數(shù) \(d\)，且其他數(shù)都是 \(d\) 的倍數(shù)，那么我們可以先把所有數(shù)都變成 \(0\),只剩下一個(gè) \(d\)，然后可以將數(shù)組構(gòu)造成 \(0,d,2d,3d \dots (n-1)d\)，保證數(shù)都是最小的。
那么思考如何得到最小的 \(d\)，對(duì)于兩個(gè)數(shù) a,b ，我們可以用類似輾轉(zhuǎn)相減的方法得到 \(gcd(a,b)\)，同理對(duì)于 \(a_i\),我們可以得到最小的 \(d = gcd(a_1,a_2,\dots a_n)\),于是本題就做完了。
Artoj P3183. 游戲升級(jí)
模擬賽的好題。
題目大意
t 組詢問(wèn)，每次給定 \(a_1,a_2,c,n\)，求:
整除分塊很一眼，然后想法是先對(duì) \(a_1\) 做一遍用哈希記錄，然后做 \(a_2\) 時(shí)添加答案。
但是 哈希會(huì)超時(shí)。
然后可以想到先 對(duì)\(a_1,a_2\) 做完，然后對(duì)于一塊答案相同的部分存在數(shù)組里面，然后就可以用雙指針來(lái)做，少了一個(gè) log。復(fù)雜度 \(O(n \sqrt n)\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define mem memset
int rd()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
int T,n,a1,a2,b1,b2,c;
unordered_map<int,PII> mp;
int calc(int l,int r,int x,int y)
{
if (x > r ||y <l) return 0;
if (l <= x && y <= r) return y-x +1;
if (x <= l && r <= y) return r-l+1;
if (x <= r && l <= x) return r-x+1;
if (y >= l && y <= r) return y-l+1;
}
struct node{int x,l,r;};
int main()
{
cin >>T;
vector<node>p1,p2;
while (T--)
{
//mp.clear();
p1.clear(),p2.clear();
cin >> a1 >> b1 >> a2 >> b2 >>n;
if (a1 < a2) swap(a1,a2),swap(b1,b2);
c= b2-b1;
int ans = 0;
for (int l = 1,r;l <= n;l=r+1)
{
if (l > a2)
{
p2.push_back({0,l,n});
break;
}
r = (a2/(a2/l));
r = min(r,n);
p2.push_back({a2/l,l,r});
}
for (int l = 1,r;l <= n;l=r+1)
{
if (l > a1)
{
p1.push_back({0,l,n});
break;
}
r = (a1/(a1/l));
r = min(r,n);
p1.push_back({a1/l,l,r});
}
reverse(p1.begin(),p1.end());
reverse(p2.begin(),p2.end());
int cnt1 = p1.size(),cnt2 = p2.size();
int j = 0;
rep(i,0,cnt1-1)
{
while (j < cnt2-1 && p2[j].x < p1[i].x-c) j++;
if (p2[j].x == p1[i].x-c)
{
ans += calc(p2[j].l,p2[j].r,p1[i].l,p1[i].r);
}
}
cout << ans << endl;
}
return 0;
}
Artoj P3184. 難題
模擬賽的好題，因沒(méi)有特判掛了60 pts。
解法
可以發(fā)現(xiàn)構(gòu)成 \(X\) 的方式都是 \(f_{2k-1}x + f_{2k}y = X\)，其中 \(f_i\) 為斐波那契的第 i 項(xiàng)。然后發(fā)現(xiàn)這個(gè)式子形如 \(ax + by = c\) , 可以用 exgcd 來(lái)解。
做到這里以為沒(méi)了，但實(shí)際上有個(gè)地方?jīng)]有考慮到：算法在枚舉斐波那契數(shù)列時(shí)，對(duì)于不同的 a,b,算出來(lái)的 x，y 是否可能重復(fù)。
我們假設(shè)存在：
我們發(fā)現(xiàn)解出來(lái) \(y\) 為負(fù)數(shù)，不符合條件，因此 \(x,y\) 并不會(huì)重復(fù)。
但是比較特別的是當(dāng) \(c=0\) 時(shí)，\(x=0,y=0\)，會(huì)被重復(fù)計(jì)算，因此需要特判 c = 0。
本題就做完了。
三元組
模擬賽遇到的好題，考驗(yàn)對(duì) \(trie\) 樹(shù)的理解。
一句話題意：給定一個(gè)序列 \(a\)，\(n<=5 \times 10^5,a_i <= 2^{30}\)，問(wèn) \((i,j,k)\) 滿足 \((a_i\ xor\ a_j) < (a_j \ xor \ a_k)\) 的三元組數(shù)量。
std 是枚舉 \(i\)，但好像枚舉 \(j\) 也可以做。
做法
枚舉 \(i\),按位考慮發(fā)現(xiàn)可以從 \(i,k\) 從第幾位開(kāi)始不同考慮。
因?yàn)榍皫孜幌嗤瑫r(shí)結(jié)果一定是相同的。
于是我們可以在trie樹(shù)上枚舉 \(a_k\) 從第 \(t\) 位開(kāi)始與 \(a_i\) 不同。
而 j 可選的條件是 \(a_j\) 的第 \(t\) 位等于 \(a_i\) 的第 \(t\) 位。
因此對(duì)于每個(gè) \(k\) 貢獻(xiàn)就為 \(pre_{k,t,c} - pre_{i,t,c}\)。
可以將貢獻(xiàn)拆開(kāi)，每個(gè)節(jié)點(diǎn)維護(hù) \(pre_{k,t,c}\) 的和還有 \(k\) 的數(shù)量。
\(c\) 為 \(a_i\) 的第 \(t\) 位。
此時(shí)對(duì)于每個(gè) k 都要預(yù)處理出每一位，復(fù)雜度 \(n \log^2 V\)，過(guò)不去。
考慮優(yōu)化，我們發(fā)現(xiàn)對(duì)于每個(gè) \(k\) ，需要查詢的每次都是其所在的那一位，因此只需要保存所在那一位即可。
具體實(shí)現(xiàn)為對(duì)于 \(trie\) 樹(shù)上每個(gè)節(jié)點(diǎn)保存一個(gè) \(sum\)，表示所有 k 的 \(pre_{k,c}\) 的和。
還有保存一個(gè) \(cnt\)，表示 k 的數(shù)量。
然后枚舉 i，貢獻(xiàn)為 \(sum - cnt * pre[i][c]\)
點(diǎn)擊查看代碼
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define ll long long
const int N = 5e5+5;
int n,a[N];
int son[N*32][2];
int cnt[N*32][2];
ll sum[N*32][2];
int tot;
ll pre[N][35][2];
void insert(int x,int id)
{
//cout << "insert" << x << endl;
int p = 0;
for (int i = 30;i >= 0;i--)
{
int ch = x >> i & 1;
if (!son[p][ch]) son[p][ch] = ++tot;
p = son[p][ch];
for (int c = 0;c < 2;c++)
cnt[p][c]++,sum[p][c] += pre[id][i][c];
// cout << p << ' ';
//cout << id << ' ' << i << ' ' << ch << endl;
}
//puts("");
}
int query(int id)
{
int p = 0;
ll res = 0;
for (int i = 30;i >= 0;i--)
{
int ch = a[id]>>i&1;
//cout << i << endl;
if (son[p][!ch])
{
// cout << i << endl;
int t2 = son[p][!ch],c = ch;
// cout <<t2 << ' ' << ch << endl;
res += 1ll*sum[t2][ch] - 1ll*cnt[t2][ch] * pre[id][i][c];
}
if (son[p][ch])
p = son[p][ch];
else break;
}
return res;
}
signed main()
{
cin >> n;
for (int i = 1;i <= n;i++) scanf("%lld",&a[i]);
for (int i = 1;i <= n;i++)
for (int j = 30;j >= 0;j--)
pre[i][j][(a[i]>>j&1)] = 1;
for (int j = 30;j >= 0;j--)
for (int k = 0;k < 2;k++)
for (int i = 1;i <= n;i++)
pre[i][j][k] += pre[i-1][j][k];
// for (int i = 1;i <= n;i++)
// {
// rep(j,0,3)
// rep(k,0,1)
// {
// cout << i << ' ' << j << ' ' << k << ' ' << pre[i][j][k] << endl;
// }
// }
ll ans = 0;
for (int i = n;i >= 1;i--)
{
// cout << query(i)<<endl;
ans += query(i);
insert(a[i],i);
}
cout << ans << endl;
return 0;
}
P4284 [SHOI2014] 概率充電器
感覺(jué)是一道非常好的題啊。
樹(shù)形 DP + 概率期望。
題意：給定一棵樹(shù)，每個(gè)點(diǎn)有概率自己帶電，每條邊也有概率可以傳導(dǎo)電，問(wèn)期望帶電的點(diǎn)的個(gè)數(shù)。
做法
首先是一個(gè)非常簡(jiǎn)單經(jīng)典的 \(trick\)，看到期望但是值只有 \(1\)，于是可以將期望轉(zhuǎn)化成求每個(gè)點(diǎn)被點(diǎn)亮的概率之和。
于是考慮在樹(shù)上做樹(shù)形 DP。
首先我們可以設(shè)出 \(g_x\) 表示考慮 \(x\) 及其子樹(shù)，使得 \(x\) 帶電的概率。
這個(gè)轉(zhuǎn)移非常好想：\(\large {g_x = 1 - \sum (1-g_{son} \times p_{x,son})}\)。
從反面考慮一下就做完了。
然后需要考慮父親對(duì)當(dāng)前 \(x\) 的影響，設(shè) \(f[x]\) 表示 \(x\) 帶電的概率。
我們發(fā)現(xiàn)父親能對(duì) \(x\) 產(chǎn)生影響當(dāng)且僅當(dāng)父親不是由 \(x\) 點(diǎn)亮的。
因此設(shè) \(p_1\) 表示父親不是由 \(x\) 點(diǎn)亮的概率，則有：
\(\huge p_1 = \frac {(1-f_{fa})}{1-p_{fa,x}*g_x}\)
那么轉(zhuǎn)移就為：
code
// Problem: P4284 [SHOI2014] 概率充電器
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4284
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: Eason
// Date:2024-09-26 16:32:38
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define rd read
#define PID pair<int,double>
int read()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
const int N = 5e5+5;
const double eps = 1e-8;
int n;
vector<PID> v[N];
double p[N];
double f[N];
double g[N];
double val[N];
int fa[N];
void dfs(int x,int fa)
{
if (v[x].size() == 1 && x != 1)
{
g[x] = p[x];
return;
}
double tp = 1;
for (auto [y,pc]:v[x])
{
if (y == fa) continue;
dfs(y,x);
val[y] = pc;
tp *= (1-(pc*g[y]));
}
tp *= (1-p[x]);
g[x] = 1-tp;
}
void dfs2(int x,int fa,double pc)
{
//cout << x << endl;
if (x != 1)
{
double p1 = f[fa];//p1表示父親的子樹(shù)除x以外的概率。
p1 = 1-p1;
if (1-g[x]*pc < eps)
{
f[x] = 1;
}
else
{
p1 /= (1-g[x]*pc);
p1 = 1-p1;
f[x] = g[x] + (p1 * pc) - g[x] * p1* pc;
}
}
for (auto [y,pc]:v[x])
{
if (y == fa) continue;
dfs2(y,x,pc);
}
}
int main()
{
cin >> n;
rep(i,1,n-1)
{
int x= rd(),y = rd(),p = rd();
double ds = p/100.0;
v[x].push_back({y,ds});
v[y].push_back({x,ds});
}
rep(i,1,n)
{
int x = rd();
p[i] = x/100.0;
}
if (n == 1)
{
cout << p[1] << endl;
return 0;
}
dfs(1,0);
f[1] = g[1];
dfs2(1,0,0);
double ans = 0;
rep(i,1,n)
{
//cout << i << ' ' << f[i]<< ' '<<g[i] << endl;
ans += f[i];
}
printf("%.6f",ans);
return 0;
}
C. Lazy Narek
VP打的，結(jié)果連 C 都做不出來(lái) /qd /qd
題意：
給定 \(n\) 個(gè)字符串，任選幾個(gè)按順序拼在一起,設(shè)為字符串 \(S\)，令 \(cnt\) 為 \(S\) 中 "narek" 的數(shù)量，問(wèn) \(\max \{S.size - cnt*5 \}\)。
一開(kāi)始想的 \(DP\) 為 \(dp_{i}\) 表示考慮前 \(i\) 個(gè)的答案。然后轉(zhuǎn)移考慮每個(gè)串末尾的可能。但是發(fā)現(xiàn)一個(gè)問(wèn)題就是只能考慮到當(dāng)前這個(gè)和前一個(gè)的貢獻(xiàn)。換句話說(shuō) \(narek\) 跨過(guò)幾個(gè)字符串的情況無(wú)法考慮，遂破防看題解。
正解
非常巧妙的 \(DP\) 啊。設(shè) \(dp[i]\) 表示當(dāng)前已經(jīng)匹配了 \(i\) 個(gè)字符，正在匹配 "narek" 中的第 \(i-1\) 個(gè)的答案。
為什么能這樣設(shè)置呢？因?yàn)槲覀兛梢园l(fā)現(xiàn)答案與當(dāng)前是第幾個(gè)字符串沒(méi)有什么關(guān)系，而且從一個(gè)一個(gè)字符匹配 "narek" 的角度來(lái)思考可以解決跨字符串的問(wèn)題，并且每個(gè)字符串選或不選只關(guān)系到當(dāng)前匹配到第幾個(gè)字符。
其實(shí)也可以看成是節(jié)省了一維的空間。
考慮轉(zhuǎn)移。
枚舉第 \(i\) 個(gè)字符串，枚舉當(dāng)前匹配到了第 \(k\) 位，那么只需要掃一遍字符串，從 \(k\) 位往后循環(huán)匹配，記錄貢獻(xiàn)。
設(shè)掃完后匹配到了第 \(now\) 位，則轉(zhuǎn)移就為：\(dp[now] = max(dp[now],dp[k]+res)\)
code
// Problem: C. Lazy Narek
// Contest: Codeforces - Codeforces Round 972 (Div. 2)
// URL: https://codeforces.com/contest/2005/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: Eason
// Date:2024-09-27 10:51:26
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define rd read
int read()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
const int N = 2e3+5;
int t;
int n,m;
int dp[10];
int tmp[10];
string str[N];
string narek = "narek";
int main()
{
cin >> t;
while (t--)
{
cin >> n >> m;
rep(i,1,n) cin >> str[i];
memset(dp,-INF,sizeof dp);
dp[0] = 0;
rep(i,1,n)
{
memcpy(tmp,dp,sizeof tmp);
rep(k,0,4)
{
int now = k,res = 0;
rep(j,0,m-1)
{
int idx = narek.find(str[i][j]);
if (idx == -1) continue;
if (idx != now) res--;
else res++,now = (now+1)%5;
}
tmp[now] = max(tmp[now],dp[k] + res);
}
memcpy(dp,tmp,sizeof dp);
}
int ans = 0;
for (int i = 0;i < 5;i++) ans = max(ans,dp[i]- 2 * i);
cout << ans << endl;
}
return 0;
}
關(guān)于最后為什么要寫(xiě)
for (int i = 0;i < 5;i++) ans = max(ans,dp[i]- 2 * i);
而不是輸出 \(dp[0]\) ，這是因?yàn)榈阶詈蟛灰欢ㄊ莿偤闷ヅ渫?，可能多匹配了幾位?/p>
HACK：
1
2 5
ppppn
arekn
如這個(gè)數(shù)據(jù)，最后會(huì)匹配成 "narekn"，因此 \(dp[1] - 1\times 2\) 才是答案。
CSP-S 模擬賽 A. 序列
給點(diǎn)序列 \(a_1,a_2,\cdots ,a_n\)，問(wèn)有多少非負(fù)整數(shù)序列 \(x_1,x_2,\cdots,x_n\) 滿足：
- \(\forall i,0 \le x_i \le a_i\)。
- 滿足 \(x_1 | x_2 | \cdots | x_n = x_1 + x_2 + \cdots + x_n\)。
\(n \le 16,a_i < 2^{60}\)
狀壓+數(shù)位 DP 好題。
條件二可以轉(zhuǎn)化為 \(x\) 兩兩并為 \(0\)。按位考慮，即每一位至多一個(gè) \(1\)。
考慮從高位開(kāi)始給每一位填數(shù)，那么需要判斷是否超過(guò) \(a_i\) ，可以想到用數(shù)位 \(DP\)。
對(duì)于每一個(gè)數(shù)字記錄當(dāng)前是否達(dá)到最大限制，即數(shù)位 DP 中的 \(limit\)。
用一個(gè) \(16\) 位二進(jìn)制記錄即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define int ll
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define addev(a,b,c) v[a].push_back({b,c});
#define rd read
int read()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
const int N = 25,M = 66,mod = 998244353;
int n,a[N];
int num[N][M];
int f[M][(1<<16)+10];
void solve()
{
cin >> n;
rep(i,1,n) a[i] = rd();
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= 60;j++)
{
num[i][j] = (a[i]>>(j-1))&1;
}
}
for (int j = 0;j < (1<<n);j++) f[0][j] = 1;
for (int i = 1;i <= 60;i++)
{
for (int j = 0;j < (1<<n);j++)
{
int cur = 0;
for (int k = 1;k <= n;k++)
{
if ((j>>(k-1)&1) && num[k][i]==0) cur += (1<<(k-1));
}
(f[i][j] += f[i-1][cur])%=mod;
for (int k = 1;k <= n;k++)
{
int sj = (j>>(k-1))&1;
int limit = 1;
if (sj == 1) limit = num[k][i];
if (limit == 0) continue;
int ncur = cur;
if (sj) ncur += (1<<k-1);
(f[i][j] += f[i-1][ncur])%=mod;
}
}
}
cout << f[60][(1<<n)-1] << endl;
}
signed main()
{
int t;t = 1;
while(t--)
{
solve();
}
return 0;
}
A. 卡牌游戲
來(lái)源：CSP-S Day 8 模擬賽
你有兩個(gè)屬性攻擊力 \(A\) 和增量 \(D\)，初始為 \(0\)。
還有一個(gè) \(S\) 表示總傷害，初始為 \(0\)。
你將進(jìn)行 \(n\) 輪游戲，每輪有 \(a_i,b_i,c_i\)，每輪開(kāi)始 A += D。
接下來(lái)選擇一項(xiàng)：
- \(S \ += A+a_i\)
- \(D \ += b_i\)
- \(A\ += c_i\)
問(wèn) \(S\) 的最終最大值。
考慮計(jì)算每一項(xiàng)操作對(duì)于 \(S\) 的貢獻(xiàn)，考慮需要計(jì)算記錄哪些東西。
操作一可以直接加。
對(duì)于操作三，若我們知道后面攻擊了 \(cnt\) 次，則我們可以知道該操作對(duì)于 \(S\) 的貢獻(xiàn)為 \(cnt \times c_i\)。
但是操作二似乎沒(méi)有那么好記錄，發(fā)現(xiàn)增量對(duì)于 \(S\) 的貢獻(xiàn)大概是 \(\sum_j (j-i)*b_i\)，其中 \(j\) 是 \(i\) 后面選擇操作 \(1\) 的游戲輪。
那么我們發(fā)現(xiàn)只需要知道 \(i\) 后面所有的 \(j\) 的和。
則狀態(tài)設(shè)計(jì)為：\(dp_{i,j,k}\) 表示考慮 \([i,n]\) 輪游戲，選擇 \(j\) 輪游戲進(jìn)行進(jìn)攻，這 \(j\) 輪游戲的輪數(shù)和為 \(k\)。
則轉(zhuǎn)移就非常簡(jiǎn)單了。
感覺(jué)是一道 DP 好題，需要仔細(xì)研究狀態(tài)的設(shè)計(jì)。
const int N = 105;
int n;
int a[N],b[N],c[N];
ll dp[105][105][5005];
void solve()
{
cin >> n;
for (int i = 1;i <= n;i++) a[i] = rd(),b[i] = rd(),c[i] = rd();
memset(dp,-INF,sizeof dp);
dp[n+1][0][0] = 0;
for (int i = n;i >= 1;i--)
{
for (int j = 1;j <= n-i+1;j++)
{
for (int k = i*j;k <= n*(n+1)/2;k++)
{
ll gx1 = -INF,gx2 = -INF,gx3 = -INF;
if (j >= 1 && k >= i)
gx1 = dp[i+1][j-1][k-i] + a[i];
gx2 = dp[i+1][j][k] + 1ll*j * c[i];
gx3 = dp[i+1][j][k] + 1ll*(k-j*i)*b[i];
dp[i][j][k] = max({gx1,gx2,gx3});
}
}
}
ll ans = 0;
for (int j = 1;j <= n;j++)
for (int k = 0;k <= n*(n+1)/2;k++)
ans = max(ans,dp[1][j][k]);
cout << ans << endl;
}
時(shí)間復(fù)雜度 \(O(n^4)\)，有點(diǎn)小卡。
A. 中位數(shù)
來(lái)源：2024 CSP-S 模擬賽 Day 15
你有一個(gè)序列 \(a_1,a_2,…,a_n\)。
定義 \(b_{l,r}\) 表示序列 \(\{a_i\}_{l≤i≤r}\) 的中位數(shù)。定義 \(c_{l,r}\) 為序列 \(\{b_{i,j}\}_{l≤i≤j≤r}\) 的中位數(shù)。
求 \(\{c_{i,j}\}_{l≤i≤j≤r}\) 的中位數(shù)是多少。
對(duì)于一個(gè)大小為 \(m\) 的序列，我們定義它的中位數(shù)為第 \(\left \lceil \frac{m}{2}\right \rceil\) 小的數(shù)字。
一個(gè)經(jīng)典的trick：\(a_i \ge x \rightarrow 1,a_i < x \rightarrow 0\)
看到中位數(shù)，可以想到先二分中位數(shù)為 \(x\)。
然后我們將大于等于 \(x\) 的數(shù)看成 \(1\)，小于 \(x\) 的數(shù)看成 \(0\)，得到一個(gè)新序列。
則通過(guò)我們?cè)谛滦蛄械玫降拇鸢妇涂梢灾来鸢概c \(x\) 的大小關(guān)系。
在新序列上考慮原問(wèn)題。
首先 \(b_{l,r}\) 可以通過(guò)一維前綴和直接判斷，當(dāng) \(sum_r-sum_{l-1} > \frac{(r-l+1)}{2}\)，\(b_{l,r}\) 為 \(1\)。
同理，\(c_{l,r}\) 也可以用二維前綴和算出來(lái)。
然后這題就做完了。
和這題同個(gè) trick 的經(jīng)典題目：P2824 [HEOI2016/TJOI2016] 排序
題意是區(qū)間排序操作，在操作最后單點(diǎn)查詢。
做法是二分答案，然后 \(a_i \ge x \rightarrow 1,a_i < x \rightarrow 0\)。
那么區(qū)間排序就可以用區(qū)間賦值 \(0/1\) 來(lái)完成。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define addev(a,b,c) v[a].push_back({b,c});
#define rd read
int read()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
const int N = 1e5+5;
int n,m,p[N];
struct node
{
int op,l,r;
}Q[N];
int idx;
struct node2
{
int sum,tag=-1;
}tr[N<<2];
void stf(int k,int l,int r,int c)
{
tr[k].sum = (r-l+1) * c;
tr[k].tag = c;
}
void psd(int k,int l,int r)
{
if (tr[k].tag != -1)
{
int mid = l + r >> 1;
stf(k<<1,l,mid,tr[k].tag);
stf(k<<1|1,mid+1,r,tr[k].tag);
tr[k].tag = -1;
}
}
void modify(int k,int l,int r,int x,int y,int c)
{
if (x > r || y < l) return;
if (x <= l && r <= y)
{
stf(k,l,r,c);
return;
}
int mid = l + r >> 1;
psd(k,l,r);
modify(k<<1,l,mid,x,y,c);
modify(k<<1|1,mid+1,r,x,y,c);
tr[k].sum = tr[k<<1].sum + tr[k<<1|1].sum;
}
int query(int k,int l,int r,int x,int y)
{
if (x > r || y < l) return 0;
if (x <= l && r <= y) return tr[k].sum;
int mid = l+ r >> 1;
psd(k,l,r);
return query(k<<1,l,mid,x,y) + query(k<<1|1,mid + 1,r,x ,y);
}
void build(int k,int l,int r,int x)
{
if (l == r)
{
tr[k] = {(p[l] >= x),0};
return;
}
int mid =l + r >> 1;
build(k<<1,l,mid,x);build(k<<1|1,mid+1,r,x);
tr[k].sum = tr[k<<1].sum + tr[k<<1|1].sum;
tr[k].tag = -1;
}
int check(int x)
{
build(1,1,n,x);
for (int i = 1;i <= m;i++)
{
auto[op,l,r] = Q[i];
int cnt = query(1,1,n,l,r);
// cout << cnt << endl;
if (cnt == 0) continue;
modify(1,1,n,l,r,0);
if (op == 1) modify(1,1,n,l,l+cnt-1,1);
else modify(1,1,n,r-cnt+1,r,1);
}
return query(1,1,n,idx,idx);
}
void solve()
{
cin >> n >> m;
for (int i = 1;i <= n;i++) p[i] = rd();
rep(i,1,m)
{
Q[i] = {rd(),rd(),rd()};
}
idx = rd();
int l = 1,r = 1e5;
while (l < r)
{
int mid = l + r+1 >> 1;
if (check(mid)) l = mid;
else r = mid -1;
}
//cout << check(6) << endl;
cout << l << endl;
}
int main()
{
int t;t = 1;
while(t--)
{
solve();
}
return 0;
}
[ABC282Ex] Min + Sum
一道最小值分治的 trick。
又稱笛卡爾樹(shù)分治。
題意：求 (l,r) 對(duì)數(shù)滿足 \(1\le l \le r \le n\) 且 \(\sum_{i=l}^rB_i+\min_{i=l}^rA_i\le S\)
做法考慮分治，將 \(mid\) 設(shè)為區(qū)間最小值的位置，這一步可以用 \(st\) 表做。
然后將將原區(qū)間 \([l,r]\) 劃分成 \([l,mid-1],[mid+1,r]\) ，因此我們只需要考慮 \((l,r)\) 跨過(guò) \(mid\) 的貢獻(xiàn)。
我們發(fā)現(xiàn)由于區(qū)間和的單調(diào)性，在確定 \(l,r\) 其中一個(gè)時(shí)，另一個(gè)可以二分求得。
同時(shí)為了保證復(fù)雜度，我們枚舉左右中長(zhǎng)度較小的區(qū)間，于是本題就做完了。
復(fù)雜度分析
題解區(qū)還看到一種更nb的做法，直接用單調(diào)棧算出該值作為最小值的最左和最右，然后直接枚舉左右區(qū)間中更小的區(qū)間，二分計(jì)算。
這兩種方法的復(fù)雜度都可以用從笛卡爾樹(shù)的角度證明。
考慮每個(gè)位置 \(i\) 在暴力枚舉中產(chǎn)生了多少貢獻(xiàn)。
設(shè)當(dāng)前區(qū)間節(jié)點(diǎn)為 \(x\)，而位置 \(i\) 在 \(x\) 的子樹(shù) \(y\) 中，且 \(y\) 是 \(x\) 較小的子樹(shù)。
那么在枚舉完子樹(shù) \(y\) 后，下一次再枚舉到 \(i\) 時(shí)，就應(yīng)是 \(x\) 作為子樹(shù)進(jìn)行枚舉。
而又有 \(siz_x \ge 2 \times siz_y\) ，于是我們發(fā)現(xiàn)每一次枚舉 \(i\) 的時(shí)候，其所在區(qū)間就翻倍。
也就是說(shuō)每個(gè)位置最多被枚舉 \(O(n \log n)\) 次。
類似啟發(fā)式合并。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define int ll
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define mem memset
#define rd read
int read()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
const int N = 2e5+5;
int n,a[N],b[N];
int sum[N];
int S;
int dp[N][25];
void prework()
{
for (int i = 1;i <= n;i++) dp[i][0] = i;
for (int j = 1;j <= 20;j++)
for (int i = 1;(i+(1<<j)-1) <= n;i++)
{
int t1 = dp[i][j-1],t2 = dp[i+(1<<(j-1))][j-1];
if (a[t1] < a[t2]) dp[i][j] = t1;
else dp[i][j] = t2;
}
}
int query(int l,int r)
{
int k = log2(r-l+1);
int t1 = dp[l][k],t2 = dp[r-(1<<k)+1][k];
return ((a[t1] < a[t2])?t1:t2);
}
int ans;
int calcl(int id,int l,int r,int num)
{
l--;
while (l < r)
{
int mid = l + r + 1>> 1;
if (sum[mid] - sum[id-1] <= num) l = mid;
else r = mid - 1;
}
return l;
}
int calcr(int id,int l,int r,int num)
{
r++;
while (l < r)
{
int mid =l + r>>1;
if (sum[id]-sum[mid-1] <= num) r = mid;
else l = mid + 1;
}
return l;
}
void solve(int l,int r)
{
if (l > r) return;
int mid = query(l,r);
if (mid-l < r-mid)
{
for (int i = l;i <= mid;i++) ans += calcl(i,mid,r,S-a[mid]) - mid+1;
}
else{
for (int i = mid;i <= r;i++) ans += mid - calcr(i,l,mid,S-a[mid]) + 1;
}solve(l,mid-1);solve(mid+1,r);
}
signed main()
{
cin >> n >> S;
rep(i,1,n) a[i] =rd();
rep(i,1,n) b[i] =rd(),sum[i] = sum[i-1] + b[i];
prework();
solve(1,n);
cout << ans << endl;
return 0;
}
CF1956D Nene and the Mex Operator
*2000
賊有趣的 \(DP\) 加構(gòu)造。
題意
給定長(zhǎng)度為 \(n\) 的序列 \(a_i\)，滿足 \(1\leq n\leq 18,0\leq a_i\leq 10^7\)。定義一次操作為將 \([l,r]\) 區(qū)間賦值為 \(a_l,\ldots,a_r\) 的 \(\mathrm{mex}\) 值，求在 \(5\times 10^5\) 次操作之內(nèi)序列和的最大值，并給出操作序列。
分析
題目要求求出最大值并給出構(gòu)造方案。
我們先思考題目給出的操作有什么性質(zhì)。
由于題目給出的限制 \(cnt<=5 \times 10^5\) 非常大，所以我們大膽嘗試。
通過(guò)手玩樣例，我們猜測(cè)對(duì)于任意區(qū)間 \([l,r]\) 我們都可以將其中每個(gè)數(shù)變成 \(r-l+1\) ，即區(qū)間長(zhǎng)度。
等下再證明這玩意，先看看知道了這條性質(zhì)怎么求出最大值。
考慮 \(DP\)，設(shè) \(f_{i}\) 表示前 \(i\) 個(gè)能得到的最大值，直接枚舉 \(j\) 轉(zhuǎn)移：
過(guò)程中記錄一下上次的轉(zhuǎn)移點(diǎn)，就可以知道操作了哪些區(qū)間。
再考慮剛才的操作，我們假設(shè)區(qū)間長(zhǎng)度 \(len = 5\)
而最后的狀態(tài)是
\(5 \ 5 \ 5 \ 5 \ 5\)
想要達(dá)成這個(gè)狀態(tài)，必不可少的是
\(4 \ 3 \ 2 \ 1 \ 0\)
設(shè) \(func(l,r)\) 表示對(duì) \([l,r]\) 進(jìn)行一次操作。
設(shè) \(g_i\) 表示在原區(qū)間形成 \(i,i-1,i-2,\dots 0\) 的所需操作集。
我們發(fā)現(xiàn) \(g_4 = g_3 + func(1,5) + g_3\)
于是我們可以得出 \(g_i = g_{i-1}+func(l,r)+g_{i-1}\)
而操作數(shù)剛好為 \(f_i = 2^{i}-1\)
\(2^{18} + 18 \le 5 \times 10 ^ 5\) 穩(wěn)穩(wěn)通過(guò)！
2028E - Alice's Adventures in the Rabbit Hole
題意
給定一棵樹(shù)，皇后想處死愛(ài)麗絲，而愛(ài)麗絲想逃出去。愛(ài)麗絲若在葉子節(jié)點(diǎn)則被處死，在根節(jié)點(diǎn)則逃出。
每次操作都有 \(\frac{1}{2}\) 的概率由皇后或愛(ài)麗絲來(lái)操作一次操作可以將愛(ài)麗絲移動(dòng)到相鄰的節(jié)點(diǎn)。
問(wèn)愛(ài)麗絲起點(diǎn)在 \(1,2,\dots , n\) 時(shí)，愛(ài)麗絲逃出的概率。
做法
先考慮一條鏈的情況：
\(1,2,3,\dots,d,\dots,n\)
假設(shè)起點(diǎn)在 \(i\) 的答案為 \(f_i\)。
則有
即 \(f\) 是一個(gè)等差數(shù)列，所以：
通項(xiàng)為：
我們?cè)跇?shù)上做一個(gè)短鏈剖分。
解釋一下，就是把樹(shù)鏈剖分的重兒子變成到最近葉子的距離最小的兒子。
對(duì)于每條短鏈，我們需要額外算上鏈頂?shù)母赣H。
然后就可以將其當(dāng)做鏈上的情況了。
假設(shè)當(dāng)前在 \(i\),\(p\) 是 \(i\) 跑到鏈的父親的概率，則 \(1-p\) 是 \(i\) 跑到葉子的概率。
因?yàn)楫?dāng)愛(ài)麗絲跑到當(dāng)前鏈的父親上時(shí)，此時(shí)已經(jīng)換了一條鏈了，所以需要分開(kāi)考慮。
則有：
而 \(p\) 可以用上面的公式算。
于是做完了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define int ll
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define addev(a,b,c) v[a].push_back({b,c});
#define rd read
int read()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
const int N = 2e5+5,mod = 998244353;
int n;
int siz[N],top[N],son[N];
int dep[N];
int dis[N];
int fat[N];
int inv[N];
vector<int> v[N];
int ksm(int a,int b)
{
int res= 1;
while (b)
{
if (b & 1) res = 1ll*res * a%mod;
a = 1ll * a * a %mod;
b >>= 1;
}
return res;
}
void dfs1(int x,int fa)
{
fat[x] = fa;
dep[x] = dep[fa] + 1;
for (auto y : v[x])
{
if (y == fa) continue;
dfs1(y,x);
if (!son[x] || dis[son[x]] > dis[y]) son[x] = y;
}
if (son[x])
dis[x] = dis[son[x]] + 1;
}
int f[N];
void dfs2(int x,int tp)
{
top[x] = tp;
int len = dis[tp]+1 + (tp!=1);
int d = dep[x] - dep[tp]+2-(tp==1);d = len-d+1;
f[x] = (d-1)*(ksm(len-1,mod-2))%mod*f[fat[tp]]%mod;
if (x==1)f[x]=1;
if (son[x]) dfs2(son[x],tp);
for (auto y : v[x])
{
if (y == fat[x] || y == son[x]) continue;
dfs2(y,y);
}
}
void solve()
{
cin >> n;
rep(i,1,n-1)
{
int x= rd(),y = rd();
v[x].push_back(y);
v[y].push_back(x);
}
dfs1(1,1);
dfs2(1,1);
rep(i,1,n) cout << f[i] << ' ';
puts("");
rep(i,0,n) v[i].clear(),f[i] = top[i] = siz[i] = dep[i] = dis[i] = fat[i] = son[i] = 0;
}
signed main()
{
rep(i,1,2e5) inv[i] = ksm(i,mod-2);
int t;t = rd();
while(t--)
{
solve();
}
return 0;
}
A. ??
來(lái)源：2024 NOIP 模擬賽 Day 12
抽象題目加抽象解法。
笛卡爾樹(shù) + 樹(shù)形 dp
題意
有 \(n\) 個(gè)人站成一行，能力值分別為 \(a_1, a_2, \dots, a_n\)。
會(huì)進(jìn)行 \(n - 1\) 輪比賽。每次比賽，裁判會(huì)選出兩個(gè)序列中相鄰的選手，其中能力值更高的選手將獲得勝利，而另一位選手會(huì)被淘汰。當(dāng)兩個(gè)人能力相同的時(shí)候，你可以任意選擇勝者。敗者會(huì)離開(kāi)隊(duì)伍，而勝者的能力值會(huì)增加 \(1\)，并且剩下的人合并成一行，繼續(xù)進(jìn)行比賽。
你可以任意選擇比賽順序和相同情況下的勝者，問(wèn)最后哪些選手可能成為最后的贏家。從小到大輸出這些選手的編號(hào)。
做法
我們對(duì)于原序列建笛卡爾樹(shù)，首先最大值是一定可以贏的。
然后我們觀察到每個(gè)節(jié)點(diǎn)可以將其子樹(shù)所有點(diǎn)吃掉。
設(shè)選手 \(i\) 能否贏為 \(ans_i\)。
于是我們可以列出 dp：\(f_i\) 表示我們將子樹(shù) \(i\) 刪掉，取代為一個(gè)權(quán)值為 \(f_i\) 的數(shù)且 \(ans_i=1\)，滿足 \(f_i\) 最小。
可以得到：
-
\(f_i \ge a_{fa}\)
-
\(f_i \ge f_{fa} - (siz_{fa} - siz_i)\)
于是 \(f_i\) 為兩者取個(gè) \(max\)。
從上往下做就做完了。
day4 C 互不相同
給定 \(a_i\)，定義一次操作為選擇一段子區(qū)間加上任意整數(shù) \(x\)，問(wèn)至少幾次操作使得全局互不相同。
假設(shè)做了 k 次區(qū)間加法 產(chǎn)生 \(2k\) 個(gè)端點(diǎn)
可以發(fā)現(xiàn)端點(diǎn)之間每個(gè)區(qū)間內(nèi)部都是互不相同的。
那么原題可以等價(jià)為我們選擇一個(gè)左端點(diǎn)每次貪心的選直到有相同的就新開(kāi)一個(gè)區(qū)間。
此時(shí)需要操作的次數(shù) = (區(qū)間數(shù)+1)/2
因?yàn)橐淮尾僮鲿?huì)產(chǎn)生兩個(gè)端點(diǎn)。
此時(shí)還有一個(gè)問(wèn)題是左右兩端的貢獻(xiàn)計(jì)算，一種方法是枚舉左端點(diǎn)找出對(duì)應(yīng)右端點(diǎn)，
另一種方法是強(qiáng)行將原序列拼成一個(gè)環(huán)，即將原數(shù)組復(fù)制一遍，往后倍增跳滿足 r-l+1<=n
便能自然地算出左右端貢獻(xiàn)了。
https://www.luogu.com.cn/problem/CF1237F
CF1237F Balanced Domino Placements
題目描述
給定一個(gè) \(h\) 行 \(w\) 列的方格棋盤(pán)，上面已經(jīng)放置了一些多米諾骨牌。每個(gè)多米諾骨牌恰好覆蓋棋盤(pán)上相鄰的兩個(gè)格子，每個(gè)格子最多只能被一個(gè)多米諾骨牌覆蓋。
我們稱一個(gè)多米諾骨牌的放置方式為“完全平衡”，如果沒(méi)有任何一行或一列中存在被兩個(gè)不同多米諾骨牌覆蓋的兩個(gè)格子。換句話說(shuō)，每一行和每一列要么沒(méi)有被覆蓋的格子，要么只有一個(gè)被覆蓋的格子，要么有兩個(gè)被覆蓋的格子且這兩個(gè)格子屬于同一個(gè)多米諾骨牌。
現(xiàn)在給定一個(gè)已經(jīng)完全平衡的多米諾骨牌放置方式，問(wèn)有多少種方法可以在此基礎(chǔ)上再放置零個(gè)或多個(gè)多米諾骨牌，且仍然保持完全平衡。請(qǐng)輸出方案數(shù)對(duì) \(998\,244\,353\) 取模的結(jié)果。
當(dāng)前的網(wǎng)格中有部分行部分列被叉掉，問(wèn)還能放骨牌的方案數(shù)。
直接思考，先放豎著的再放橫著的，發(fā)現(xiàn)豎著的骨牌會(huì)叉掉兩行一列
對(duì)于橫著的產(chǎn)生影響，互不獨(dú)立，不方便計(jì)算。
簡(jiǎn)化問(wèn)題，考慮只有豎著的。
變成了有若干固定行不可選，一次得選兩行的方案數(shù)，dp。\(f_{i,j}\) 表示前 \(i\) 行選 \(j\) 次的方案數(shù)。
當(dāng)然此時(shí)這些選出來(lái)的骨牌的列是錯(cuò)開(kāi)的而且不固定。
算方案數(shù)我們只需要在剩下沒(méi)有被叉的列中選出 \(j\) 列即可
因此最終為 \(f_{n,j} \times A_{cnth}^{j}\)
同理我們也可以計(jì)算出 \(g_{m,i}\) 表示只考慮橫著的。
此時(shí)似乎橫豎會(huì)互相影響，我們這樣想：
不具體考慮每一個(gè)骨牌的具體位置，而是考慮使他們錯(cuò)開(kāi)，互不影響。
比如說(shuō)假設(shè)有 \(i\) 個(gè)豎著的，\(j\) 個(gè)橫著的。\(cnt_x \ cnt_y\) 分別是沒(méi)有被叉的行和列的數(shù)量
\(f_{n,i}\) 算出了 \(n\) 行選出 \(i\) 張骨牌的方案數(shù)，
考慮這 \(i\) 張骨牌能放在哪 \(i\) 列里？
可以在 \(cnt_x - 2\times j\) 個(gè)列中選擇，因?yàn)橐粡垯M著的會(huì)叉掉兩列。
乘法原理乘上 \(A_{cntx-2\times j}^{i}\)
此時(shí)還有一點(diǎn)問(wèn)題。
橫著的同時(shí)會(huì)叉掉一行，因此橫著的也只能在 \(cnt_y - 2\times i\) 行中選擇
再乘上 \(g_{m,j} \times A_{cnt_y-2\times i}^{j}\)
得到最終答案。
C. 異或可達(dá)
模擬賽 day5 C
題意
給定 \(m\) 條邊和常量 \(k\)，\(q\) 個(gè)詢問(wèn)，給定\(d\)。
問(wèn) \((x,y)\) 數(shù)量
滿足 \(x < y\) 且 \(x,y\) 聯(lián)通且每條邊權(quán) \(c_j \ xor \ d < k\)。
做法
要維護(hù)無(wú)向圖連通性。
想到并查集。
查詢并不簡(jiǎn)單，考慮將查詢離線并放在一起。
\(c_j \ xor \ d < k\) 限制條件提醒我們將問(wèn)題放在 trie 樹(shù)上思考。
我們考慮在trie樹(shù)上分治。
假設(shè)當(dāng)前在 \(x\) ，只考慮當(dāng)前位。
當(dāng) k = 1，d = 1
那么 $son_{x,0} $ 整棵子樹(shù)下的邊都應(yīng)被選入。
于是我們暴力將 \(son_{x,0}\) 整棵子樹(shù)加入，并繼續(xù)在 \(son_{x,1}\) 分治。
加入后我們用可撤銷并查集將操作撤銷（類似于線段樹(shù)分治
其他情況同理。
于是，每條邊都只會(huì)被添加 \(\log V\) 次，問(wèn)題在 \(n \log V \log n\) 的時(shí)間復(fù)雜度被解決。
模擬賽 day6 D. 阻礙
題意
帶權(quán)無(wú)向圖，問(wèn)那些邊刪除后使得 \(1\) 到 \(n\) 的最短路 \(dist_{1,n}\) 加 \(1\)。
這是一道最短路問(wèn)題，考慮先把最短路徑圖建出來(lái)。
此時(shí)得到一個(gè) DAG。
DAG 上思考問(wèn)題不太簡(jiǎn)單。
不妨我們考慮該 DAG 上的以 \(1\) 為根搜索樹(shù)。
此時(shí)會(huì)發(fā)現(xiàn)一些性質(zhì)：
- 滿足條件的邊一定不會(huì)在搜索樹(shù)之外
? 因?yàn)閯h除后，搜索樹(shù)的最短路依舊是 \(dist_{1,n}\)，因此滿足條件的邊在 \(1-n\) 的路徑上
-
考慮維護(hù)每條邊刪除后的最短路，搜索樹(shù)外的一條邊 \((u,v)\) 可以更新他們路徑上的所有邊的答案
貢獻(xiàn)為：\(dist_{1,u} +dist_{v,n} + w(u,v)\)
于是得到做法，我們將樹(shù)外的邊按照上面的貢獻(xiàn)從小到大排序，每次覆蓋一段路徑。
可以使用并查集維護(hù)，\(f_i\) 表示 \(i\) 上最近的沒(méi)有被覆蓋的點(diǎn)。初始 \(f_i = i\)
最后查一遍在 \(1-n\) 路徑上所有的邊就做完了。
kruskal 重構(gòu)樹(shù)
P11907 [NHSPC 2023] F. 恐怖的黑色魔物
在一個(gè)三維的網(wǎng)格上，可以移動(dòng)到相鄰的點(diǎn)。
點(diǎn)權(quán)值 \(d\) 為最近關(guān)鍵點(diǎn)的曼距。
\(q\) 次查詢問(wèn) \(s \rightarrow t\) 路徑上最小權(quán)值最大。
做法
首先 \(d\) 可以用多源bfs 解決。
最小權(quán)值最大容易想到最大生成樹(shù)，點(diǎn)權(quán)可以通過(guò) \(w(u,v) = \min (d_u,d_v)\) 解決。
或者直接每次選最大權(quán)值的點(diǎn)找已經(jīng)被加入的鄰居去更新生成樹(shù)。
可以建 kruskal 重構(gòu)樹(shù)解決。
值得注意的一個(gè) trick 是在建kruskal重構(gòu)樹(shù)時(shí)不需要跑 lca 來(lái)最小權(quán)值。
我們的做法是發(fā)現(xiàn)合并兩個(gè)聯(lián)通塊直接只需要任意兩個(gè)點(diǎn)連上邊即可，
因此我們不需要新建點(diǎn)，啟發(fā)式合并兩棵樹(shù)的根，邊權(quán)為原點(diǎn)權(quán)。
與原重構(gòu)樹(shù)性質(zhì)一致。
樹(shù)高便變?yōu)榱?\(O(\log n)\)，只需要兩個(gè)點(diǎn)往上暴力跳即可。
代碼大概是這樣：
find(x);find(y);
if (dep[x] < dep[y])swap(x,y);
while (dep[x] > dep[y]) mx = min(maxn,fval[x]),x = fa[x];
while (x != y)
{
mx = min({mx,fval[x],fval[y]});
x = fa[x],y = fa[y];
}
int find(int x)
{
// cout<< x <<endl;
if (fa[x] != x)
{
int t = find(fa[x]);
dep[x] = dep[fa[x]] + 1; // 維護(hù)深度
return t ;
}
dep[x] = 1;
return fa[x];
}
浙公網(wǎng)安備 33010602011771號(hào)