B - b UVALive - 6918——位运算

朴灿烈づ我的快乐病毒、 2022-06-11 09:13 110阅读 0赞

Think:  
1知识点：位运算+数学归纳规律  
2思考：相信自己，决不放弃

[vjudge题目链接][vjudge]

以下为Wrong Answer代码——变量存储超出存储大小

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    
    using namespace std;
    
    typedef long long LL;
    
    int link1[104], link2[104];
    LL a[104], b[104];
    
    void tra(int link[], int x);
    
    int main(){
        int T, k = 1, i, j;
        LL l, r, w, sum1, sum2;
        scanf("%d", &T);
        while(T--){
            scanf("%lld %lld", &l, &r);
            tra(link1, l);
            tra(link2, r);
            for(i = 0; i < 64; i++){
                if(link1[i] == link2[i]){
                    a[i] = b[i] = link1[i];
                }
                else {
                    for(j = i; j < 64; j++){
                        a[j] = 1;
                        b[j] = 0;
                    }
                    break;
                }
            }
            sum1 = sum2 = 0, w = 1;
            for(i = 63; i >= 0; i--){
                sum1 += a[i]*w;
                sum2 += b[i]*w;
                w *= 2;
            }
            printf("Case %d: %lld %lld\n", k++, sum1, sum2);
        }
        return 0;
    }
    void tra(int link[], int x){
        stack <int> sta;
        while(!sta.empty()){
            sta.pop();
        }
        int i, t, l, tp = 0;
        while(x){
            t = x%2;
            sta.push(t);
            x /= 2;
        }
        l = sta.size();
        for(i = 64; i > l; i--)
            link[tp++] = 0;
        while(!sta.empty()){
            link[tp++] = sta.top();
            sta.pop();
        }
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    
    using namespace std;
    
    typedef long long LL;
    
    int link1[104], link2[104];
    LL a[104], b[104];
    
    void tra(int link[], LL x);
    
    int main(){
        int T, k = 1, i, j;
        LL l, r, w, sum1, sum2;
        scanf("%d", &T);
        while(T--){
            scanf("%lld %lld", &l, &r);
            tra(link1, l);
            tra(link2, r);
            for(i = 0; i < 64; i++){
                if(link1[i] == link2[i]){
                    a[i] = b[i] = link1[i];
                }
                else {
                    for(j = i; j < 64; j++){
                        a[j] = 1;
                        b[j] = 0;
                    }
                    break;
                }
            }
            sum1 = sum2 = 0, w = 1;
            for(i = 63; i >= 0; i--){
                sum1 += a[i]*w;
                sum2 += b[i]*w;
                w *= 2;
            }
            printf("Case %d: %lld %lld\n", k++, sum1, sum2);
        }
        return 0;
    }
    void tra(int link[], LL x){
        stack <int> sta;
        while(!sta.empty()){
            sta.pop();
        }
        int i, l, tp = 0;
        LL t;
        while(x){
            t = x%2;
            sta.push(t);
            x /= 2;
        }
        l = sta.size();
        for(i = 64; i > l; i--)
            link[tp++] = 0;
        while(!sta.empty()){
            link[tp++] = sta.top();
            sta.pop();
        }
    }

[vjudge]: https://vjudge.net/contest/174578#problem/B