[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题解翻译”

[国家集训队2011]Crash的文明世界 …

题目: http://cogs.pro/cogs/problem/problem.php?pid=1888 Crash小朋友最近迷上了一款游戏——文明5(CivilizationV)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。 现在Crash已经拥有了一个N个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此Crash只修建了N- … 继续阅读“[国家集训队2011]Crash的文明世界 …”

[Topcoder SRM 467]均匀字符串Next…

题目: http://cogs.pro/cogs/problem/problem.php?pid=1906 我们称一个字符串是“均匀的”,如果它每个长度为n的连续子串都包含不超过d个不同的字符。对于一个字符串seed和一个长整型整数k,定义k大均匀字符串为:所有和seed长度相同且字典序大于等于seed的均匀字符串中,按字典序从小到大,从0开始数的第k个。这里所说的字符串只包含小写字母。给出n,d … 继续阅读“[Topcoder SRM 467]均匀字符串Next…”

WC2015总结&解题报告(伪)

这次三道题:k小割,混淆与破解,未来程序。 先看“k小割”:啥啥啥这都是啥…… 然后看“混淆与破解”:范浩强居然真敢把讲课内容出出来……但是问题①GL算法的后半部分完全没听懂②即使听懂了算法显然也做不出来,不过没准前40分(m=1)的可做 “未来程序”:去年是给程序和输出凑输入,今年直接给程序(源代码都给了)和输入求输出? 不管了第一题10分暴力走你┏ (゜ω゜)=☞,方法是2^m枚举边集然后O( … 继续阅读“WC2015总结&解题报告(伪)”