Codechef May Challenge, 2015

Tue, 19 May 2015 11:10:57 +0800

Read all

Codechef January Challenge, 2015

Sun, 15 Feb 2015 19:51:08 +0800

Read all

Codechef November Challenge 部分题解

Sun, 15 Feb 2015 19:50:44 +0800

只做了其中的几个题。
 

Read more

Codechef September Challenge 题解

Sat, 20 Sep 2014 12:14:58 +0800

Read all

Codechef May Challenge 简要题解

Tue, 20 May 2014 21:01:56 +0800

马上就要ZJOIDay2了,补上这个月challenge的题解。

Read all

Codechef April Challenge 简要题解

Sat, 10 May 2014 20:21:36 +0800

POTATOES  BINTREE  ADIGIT  CNPIIM  TANGDIV  ANUCBC 签到题
 
FBCHEF
 
    要求维护一棵带权有根树,每个时刻可能对一个点投放炸弹,威力为x,则对于一个点,与其距离d,那么将这个点的权值减去int(x/(1<<d)).询问时是询问一个点的子树中有多少个点的权值非正。
 
    对于每次修改,有影响的点和这个点的距离不会超过log(x).更新的时候沿着这个点往上走log(x),按照bfs序更新。最后离线统计答案。
 
GERALD08
   一颗有根树,边为黑色或白色。Chef每次可以操作白边,Ksen每次可以操作黑边。两人轮流割边,割了以后把在这条边以下的边全部割掉。不能操作者败。问胜败情况。
 
    
    使用Surreal_Number.Surreal Number 表示的是一种局面,递归定义,表示为{L|R},其中L代表Chef能转移到的局面,R代表Ksen能转移到的局面。每个Surreal Number都对应着一个数,这个数可以表示为a+b/(2^k), a,b,k为整数。把两个状态并起来就是直接把两者的Surreal Number相加。要往上面加一个白边,如果之前加入的也是白边,那么就直接+1,否则假设之前的surreal number为a+b/(2^k),那么新的surreal number为(b+2^k)/(2^(a+k)).
    如果是黑边,可以先把状态取反,按照上述方法算完后,再次取反。最后如果局面的surreal number为G,G>0则Chef必胜,G<0则Ksen必胜,G=0则后手必胜。因为涉及高精,使用python+常数优化可过。
 
SEAPERM(Challenge Problem)
    我的思路是前几个放几个大的,把后面从小到大排序,然后调整参数,小范围random_shuffle 或 某种排序,多次取最优。改进后最终得了0.99pt.
 
LMATRIX3(Make it Zero3)
    不会。 T_T