26.10.14 比赛记录

更新于 2026年10月27日约 1 分钟阅读

T1 今汐的巡防分区

这题赛时我用的二维 DP,我甚至没有意识到算的那个 DP 数组就是组合数,换成公式计算组合数应该就可以过了。

#include<bits/stdc++.h>
using namespace std;
const int P=998244353,M=1e6+1e3+5;
int T,n,m,a,b,c,d;
int fac[M],ifac[M];
inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*a%P;
        a=1ll*a*a%P,b>>=1;
    }
    return res;
}
inline int C(int a,int b){
    a+=b;
    if(b<0||b>a)return 0;
    return 1ll*fac[a]*ifac[b]%P*ifac[a-b]%P;
}
signed main(){
    freopen("Jinhsi.in","r",stdin);
    freopen("Jinhsi.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>T;
    fac[0]=ifac[0]=1;
    for(int i=1;i<M;i++)fac[i]=1ll*fac[i-1]*i%P;
    ifac[M-1]=qpow(fac[M-1],P-2);
    for(int i=M-1;i>=1;i--)ifac[i-1]=1ll*ifac[i]*i%P;
    while(T--){
        cin>>n>>m>>a>>b>>c>>d;
        int ans=0,inv=qpow(C(m,n),P-2);
        for(int i=0;i<=a;i++)(ans+=1ll*C(a+d-i,i)*C(m-a-d+i,n-i)%P*inv%P)%=P;
        for(int i=c;i<=min(n,b+c);i++)(ans+=1ll*C(b+c-i,i)*C(m-b-c+i,n-i)%P*inv%P)%=P;
        cout<<ans<<'\n';
    }
    return 0;
}

T2 卡提希娅的接线方案

注意到操作的次数 i<dist(s,t)i<\text{dist}(s,t) 时,每次可以删掉路径上一条最大的边。如果 i≥dist(s,t)i\ge \text{dist}(s,t),则 a=i−dist(s,t)=0,1,…,k−dist(s,t)a=i-\text{dist}(s,t)=0,1,\dots,k-\text{dist}(s,t),我们可以用多余的操作,把连接 s,ts,t 的边变成距离 s→ts\to t 路径不超过 aa 的所有边中最短的那条边。注意这里边 u→vu\to v 到路径 s→ts\to t 的距离定义为 u,vu,v 到路径 s→ts\to t 距离中较大的那个值。这题赛时我把正解思路想出来了,但是显然没有调出来。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int n,s,t,f[N],up[N],q[N],sum,m,dis[N],mi[N];
vector<pair<int,int>>g[N];
bool path[N];
void dfs(int u,int fa,int x){
    f[u]=fa,up[u]=x;
    for(auto [v,w]:g[u]){
        if(v==fa)continue;
        dfs(v,u,w);
    }
}
vector<int>e;
void dfs1(int u,int d,int fa){
    dis[u]=min(dis[u],d);
    for(auto [v,w]:g[u]){
        if(v==fa)continue;
        dfs1(v,dis[u]+1,u);
    }
}
signed main(){
    freopen("Cartethyia.in","r",stdin);
    freopen("Cartethyia.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    memset(dis,0x3f,sizeof dis);
    memset(mi,0x3f,sizeof mi);
    cin>>n>>s>>t;
    for(int i=1,u,v,w;i<n;i++){
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dfs(1,0,0);
    for(int x=s;x;x=f[x])path[x]^=1;
    for(int x=t;x;x=f[x])path[x]^=1;
    for(int i=1;i<=n;i++)
        if(path[i])e.push_back(up[i]),dis[i]=dis[f[i]]=0;
    sort(e.begin(),e.end(),greater<int>());
    m=e.size();
    if(!m){
        for(int i=0;i<=n;i++)cout<<"0 ";
        return 0;
    }
    for(int i:e)sum+=i;
    for(int i=0;i<m;i++)q[i+1]=q[i]+e[i];
    dfs1(s,0,0);
    for(int i=1;i<=n;i++)
        for(auto [v,w]:g[i])
            mi[max(dis[i],dis[v])]=min(mi[max(dis[i],dis[v])],w);
    for(int i=1;i<=n;i++)mi[i]=min(mi[i-1],mi[i]);
    for(int i=0;i<m;i++)cout<<sum-q[i]<<' ';
    for(int i=m;i<=n;i++)cout<<mi[i-m]<<' ';
    return 0;
}

T3 爱弥斯的观测记录

拆位 DP。

#include<bits/stdc++.h>
#define bp(x) __builtin_popcount(x)
using namespace std;
const int mask=0x3ff,N=1e5+5,B=1<<10;
int n,k[N],l[N],h[N],dp[N],best[B][B][21],pre[N],idx[B][B][21],mx;
vector<int>ans;
int main(){
    freopen("Aemeath.in","r",stdin);
    freopen("Aemeath.out","w",stdout);
    cin>>n;
    for(int i=1,a;i<=n;i++)cin>>a,l[i]=a&mask,h[i]=(a>>10)&mask;
    for(int i=1;i<=n;i++)cin>>k[i];
    for(int i=1;i<=n;i++){
        for(int j=0,t;j<B;j++)
            if((t=k[i]-bp(j&h[i]))>=0&&best[j][l[i]][t]+1>dp[i])
                dp[i]=best[j][l[i]][t]+1,pre[i]=idx[j][l[i]][t];
        for(int j=0,t;j<B;j++)
            if(dp[i]>best[h[i]][j][t=bp(l[i]&j)])
                best[h[i]][j][t]=dp[i],idx[h[i]][j][t]=i;
    }
    for(int i=1;i<=n;i++)if(dp[i]>dp[mx])mx=i;
    for(int i=mx;i;i=pre[i])ans.push_back(i);
    cout<<ans.size()<<'\n';
    for(auto it=ans.rbegin();it!=ans.rend();it++)cout<<*it<<' ';
    return 0;
}

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC