2019/3/22更新
题目1 : Exam07_TwoSingleNumbers
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
描述
一个整型数组里除了两个数字（互不相同）之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
输入
第一行：数组的长度N(1<n<100000)
第二行：N个整数，空格隔开
输出
只出现了1次的那两个数，小的在前大的在后，空格隔开
样例输入
10
5 5 6 7 9 9 7 3 3 2
样例输出
2 6
AC代码
#include <iostream>
#include "stdio.h"
#include <string.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int MAX=0x3f3f3f3f;
const int maxn = 10001;
int a[maxn], n;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int t = 0, cnt = 0;
for(int i = 1; i <= n; i++) //对所有的数进行异或运算
t ^= a[i];
int tmp = t;
while(tmp % 2 == 0) {
cnt++;
tmp >>= 1;
}
int x = 0, y = 0;
for(int i = 1; i <= n; i++) //找出其中异或后为1的数
if((a[i] >> cnt)%2) x ^= a[i];
for(int i = 1; i <= n; i++) //同理
if((a[i] >> cnt)%2 == 0) y ^= a[i];
printf("%d %d\n", x, y);
return 0;
}
题目2 : Exam08_ChangeBit
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
描述
给定两个整数A和B，需要改变几个二进制位才能将A转为B。
输入
1行：A和B，空格隔开
输出
需要改变的位数
样例输入
10 8
样例输出
1
AC代码
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int A,B;
cin>>A>>B;
int num = 0;
for(int i = 0;i < 32;i++)
{
if(((A>>i)&1)!=((B>>i)&1))//向右移位同一位如果不一样就要改变
num++;
}
cout<<num;
}
题目3 : Exam09_StrangeDonate
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
地产大亨Q先生临终的遗愿是：拿出100万元给X社区的居民抽奖，以稍慰藉心中愧疚。
麻烦的是，他有个很奇怪的要求：
100万元必须被正好分成若干份（不能剩余）。每份必须是7的若干次方元。比如：1元, 7元，49元，343元，...
相同金额的份数不能超过5份。
在满足上述要求的情况下，分成的份数越多越好！
请你帮忙计算一下，最多可以分为多少份？
输入
固定输入：1000000
输出
最多可以分为多少份
样例输入
1000000
样例输出
无
AC代码
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
int count = 0;
int visit[10] = {0};
int num;
void dfs(int step,int count) { //step代表7的几次方
if(visit[step] > 5) {
//相同金额的份数不能超过5份
return;
}
if(count > 1000000) {
return;
}
else if(count == 1000000){
num = 0;
for(int i = 0; i < 10; i++)
{
num += visit[i];
}
cout<< num;
exit(0);
}
count += pow(7,step);
visit[step]++;
dfs(step, count);
//两种路 visit[step]+1
dfs(step+1, count); //visit[step+1]+1
visit[step]--;
count -= pow(7,step);
}
int main() {
dfs(0,0);
return 0;
}
