题目集

B 小雷的神奇电脑

题目描述

小雷有一台特殊的电脑，这台电脑有一个$m$位的寄存器，能够存储一个$m$位的二进制数。换句话说，这台电脑可以存储一个从$0$到$2^m-1$之间的任何非负整数。
小雷还有一组$n$个非负整数的列表（中每一个数都严格小于$2^m$）。他想要找出这个列表中任意两个不同的数（下标不同就行），将它们放入电脑中进行同或运算后，得到的结果是所有可能的同或结果中最大的那个。
同或运算解释
同或运算（XNOR）是一种逻辑运算，它接受两个二进制位作为输入，并根据以下规则产生输出：
• 如果两个输入位相同，则输出为$1$；
• 如果两个输入位不同，则输出为$0$。
对于两个整数$A$和$B$，它们的同或结果是通过将$A$和$B$转换为二进制表示，然后对每个位进行同或运算得到的。

解题思路

同或运算时，两数值接近时，运算后的值最大

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int main()
{int n,m;cin>>n>>m;int ma=(1<<m)-1;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);for(int i=0;i<n-1;i++){ma=min(ma,a[i]^a[i+1]);}cout<<(1<<m)-1-ma;return 0;
}

C 岗位分配

题目描述

学校马上要举行校运会了，有众多志愿岗位需要被分配。但是负责老师临时有事现在由你来分配这些岗位。
现在有$n$个岗位，$m$位志愿者，每个岗位至少需要$a_i$个志愿者，你需要将志愿者分配到岗位上，并且可以有志愿者空闲下来作预备。
请你给出可能的分配情况总数。

答案可能会很大，故需要对$998,244,353$取模。

注：所有岗位需求志愿者的总和不超过志愿者的总和且志愿者间无差别。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353; // 模
int dp[5050]; // 储存组合数
signed main()
{int n,m;cin>>n>>m;int sum=0;for(int i=0;i<n;i++){int x;cin>>x;sum+=x;}m-=sum; dp[0]=1; // 将剩余的 m 个人，分到 n+1 个位置，位置可无人for(int i=0;i<=n;i++){for(int j=1;j<=m;j++){dp[j]+=dp[j-1];dp[j]%=mod;}}cout<<dp[m]%mod;return 0;
}

D 简单的素数

题目描述

判断一个数是不是素数

AC代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
const int N = 2e5 + 10;void solve() {int n;cin>>n;int f=0;if(n==1)    cout<<"No\n";else{f=0;for(int i=2;i<=n/i;i++){if(n%i==0){f=1;break;}}if(f==0)    cout<<"Yes\n";else    cout<<"No\n";}
}signed main() {IOSint t;cin>>t;while (t--)solve();return 0;
}

F 小雷的算式

题目描述

小雷今天要写加法题啦！
老师在黑板上写了一个加法式子，小雷想用他喜欢的方式写出来。
小雷喜欢从大到小写下自己的算式并算出答案。
你得到了黑板上的式子，请你用小雷喜欢的方式写出来并计算出答案。

模拟，按要求输出

AC代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
const int N = 2e5 + 10;
string s;
void solve() {s.clear();cin>>s;int num=0;vector<int>ans;int sum=0;for(int i=0;i<s.size();i++){if(s[i]=='+'){sum+=num;ans.push_back(num);num=0;}else{num=num*10+(int)(s[i]-'0');}}sum+=num;ans.push_back(num);sort(ALL(ans));for(int i=ans.size()-1;i>=0;i--){if(i!=ans.size()-1)    cout<<"+";cout<<ans[i];}cout<<'\n';cout<<sum;}signed main() {IOSint t;t = 1;while (t--)solve();return 0;
}

H 聪明且狡猾的恶魔

题目描述

有一天，恶魔们得到了一箱宝藏，箱子中有$x$枚金币。一共有$n$个恶魔，编号从$1到n$。编号最小的恶魔就是恶魔老大。 根据恶魔之间的规则，在分配财宝的时候，将会由恶魔老大提出分配方案。在方案提出后，所有恶魔对方案进行投票，包括恶魔老大在内。每一个恶魔都非常的贪婪，渴望得到尽可能多的金币，同时每一个恶魔又都非常的狡猾，他们都会选择对自己最有利的情况进行投票。如果一个方案$50$%及以上的恶魔投赞成票，那么该方案会被同意执行；否则，该方案不会被执行。 如果方案没有被执行，那么提出方案的恶魔老大将会被恶魔们杀死，他不配成为恶魔老大。剩下恶魔中编号最小的恶魔将会成为新的恶魔老大，然后重新按照上述规则，重新由新的恶魔老大提出新的方案进行操作，直到剩下最后一个恶魔或者有一个恶魔老大的方案被同意执行，那么分配结束。 现在让你作为编号为1的恶魔，你是恶魔老大，请问聪明的你要怎么样才能让自己在不被杀死的情况下获得最多的金币呢。

AC代码

 // 金币数减去人数的一半#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
void solve() {int n,x;cin>>x>>n;int ans=0;if(n%2==0)    ans=x-n/2+1;else    ans=x-n/2;cout<<ans<<'\n';
}signed main() {IOSint t;cin>>t;
// 	t = 1;while (t--)solve();return 0;
}

I 马拉松

题目描述

小明生活在一个名为running的国家，该国家由 $n$ 个城市组成，编号从 $1$ 到 $n$，还有 $n-1$ 条双向道路连接着这些城市。从任何一个城市都可以到达另一个城市。每条道路都连接着两个城市 $a$ 和 $b$ 。这个国家是一个热爱跑步的国家，因此每天都会在一对城市 $(u$ ，$v)$ 之间举办一次马拉松，从 $u$ 作为起点， $v$ 作为终点，且 $u$ != $v$ 。小明需要用最短的路径到达从 $u$ 到达 $v$（注意 $(u$ ，$v)$ 和 $(v$ ，$u)$ 是不同的马拉松）。
令小明头疼的是该国家有两个城市 $x$ 和 $y$，当小明经过 $x$ 城市后又跑到 $y$ 城市，那么该城市的警察就会阻止小明继续参加比赛。
小明想知道在举办的所有马拉松路线中他会有多少个马拉松会在他参加时会被警察阻止。

解题思路

找到能到达 点x 的 其他点 $a_1$ 且这些点不在，点x 到 点y 的路径上;
找到能到达 点y 的 其他点 $a_2$ 且这些点不在，点x 到 点y 的路径上;
$a_1$ * $a_2$ 就是答案

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,x,y;
vector<int>e[N];
int cnt[N];
bool st[N];
void dfs(int x,int y,int num)
{memset(st,0,sizeof st);queue<int>q;q.push(x);while(q.size()){int t=q.front();q.pop();if(st[t]||t==y)    continue;st[t]=1;cnt[t]+=num;for(auto x : e[t])q.push(x);}
}
int main()
{cin>>n>>x>>y;for(int i=0;i<n;i++){int a,b;cin>>a>>b;e[a].push_back(b);e[b].push_back(a);}dfs(x,y,1);dfs(y,x,10);int a1=0,a2=0;for(int i=1;i<=n;i++){if(cnt[i]==1)    a1++;if(cnt[i]==10)    a2++;}cout<<a1*1ll*a2;return 0;
}