Multi-University Training Contest #7

Tue, 12 Aug 2014 18:54:43 +0800

贡献了两个-7.

Read more

Multi-University Training Contest #5 & #6

Fri, 08 Aug 2014 12:48:18 +0800

这两场由于爆OJ,罚时倍杀,我们队已经连续两场滚到Rank#30后了.

Read all

Multi-University Training Contest # 4

Mon, 04 Aug 2014 12:46:27 +0800

Read all

ZOJ Monthly, June 2014

Sun, 01 Jun 2014 22:55:51 +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