河南萌新联赛2024第（四）场：河南理工大学补题（B，C，I）

河南萌新联赛2024第（四）场：河南理工大学

B 小雷的神奇电脑

题意：

小雷的电脑有一个m位的寄存器，可以存储m位的二进制数。有n个数，请给出所有同或的结果中最大的那个。

同位运算：

将整数转换为m位二进制表示，如果两个数相同为1，不同为0.

思路：

1.我在解题中，想着把它和异或联系在一起，最后发现行得通。

2.我们可以把两个数先异或，得到的结果与二进制下（2^m-1)的结果异或即可得到答案ma。

3.想得到最大的结果应该选择接近的两个数，每次进行上述操作，如果当前结果更大一些则更新ma，最终输出即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//#define int long long
#define endl "\n"
int a[200005];//int b[19] = {1, 4, 8, 16, 32, 64, 128, 216, 512, 1024, 2048, 4096, 8192, 16384, 32764, 65528, 131056, 262112};void solve() {int n, m;cin >> n >> m;int r = pow(2, m ) - 1;int ma = -1;for (int i = 1; i <= n; i++) {cin >> a[i];}sort(a + 1, a + n + 1);for (int i = 1; i < n; i++) {int u = a[i] ^ a[i+1];u = u ^ r;ma = max(u, ma);}cout << ma << endl;
}int main() {IOSint t;t = 1;
//	cin >> t;while (t--) {solve();}return 0;
}

看c题前，先补充一点乘法逆元的内容。

乘法逆元：

为什么要用乘法逆元呢？

因为对于除法取模不存在呀，取模只对乘法才存在。乘法逆元就是把除法取模转化为乘法逆元运算。

(a/b)%p=m;   (a*x)%p=m;a%p=(m*b)%p;
(a*x)%p=m%p=(m*b*x)%p;
(b*x)%p=1;

x为b的逆元。求a/b等价于a*b的逆元。

如何求解逆元？

用费马小定理，这个是有条件限制的，需要模数p为质数，不过竞赛中一般都满足。

b^p-1%p=1;
b*b^p-2=1;#define mod 998244353
int quickpow(int a,int b)
{int p=1;while(b){if(b&1)p=a*p%mod;a=a*a%mod;b>>=1;}return p%mod;
}
//逆元取模，ans/i%mod=ans*i^(mod-2);for(int i=1;i<=n;i++){ans=ans*quickpow(i,mod-2)%mod;}

C 岗位分配

题意：

有n个岗位，m位志愿者，每个岗位至少有a[i]个志愿者，你需要将志愿者分配到岗位上，可以有志愿者空闲，每个志愿者无差别，青给出可能的分配情况总数，结果可能会很大，所以需要对998244353取模

解题思路：

这是一个组合数问题。

1.因为我们在把剩下的人分成几部分时，每部分至少有一个人，所以，我们可以先将每个岗位上分配a[i]-1个人，同时m-=a[i]-1;

2.接着我们去分配剩下的人，剩下的人可以分成3部分或者4部分;

3.我们用两个挡板将剩下的人分为3部分，这样就意味着没有空闲下来的人员，其结果用ans记录，具体操作看代码

4.我们用三个挡板将剩下的人分为4部分，这样就意味着有空闲下来的人员，其结果用r记录，具体操作看代码

5.取模时，需要用到乘法逆元，最后将（r+ans）%mod 得到结果。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[1050];
#define mod 998244353
int quickpow(int a,int b)
{int p=1;while(b){if(b&1)p=a*p%mod;a=a*a%mod;b>>=1;}return p%mod;
}
void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];m-=(a[i]-1);}m-=1;//分配剩下的人时，有多少空位int ans=1,r=1;//有空闲下来的人员for(int i=m;i>=m-n+1;i--){ans=ans*i%mod;}//逆元取模，ans/i%mod=ans*i^(mod-2);for(int i=1;i<=n;i++){ans=ans*quickpow(i,mod-2)%mod;}//无空闲下来的人员for(int i=m;i>=m-n+2;i--){r=r*i%mod;}for(int i=1;i<=n-1;i++){r=r*quickpow(i,mod-2)%mod;}cout<<(r+ans)%mod<<endl;
}
signed main()
{int t;t=1;while(t--){solve();}return 0;
}

I 马拉松

题意：

有n个城市，城市x，y之间会有警察阻止比赛，接下来，给出n-1条道路，求出在比赛中会有多少个马拉松被警察阻止

解题思路：

从x到y搜索，y到x搜索，x经过的节点标记为1，用a记录数目，y经过的节点标记为2，用b记录数目，a*b即为结果

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=3e5+10;
vector <int> p[N];
int cnt[N],c[N];
void bfs(int x,int y,int r)
{memset(c,0,sizeof(c));queue<int>q;q.push(x);while(!q.empty()){int k=q.front();q.pop();if(c[k]) continue;//如果标记过则跳过 if(k==y) continue;//如果到达x，y的节点则跳过c[k]=1;//标记cnt[k]+=r;for(auto t:p[k]){q.push(t);} }} signed main()
{IOSint n,x,y,u,v;int a=0,b=0;cin>>n>>x>>y;for(int i=1;i<=n;i++){cin>>u>>v;p[u].push_back(v);p[v].push_back(u);} bfs(x,y,1);//用1标记x到y的节点 bfs(y,x,2);//用2标记y到x的节点 for(int i=1;i<=n;i++){if(cnt[i]==1)a++;if(cnt[i]==2)b++;}cout<<a*b<<endl;
}