posts - 11, comments - 2, trackbacks - 0, articles - 0

Waterloo local 2001.01.27

Posted on 2009-02-11 18:43 hello_world 阅读(1298) 评论(0)  编辑 收藏 引用
Waterloo local 2001.01.27
  题目分类
 Gopher II  图论,二分图匹配
Tight words  DP
 WERTYU  简单题
Division math(高精)
Hotter Colder 半平面交(geometry)

Gopher II:
只需要把老鼠看着一个集合,鼠洞看着一个集合,然后鼠与洞之间有边相连仅当鼠能在规定时间跑到洞中,然后求最大匹配,用总数减去最大匹配即为答案!

Tight words :
题意:给一个字母表 {0, 1, ... , k}, 0 <= k <= 9 ,问一串长度为 n 的字符串(只含给定字母表中的字符)是否是紧凑的,紧凑的定义是相邻字符之差的绝对值不大于 1

dp中状态是长度为 i 最后一个字符为 j 的概率p[i][j],状态转移为
p[i][j]  =  1/k                              (i=0;   j=1,2..k)
p[i][0] =  p[i-1][0]/k   +   p[i-1][1]/k                                  (i>0)
p[i][k] =  p[i-1][k]/k   +   p[i-1][k-1]/k                               (i>0)
p[i][j]  =  p[i-1][j-1]/k +   p[i-1][j]/k    +    p[i-1][j+1]/k      (i>0,   j=1, 2, 3...  k-1)




Division :
这道题要高精度, 建议用 java
题目问 (t^a - 1)/(t^b -1) 是不是小于 100位 的整数,如果是,求出它的值
t, a, b 为小于2147483647 的正整数
我做的时候是先猜出他的判断条件,判断条件比较容易猜:

猜想 :仅当 b | a 时,上述表达式是整数

有这个猜想,就可以把上述表达式化减成等比数列
1 + t^b + (t^b)^2 + (t^b)^3 + ... + (t^b)^(a/b - 1)
接下来只要二分求出这个式子的和,由于和有最大100位,所以要用高精度,还有要注意特判 t==1 的特殊情况,我在这里wa了好几次

做题时因为是猜的,交的很忐忑 ><!现在贴出证明,从discuss里淘出来的
gcd(a^m - 1, a^n - 1) (m > n)

if m = p*n + r (0<r<n)
then
a^m - 1 = a^(p*n+r) - a^r + a^r - 1
= a^r(a^(p*n)-1) + (a^r-1)

since (a^n-1) | (a^(p*n)-1)

and (a^r-1) < (a^n-1)

so r==0

所以   m%n==0




Hotter Colder:
题目不赘述了,有兴趣的可以直接看题目
这道题中的游戏很像一个人不断报价,另一个人不断告诉你是多了还是少了,
与报价不同,报价是一维的,这道题是二维的
很裸的半平面交, 数据很弱,而且就题目本身来说,它是切割一次输出一次答案,
这里用 o(n^2) 的算法反而比 o(nlogn)的算法好


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理