还是上周和同学一起尝试的kickstart第G轮比赛，这个是第二题的思路和解法。
在经历各种报错，各种思路修正之后终于搞定了！快写下来！
题目理解
就是找一个最大的K，使得K和每个元素进行亦或运算的和小于某个值。
题目解答
Test set1 暴力求解
下面的代码仅仅适应于小测试集。而之所以设置从127开始找，是因为看到了他给的测试集的范围。
对于Test set1中的每个元素而言，0<=Ai<=100,所以可以用6位表示。M也是可以用6位来表示，如果K的最高位不是第6位，而是第7位甚至更高，那么取亦或之后必然会大于128也就大于M，所以对于这个测试集来说，只要从127往下找到第一个符合条件的数字即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<iostream>
#include <vector>
#include <math.h>
#include <bitset>
// typedef long long ll;
using namespace std;
void solve(int case_num){
int N,M;
cin>>N>>M;
int res = 0;
int temp = 0 ;
vector<int> arr;
bool find = false;
for(int i =0;i<N;i++){
int mi;
cin >> mi;
arr.emplace_back(mi);
}
for(int i = 127;i>=0;i--){
for(int j=0;j<N;j++){
temp += arr[j]^i;
}
if(temp <= M){
find = true;
res = i;
break;
}
temp = 0;
}
res = find?res:-1;
cout << "Case #" << case_num << ": " << res << endl;
}
int main(){
int t;
cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
}
return 0;
}
|
贪心+位运算巧妙运用
按照上面的方法，我们可以发现这个大样例的0<=Ai<=pow(10,15),对应M也是这个范围。我们可以发现要用49位来表示，也就是说从pow(2,50)开始往下找到第一个符合条件的即可。但是这个数太大了。
然后我们发现原来式子的值可以这么改。
这样我们就通过位运算来找最大的K值了。
怎么找呢。我们找K的时候也是按照比特位从高位开始找，尽可能让高位取1，注意这里要保证当我这个位置取1之后加上后面的所有值的最小值不会超过M，那么才可以取。如果取不了1，那就试一下可不可以取0，同理如果这个位置取0，也要看加上后面所有位所形成的最小值会不会超过K，若是没有超过，则可以取，如果超过，那么说明这个数不存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 50;
LL pre[maxn], zeros[maxn], ones[maxn], minc[maxn], vis[maxn];
int main(){
int T;
scanf("%d", &T);
for (int t = 1; t <= T; ++t) {
LL N, M;
scanf("%lld %lld",&N, &M);
for(int i = 0;i<maxn;i++){
vis[i] = 0;
}
for(int i = 0; i <N; i++){
LL temp;
scanf("%lld", &temp);
for(int j = maxn - 1; j >= 0; j--){
if((temp>>j)&1){
vis[j]++;
}
}
}
for(int i = maxn-1; i >= 0; i--){
LL a = vis[i] * (1LL<<i);
LL b = (N-vis[i]) * (1LL<<i);
ones[i] = a;
zeros[i] = b;
minc[i] = min(a,b);
}
pre[0] = 0;
for(int i = 1;i < maxn; i++){
pre[i] = pre[i-1]+minc[i-1];
}
LL res = 0;
LL temp = 0;
for(LL i = maxn - 1; i >=0; i--){
if((zeros[i]+temp+pre[i])<=M){
temp += zeros[i];
res += (1LL<<i);
}else if(temp+ones[i]+pre[i]<=M){
temp += ones[i];
}else{
res = -1;
break;
}
}
printf("Case #%d: %lld \n", t, res);
}
return 0;
}
|
这个地方一定需要搞清楚的是，从最高位开始找的时候，并不是取1就可以，因为后面所有的位的0和1的情况会形成一个数字的范围，而不是0.一定要注意。
本题收获
- 要注意看测试集的测试用例的条件，尤其是大小，直接会决定我们的数据类型是int或者long long或者其他。
- 要注意题目隐含的条件，这个条件并不是单纯的从最高位到最低位的贪心，而是有后续隐含条件的贪心，所以一定要注意。
- 对于位运算，一定要学会使用移位运算符以及对应的位运算操作，有时候可能会有巧妙的作用。
- 因为c++的灵活性，可以通过地址进行操作，所以在使用数组的时候一定要注意不要越界，在进行相关条件判断的时候一定要小心。当报错说运行时错误的时候，多半就是for循环的条件写错了或者数组越界了。还有当你发现在本地跑的和在kickstart上跑同一份代码，但是结果不一样的时候，多半也是地址错了，以后要注意！
- 做出来这个题目的感觉很爽啊，继续加油～