TopCoder SRM 543 DIV2

昨天熬夜做了人生的第二场SRM，还是有所收获的，总结总结。

250：

超级简单的题，读懂题意就基本上出来了。

500：

一道考异或操作的题，给定一个整数区间[L,R]，要求计算L XOR L+1 XOR L+2 XOR ...... XOR R 的值，L,R可以在1-4000000000的范围内。

乍一看，模拟肯定会超时的，于是分解吧，分解成二进制数，根据XOR的性质来看看是否能够有些思路，

把0-15分解成二进制数：

0000 0

0001 1

0010 2

0011 3

0100 4

0101 5

0110 6

0111 7

1000 8

1001 9

1010 10

1011 11

1100 12

1101 13

1110 14

1111 15

逐位的考察，发现第i位，会出现连续的i+1个0或者1，由于异或的性质，xor 0 是不影响的结果的，忽略0的个数，考察1的个数对于i>0的位来讲，只有在[L,R]区间的开始和末尾的一段会对xor后的结果有影响，因为中间的一段1的个数都是2^i的倍数个，xor以后结果仍然是0，那么L，R必然在这特殊的两段内，如果在这两段内第i位的值都是0，那么结果就是0，如果L所在段为1，R所在段为0，那么L所在段异或的结果为 (L mod 2^i)，如果L所在段第i位为0，R所在段第i位为1，那么R所在段的异或结果就是not（R mod 2^i）,如果同时为1，考虑两种情况，L，R在同一段内，那么1的个数为（R-L）个，如果L,R不在同一段内，结果就是 （L mod 2^i）xor (not (R mod 2^i)).其实这两种情况都可以归并为L,R不在同一段内的结果，应为考察的段的长度为2^i,是偶数，那么

111......11111

l r

l - r 之间所有1异或的结果其实就等于0-l-1 r+1-2^i这两段内所有1异或的结果。 而如果L,R在同一段内，那么按照第二种方式计算的意义就是 l-2^i 和 0-r 这两段1异或结果的异或，由于异或的性质，l-r这一段实际上相当于没有异或过，所以结果就是0-l-1 r+1-2^i这两段内所有1异或，等价于l-r之间的异或。

而第0位需要特殊处理下，判断[L,R]内第0位为1的个数即可。

各种蛋疼：默认的整数常量是int型，如果需要使用超出int型范围的整数，那么在常量后面加ll比如123ll（当时没测极限数据就交了，导致悲剧了。System Test Failed。。。）

讲了这么多，由于表达力很搓，还是贴出代码，免得以后忘记。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct EllysXors{
	long long p2[64];
	void init(){
		p2[0]=1;
		for(int i=1;i<64;i++){
			p2[i] = p2[i-1]<<1;
			//cout<<p2[i]<<endl;
		}
	}
	long long getXor(long long L,long long R){
		init();
		long long ans;
		ans = (!(L&1))&&(((R-L+1)/2)%2);
		ans = ans||((L&1)&&(((R-L+2)/2)%2));//第一位特殊处理
		int len = max((int)log2(L)+1,(int)log2(R)+1);
		for(int i=1;i<len;i++){
			long long b1,b2,r1,r2;
			b1 = !(((1ll<<i)&L)==0);
			b2 = !(((1ll<<i)&R)==0);
			r1 = L%p2[i];
			r2 = R%p2[i];
			//cout<<b1<<" "<<b2<<" "<<r1<<" "<<r2<<endl;
			if((b1^1)&&(b2^1))ans+=0;//都是0
			if((b1&1)&&(b2^1)){
				if(!(r1%2))ans+=0;//偶数次1
				else ans+=(1ll<<i);//奇数次1
			}
			if((b1^1)&&(b2&1)){
				if(!(r2%2))ans+=(1ll<<i);
				else ans+=0;
			}
			if((b1&1)&&(b2&1)){
				long long set=0;
				if(r1&1)set=1;
				if(!(r2&1))set=!set;
				ans+=(set<<i);
			}
			//cout<<ans<<endl;
		}
		return ans;
	}
};

1000：题目还没看就OVER了。。