poj 1743 题意：n个数字（1..88）表示的音符，问最长的连续两段长度至少为5的变化相同的音符段的长度。。。 思路：求最长重复字串。。。。很容易想到后缀数组。。但是这道题多了一个不可重叠的要求。 先二分答案,把题目变成判定性问题:判断是否 存在两个长度为 k 的子串是相同的,且不重叠。解决这个问题的关键还是利用 height 数组。把排序后的后缀分成若干组,其中每组的后缀之间的 height 值都 不小于 k。例如,字符串为“aabaaaab”,当 k=2 时,后缀分成了 4 组,如图 5 所示。 容易看出,有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。然 后对于每组后缀,只须判断每个后缀的 sa 值的最大值和 …

ural1517 题意：给出两个字符串，求最长的公共字串（要求出具体的字符串是什么） 思路：依然是后缀数组，在更新长度 的时候记录起始位置即可，1A。以及，发现多开了一个完全没有必要的数组w[],这次已删。 20160730update:模板已更正，lrj的模板的rk[i]为0 的时候会出现re的问题...已特判。 /* *********************************************** Author :111qqz Created Time :2016年07月31日 星期日 00时36分19秒 File Name :code/ural/1517.cpp …

poj2774 题意：给出两个字符串，问最长的公共连续字串。 思路：后缀数组模板题。 具体可以参考两篇国集论文（09，04） topcoder中的讲解 codechef上的讲解 还有一篇讲 dc3算法的论文：SuffixArrays_dc3 这里不谈具体的后缀数组的学习内容，说说大概的学习过程。 首先要理解**后缀，后缀数组（sa[]），名次数组(rk[])，height数组，lcp **这些概念 先从定义入手，得到sa数组的n2logn的求法... 由于复杂度爆炸，所以有了两个算法来优化求sa的过程，一个是nlogn的倍增，还有一个是O(n)的dc3。。。 倍增的算法中用到了radix sort 上面这些，都是在说如何求sa,但是 …

hdu1280 题意：给出n(3000)个数，两两求和，输出最大的m(5000)个和。 思路：由于数据有限，想到计数排序。。。以及，m个可能刚好某个数据没有全部输出，要在while里判断一下。。 。。。好好的人。。怎么开始刷水了。。。。。 其实是因为最近在看.suffix array...然后里面涉及到了radix sort..算法课的时候到是写过。。。不过快忘了orz。。所以打算找几道题目。。。？ 然而这是计数排序不是基数排序啊摔/！ /* *********************************************** Author :111qqz Created Time :2016年07月30日 星期六 17 …

原文链接：链接 讲了后缀数组的概念，然后从最暴力的O(nnlogn )的复杂度(O(n)用来比较字符串，O(nlogn)是排序的复杂度)逐步优化，依据各个串之间的关系，大概讲了倍增算法，以及给出了一篇The Skew Algorithm 的论文。 文中实现的倍增算法的复杂度是O（Nlog2N）的。。是因为作者不会基数排序23333。 This text will focus on the construction of Suffix Arrays, it will aim to explain what they are and what they are used for and hopefully some examples …

1874: [BeiJing2009 WinterCamp]取石子游戏 Time Limit: 5 Sec Memory Limit: 162 MB Submit: 726 Solved: 296 [Submit][Status][Discuss] Description 小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子。 Input 输入文件的第一行为石子的堆数N 接下来N行，每行一个数Ai，表示每堆石子的个数 接下来一行为每次取石子个数的种类数M 接下来M …

cf429 b 题目链接 题意： n*m个格子，每个格子有一个人value a[i][j]>0，连个人，一个从左上角到右下角，每次只能向下或者向右移动，一个从左下到右上，每次只能向上或者向右移动，现在要求两个人恰好相遇一次，相遇点的a不算数，问在满足这样的条件下使得两个人的a最大。。。（很坑的一点是。。这里相遇并不考虑时间。。就是说，不在同一时间都到达过某一格子，也认为相遇。所以我认为，题目含义更准确的说法是，路径只有一个交点） 思路：很巧妙。先预处理4个二维数组，分别表示点(i,j）到四个角落的最大值。（这个处理很容易，类似数字三角形） 然后枚举相遇的点，对于确定的相遇的点(x,y)，我们可以认为是四个角落各连一条线到 …

hdu 2050题目链接 题意：n条折线。。最多能把平面分成几部分。。 思路：联想到m条直线，最多能把平面分成m*(m+1)/2+1部分。。 画图发现。。。 f[2*n-1]==g[n]。。 /* *********************************************** Author :111qqz Created Time :2016年07月27日 星期三 20时28分57秒 File Name :code/hdu/2050.cpp ************************************************ */ #include <cstdio> #include …

hdu 2049 题目链接 题意：n个妹子和n个汉子对应。。然后让每个汉子取选一个妹子，不能重复，问恰好有m个汉子选错妹子的可能的方案数。 思路：从n个中选n-m个，然后做剩余m个错排即可。 答案就是c[n][n-m]*d[m] c[]为组合数公式，d为错排公式。 然而wa到死。。。 因为我用了double....有毒。。。 double表示整数也是会丢失精度的！！！ double表示整数也是会丢失精度的！！！ double表示整数也是会丢失精度的！！！ double表示整数也是会丢失精度的！！！ double表示整数也是会丢失精度的！！！ 我自杀去了，世界再见（x /* …

。。。重新编译一次就可以了。。。orz