NOIP集训-10.21总结
NOIP集训-10.26总结

NOIP集训-10.22总结

YYY posted @ 2015年10月22日 17:18 in OI相关 with tags 异或 搜索 逆序对 , 494 阅读
_THIS_IS_START_OF_ARTICLE_
其实这套题还是蛮简单的...
然而我还是挂零了...
 
挂零了!!!
考场上简直不要胡思乱想..
---------------------------------------------------------------------------------------
异或:SuperOj947
首先可以知道对于一个偶数a,一定有a⊕(a+1)=1
首先可以知道k=1时,输出l
k=2时,输出l⊕r
k=4时,若r-l+1>4,一定可以选出偶奇偶奇这样的形式
       若r-l+1=4,2^4暴力就可以了
k=3是最复杂的,现在我们尝试在[l,r]内选出3个数使其异或和为0(为1的话就当成k=2的情况做就好)
我们需要在[l,r]以内选出三个数x,y,z满足x⊕y⊕z=0
不妨假设x>y>z,假设x=2^t+a,y=2^t+b,那么一定有z<2^k
只需要取a=(2^t)-1,b=0,z=(2^t)-1就可以了,
然后只需要枚举t,验证x,y,z是否在[l,r]以内就好,
可以证明这样一定是最优的,因为这样同时让最大的数(x)取到了最小,让最小的数(z)取到了最大
---------------------------------------------------------------------------------------
树:SuperOj948
考试的时候看了一眼就就开始写点分了,结果发现常数太大了只能得60分
然后!!这个题的标算是O(n)的!!O(n)你特么给3*10^5的范围!!
好吧,只需要发现每条边的贡献是其两边点的个数之积,这个O(n)算出来就行了
最后还要把答案乘以二,因为点对是有序的((u,v)和(v,u)是两个不同的点对)
---------------------------------------------------------------------------------------
玩具:SuperOj949
乍一看是神题,仔细一看发现是SB题(我到考试结束都没发现这个..因为根本就没看这道题,调第二题去了..)
发现两个玩具如果宽度相加大于了总的宽度,他们一定不能互换位置
如果可以找到一对玩具,他们的相对位置是和原来相反的且不能互换,那么就不行
如果这不到这样的一对,就可以
---------------------------------------------------------------------------------------
_THIS_IS_END_OF_ARTICLE_

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter