2024科技文化節程序設計競賽

補題鏈接

https://www.luogu.com.cn/contest/178895#problems

A. 簽到題

忽略掉大小為1的環，答案是剩下環的大小和減環的數量

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e6;
int n,a[N+5],cnt[N],ans;
bool vis[N];
int main(){sci(n);assert(1<=n && n<=N);rep(i,1,n){sci(a[i]);cnt[a[i]]++;}rep(i,1,n){assert(cnt[i]==1);}rep(i,1,n){if(a[i]==i || vis[i])continue;ans--;for(int j=i;!vis[j];j=a[j]){vis[j]=1;ans++;}}pte(ans);return 0;
}

E. 旅行（構造）

考慮怎么把一個點連的邊都用完，然后遞歸到n-1個點的情況即可

這里的做法是，從1號點開始走，先去3再回來，再去4再回來，直到去n再回來

然后從1去2，然后解決n-1個點的情況，然后從2回1

遞歸

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e6,M=N+5;
int c,n;
vector<int>p;
void sol(int x){p.pb(x);rep(i,x+2,n){p.pb(i);p.pb(x);}if(x+1<=n){sol(x+1);p.pb(x);}
}
int main(){sci(n);assert(2<=n && n<=1000);sol(1);int sz=SZ(p);rep(i,0,sz-1){printf("%d%c",p[i]," \n"[i==sz-1]);}return 0;
}

for循環

注意到剩的i+1到i的邊不必急著回來，可以最后從n->n-1->...->1統一回來

// 這是一份標程#include<iostream>
using namespace std;int main() {int n; cin >> n;for(int i = 1; i <= n; i++) {cout << i << ' ';for(int j = i + 2; j <= n; j++) {cout << j << ' ' << i << ' ';}}for(int i = n - 1; i > 0; i--) {cout << i << ' ';}return 0;
}

I. 三元環計數（組合數學/bitset）

~~我是不動腦子沒有視力的算競選手，看到三元環當然是bitset大力出奇跡啦~~

注意到題目給的競賽圖，也就是任意兩個點之間都有邊

所以任取三個點，只有兩種情況，

一種是三元環，

一種是存在一個點a，a指向b，a指向c

用C(n,3)減去第二種情況即可

組合數學

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=4e3+10;
int t,n,v;
char s[N];
ll ans;
int main(){sci(n);assert(3<=n && n<=4000);ans=1ll*n*(n-1)*(n-2)/6;rep(i,1,n){scanf("%s",s+1);int m=strlen(s+1);assert(m==n);int v=0;rep(j,1,n){v+=(s[j]-'0');}ans-=1ll*v*(v-1)/2;}ptlle(ans);return 0;
}

bitset

n=4000，O(n^3/w)也能過真是大力出奇跡了…

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=4e3+10;
int n;
bitset<N>a[N],b[N];
char s[N];
ll ans;
int main(){ sci(n);assert(3<=n && n<=4000);rep(i,1,n){scanf("%s",s+1);rep(j,1,n){assert(s[i]!='1');if(s[j]=='1')a[i].set(j);else{if(i!=j)b[i].set(j);}}}rep(i,1,n){rep(j,1,n){if(a[i].test(j))ans+=(b[i]&a[j]).count();//printf("i:%d j:%d ans:%lld\n",i,j,ans);}}ptlle(ans/3);return 0;
}

B.?魔杖（dp）

注意到每個值只可能由上一行與這個值最相鄰的兩個值轉移，復雜度O(nm)

也就是要么從小于等于里最大的轉移，要么從大于等于里最小的轉移

樸素dp

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=105,M=2e4+10;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,m,a[N][M];
ll dp[N][M];
int main(){sci(n);sci(m);assert(2<=n && n<=100 && 1<=m && m<=2e4);rep(i,1,n){rep(j,1,m){sci(a[i][j]);assert(1<=a[i][j] && a[i][j]<=1e9);}sort(a[i]+1,a[i]+m+1);    }memset(dp,INF,sizeof dp);rep(i,1,m)dp[1][i]=0;rep(i,2,n){int p=1;rep(j,1,m){while(p<=m && a[i-1][p]<=a[i][j])p++;//printf("i:%d j:%d p:%d\n",i,j,p);for(auto &x:{p-1,p}){if(1<=x && x<=m){dp[i][j]=min(dp[i][j],dp[i-1][x]+abs(a[i][j]-a[i-1][x]));}}//printf("i:%d j:%d dp:%lld\n",i,j,dp[i][j]);}}ptlle(*min_element(dp[n]+1,dp[n]+m+1));return 0;
}

如果沒有注意到這個性質的話，可以用線段樹或單調隊列優化轉移

但是注意到從上一行比當前值小的轉移，就是dp[i][k]=min(dp[i-1][j]+a[i][k]-a[i-1][j])

從上一行比當前值大的轉移，就是dp[i][k]=min(dp[i-1][j]+a[i-1][j]-a[i][k])

所以分別，正序雙指針維護上一行dp[i-1][j]-a[i-1][j]，逆序雙指針維護上一行dp[i-1][j]+a[i-1][j]

雙指針dp

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=105,M=2e4+10;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,m,a[N][M];
ll dp[N][M];
int main(){sci(n);sci(m);assert(2<=n && n<=100 && 1<=m && m<=2e4);rep(i,1,n){rep(j,1,m){sci(a[i][j]);assert(1<=a[i][j] && a[i][j]<=1e9);}sort(a[i]+1,a[i]+m+1);    }memset(dp,INF,sizeof dp);rep(i,1,m)dp[1][i]=0;rep(i,2,n){int p=1;ll now=1e18;rep(j,1,m){while(p<=m && a[i-1][p]<=a[i][j]){now=min(now,dp[i-1][p]-a[i-1][p]);p++;}dp[i][j]=min(dp[i][j],now+a[i][j]);}p=m;now=1e18;per(j,m,1){while(p>=1 && a[i-1][p]>=a[i][j]){now=min(now,dp[i-1][p]+a[i-1][p]);p--;}dp[i][j]=min(dp[i][j],now-a[i][j]);}}ptlle(*min_element(dp[n]+1,dp[n]+m+1));return 0;
}

G. 回憶（掃描線入門題）

首先保證兩個區間有交集，

按端點排個序然后掃描線，在l的時候把線段加進multiset，r之后刪掉

然后答案分兩種，相交的和包含的

相交的，[1,50]和[10,100]，答案=(100-1)-(50-10)=100+10-(1+50)

就是兩端點之和減去multiset里最小的兩端點之和

然后包含的是兩端點之差減最小之差，

包含的情況是之前加的線段的右端點更靠右，

形如[1,100]和[10,50]，是100-1-(50-10)

所以用multiset里最大的兩端點之差減當前兩端點之差

當然可以用線段樹之類的數據結構寫，但感覺沒必要

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=2e5+10,M=2*N;
int n,l[N],r[N],x[M],c,ans;
vector<int>add[M],del[M];
multiset<int>in,in2;
int main(){sci(n);assert(1<=n && n<=200000);rep(i,1,n){sci(l[i]),sci(r[i]);assert(1<=l[i] && l[i]<=r[i] && r[i]<=100000000);x[c++]=l[i];x[c++]=r[i];}sort(x,x+c);c=unique(x,x+c)-x;rep(i,1,n){l[i]=lower_bound(x,x+c,l[i])-x;r[i]=lower_bound(x,x+c,r[i])-x;add[l[i]].pb(i);del[r[i]].pb(i);}rep(i,0,c-1){for(auto &v:add[i]){int w=x[l[v]]+x[r[v]];int w2=x[r[v]]-x[l[v]];if(!in.empty()){ans=max(ans,w-(*in.begin()));}if(!in2.empty()){ans=max(ans,(*in2.rbegin())-w2);//ans=max(ans,w2-(*in2.begin()));}in.insert(w);in2.insert(w2);}for(auto &v:del[i]){int w=x[l[v]]+x[r[v]];int w2=x[r[v]]-x[l[v]];in.erase(in.find(w));in2.erase(in2.find(w2));}}pte(ans);return 0;
}

H. 簡單的平方串（kmp/exkmp/哈希）

枚舉S+R的一半有多長，轉化成判斷s的[1,i]和[i+1,n]后者是否是前者的前綴的問題

這里是用exkmp求extend[i]，當然這個玩意kmp也可以求，哈希也可以

如果S+R的一半已經超過了S原來的長度，

說明后面可以任意補a-z的字符，需要預處理26的冪的前綴和

kmp

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 2e6 + 10;
const int M = 5e6 + 10;int p26[M], pmt[N];int main(int argc, char *argv[]) {if(argc == 3) {freopen(argv[1] + 1, "rb", stdin);freopen(argv[2] + 1, "wb", stdout);}ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);p26[0] = 1;for(int i = 1; i < M; i++) {p26[i] = (26LL * p26[i - 1] + 1) % mod;}int T; cin >> T;while(T--) {string s;int x, ans = 0;cin >> s >> x;if(x >= s.length()) ans = p26[(x - s.length()) / 2];for(int i = 1, j = 0; i < s.length(); i++) {while(j && s[i] != s[j]) j = pmt[j];j += (s[j] == s[i]);pmt[i + 1] = j;}for(int i = pmt[s.length()]; i; i = pmt[i]) {if(i <= s.length() / 2 && x >= s.length() - i * 2) ans++;}ans %= mod;cout << ans << '\n';}return 0;
}

exkmp

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=2e6+10,M=5e6+10,mod=998244353;
int t,x,n,sum[M];
int net[N],ex[N];
char s[N];
void extkmppre(char s[],int len){int i=0,j,pos;net[0]=len;while(i+1<len&&s[i]==s[i+1])i++;net[1]=i,pos=1;rep(i,2,len-1){if(net[i-pos]+i<net[pos]+pos){net[i]=net[i-pos];}else{j=net[pos]+pos-i;if(j<0)j=0;while(i+j<len&&s[j]==s[i+j])j++;net[i]=j,pos=i;}}
}
void extkmp(char s1[],char s2[],int l1,int l2){int i=0,j,pos;extkmppre(s2,l2);while(i<l2&&i<l1&&s1[i]==s2[i])i++;ex[0]=i,pos=0;rep(i,1,l1-1){if(net[i-pos]+i<ex[pos]+pos){ex[i]=net[i-pos];}else{j=ex[pos]+pos-i;if(j<0)j=0;while(i+j<l1&&j<l2&&s1[i+j]==s2[j])j++;ex[i]=j,pos=i;	}}
}
int main(){sci(t);assert(1<=t && t<=200000);int bs=1;sum[0]=1;rep(i,1,M-1){bs=26ll*bs%mod;sum[i]=(sum[i-1]+bs)%mod;}int m=0;while(t--){scanf("%s",s);sci(x);n=strlen(s);assert(1<=n && n<=2000000);assert(0<=x && x<=5000000);m+=n;extkmp(s,s,n,n);int ans=0;rep(i,0,n-1){if(i+ex[i]>=n && ex[i]<=i){//len=iif(2*i<=n+x)ans++;}}if(x>=n)ans=(ans+sum[(x-n)/2])%mod;pte(ans);}assert(m<=3000000);return 0;
}

哈希

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
int p26[5000006];struct pii {ll x, y;pii(ll x = 0, ll y = 0) : x(x), y(y) {}
} ha[2000006], p[2000006];pii operator + (pii a, pii b) {return pii((a.x + b.x) % mod, (a.y + b.y) % mod);}
pii operator + (pii a, int b) {return pii((a.x + b) % mod, (a.y + b) % mod);}
pii operator * (pii a, pii b) {return pii((a.x * b.x) % mod, (a.y * b.y) % mod);}
pii operator - (pii a, pii b) {return pii((a.x - b.x + mod) % mod, (a.y - b.y + mod) % mod);}
bool operator == (pii a, pii b) {return a.x == b.x && a.y == b.y;}const pii base(131, 13331);pii gethash(int L ,int R) {return ha[R] - ha[L - 1] * p[R - L + 1];
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);p26[0] = 1;for(int i = 1; i < 5000006; i++) {p26[i] = (26LL * p26[i - 1] + 1) % mod;}p[0] = {1, 1};for(int i = 1; i <= 2000000; i++) {p[i] = p[i - 1] * base;}int T; cin >> T;while(T--) {string s; int x, ans = 0;cin >> s >> x;for(int i = 0; i < s.length(); i++) {ha[i + 1] = ha[i] * base + s[i];}for(int i = (s.length() & 1); i < s.length() && i <= x; i += 2) {int len = i + s.length();len = s.length() - len / 2;if(gethash(1, len) == gethash(s.length() - len + 1, s.length())) ans++;}if(x >= s.length()) ans = (ans + p26[(x - s.length()) / 2]) % mod;cout << ans << '\n';}return 0;
}
解釋

D. 地牢探索（二叉樹種類數卡特蘭數）

~~其實不如直接暴力dp打個表找找規律~~

首先，分母是卡特蘭數，卡特蘭數是C(2n,n)/(n+1)

藍色的是可以掛葉子的地方，對于n個點的每一種二叉樹形態，都有n+1個掛葉子的地方

獨立考慮每個有貢獻的葉子，n個點能掛2n個兒子，已經用了n-1條邊建樹，所以還能掛n+1個

雖然掛完之后二叉樹形態可能相同，但是產生貢獻的葉子不一樣

掛上葉子之后是n+1個點，所以n+1個點的所有二叉樹形態總的葉子和是C(2n,n)，

也就是n個點時，分子是C(2n-2,n-1)

所以輸出化簡后的值即可，注意這個取模是2148473647，爆了int

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const ll mod=2148473647;
int n;
ll modpow(ll x,ll n,ll mod){ll res=1;for(;n;n/=2,x=1ll*x*x%mod){if(n&1)res=1ll*res*x%mod;}return res;
}
int main(){ sci(n);assert(1<=n && n<=1000000000);ll x=1ll*n*(n+1)/2;x%=mod;ll y=modpow(2ll*n-1,mod-2,mod);x=1ll*x*y%mod;ptlle(x);return 0;
}

C. 靜水監獄（計算幾何）

判一下在凸包上還是凸包內還是凸包外，這里是用的二分，其實暴力找復雜度也夠

對于在凸包內的情況，最近的距離的那條邊是不會變的，

假設最近的距離是a，那么求一下時間就是 $t = \int_{0}^{a}\frac{ds}{v_{0}+k*s}$

換元令u=v0+ks解一下定積分就做完了，答案是 $\frac{1}{k}(ln(v_{0}+k*a)-ln(v_{0}))$

~~當然可以參考一下澤與給的微分方程式子，重生之我在院賽學微分方程~~

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e3+5;
struct Point{int x,y;
}p[N];
int t,n,m;
db v0,k;
ll cross(Point o,Point a,Point b){return 1ll*(a.x-o.x)*(b.y-o.y)-1ll*(a.y-o.y)*(b.x-o.x);
}
int binary(Point *p,Point &tp){//條件：p點集必須是順時針或者逆時針//（注意3點共線下的點也必須滿足這個條件）//（如果有3點共線極角序不能完成該條件）int l=0,r=n-1;while(l<r){int m=(l+r)>>1;ll c1=cross(p[0],p[m],tp);ll c2=cross(p[0],p[(m+1)%n],tp);ll c3=cross(p[m],p[(m+1)%n],tp);if(c1>=0 && c2<=0 && c3>=0){if(!c3 || (m==1 && !c1) || (m==n-2 && !c2))return 0;return 1;}if(c1>=0)l=m+1;else r=m;}return -1;
}
db cal(db x,db y,db x1,db y1,db x2,db y2){db cross = (x2 - x1) * (x - x1) + (y2 - y1) * (y - y1); if (cross <= 0)return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1)); db d2 = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); if (cross >= d2)return sqrt((x - x2) * (x - x2) + (y - y2) * (y - y2)); db r = cross / d2; db px = x1 + (x2 - x1) * r; db py = y1 + (y2 - y1) * r; return sqrt((x - px) * (x - px) + (y - py) * (y - py)); 
}
int main(){sci(n);rep(i,0,n-1){sci(p[i].x),sci(p[i].y);}reverse(p,p+n);p[n]=p[0];scanf("%d%lf%lf",&m,&v0,&k);while(m--){Point tp;scanf("%d%d",&tp.x,&tp.y);int v=binary(p,tp);if(v==1){db s=1e18;rep(i,0,n-1){s=min(s,cal(tp.x,tp.y,p[i].x,p[i].y,p[i+1].x,p[i+1].y));}db ans;if(k==0)ans=s/v0;else ans=1/k*(log(v0+k*s)-log(v0));printf("%.10lf\n",ans);}else if(v==0){puts("0");}else{puts("-1");}}return 0;
}

F.?感染的圣巢（樹直徑）

細節比較多，但整體還是有跡可循的

離線，倒著把點加回來，刪點的樹直徑不會做，但是加點的樹直徑是好做的

每個被刪的點，只需要考慮它往上到根這些點，最多60個，

把這60*2e5個點建出樹來，剩下的樹的部分不用建出來，只需要搜到對應的第一層就返回即可

因為只要底下的層數>=1，就一定能找到兩個最遠的兒子（比如找編號最小和最大的）

預處理這棵樹每個點被刪的時機，只需用父親的被刪時間和當前點的被刪時間取min

先對n個點操作完之后剩的部分的樹，求出直徑的兩個點

后面按刪的時機倒著把點都加回來，時機相同時，加的時候按點號從小到大加

開map/unordered_map常數比較大會tle，所以只能把60*2e5個點加進01trie

~~懶得寫了，直接抄澤與的代碼~~

// 確認這份是 STD 了#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N = 2e5 + 5;
const int M = 61 * N;ll q[N], num[M];
int cnt, ans[N], n, m;
int son[M][2], dep[M], t[M], fa[M];ll rd() {ll ret = 0; char ch = getchar();for(; isdigit(ch); ch = getchar())ret = (ret << 1) + (ret << 3) + (ch ^ 48);return ret;
} void insert(ll x, int time) {int u = 1, flag = 0;for(int i = 59; i >= 0; i--) {int temp = !!(x & (1LL << i));if(flag) {if(!son[u][temp]) {son[u][temp] = ++cnt;dep[cnt] = dep[u] + 1;num[cnt] = num[u] * 2 + temp;t[cnt] = m;fa[cnt] = u;}u = son[u][temp];}if(temp) flag = 1;}t[u] = min(t[u], time);
}int numdis(ll u, ll v) {if(u > v) swap(u, v);int i = 59, j = 59;while(!(v >> j)) j--, i--;while(!(u >> i)) i--;while(i >= 0 && ((u >> i) & 1) == ((v >> j) & 1)) i--, j--;return i + j + 2;
}int dis(int u, int v) {if(u == v) {int ret = 0;if(!son[u][0] && !son[u][1]) ret = max(ret, (n - dep[u]) * 2);else if(!son[u][0] || !son[u][1]) {ret = max(ret, (n - dep[u] - 1) * 2);if(u == 1) ret = max(ret, n - dep[u]);}return ret;}int ret = numdis(num[u], num[v]);if(!son[u][0] || !son[u][1]) ret += n - dep[u];if(!son[v][0] || !son[v][1]) ret += n - dep[v];return ret;
}vector<int> vec[N];int main(int argc, char *argv[]) {// if(argc == 3) {//     freopen(argv[1] + 1, "rb", stdin);//     freopen(argv[2] + 1, "wb", stdout);// }n = rd(), m = rd();dep[1] = num[1] = cnt = 1;for(int i = 1; i < M; i++) t[i] = m;for(int i = 1; i <= m; i++)q[i] = rd(), insert(q[i], i - 1);for(int i = 2; i <= cnt; i++)t[i] = min(t[i], t[fa[i]]);for(int i = 2; i <= cnt; i++) {vec[t[i]].push_back(i); }int u = 1, v = 1, d = dis(1, 1);for(int i = m; i > 0; i--) {for(int w : vec[i]) {int tu = u, tv = v, td = d, temp;if((temp = dis(w, w)) > td) tu = w, tv = w, td = temp;if((temp = dis(v, w)) > td) tu = v, tv = w, td = temp;if((temp = dis(u, w)) > td) tu = u, tv = w, td = temp;u = tu, v = tv, d = td;}ans[i] = d;}for(int i = 1; i <= m; i++) {cout << ans[i];if(i == m) cout << '\n';else cout << ' ';}return 0;
}

當然可以把求lca距離的部分改成倍增，從O(n)變成O(logn)，其中n是60，因為庫函數近似O(1)

int lg(ll x){return 63-__builtin_clzll(x);
}
int dis(ll p,ll q){int x=lg(p),y=lg(q);if(x>y)swap(p,q),swap(x,y);q>>=(y-x);if(p==q)return y-x;per(i,6,0){int s=1<<i;if((p>>s)^(q>>s))p>>=s,q>>=s;}p>>=1;int z=lg(p);return y-z+x-z;
}