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 砂糖的培养方

难难的数学题,我不会。最优策略是强打强,弱打弱,我不知道怎么证。设 2h2^h 人中有 ss 人比目标强,胜率为 Fs(h)F_s(h)。转移方程 Fh(2j)=pFh−1(j)F_h(2j) = pF_{h-1}(j),如果还多一人,Fh(2j+1)=p[qFh−1(j)+pFh−1(j+1)]F_h(2j+1) = p[qF_{h-1}(j) + pF_{h-1}(j+1)]。后面还要维护一个前缀和 Hh(x)H_h(x) 函数,由于我的数学能力为零,我真的不会了。以下粘贴题解:求答案等价于维护前缀和 Hh(x)=∑s=0x−1Fh(s)H_h(x) = \sum_{s=0}^{x-1} F_h(s)。令 x=2j+b<2hx = 2j + b < 2^h (b∈{0,1}b \in \{0, 1\}),奇偶项合并可得 Hh(x)=2pHh−1(j)+p(p+b)Fh−1(j)−ph−1H_h(x) = 2pH_{h-1}(j) + p(p + b)F_{h-1}(j) - p^{h-1},全段和满足 S0=1S_0 = 1、Sh=2pSh−1+qh−1−ph−1S_h = 2pS_{h-1} + q^{h-1} - p^{h-1}。x=2hx = 2^h 时直接取 ShS_h。

#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 菲米尼的零件清单

每次给定一个区间 [l,r][l,r],需要通过交换的方式把这个区间排成非降序,且交换的元素之和不能超过 kk。我们只需查询一个区间的所有逆序对的和的最大值即可。但是逆序对的数量是 n2n^2 级别的,把全部逆序对都记录下来显然不行。我们可以用单调栈的思想,区间里一个数在更左边并且更小显然不优,因此只需考虑一个数前面的比它大的数中最靠右的那一个。离线下来扫描线,线段树求区间最大值即可。

#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 提纳里的巡林路线

本题要求一条路径 A→BA\to B,记 HH 为树上所有点到 A→BA\to B 距离的最大值,求 max⁡(H×dist(A,B))\max(H\times \text{dist}(A,B))。

从一个点出发走到一个叶子的路径称为一条链。需要找出一个点出发的所有链中,最长的三条。用数学可以算出来把最长的链作为 HH,其余两条链连起来作为 A→BA\to B,答案就是最大的。接下来就是计算一个点走出前三长链的长度以及数量,用树形 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;
}

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC