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 卡提希娅的接线方案
注意到操作的次数 时,每次可以删掉路径上一条最大的边。如果 ,则 ,我们可以用多余的操作,把连接 的边变成距离 路径不超过 的所有边中最短的那条边。注意这里边 到路径 的距离定义为 到路径 距离中较大的那个值。这题赛时我把正解思路想出来了,但是显然没有调出来。
#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;
}