`
Coco_young
  • 浏览: 119185 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

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了。。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics