Znzryb's Blog
0%

牛客周赛 Round 56 C 异或故事

Posted on Edited on

题目大意

给定一个整数 a，需要构造两个正整数 x、y，使得 x XOR y = a，并满足题目额外的范围/特殊要求（需要对某些边界值特判）。输出一组可行的 x 与 y。

pass 7 / 10 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71053412

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int t,a,b;const int amax=1e9+10;
int main()
{
    cin>>t;
    while(t--) {
        cin>>a;
        for(int i=1;i<=amax;i++) {
            b=i^a;
            if(b>0) {
                cout<<i<<" "<<b<<endl;
                break;
            }
        }
    }
    // a=1^0;
    // std::cout << a << std::endl;
    return 0;
}
// WA https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71053412

前面一直WA，看到这个题解终于懂了。

https://ac.nowcoder.com/acm/discuss/blogs?tagId=271232

其实主要就是要特判1和1e9，这两个通过我们的算法得出的另一个数会超范围，故需要特判。

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
// https://ac.nowcoder.com/acm/contest/88392
#include <iostream>
#include <bitset>
#include <cmath>
#include <deque>
using namespace std;
int a,b,c,t;
bitset <64> numa,num3;
deque <int> a2;
typedef long long ll;
inline ll convNum3(int leng){       // 将num3转为10进制
    ll res=0;
    for(int i=0;i<leng;i++) {
        if(num3[i])
            res+=pow(2,leng-1-i);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int _=1;_<=t;_++){
        cin>>a;
        ll oa=a;
        numa.reset();num3.reset();
        while(true){
            if(a==0) break;
            a2.push_back(a%2);
            a/=2;
        }
        int leng=a2.size();         // 这种循环上限还是用一个量（前面发现调不对发现是因为<a2.size(),但a2的大小一直在变）
        for(int i=0;i<leng;i++){
            numa[i]=a2.back();
            a2.pop_back();
        }
        for(int i=0;i<leng;i++) {
            num3[i]=numa[i];
            if(i==leng-1) {
                if(num3[i]) num3[i]=false;
                else num3[i]=true;
            }
        }
        ll ans3=convNum3(leng);
        if(oa==1000000000) {
            cout<<999999999<<" "<<1023<<endl;
            continue;
        }
        if(oa==1) {
            cout<<"2 3"<<endl;
            continue;
        }
        cout<<1<<" "<<ans3<<endl;
        //cout<<"xor res: 1^"<<ans3<<"="<<(ans3^1)<<endl;
    }
}
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71768673