【算法学习笔记】29.规律题解题报告 SJTU OJ 1101 SuperXOR

Description

Pangzi recently realized that bitwise XOR operation is just an addition without carries. For example, when computing (1001)_2 XOR (1101)_2, you write down:

  1001
+ 1101
-------
  0100

You see, everything is like an addition, except that there are no carries.

After realizing this, Pangzi invented Super XOR. It is just an addition on decimal numbers without carries. For example, 123 SUPERXOR 789 = 802, since 1+7=8, 2+8=0, 3+9=2.

Now comes a question. Given N, find 1 SUPERXOR 2 SUPERXOR 3 SUPERXOR 4 SUPERXOR ... SUPERXOR N

Input Format

The first line contains an integer T (1 <= T <= 1000), indicating the number of test cases.

T lines follow each containing 1 integers N (1 <= N <= 10^12).

Output Format

Output T lines, each line is an integer: the answer for the corresponding test case.

Sample Input

Sample Output

Case Limits

Time limit: 500 msec

Memory limit: 64 MB

会发现所有的xxxx99 的叠加superXOR都是0

原因是这样的比如 1499 一直superxor到0001

在千位有(1499-1000+1)个=500个1xor 因为500是10的倍数所以肯定xor的结果是0

在百位有499-400+1 = 100个4 有 399-300+1=100个3 有100个2 有100个1 所以也是0

在十位有150个9 ....有150个1 所以也是0

在个位有有150*10个9.... 所以也是0

至于为什么最小的循环单位是99 而不是9 是因为99=base^2 - 1

所以对于每个数abcdef 只要计算到abcdef-->abcd00到 abcdef即可

#include <iostream>
#include <cstring>
using namespace std;
//superXOR 满足(aºbºc) = aº(bºc )
//前所有的1+xxxx99项xor在一起都是0000000 


int ans[15]={0};//用来存储结果

//向ans中加x
void add(unsigned long long x){
    int i = 0;//从个位开始
    while(x){
        ans[i] += (x % 10);//加上最初的x的当前位的那个数
        //因为当前位是最低位(个位) 所以直接%10就可以了
        ans[i] %= 10;
        i++;//计算高一位的
        x /= 10;//处理左一位
    }
}
//计算从l加到r的superXOR
void superXOR(unsigned long long l, unsigned long long r){
    //将ans初始为0
    memset(ans,0,sizeof(ans));
    for (unsigned long long i = l; i <= r; ++i)
        add(i);//向ans中叠加

    //输出时要反着输出,这时候要找第一个最高位
    int high=14;//假设high是14
    for (; high>=0; --high) if(ans[high]!=0)//不是0
        break;
    if(high == -1)//说明全是0
        cout<<0;
    else
        for (int i = high; i >=0 ; --i)
            cout<<ans[i];
    cout<<endl;
}

inline bool judge(unsigned long long x){
    return x%100==99;
}

int main(int argc, char const *argv[])
{
    int N; cin>>N;
    for (int i = 0; i < N; ++i)
    {
        unsigned long long x; cin>>x;
        if(x<99)
            superXOR(1,x);
        else{
            unsigned long long tmp = x;
            while(!judge(tmp))
                tmp--;
            superXOR(tmp+1,x);
        }
    }
    return 0;
}

View Code