8.7 2024第（四）场：河南理工大学

[河南萌新联赛2024第（四）场：河南理工大学 ](河南萌新联赛2024第（四）场：河南理工大学_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com))

C 岗位分配

m个志愿者，n个岗位，每个岗位至少a[i]个志愿者，求几种分配方式

思路

其实也就是数学中的组合数，赛事一直在推如何组合，最终主要思路是分配1…k个进行累加。有代码用类似dp，前缀和做的。还不懂是什么思路。看题解上有关于组合数隔板法

一个数学组合数问题，都没解决。隔板法，倒是脑子里出现过，可惜没去尝试，一下午连个数学题都没解决，就真的是能力问题了。没学过的算法还好，学了十几年的数学，这个问题都没解决，惭愧。

步入正题：

既然用隔板法，也就是，在空位上插板，板子不能插到同一个位置，总要分隔物品。

我们将待分配的志愿者看作小球。一共n项任务还有一部分是空闲的小球，所以需要分为n+1,那就需要n个隔板。

那么待分配的小球有多少个？

m - sum(i) ?

当然不是啦。

因为前面特意提到板子不能插到一个位置！！！，那么每两个板子至少有一个球。所以我们可以将所有 a[i]先减 1，全部少分配一个。

此时小球数量也就是 k=m-sum[i]+n

已知小球数量k和隔板数量n，现在再来看有多少空位

@ @ @ @ @

上图@表示小球，板子可以插向那些空位呢？

第一个不插，因为每项任务至少要再分配一个。最后一个插，因为最后一部分是空闲志愿者，可为0。（当然也可以前插后不插）。所以是这个样子

@ | @ | @ | @ |@ |

所以有k个小球，就有k个空位

到这答案就出来了

$$C_k^n$$

取模需要用到逆元

2024ccpc全国邀请赛（郑州）补题_once in my life 题解-CSDN博客

这篇博客，H题整理了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<int,int> 
#define fi first
#define se second
#define tup tuple<int,int,int>
const int mod=998244353;
int n,m,a[1050],ans=1,sum=0;
int quickpow(int a,int b)
{int p=1;while(b){if(b&1) p=a*p%mod;a=a*a%mod,b/=2;}return p%mod;
}
signed main()
{IOScin>>n>>m;fir(i,1,n){cin>>a[i];sum+=a[i];//为了使用插板法}int k=m-sum+n;for(int i=k;i>=k-n+1;i--)//阶乘{ans=ans*i%mod;//取模写错了}//逆元取模  a/b%c=a*b^(c-2)%cfor(int i=1;i<=n;i++){ans=ans*quickpow(i,mod-2)%mod;}cout<<ans%mod<<'\n';
}

I 马拉松

思路

可以想到和x y的节点有关，从x的节点到y的节点这些路径都会有警察阻止。所以用两个bfs,分别从x到y,y到x。

x 和 y之间的节点需要忽略，所以用cnt这个数组累加，两个点都能到就不考虑，在bfs中，遇到目标节点，跳过，防重。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<int,int> 
#define fi first
#define se second
#define tup tuple<int,int,int>
const int N=3e5+10;
vector <int> g[N];
int cnt[N],st[N];
void bfs(int x,int y,int f)
{memset(st,0,sizeof(st));queue<int> q;q.push(x);while(!q.empty()){int k=q.front();q.pop();if(st[k]) continue;//标记过，跳出if(k==y) continue;//到达y,y的节点不访问，跳过st[k]=1;cnt[k]+=f;//一定是+=，如果yx都可达，不记录for(auto it:g[k]){q.push(it);}}
}
signed main()
{IOSint n,x,y,u,v;cin>>n>>x>>y;fir(i,1,n-1){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}bfs(x,y,1) ;//从x向y搜索，标记可达节点bfs(y,x,2) ;//从y向x搜索，标记可达节点int n1=0,n2=0;fir(i,1,n){if(cnt[i]==1) n1++;if(cnt[i]==2) n2++;}cout<<n1*n2<<'\n';}