讲稿集训队作业solution

1、NOI 2000 SolutionsBy Amber假设可划分成 n 片，则问题转化为题目瓷片项链ring问题摘要解法 1源程序ring.dpr解法直接求值特殊数据结构N/A复杂度O(1)状态Accepted作题日期2005-6-10解法描述题目单词查找树 tree问题摘要解法 1源程序tree.dpr解法排序+遍历Sort + Traverse Tree特殊数据结构N/A复杂度O(N*log N) + O(Size), Size 表示输入大小。状态Accepted作题日期2005-5-21解法描述1.先排序 O(nlogn) 2.遍历 O(Size)由于排序后，数据是有序的，祖先（前缀）相同

2、的一定在一起，所以可以知道关于前 d复杂度O(ArticleLen*MaxWordLen)状态Accepted作题日期2006-5-3解法描述记 S(i.j)表示文章中第 i 位到第 j 位。记名词为 n，动词为 v，辅词为 a。分析抽象后有：两种短语：名词短语，记为 pn，正则式为：a*n；动词短语，记为 pv，正则式为：a*v。两种句子：一种正则式为 a*n，记为句型 1；一种正则式为：(a*n a*v)* ，记为句型 2。记(x, y)表示当前状态匹配了 x 个句子，y 个单词。它的比较是以x 为第一关键字，y 为第二关键字的比较。记 F(i, pn)是从第 i 位开始匹配的名词短语的状

3、态。若 S(i.j)是一个辅词，由 a*n，则下一个状态还是一个名词短语，即 F(j+1,pn) +(0, 1)。若 S(i.j)是一个名词，由句型 1 a*n，则下一个状态是一个新句子，且是一个名词短语打头，即 F(j+1,pn)+(1, 1)。若 S(i.j)是一个名词，由句型 2 (a*n a*v)*，则下一个状态还是在同一个句子中，且是一个动词短语，即 F(j+1,pv)+(0,1)。记 F(i, pv)是从第 i 位开始匹配的动词短语的状态。若 S(i.j)是一个辅词，由 a*v，则下一个状态还是一个动词短语，即 F(j+1,pv) +(0, 1)。若 S(i.j)是一个动词，由句型

4、 2 (a*n a*v)*，则下一个状态可以是一个新句子，且是一个名词短语打头，即 F(j+1,pn)+(1, 1)。若 S(i.j)是一个动词，由句型 2 (a*n a*v)*，则下一个状态可以在同一个句子中，且也是一个名词短语，即 F(j+1,pn)+(0,1)。这里 2,3 由于都是从 F(j+1,pn)转移来的，而 3 比 2 少了一个句子，比 2 优，所以情况 2可以不考虑。最后只要输出 F(1,pn)即可。由于实际状态实在太少，用化搜索会更快。这里用 Trie 来优化DP 时的操作速度，就不用枚举单词了。题目算符破译equation问题摘要解法 1源程序解法特殊数据结构N/A复杂度

5、状态Accepted作题日期解法描述题目青蛙过河frog问题摘要解法 1源程序frog.dpr解法数学特殊数据结构N/A复杂度O(1)状态Accepted作题日期2006-5-3解法描述记左岸起点为 s，右岸终点为 t。记 f(n, m)为河中有 n 块石头，m 片荷叶的最多从某个起点到某个终点通过的蛙数。这里起点，终点不在那 n 块石头内。设 n 块石头中其中一块为 p，则可以将第 1 到第 f(n-1, m)只蛙，通过 n-1 块石头(除了 p)和 m 片荷叶从 s 移动到 p。再将第 f(n-1, m)+1 到第 2f(n-1, m)只蛙，通过 n-1 块石头(除了 p)和 m 片荷叶从 s 移动到 t。最后将第 1 到第 f(n-1, m)只蛙，通过 n-1 块石头(除了 p)和 m 片荷叶从 p 移动到 t。即f(n, m) = 2f(n-1, m)。边界 f(0, m) = m+1，即 m 片叶子只能承载第 1到 m 只蛙，剩下的蛙跳到 t，最后所有蛙按次序都到 t。经过简单数列推导，有 f(n, m)=(m+1)*2n。位前缀相同的单词的范围（扫描区间）。这里 d 为深度。解法 2源程序tr