c++ - 计算给定范围内幸运因素总和的算法

Question

问题陈述:-

A number is given, N, which is given in binary notation, and it contains atmost 1000000 bits. You have to calculate the sum of LUCKY FACTOR in range from 1 to N (decimal notation).

Here, LUCKY FACTOR means, (after converting into binary representation) if rightmost or leftmost 1's neighbour is either 0 or nothing(for boundary bit).

已编辑:-

Means if rightmost one's left neighbour is 0, means it count as a LUCKY FACTOR, simlarly in the left side also

例子，

5 == 101,   LUCKY FACTOR = 2.
7 == 111,   LUCKY FACTOR = 0.
13 == 1101, LUCKY FACTOR = 1.
16 == 1110, LUCKY FACTOR = 0.
0 == 0,     LUCKY FACTOR = 0.

答案必须是二进制形式

我完全卡住了，给我一个提示。

我的代码

#include<stdio.h>
#include<string>
#include<string.h>
#include<vector>
//#include<iostream>

using namespace std;

vector<string> pp(10000001);

string add(string a, string b) {
    if(b == "") return a;
    string answer = "";
    int c = 0;
    int szeA = a.size() - 1;
    int szeB = b.size() - 1;

    while(szeA >= 0 || szeB >= 0) {
         answer = (char)( ( ( ( (szeA >= 0) ? (a[szeA] - 48) : 0 ) ^ ( (szeB >= 0) ? (b[szeB] - 48) : 0 ) )  ^ (c) ) + 48 )  + answer;
         c = ( (  ( (szeA >= 0) ? (a[szeA] - 48) : 0 ) & ( (szeB >= 0) ? (b[szeB] - 48) : 0 ) ) | ( ( (szeA >= 0) ? (a[szeA] - 48) : 0 ) & (c) ) | ( ( (szeB >= 0) ? (b[szeB] - 48) : 0 ) & (c) ) );
         szeA--;
         szeB--;
    }
    if(c) answer = '1' + answer;
    return answer;
}

string subtract(string a, string b) {
    int sze = a.size() - b.size();
    while(sze--) b = '0' + b;
    sze = a.size();
    for(int i = 0; i < sze; i++) {
        if(b[i] == '1') b[i] = '0';
        else b[i] = '1';
    }
    if(b[sze-1] == '0') {
        b[sze-1] = '1';
    }
    else {
        int i = sze-1;
        while(i >= 0 && b[i] == '1') {
            b[i] = '0';
            i--;
        }
        if(i >= 0) b[i] = '1';
        else b = '1' + b;
    }
    b = add(a, b);
    b.erase(b.begin() + 0);
    //b[0] = '0';
    while(b[0] == '0') b.erase(b.begin() + 0);
    return b;
}

string power(int index) {
    if(index < 0) return "";
    string answer = "";
    while(index--) {
        answer = '0' + answer;
    }
    answer = '1' + answer;
    return answer;
}

string convert(long long int val) {
    int divisionStore=0;
    int modStore=0;
    string mainVector = "";

    do {
        modStore=val%2;
        val=val/2;
        mainVector = (char)(modStore+48) + mainVector;
    }while(val!=0);
    return mainVector;
}

string increment(string s) {
    int sze = s.size()-1;
    if(s[sze] == '0') {
        s[sze] = '1';
        return s;
    }
    while(sze >= 0 && s[sze] == '1') {
        s[sze] = '0';
        sze--;
    }
    if(sze >= 0) s[sze] = '1';
    else s = '1' + s;
    return s;
}

main() {
    int T;
    char s[1000001];
    string answer;
    scanf("%d", &T);

    for(int t = 1; t <= T; t++) {
        int num;
        answer = "1";
        int bitComeEver = 0;
        int lastBit = 0;
        scanf("%s", s);
        int sze = strlen(s);
        // I used below block because to avoid TLE.
         if(sze > 3300) {
            printf( "Case #%d\n", t);
            for(int i = 0; i < sze; i++) printf("%c", '1');
            printf("\n");
            //continue;
        }
        else {
        if(pp[sze-1] != "") answer = pp[sze-1];
        else {
            pp[sze-1] = power(sze-1);
            answer = pp[sze-1];
        }
        answer = subtract(answer, convert(sze-1));

        ////////////////////////////
        //cout << answer << endl;
        for(int i = 1; i < sze; i++) {

            if(s[i] == '1') {
                if(s[1] == '0') {
                    num = sze-i-1;
                    if(num > 0) {
                        if( pp[num-1] == "") {
                            pp[num-1] = power(num-1);
                        }
                        if(pp[num+1] == "") {
                            pp[num+1] = power(num+1);
                        }
                        answer = add(answer, subtract(pp[num+1], pp[num-1]));
                        if(lastBit) answer = add(answer, "1");
                        //else answer = increment(answer);
                        //cout << "\t\t" << answer << endl;
                    }
                    else{
                        int inc;
                        if(lastBit) inc = 2; //answer = add(answer, "10");
                        else inc = 1; //answer = increment(answer);
                        if(s[i-1] == '0') lastBit = 1;
                        else lastBit = 0;
                        if(lastBit) inc += 2;
                        else inc += 1;

                        if(inc == 2) answer = add(answer, "10");
                        else if(inc == 3) answer = add(answer, "11");
                        else answer = add(answer, "100");
                    }
                }
                else {
                        if(num > 0) {
                            if(pp[num-1] != "") pp[num-1] =  power(num-1);
                                answer = add(answer, pp[num-1]);
                        }
                        else {
                            int inc = 0;
                            if(lastBit) inc = 1; //answer = increment(answer);
                            if(s[i-1] == '0') lastBit = 1;
                            else lastBit = 0;
                            if(lastBit) inc += 1;
                            answer = add(answer, convert(inc));
                        }
                }
                if(s[i-1] == '0') lastBit = 1;
                else lastBit = 0;
            }
        }

        if(s[sze-1] == '0') {
            if(lastBit) {
                if(s[1] == '0') {
                    answer = add(answer, "10");
                }
                else answer = increment(answer);
            }
            else if(s[1] == '0'){
                answer = increment(answer);
            }
        }

        printf( "Case #%d\n", t);
        for(int i = 0; i < sze; i++) printf("%c", answer[i]);
        printf("\n");
        }
    }
    return 0;
}

Answer 1

如果一个数字有 k 位，则计算幸运因子为 2 的此类数字的数量:

10.............01

因此这里第一个和最后两个数字是固定的，剩下的k-4个数字可以有任何值。此类数字的数量 = 2^(k-4)。

因此您可以轻松计算此类数字的幸运因子之和 = lucky_factor x 2^(k-4)(当然这是假设 k >= 4)

此外，您无需计算此数字，因为它将采用 10000000 的形式。

如果数字 n 是 11010010。那么小于 n 的 8 位数字应具有以下形式:10........ 或 1100...... 或 1101000_。如果你看到一个模式，那么我们已经根据数字 n 中 1 的数量划分了计算

.

剩下的交给你了。