C 岗位分配
题目大意：
有n个岗位，m位志愿者，每个岗位至少需要a个志愿者，并且可以有志愿者可以空闲下来作预备，给出可能的分配情况总数
思路：
首先将每个岗位分配好至少需要的志愿者，再将剩下的人进行分配，那就满足 球同盒不同模型（允许空盒），可用隔板法进行分配，需要额外开设一个空闲岗位用来预备，那么按照4个人去4个岗位，那么为c 7 3 ，具体操作可看数论模板中发布的隔板法问题，递归求组合数
Solved：
int n,m;cin>>n>>m;int q=n;while(q--){int x;cin>>x;m-=x;}for(int i=0;i<N;i++){for(int j=0;j<=i;j++){if(j==0) C[i][j]=1;else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}} cout<<(C[n+m][n])%mod<<endl;
I 马拉松
题目大意：
有n个城市，编号1-n，有n-1条双向道路连接这些城市，每天都会在一对城市 (u ，v)之间举办一次马拉松，该国家有两个城市 x 和 y，当小明经过 x 城市后又跑到 y 城市，那么该城市的警察就会阻止小明继续参加比赛。想知道有多少个马拉松在他参加时会被阻止
思路：
该题目有点像 算法进阶指南中楼兰图腾的变形，在楼兰图腾中求的是在一个序列中先升后降 和先降后升的图案总数，如果是先升后降，需要遍历每个数字左边所有比该数小的数字，右边比该数小的数字，相乘就是该数字构成的图案总数，
该题目中只需要在图中求得 与x城市直连但到达不了y城市的数量（楼兰图腾中数字左边所有比该数小的数字数量） * 与y城市直连但到达不了x城市的数量（楼兰图腾中数字右边所有比该数小的数字数量），相乘就是在所有路径中通过x城市到达y 城市的所有路径
在求法方面比较特殊，我们只需要通过x城市bfs遍历所有能够到达的城市，并将其独特标记+1，直到找到y城市，停止
在通过y城市bfs所有能够到达的城市，并将其独特标记+2
这样标记为3的城市即为两城市之间的所有城市，
标记为1的城市就是与x城市直连但到达不了y城市的城市
标记为2的城市就是与y城市直连但到达不了x城市的城市
数据范围3e5，不可用数组模拟邻接表存图，卡内存，需要vector存图
Solved：
int st[N], cnt[N];//st标记城市是否来过，cnt标记与x，y分别直连的城市
void bfs(int x, int y, int num) {memset(st, 0, sizeof(st));queue<int> q;q.push(x);while (!q.empty()) {int t = q.front();q.pop();if (st[t] != 0 || t == y)continue;st[t] = 1;cnt[t] += num;for (auto ee : e[t]) {q.push(ee);}}
}
vector<int> e[N];//邻接表
void solve() {cin >> n >> x >> y;for (int i = 1; i <= n - 1; i++) {int xx, yy;cin >> xx >> yy;//存图e[xx].push_back(yy);e[yy].push_back(xx);}//遍历城市并标记bfs(x, y, 1);bfs(y, x, 2);int cnt1 = 0, cnt2 = 0;//遍历数量for (int i = 1; i <= n; i++) {if (cnt[i] == 1)cnt1++;if (cnt[i] == 2)cnt2++;}cout << cnt1 *cnt2 << endl;
}
