4
23
2015
1

tyvj四月份有奖赛

题意什么的还是上tyvj上看吧 链接

 

A.P3792 小Q的约瑟夫环

 

实际上当约瑟夫问题k=2(即删一个人跳一个人的时候)n个人剩下的那个人的编号就是把n写成2进制后最高位1去掉移到最低位上。

这个结论我也记不得在哪看到了,不过考场上还是打了张表确认了一下。

于是考场上就写的这样的暴力。最后好像因为爆了long long然后WA掉10分。

之后看题解发现 做法真是神爆了

每次操作实际上相当于把n的二进制上有的1尽量往最低位放,然后就可能消掉一些0。而1的个数是始终不会变的,所以ans就是与n的二进制表示上的1的个数位数相同的且每一位都是1的数!Orz唐老师

 

B.P3793 小Q的幸运数字

 

这题其实很简单。我们差分这个序列,就成了一个经典问题了。前缀和?用组合恒等式即可。

 

D.P3798 小Q的幻想之乡

 

写出式子来发现好像jzptab啊,然后化简了一下发现真和jzptab一样啊。推式子的时候细心一点。

 

C.P3794 小Q的无敌异或

 

我考场上会做第一问的100分,但是只会做第二问的50分啊。哭瞎

第一问从前往后扫,然后记录一下每一位为1的有多少个,然后按位考虑统计一下就好了。

第二问是难点,当然后来才发现也不难。不妨认为a[i]的前缀和为sum(i) 那么一段区间a[l……r]的和的k位上为1的充要条件是

(sum(r)-sum(l))%2^(k+1)>=2^k

看见式子是不是感觉很有道理啊。然后我们还是按位考虑,计算有多少个子区间和为k位上为1。

有了上面这个式子之后,我们就可以对sum(r)%2^(k+1)进行离散化,然后用树状数组查询一下就可以了。

当然还有分情况。

 

T4只有我一个人A什么情况,神犇们都不屑于参加这种比赛吗QAQ

alpq本来可以AK的,然后T3优化常数写挂了(之前的提交A了),T4不小心推错了式子。momo。。。

领个奖品居然还要爆照,我长成这样爆了照以后在OI届还怎么混啊

Category: tyvj有奖赛 | Tags: | Read Count: 440
Avatar_small
Tunix 说:
2015年4月23日 16:03

跪跪跪!!!zyf怒踩alpq


登录 *


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

| Theme: Aeros 2.0 by TheBuckmaker.com