B、入门mex
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
一、题目要求
mex在许多题目中都有所考察，本题就来带大家入门mex
我们规定一些数字的mex是指满足下列要求的数字x
1、对于所有0≤y<x，y都在这些数字里出现过
2、x没有在这些数字里出现过
例如{1,2,3}的mex是0,{0,1,2,3,6,5}的mex是4
你也可以这样理解，一些数字的mex是从0往上枚举，第一个没出现的数字。
现在给你大小为n的数组a，请你回答选最多k个数字，mex最大是多少？
输入描述:
第一行两个整数n和k
接下来一行n个数字表示数组a
1≤k≤n≤10^5,0≤ai≤10^9
输出描述:
输出一行一个整数表示你的答案
示例1
输入
7 3 2 0 2 3 2 1 9
输出
3
说明
选三个数，最优方案是选0,1,2,mex为3
二、思路
1.可以随便选取k个数字，看谁的mex最大
2.如果整个数组里面没有0，则无论k为多少，它们最大的mex均为0
3若有0出现，则选取k个不同的数，最好这k个数字连续
例如：012的mex是3,025的mex则是1
即从0往上枚举第一个没有出现的数字
（ps:一定要读懂题意，本来一直以为是选择连续k个数字，就一直在wa）
三、代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+10;
int a[N],b[N];
int n,k;
void solve()
{
int i,j;
cin>>n>>k;
for(i=0; i<n; i++)
{
cin>>a[i];
}
sort(a,a+n);
if(a[0]!=0)
{
cout<<"0"<<'\n';
}
else
{
int p=0;
for(i=0; i<n; i++)
{
if(a[i]!=a[i+1])
{
b[p++]=a[i];
}
}
int ans=1;
for(i=1; i<=k-1; i++)
{
if(b[i]!=ans)
break;
else
ans++;
}
cout<<ans<<endl;
}
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}C、计数问题
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
一、题目要求
首先，出题人将给你一个正整数n
其次，你需要给出有多少种方案，使得A、B、C、D四个数字都是正整数且A∗B+C∗D=n
两个方案不同当且仅当A、B、C、D至少有一个数字不同，例如1∗1+3∗1和1∗1+1∗3是不同的两个方案
可以证明，1≤n≤1e5时答案小于等于9∗10^18所以不需要取余
输入描述:
一行一个正整数nnn，保证1≤n≤10^5
输出描述:
输出一个整数表示你的答案
示例1
输入
4
输出
8
说明
八种方案分别为(1,1,1,3),(1,1,3,1),(1,2,1,2),(1,2,2,1),(1,3,1,1),(2,1,1,2),(2,1,2,1),(3,1,1,1)
示例2
输入
1
输出
0
二、思路
1如果要算有几种方案，可以用左半部分的方案数乘以右半部分的方案数
例如当n=4的时候
f[4]=f[1]*f[3]+f[2]*f[2]+f[3]*f[1]=1*2+2*2+2*1=8
f[1]代表的是1 的因子个数 f[1]=1
f[2]代表的是2的因子个数 f[2]=2
f[3]代表的是3的因子个数 f[3]=2
三、代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
int n,f[N],ans;
signed main()
{
cin>>n;
int i,j;
for(i=1;i<=100000;i++)
{
for(j=1;j<=i/j;j++)
{
if(i%j==0)
{
f[i]++;
if(i/j!=j)
f[i]++;
}
}
}
for(i=1;i<n;i++)
{
ans+=f[i]*f[n-i];
}
cout<<ans<<endl;
return 0;
}
/*
思路：
例如：f[4]=f[1]*f[3]+f[2]*f[2]+f[3]*f[1];
*/D、AND and SUM
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
一、题目要求
给定两个整数a 和 s，问是否存在两个非负整数满足：
x&y=a
x+y=s
如果存在，输出 `Yes`，如果不存在输出`No`。
因为本题比较简单，数据给了多次查询。
输入描述:
第一行一个整数T，表示查询次数。
接下来T行，每行两个整数：a和s。
数据保证1≤T≤10^5，0≤a,s≤2^60;
输出描述:
T行，每行按要求输出`Yes`或者`No`。
示例1
输入
2 1 8 4 2
输出
Yes No
二、思路
&（按位与）：1&1=1,1&0=0，0&0=0,0&1=0
假设a的二进制数为101
x:101
y:1?1，
a:101
如果想要x&y==a，则需要满足s-a的那个数字y的二进制数中1的位置要等于a中二进制数1 的位置
三、代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int s,a,t;
signed main()
{
cin>>t;
while(t--)
{
cin>>a>>s;
if(a>s)
{
cout<<"No"<<'\n';
}
else
{
int x=s-a;
int y=a;
int ans=x&y;
if(ans==a)
cout<<"Yes"<<'\n';
else
cout<<"No"<<'\n';
}
}
return 0;
}
