Kickstart Practice Round 2018 Problem Problem B. Googol String

题意

A "0/1 string" is a string in which every character is either 0 or 1. There are two operations that can be performed on a 0/1 string:

switch: Every 0 becomes 1 and every 1 becomes 0. For example, "100" becomes "011". reverse: The string is reversed. For example, "100" becomes "001". Consider this infinite sequence of 0/1 strings:

S0 = ""

S1 = "0"

S2 = "001"

S3 = "0010011"

S4 = "001001100011011"

...

SN = SN-1 + "0" + switch(reverse(SN-1)).

You need to figure out the Kth character of Sgoogol, where googol = 10100.

Input The first line of the input gives the number of test cases, T. Each of the next T lines contains a number K.

Output For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the Kth character of Sgoogol.

Limits 1 ≤ T ≤ 100. Small dataset 1 ≤ K ≤ 105. Large dataset 1 ≤ K ≤ 1018.

解法

找规律发现index为2^m的值为0.设字符串长度为len,则len=(2ⁿ)-1,当k>2^n-1的时候,字符串则下标为k的字符等于下标为2^n-1 - k % (2^n-1),当k>2^n-1时,下标为k的字符等于下标为 k % (2^n-1)的字符,递推求解,知道k为2的整数次幂,同时记录翻转次数即可.最终答案为翻转次数&1.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 63;

ll bit[N];

void init() {
    bit[0] = 1;
    for(int i=1; i<63; i++) {
        bit[i] = bit[i-1] * 2;
    }
}

int get_bit(ll k) {
    for(int i=0; i<63; i++) {
        if(bit[i] - 1 >= k) return i;
    }
    return -1;
}

bool check(ll k) {
    return ((k-1) & k) == 0;
}

int main() {
    freopen("./B-large-practice.in", "r", stdin);
    //freopen("./B-small-practice.in", "r", stdin);
    freopen("./solve.out", "w", stdout);
    int T;
    scanf("%d", &T);
    init();
    for(int c = 1; c <= T; c++) {
        ll k;
        scanf("%ld", &k);
        int n = get_bit(k);
        int cnt = 0;
        while(n) {
            if(check(k)) {
                printf("Case #%d: %d\n", c, cnt&1);
                break;
            }
            if(k > bit[n-1]) {
                k = bit [n-1] - (k % bit[n-1]);
                cnt ++;
            }else {
                k = k % bit[n-1];
            }
            n--;
        }
    }
    return 0;
}