sjtu oj 1201. 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

一开始读错题了..这都能读错也是没谁了。

就是求1~n这些数的和不进位。难度不大。但注意细节，思路一定要清晰。否则无限tle 无限re

思路：打表发现末尾是99的结果是0 那么找到比n小的末尾是99的对***99~n 求其和就行了。

/* ***********************************************
Author        :guanjun
Created Time  :2016/3/12 9:39:27
File Name     :sjtu1201.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ll long long

#define mod 90001
#define INF 0x3f3f3f3f
#define maxn 10010
#define cle(a) memset(a,0,sizeof(a))

const double eps=1e-5;
using namespace std;

int ar[100],num;
void add(ll x){
    num=0;
    while(x>0){
        ar[num]+=(x%10);
        ar[num]%=10;
        x/=10;
        num++;
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    int t;
    ll n,k,m;
    cin>>t;
    while(t--){
        cin>>n;
        m=n;
        cle(ar);
        if(n>99){
            while(1){
                if(n%100==99){
                    k=n+1;
                    break;
                }
                n--;
            }
            for(ll i=k;i<=m;i++)add(i);
        }
        else for(ll i=1;i<=n;i++)add(i);
        ll ans=0;
        ll tmp=1;
        for(int i=0;i<num;i++){
            ans+=ar[i]*tmp;
            tmp*=10;
        }
        cout<<ans<<endl;
    }
    return 0;
}