算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
   给两个长度为200,000的全排列a,b. 寻找整数k的个数,使a的每个数加上k以后,是b的子序列.

算法分析:
   用线段树维护哈希值...神思想...

   根据b数组构造c数组,使c[b[i]] = i, 也就是大小为i的值在b中的位置.
   这样的话,从k 到 k+n,就对应了c中的一段连续区间. 这是一个匹配问题, 很容易想到多项式哈希.
   
   我一开始想的匹配方法是将c数组中的子串进行离散化去和a的变化数组进行匹配,发现需要用splay维护.... GGG...
   
   正解是,用c数组一段连续区间,对应的b数组中的位置进行哈希直接和a数组匹配,这样不需要涉及数值的离散化,位置的离散化直接用线段树就和哈希值一块维护了. Orz....

代码 http://codeforces.ru/contest/213/submission/1997993
posted on 2012-08-10 22:54 西月弦 阅读(459) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

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