http://www.tsinsen.com/ViewGProblem.html?gpid=-1000001306
【题意】
定义x[1]=1,x[2k]=-x[k],x[2k-1]=(-1)^(k+1) x[k](k>1),回答三类询问
1、求xn
2、判断x1+..+xn的正负
3、求x1+..+xn
【输入】
第一行q,表示询问个数
接下来q行,每行两个数字c、n
表示询问类型和n(n<=10^8)
【输出】
询问1、3输出值即可
询问2输出“+”或“-”或“0”
唯一做出来的一道集训队题啊,最简单的一道了
而且是观察规律得出的结论
首先我把前64个的值打了一下表,然后观察
发现对于[1..4],[1..1]=[3..3],[2..2]=-[4..4] (=的意思是序列相同,=-是序列的值互为相反数)
拉长以后发现还具有如此规律,例如
对于[1..128],[1..32]=[65..96],[33..64]=-[97..128]
利用这个结论,就可以在logn时间内求x[1]+..x[n]了
如果知道这个还是不会求的话……何必勉强自己做集训队互测题呢……
program apex; var q,c,i,j,k:longint; one,o,n:int64; sum:array [0..64] of int64; function quick (now:int64):int64; var k:longint; ans:int64; begin if now=0 then exit(0); if now=1 then exit(1); if now=2 then exit(0); k:=trunc(ln(now)/ln(2)); if one shl k=now then exit(sum[k]); ans:=sum[k]; now:=now-(one shl k); if now<=one shl (k-1) then exit(ans+quick(now)); exit(-(quick(now)-sum[k-1])+ans+sum[k-1]); end; begin one:=1; sum[0]:=1; sum[1]:=0; for i:=2 to 63 do sum[i]:=sum[i-2]*2; read(q); for i:=1 to q do begin read(c,n); case c of 1:writeln(quick(n)-quick(n-1)); 2:begin o:=quick(n); if o=0 then writeln(0) else if o>0 then writeln('+') else writeln('-'); end; 3:writeln(quick(n)); end; end; end.