Posted on 2009-11-16 02:34
王之昊 阅读(190)
评论(0) 编辑 收藏 引用
NOT TWO
一道有意思的数学题, m * n的棋盘最多能放几个子,要求每格只能放一个,且任意两个的距离不能为2
令人眼前一亮的是出题人把棋盘划分为四部分,每部分相互独立,的确优美
IOIString
关键想到反面.即求有多少个不是IOIString的串,再用所有情况减去之. 而这样想是看到了一个结论:
若该串不是IOIString,那么其所有的 I 等距, 且相邻 I 差距奇数个.然后就可以搞了.
简略证明一下那个结论: 题目说 I 在 位置 a 上, O 在位置 a + b上, I在位置 a + 2*b上 就构成了一个IOIString.
1 那么相邻的两个I之间必相差奇数.如果相差偶数( a , a + 2*k) 那么中间必有 (a + k)是O,矛盾
2 必等距, 如果不等距 三个位置为a , a + b a + b + c ( b != c)则中间必有一点为 a + (b+c)/2是O ,矛盾
此题让我第一次在tc上tle, 悲剧
IOIString 和IOI有什么关系莫?
IncreasingNumber
看到10^18数位的数着实吓了一跳, 这么长的一个数!!!
出题者将一个递增数表示成 a*1 + b*11 + c*111 + .... (a + b + c + .. <= 9)的表示方式以前没见过,感觉很好
然后接下来的就简单了.自然想到把模divisor相等的归到一类.而且这一类里面的东西是等价的.然后再dp
1 , 11, 111, ..., ( mod divisor)是一个P字形的循环.刚开始没反应过来
举个例子来说如果 11 = 1111 ( mod d) 那么 111 = 11111(mod d) 因为 11 * 10 + 1 = 1111 * 10 + 1 (mod d)
无限ym petr. 再次 ym petr~~