【codechef】January Challenge 2015

2015年1月12日2,0520

CHEFSTON

GCDQ

gcd满足区间加法TAT,所以维护前缀和后缀和就好了

SEAVOTE

去掉所有0后

若∑bi < tot 或∑bi >= 100+n 则无解

否则有解

ONEKING

按照右端点排序,选择第一个的右端点,删去覆盖其的线段。。。

剩下的线段同理

CLPERM

答案根据第一个不能合成的数奇偶性得出

若用一些数字合成1-sum,加入一个数x(x<=sum+1),则能合成sum+x

由于sumK<=5^10^5,若能合成1-500000,依据上面的结论,可以获得所有1-剩余的n-K个数字之和

所以暴力判断1-500000是否能合成(根号级别的运算次数),若能的话根据剩余的n-K个数字之和得到答案


QSET

如果a,b满足前缀和取模相等,则a+1~b的和取模等于0

显然可以用线段树维护区间 前缀和取模为0,1,2的数量

单点修改区间查询

XRQRS

kuribohG说,裸题+傻逼题,作为一个中国人都应该可以A掉

唔可持久化字典树裸题。。。

纯模板没啥难度

SEALCM

举个例子

lcm能被12整除的=m^n-lcm不能被12整除的

lcm不能被12整除的=(M-M/4)^N+(M-M/3)^N-(M-(M/4+M/3-M/12)^N

比较麻烦的容斥

RANKA

写这个我血都要喷了

usedtobe提供了一种简单的做法

——————————————————–

1111->0000->2222->0000

1111   0000   2222   0000

1111   0000   2222   0000

1110   0002   2202   0010

——————————————————–

以下是我用的做法。。。

我没考虑到如果棋盘上只有一个空格,其它均为1,在空格放2会把全部的1都吃掉

我认为吃对方的棋子首先自身棋子要有气T T(主要是自己弱)

设两种棋子分别为1,2

开始的想法是,先填上半2,然后填下半1的时候把上半1吃掉

然后想个办法让每次填的顺序不同

发现每次每半边留一个异色棋子即可,然后每次改变异色棋子的位置

即如下(为了简便缩小了棋盘),还要注意不能出现重复的情况

1000->0222->0222->0000->0100->2022

0000   2222   2222   0000   0000   2222

0000   0000   0000   1111   1111   0000

0000   0000   0002   1112   1111   0000

结果发现这样只有5000步TAT FK!

又拿出两行来,一开始是这样

0000

1111

做完一次在第一行放个1变成

1000

1111

然后重新搞。。。。这样就能把方案乘以9了

但是这样容易有重复的情况。。。在每次的开始和结束局面

只要把异色棋子的枚举范围每次缩小一点即可

以下代码有一行if(bx==T+2&&by<k)continue;

唔我的逗比代码,把注释去掉运行可以看到每一步的运行

单独的提子我没有搞出来

SEAND2

写了个无脑随机化得分0.755

预处理f[i][j]表示第10^i mod b[j]的值,在随机交换过程中可以加速