HAOI2015 解题报告

先给出ydc的题解地址: http://ydc.blog.uoj.ac/blog/336 T1(树上染色): 题目地址: http://cojs.tk/cogs/problem/problem.php?pid=1962 首先有一个基础的想法是DP:令f[i][j]代表以i为根的子树中选了j个黑色点的最小代价(代价指该子树中所有边对答案的贡献之和)。在转移时,只需要枚举在当前儿子中放几个黑色点,计算 … 继续阅读“HAOI2015 解题报告”

[CF 303D]Rotatable Number解题报告

 题目翻译 http://cogs.pro/cogs/problem/problem.php?pid=1939 题解 出于可看性,就不用那么严格的数学语言讲了…… 首先明确一下“循环数”的定义:比如142857,它乘以1,2,3,4,5,6(必须是连续的这些数)能不重不漏地得到142857的所有循环排列。 假设我们拿到了一个(十进制下的)循环数,不妨取142857.令x=0.142857 … 继续阅读“[CF 303D]Rotatable Number解题报告”

[CF 251E]Tree and Table题解翻译

题解翻译 如果N=1,则答案为2. 如果树中存在一个度数大于3的节点在,则答案为0.原因是网格中的每个格子的邻居数不超过3. 如果树中没有度数为3的节点,则答案为2N^2-2N+4.这一公式可以在题目其他部分的解答中自然地推导出。同时,我们也可以写一个简单的DP来计算这种情况下的答案。无论如何,我们现在证明这一公式。 首先,我们解决一个略有不同的问题,它在原问题的一个主要情况中也能用到。我们希望找 … 继续阅读“[CF 251E]Tree and Table题解翻译”

[CF 273D]Dima and Figure解题报告

题目翻译 http://cogs.pro/cogs/problem/problem.php?pid=1925 题解 就是DP…… F[k][mask][i][j]代表:当前图形的最下端是第k行,左右边界的开放/收缩情况是mask,第k行涂黑了i~j列。 具体讲,mask=0代表左右边界均收缩,mask=1代表左开放右收缩,mask=2代表左收缩右开放,mask=3代表左右均开放。 “收缩”左边界的 … 继续阅读“[CF 273D]Dima and Figure解题报告”

[CF 249E]Endless Matrix解题报告

题目翻译 http://cogs.pro/cogs/problem/problem.php?pid=1923 题解 首先很容易想到,我们只需要算“二维前缀和”,即以某点为右下角的子矩阵内的元素和。然后要求的那个值用容斥原理减一减就能算出来。 下面看怎么算二维前缀和(当然是模意义下的),记为S(i,j): 以6*6矩阵为例: 假设我们想算S(2,5)。它由两部分组成:第一部分是左上角的2*2矩阵,也 … 继续阅读“[CF 249E]Endless Matrix解题报告”

后缀自动机:O(N)的构建及应用

译者的话: 原文地址http://e-maxx.ru/algo/suffix_automata 俄文用google机翻成英文再翻成中文,错误在所难免,大家多包涵……如果有什么奇怪的话直接略过吧,因为这说明我也没看懂…… 后缀自动机 后缀自动机(单词的有向无环图)——是一种强有力的数据结构,让你能够解决许多字符串问题。 例如,使用后缀自动机可以在某一字符串中搜索另一字符串的所有出现位置,或者计算不同 … 继续阅读“后缀自动机:O(N)的构建及应用”

N=8时非递归FFT的演示

说明: S是用到的数组,S0~S3代表四个阶段 系数向量是a 第0轮(Rader变换后): 第1轮: 第2轮: 第3轮: 后记: 其实本来我是想写个类似讲解的东西的……然后发现智商太低写不出来……然后就像这样弄了个演示……然后就发现它变成了公式恐惧症患者的福音(╯‵□′)╯︵┻━┻ 然而!这并没有什么卵用(╯‵□′)╯︵┻━┻ 不过这里按照Rader-Brenner算法(也就是刘汝佳的模板所采用算 … 继续阅读“N=8时非递归FFT的演示”

[CF 335E]Counting Skyscrapers题解翻译

题目翻译: 见http://cogs.pro/cogs/problem/problem.php?pid=1921 题解翻译: 这道题中的摩天大楼描述了被称作跳跃表(Skip List)的数据结构。跳跃表在某种意义上和AVL、红黑树相似,因为它支持O(logN)的插入,操作和查找(包括上下界查询),同时支持常数时间的在排序顺序中前后移动。跳跃表和任何树结构都不同,因为它有实用的,不需要线程锁的(所谓 … 继续阅读“[CF 335E]Counting Skyscrapers题解翻译”