codeforces round #594 题解

rating暴涨,感谢hzwer带妹修行(雾

A. Integer Points

sb题,对于y=x+a和y=-x+b,有整数交点的条件是a,b之差是2的倍数。

 

B. Grow The Tree

sb题,一共有n个棒,其中一半用于向上拓展,另一半用于向右,贪心地取n/2个最短的棒向一个方向延伸,剩下的棒向另一个方向。选择最短的棒,由于数字范围<=10000,遂想到计数排序。

 

C.Ivan the Fool and the Probability Theory

花了一个小时才想明白……

首先考虑只有一行的情况,同色的最多只能有两个连在一起,情况数即可由斐波那契数列递推得到。

再考虑之后的每一行,根据题意,该行要么和前一行的每一位都不同,要么和前一行完全相同。显然,第二种情况必须满足前一行是黑白交替的,如ABABABAB或BABABABA,则将全部的情况分为两种:

1.第一行形如AABBABAB,即存在两个同色的连在一起的情况,此时若第一行确定了,整个n*m的图也随之确定。

2.第二行形如ABABABAB,即不存在两个同色的连在一起的情况,那么对于接下来的每一行,要么和第一行一样(ABABABAB),要么和第一行每一位都不同(BABABABA),由于不能存在完全相同的三行,依然满足斐波那契数列。

以4*5为例,只考虑第一行,情况数为16(其中包括ABABA和BABAB这两种情况),那么有14个图已经确定了,只讨论剩下2种。

第一行可以为ABABA或BABAB,第二行也可以为BABAB或ABABA,因此F[1]=2,F[2]=2*2=4;递推得到F[4]=10.

答案为:F[4]+14=24.

 

点赞
  1. seahore说道:

    sb题还行

发表评论

电子邮件地址不会被公开。 必填项已用*标注