昨天熬夜做了人生的第二场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了。。
分享到:
相关推荐
topcoder-srm Topcoder SRM竞赛解决方案 测试是使用kawigi edit构建的。
你可以通过这道题去了解Topcoder的题目以及比赛形式
关于TopCoder的竞赛指导,不仅仅是SRM,还有Bug Race、软件比赛的资料,是我从网上收集的,大部分是中文的
topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 , 1 <= K <= 1000.
TopCoder SRM程序 我尝试过的TopCoder SRM程序列表。 在大多数时候,比赛时间与我的工作/其他活动冲突,因此我对TopCoder不太活跃。 但是我尽力去参加比赛,因为这很有趣。 就像在任何在线比赛中所期望的那样,代码...
topcoder-srm 顶级编码器srm问题集锦
Topcoder软件比赛注册方法和平台使用 Topcoder算法大赛客户端安装流程 Topcoder算法大赛客户端登陆及使用 Topcoder算法大赛注册流程 Topcoder图形比赛注册方法和平台使用
适合topcoder新手
topcoder竞赛的算法讲座ppt
TopCoder比赛登录使用的客户端,需要配置Java环境
topcoder算法讲座ppt
TopCoder新手入门指南,一步步操作既可以了,然后开启您的Topcoder编程之旅吧。
topcoder arena,包含ContestAppletProd.jnlp,CodeProcessor.jar,FileEdit.jar,TZTester,运行需要jre环境
Topcoder的Java客户端,安装前确定已经安装了JRE
用于topcoder的第3方编辑器插件。
TopCoper SmartWordToy problem 解决方法,C++源码。 Problem Statement The toy company "I Can't Believe It Works!...Form: http://community.topcoder.com/stat?c=problem_statement&pm=3935&rd=6532
topcoder的比赛作品,编译通过的。可以放心使用。
topcoder入门,对想做tc,但又不知道怎么搞的很有帮助,我首先也不知道搞。
给新手提供的TopCoder注册方法和平台使用 十分详细
这是一类关于acm学习的资料,它详细的说明了Acm学习的内容,如何提高编写软件的能力