第一题
题目描述
给定1001个范围在[1,1000]的数字，保证只有1个数字重复出现2次，其余数字只出现1次。试用O(n)时间复杂度来求出出现2次的这个数字。
不允许用数组
输入格式
第一行：一个整数1001；
第二行：1001个用空格隔开的整数，具体入题面描述
输出格式
一个整数，即重复出现的数字
样例数据
请自己设计
数据规模与约定
如题目描述
时间限制：1 \text {s}1s
空间限制：256 \text {MB}256MB
这道题其实就是用异或
首先先抑或上所有的树。
。然后再抑或1~1000的数。
代码如下，
#include<bits/stdc++.h>
using namespace std;
int n,sum,x;
int main(){
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{cin>>x;
sum=sum^x;
}
for(int i=1;i<=1000;i++)
{
sum=sum^i;
}
cout<<sum;
return 0;
}
第二题
给定一个含有 nn 个数的序列 a_1a1,a_2a2...a_nan, 求满足以下性质的二元组(i,j)的数量
-
1 1\leqslant i < j \leqslant n1⩽i<j⩽n
-
2 a_i\&a_j > a_i \quad xor \quad a_jai&aj>aixoraj
其中 \&& 表示与运算, \hat{}^ 表示异或运算。
(0011)_2 \& (0101)_2 = (0001)_2(0011)2&(0101)2=(0001)2
(0011)_2 \quad xor \quad (0101)_2 = (0110)_2(0011)2xor(0101)2=(0110)2
\huge\textbf{输入格式}输入格式
第一行一个整数 TT ,表示数据组数
之后一行 11 个整数 nn ,表示序列长度
接下来一行 nn 个整数, 表示 a_1a1,a_2a2...a_nan
\huge\textbf{输出格式}输出格式
对于每一次询问,输出一个整数表示答案
\huge\textbf{输入样例}输入样例
551 4 3 7 1031 1 146 2 5 322 411Copy
\huge\textbf{输出样例}输出样例
13200Copy
\huge\textbf{数据范围与约定}数据范围与约定
对于 30\%30% 的数据 1\leqslant n\leqslant 10^31⩽n⩽103,1\leqslant a_i\leqslant 10^91⩽ai⩽109
对于另外 30\%30% 的数据 1\leqslant n\leqslant 10^51⩽n⩽105,1\leqslant a_i <2^{10}1⩽ai<210
对于 100\%100% 的数据 1\leqslant T\leqslant 51⩽T⩽5,1\leqslant n\leqslant 10^51⩽n⩽105,1\leqslant a_i\leqslant 10^91⩽ai⩽109
这道题。其实十分简单。
因为相同位数的第一位肯定是一，所以说如果相同位数比的话，那么相同位数的异或一定大于相同位数的与
所以说这道题其实我们就需要判断它们位数是否相同。
如果相同的话
，那么就加一
代码如下，
#include <bits/stdc++.h>
using namespace std;
long long t,n,a,b,c[45],d,sum;
int main()
{
freopen("calc.in","r",stdin);
freopen("calc.out","w",stdout);
cin>>t;
for(int i=1;i<=t;i++)
{
memset(c,0,sizeof(c));
cin>>n;
for(int j=1;j<=n;j++)
{
cin>>a;
b=int(log2(a)+1);
c[b]++;
// cout<<c[b]<<'*';
}
// cout<<endl;
for(int i1=1;i1<=40;i1++)
{
sum+=(c[i1]*(c[i1]-1))/2;
}
cout<<sum<<endl;
sum=0;
}
第三集
问题陈述
给定一个长度恰好为9的字符串SS，由数字组成。0到9的所有数字都恰好在SS中出现一次。
打印出SS中缺失的数字。
约束条件
- SS是一个长度为9的数字字符串。
- SS中的所有字符都是不同的。
输入
从标准输入以以下格式给出输入：
SS
输出
打印出SS中缺失的数字。
样例输入1
023456789
样例输出1
1
字符串023456789只缺少了11。因此，应该打印出11。
样例输入2
459230781
样例输出2
6
字符串459230781只缺少了66。因此，应该打印出66。
注意，使用桶的思想完成该题目，不允许使用string
这道题有一种很简单的思路。
开玩笑的就把他们所有输出数字儿加起来然后呢再减去0~9。的数字之和就得到了。
但是我们现在要用异货做。
这道题其实跟一的思路基本一样。
只不过要把这个给转成数字罢了。
代码如下，
#include<bits/stdc++.h>
using namespace std;
int sum,x;
string n;
int main(){
// freopen("num.in","r",stdin);
// freopen("num.out","w",stdout);
cin>>n;
for(int i=0;i<9;i++)
{
sum=sum^(n[i]-'0');
}
for(int i=0;i<=9;i++)
{
sum=sum^i;
}
cout<<sum;
return 0;
}
第四题。
题目描述
给定一个长度为64的序列A=(A\_0,A\_1,\dots,A\_{63})A=(A_0,A_1,…,A_63)，由0和1组成。
求A\_0 2^0 + A\_1 2^1 + \dots + A\_{63} 2^{63}A_020+A_121+⋯+A_63263。
约束条件
- A\_iA_i是0或1。
输入
从标准输入中以以下格式给出输入：
A_0A0 A_1A1 \dots… A_{63}A63
输出
将答案作为整数打印出来。
样例输入1
1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
样例输出1
13
A\_0 2^0 + A\_1 2^1 + \dots + A\_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13A_020+A_121+⋯+A_63263=20+22+23=13。
样例输入2
1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0
样例输出2
766067858140017173
题目描述
给定n个数字，依次输出每个数字二进制中1的个数。
输入格式
第一行输入一个数N；
之后N行，每行输入一个数a[i]。
输出格式
输出N行，每行一个数每个数字二进制包含1的个数。
样例数据
input
315122Copy
output
413Copy
数据规模与约定
对于100%的数据，2≤N≤200000，1≤a[i]≤10^18；
时间限制：1 \text {s}1s
空间限制：256 \text {MB}256MB
这道题其实并不难
。只需要一次一次去掉最低位的一
然后计数器加加就好了。
代码如下，
#include<bits/stdc++.h>
using namespace std;
long long a,n,sum;
int main()
{
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
sum=0;
cin>>a;
while(a)
{
a-=a&(-a);
sum++;
}
cout<<sum<<endl;
}
return 0;
}