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

题目翻译 http://cogs.pro/cogs/problem/problem.php?pid=1925 题解 就是DP…… F代表:当前图形的最下端是第k行,左右边界的开放/收缩情况是mask,第k行涂黑了i~j列。 具体讲,mask=0代表左右边界均收缩,mask=1代表左开放右收缩,mask=2代表左收缩右开放,mask=3代表左右均开放。 “收缩”左边界的意思是:在第k行之前的每一行,涂黑部分最左都没有越过i,右边界就是最右没有越过j。 “开放”左边界的意思是:在第k行之前的某一行,涂黑部分最左越过了i,右边界就是某一行越过了j。 显然,收缩边界只能由收缩边界转移而来,否则就... 查看更多

[CF 249E]Endless Matrix解题报告

题目翻译 http://cogs.pro/cogs/problem/problem.php?pid=1923 题解 首先很容易想到,我们只需要算“二维前缀和”,即以某点为右下角的子矩阵内的元素和。然后要求的那个值用容斥原理减一减就能算出来。 下面看怎么算二维前缀和(当然是模意义下的),记为S(i,j): 以6*6矩阵为例: 假设我们想算S(2,5)。它由两部分组成:第一部分是左上角的2*2矩阵,也就是1+2+3+4,这是一个自然数列求和。第二部分是三列:5,6;10,11;和17,18。特点是什么呢?我们来看每一列的和,也就是5+6,10+11,17+18这三项。第一项5... 查看更多

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

译者的话: 原文地址http://e-maxx.ru/algo/suffix_automata 俄文用google机翻成英文再翻成中文,错误在所难免,大家多包涵……如果有什么奇怪的话直接略过吧,因为这说明我也没看懂…… 后缀自动机 后缀自动机(单词的有向无环图)——是一种强有力的数据结构,让你能够解决许多字符串问题。 例如,使用后缀自动机可以在某一字符串中搜索另一字符串的所有出现位置,或者计算不同子串的个数——这都能在线性时间内解决。 直觉上,后缀自动机可以被理解为所有子串的简明信息。一个重要的事实是,后缀自动机以压缩后的形式包含了一个长度为n的字符串的所有信息,仅需要O(n)的空... 查看更多

N=8时非递归FFT的演示

说明: S是用到的数组,S0~S3代表四个阶段 系数向量是a 第0轮(Rader变换后): 第1轮: 第2轮: 第3轮: 后记: 其实本来我是想写个类似讲解的东西的……然后发现智商太低写不出来……然后就像这样弄了个演示……然后就发现它变成了公式恐惧症患者的福音(╯‵□′)╯︵┻━┻ 然而!这并没有什么卵用(╯‵□′)╯︵┻━┻ 不过这里按照Rader-Brenner算法(也就是刘汝佳的模板所采用算法)详细地写出来了N=8的FFT变换的全过程,可能对理解FFT有一定帮助吧…… ... 查看更多

[CF 335E]Counting Skyscrapers题解翻译

题目翻译: 见http://cogs.pro/cogs/problem/problem.php?pid=1921 题解翻译: 这道题中的摩天大楼描述了被称作跳跃表(Skip List)的数据结构。跳跃表在某种意义上和AVL、红黑树相似,因为它支持O(logN)的插入,操作和查找(包括上下界查询),同时支持常数时间的在排序顺序中前后移动。跳跃表和任何树结构都不同,因为它有实用的,不需要线程锁的(所谓‘无锁’),线程安全的实现方式。无锁跳跃表被用作MemSQL中主要的存储数据结构,并且Bob使用的,穿过摩天大楼的算法是一种O(logN)的方法,它能让人们估算跳跃表的大小。因此,如果Bob最... 查看更多

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

题目: http://cogs.pro/cogs/problem/problem.php?pid=1888 Crash小朋友最近迷上了一款游戏——文明5(CivilizationV)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。 现在Crash已经拥有了一个N个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此Crash只修建了N-1条道路连接这些城市,不过可以保证任意两个城市都有路径相通。 在游戏中,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,seed,k,你需要计算并输出k大均匀字符串。如果合法的字符串少于k+1个,输出空字符串。1... 查看更多

WC2015总结&解题报告(伪)

这次三道题:k小割,混淆与破解,未来程序。 先看“k小割”:啥啥啥这都是啥…… 然后看“混淆与破解”:范浩强居然真敢把讲课内容出出来……但是问题①GL算法的后半部分完全没听懂②即使听懂了算法显然也做不出来,不过没准前40分(m=1)的可做 “未来程序”:去年是给程序和输出凑输入,今年直接给程序(源代码都给了)和输入求输出? 不管了第一题10分暴力走你┏ (゜ω゜)=☞,方法是2^m枚举边集然后O(n+m)判断是否是割集 然后玩提答。 program1:这难道是传说中的快速乘?然后愉快地码了一个出来,用计算器验算正确 program2:让它算了几个小数据,发现是……Fibonac... 查看更多