26.10.12 比赛记录
更新于 2026年10月27日约 3 分钟阅读
T1 凯瑟琳的委托分组
倒序遍历整个排列,把不断删边转换成不断加边,用并查集维护每个连通块的负责人。
初始时每个点单独构成一个连通块,每次添加一个点的所有连边,把这个点的所有排在它后面的邻居点所处连通块的负责人设置为它。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,p[N],fa[N],pp[N],ans[N];
vector<int>g[N];
int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];pp[p[i]]=i;
g[i].clear();
fa[i]=i,ans[i]=0;
}
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=n;i>=1;i--){
int u=p[i];
for(int v:g[u]){
if(pp[v]<pp[u])continue;
int fy=fnd(v);
ans[fy]=u;
fa[fy]=u;
}
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<" \n"[i==n];
}
int main(){
freopen("Katheryne.in","r",stdin);
freopen("Katheryne.out","w",stdout);
cin.tie(0)->sync_with_stdio(0);
cin>>T;
while(T--)solve();
return 0;
}
T2 砂糖的培养方
难难的数学题,我不会。最优策略是强打强,弱打弱,我不知道怎么证。设 人中有 人比目标强,胜率为 。转移方程 ,如果还多一人,。后面还要维护一个前缀和 函数,由于我的数学能力为零,我真的不会了。以下粘贴题解:求答案等价于维护前缀和 。令 (),奇偶项合并可得 ,全段和满足 、。 时直接取 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=65,P=998244353,inv=828542813;
int T,n,l,r,p,q,pp[N],qq[N];
map<int,int>mp[N];
int qpow(int x,int y){
int res=1;
while(y){
if(y&1)res=res*x%P;
x=x*x%P,y>>=1;
}
return res;
}
int F(int dep,int x){
if(!dep)return 1;
if(x==(1ll<<dep)-1)return qq[dep];
if(mp[dep].count(x))return mp[dep][x];
if(~x&1)return mp[dep][x]=F(dep-1,x>>1)*p%P;
return mp[dep][x]=(F(dep-1,x>>1)*q%P+F(dep-1,(x+1)>>1)*p%P)*p%P;
}
int H(int dep,int x){
if(!x)return 0;
if(!dep)return 1;
if(x==(1ll<<dep))return (H(dep-1,x>>1)*2*p%P+qq[dep+1]-pp[dep+1]+P)%P;
return (H(dep-1,x>>1)*2*p%P+F(dep-1,x>>1)*p%P*(p+(x&1))%P-pp[dep+1]+P)%P;
}
signed main(){
freopen("Sucrose.in","r",stdin);
freopen("Sucrose.out","w",stdout);
cin>>T;
while(T--){
cin>>n>>l>>r>>p;
if(p<50)p=100-p,l=(1ll<<n)+1-l,r=(1ll<<n)+1-r,swap(l,r);
pp[0]=qq[0]=1,q=100-p,p=p*inv%P,q=q*inv%P;
for(int i=1;i<=n+2;i++)pp[i]=pp[i-1]*p%P,qq[i]=qq[i-1]*q%P;
cout<<(H(n,r)-H(n,l-1)+P)%P*qpow((r-l+1)%P,P-2)%P<<'\n';
for(int i=0;i<=n;i++)mp[i].clear();
}
return 0;
}
T3 菲米尼的零件清单
每次给定一个区间 ,需要通过交换的方式把这个区间排成非降序,且交换的元素之和不能超过 。我们只需查询一个区间的所有逆序对的和的最大值即可。但是逆序对的数量是 级别的,把全部逆序对都记录下来显然不行。我们可以用单调栈的思想,区间里一个数在更左边并且更小显然不优,因此只需考虑一个数前面的比它大的数中最靠右的那一个。离线下来扫描线,线段树求区间最大值即可。
#include<bits/stdc++.h>
#define mid (L+R)/2
#define ls (u<<1)
#define rs (u<<1|1)
using namespace std;
const int N=1e6+5;
int n,m,w[N],p[N],stk[N],top,tr[N<<4],l[N],k[N],ans[N];
vector<int>q[N];
void modify(int u,int L,int R,int x,int val){
if(L==R){tr[u]=max(tr[u],val);return;}
if(x<=mid)modify(ls,L,mid,x,val);
if(x>mid)modify(rs,mid+1,R,x,val);
tr[u]=max(tr[ls],tr[rs]);
}
int query(int u,int L,int R,int l,int r){
if(l<=L&&R<=r)return tr[u];
int res=0;
if(l<=mid)res=max(res,query(ls,L,mid,l,r));
if(r>mid)res=max(res,query(rs,mid+1,R,l,r));
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1,r;i<=m;i++){
cin>>l[i]>>r>>k[i];
q[r].push_back(i);
}
for(int i=1;i<=n;i++){
while(top&&w[stk[top]]<=w[i])top--;
p[i]=stk[top];
stk[++top]=i;
}
for(int i=1;i<=n;i++){
if(p[i])modify(1,1,n,p[i],w[p[i]]+w[i]);
for(int j:q[i])ans[j]=query(1,1,n,l[j],i)<=k[j];
}
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
return 0;
}
T4 提纳里的巡林路线
本题要求一条路径 ,记 为树上所有点到 距离的最大值,求 。
从一个点出发走到一个叶子的路径称为一条链。需要找出一个点出发的所有链中,最长的三条。用数学可以算出来把最长的链作为 ,其余两条链连起来作为 ,答案就是最大的。接下来就是计算一个点走出前三长链的长度以及数量,用树形 DP 就能算出来。此题细节较多,比较难调。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+5;
int n,dn[N],up[N];
ll cd[N],cu[N],mxcnt,mx;
vector<int>g[N];
void dfs1(int u,int fa){//计算出向下最长链
dn[u]=0,cd[u]=1;
for(int v:g[u]){
if(v==fa)continue;
dfs1(v,u);
if(dn[v]+1>dn[u])dn[u]=dn[v]+1,cd[u]=cd[v];
else if(dn[v]+1==dn[u])cd[u]+=cd[v];
}
}
void dfs2(int u,int fa){//计算出向上最长链
vector<pair<int,ll>>a;
a.push_back({up[u],cu[u]});
for(int v:g[u]){
if(v==fa)continue;
a.push_back({dn[v]+1,cd[v]});
}
int d1=0,d2=0;
ll c1=0,c2=0;
for(auto [dep,cnt]:a){
if(dep>d1)d2=d1,c2=c1,d1=dep,c1=cnt;
else if(dep==d1)c1+=cnt;
else if(dep>d2)d2=dep,c2=cnt;
else if(dep==d2)c2+=cnt;
}
for(int v:g[u]){
if(v==fa)continue;
up[v]=d1+1,cu[v]=c1;
if(d1==dn[v]+1&&c1==cd[v])up[v]=d2+1,cu[v]=c2;
else if(d1==dn[v]+1)cu[v]-=cd[v];
dfs2(v,u);
}
}
void dfs3(int u,int fa){
vector<pair<int,ll>>a;
if(fa)a.push_back({up[u],cu[u]});
for(int v:g[u]){
if(v==fa)continue;
a.push_back({dn[v]+1,cd[v]});
}
if(a.size()>=3){
sort(a.begin(),a.end(),greater<pair<int,ll>>());
int d1=a[0].first,d2=a[1].first,d3=a[2].first;
ll val=1ll*d1*(d2+d3),cnt;
if(d2>d3){
ll cntd3=0;
for(auto i:a)
if(i.first==d3)cntd3+=i.second;
cnt=a[1].second*cntd3;
if(d1==d2)cnt+=a[0].second*cntd3;
}
else{
ll cntd2=0,sum=0;
for(auto i:a)
if(i.first==d2)
cntd2+=i.second,sum+=i.second*i.second;
cnt=(cntd2*cntd2-sum)/2;
}
if(val>mx)mx=val,mxcnt=cnt;
else if(val==mx)mxcnt+=cnt;
}
for(int v:g[u])
if(v!=fa)dfs3(v,u);
}
int main(){
freopen("Tighnari.in","r",stdin);
freopen("Tighnari.out","w",stdout);
cin>>n;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
cu[1]=1;
dfs2(1,0);
dfs3(1,0);
if(!mxcnt)cout<<"0 1";
else cout<<mx<<' '<<mxcnt;
return 0;
}