Xiao Luo

UVA11584这道题需要两次dp 第一次定义：$S$为字符串，$IsPalindrome[i][j]$为第$i$个字符到第$j$个字符组成的子串是否为回文$i\leq j$。初始化： IsPalindrome[i][i]=true\\ IsPalindrome[i-1][i]=(S[i]==S[i-1])转移方程： IsPalindrome[i][j] = IsPalindrome[i + 1][j - 1] \&\& (s[i] == s[j])如果子串的左边一个字符和其右边一个字符相等，那在这个字串往左右各拓展一格字符形成的新字串仍然时回文串。 第二次定义：$dp[j]$为前j各字符组成的字串划分成的最小回文串数量。初始化：$dp[j]=0$转移方程：123456789101112for (int j = 1; j <= Len; ++j) { //将第j个字符看作单独的字串 dp[j] = dp[j - 1] + 1; for (int i = 1; i < j; ++i) { //如果i到j是回文串 if (IsPalindrom ...

题目链接@[toc] A - 数字组合 小蒜有 n(1≤n≤20)个正整数，找出其中和为 t(t 也是正整数)的可能的组合方式。如：n=5,5 个数分别为 1,2,3,4,5，t=5；那么可能的组合有 5=1+4和 5=2+3和 5=5三种组合方式。输入格式输入的第一行是两个正整数 n 和 t，用空格隔开，其中 $1 \le n \le 20$, 表示正整数的个数，t 为要求的和 $(1≤t≤1000)$接下来的一行是 n 个正整数，用空格隔开。输出格式和为 t 的不同的组合方式的数目。输出时每行末尾的多余空格，不影响答案正确性样例输入 5 51 2 3 4 5样例输出 3 定义:$dp[i][j]$为考虑前$i$个数和为j的组合的个数初始化：$dp[i][0]=1$，即不管考虑多少个数，和为0的组合方案数只有一个，就是没有加数。转移方程：$dp[i][j] = dp[i - 1][j] + (j - a[i] >= 0 ? dp[i - 1][j - a[i]]:0)$。前$i$个数和为$j$的方案数等于前$i-1$个数和为j的方案数加上前$i-1 ...

题目链接@[toc] FloydA Calling Circles 题意：如果两个人互相打电话（直接或者间接），则说他们在同一个电话圈里。例如，a打给b，b打给c，c打给d，d打给a，则这四个人在同一个圈里；如果e打给f，而f不打给e，则不能推出e和f在同一个电话圈。输入$n(n\leq 25)$个人的m 次电话，找出所有的电话圈。人名只包含字母，不超过25个字符，且不重复。感谢@UKE自动机 提供的翻译 题目要求有向图里的所有环，并且两个环如果有交点则视为同一个环。 首先，求有向图的可达矩阵，采用Floyd-Warshall算法。 如果在有向图内，由A点可达B点，由B点也可达A点，则说明A，B两点在同一个环内。 在可达矩阵上遍历求解即可。12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899 ...

@[toc] 堆的简介转载链接（堆的基本概念） 对顶堆简介对顶堆是由一个大顶堆和一个小顶堆组合而成的数据结构，与传统堆维护最大数不同，对顶堆用于动态维护第$k$大的数。在对顶堆中，小根堆位于大根堆的上方，即保证了小根堆的所有数始终比大根堆大。比如维护这样一个数组$[1,4,6,8,10,14,16,18,23,55]$，此时需要维护第7大的数（也就是8），那么此时对顶堆的结构如下图所示。其中，红色的节点为小根堆，绿色的节点为大根堆。 其中，数字8为小根堆对顶，数字6为大根堆堆顶。可以看到，由于小根堆堆底元素小于堆顶，而大根堆堆底元素小于堆顶，这样的组合保证了整个数据结构中上方的元素永远大于下方的。即小根堆的堆顶永远大于大根堆的堆顶。而此时，小根堆的元素有7个，而大根堆的元素有3个，由于小根堆大于大根堆，并且小根堆堆顶元素为小根堆最小的元素，因此所求的第7大的元素即为小根堆的堆顶元8。 $k$值修改 为了保证$k$值在修改后仍能保持这样特殊的数据结构，我们需要在k值发生变化时交换两个堆中的元素，不过每次交换只对相应的堆顶进行操作。比如原先的k值是7，现在将$k$修改为6，那相应的就需要小 ...

UVA12589预处理：首先，我们将所有向量按斜率从大到小排序。因为在连上某个向量时，在他之前的向量都会为它贡献底部的面积。观察题目的图，可以发现除了第一个向量之外，剩下向量新增的面积都是由底部一个矩形和上面一个三角性组成，而三角形只和当前向量有关，当矩形面积等于当前的总高度乘当前向量的长。因此，向量放的越早，其为后续贡献的矩形面积就越多，因此选择先放斜率大的。定义：$dp[i][j][k]$为考虑前$i$个向量，并选择了其中的$j$个并且此时高度为$k$时的最大面积。（$dp$找状态参数可以观察题目，只要一个状态能唯一表示即可）。$DP(ID,Choose,High)$返回考虑到第$ID$个向量，选择了$Choose$个向量，当前高度为$High$作为起始条件后能达到的最大面积。初始化：$dp=-1$用-1来标记未搜索过转移方程及边界条件：1234567891011121314151617181920212223int DP(int ID, int Choose, int High) { int& Ans = dp[ID][Choose][High]; //如果选够 ...

@[toc] 简介KMP算法是一种字符串匹配算法，它利用了模式串（被匹配串）自身的相关信息来减少匹配次数。本文假设文本串（待匹配串）为T，模式串（被匹配串）为P。而T，P的长度分别为TLen，PLen。记T~i~为T的前i个字符构成的子串，T~-i~为T后i个字符构成的子串，P同理。 求辅助数组在实现这个算法前，我们需要先求一个特殊的数组，暂且记为Pre[PLen+1]。这个数组的含义为Pre[i]=max(j),其中记H=P~i~，其中j满足(j<=i&&H~j~=H~-j~)，即P~i~的最长的（前缀等于后缀）的长度。我们暂且把为什么要这个放在一边，先看看怎么求。首先，先上代码。 123456789101112131415template<typename Ty>inline void KMP<Ty>::ComputePrefixFunction() { Pre = new int[PLen + 1]; Pre[1] = 0; int k = 0;//k表示当前的前后缀匹配长度 for (int q = 2; q <= ...

简介字典树，即Trie树，是一种常用的数据结构。比如一个单词“apple”，可以分为五个字母，一般以一个虚节点为起始节点，记为$root$，那么apple这个单词就可以表示为$root$->a->p->p->l->e,同理，$bad$就是$root$->b->a->d。字典树的优点在于其不仅增加单词的复杂度是线性的，其查询单词或前缀的复杂度也是线性的。就好像翻字典一样，先找第一个字母，再第二个，比盲目的大海捞针要快上许多。 一种错误的实现之前我有想到过开一个二维的数组$tree$[字母][深度],来记录，比如bad就是tree[‘b’][0]=tree[‘a’][1]=tree[‘d’][2]=true。但是这样做会存在一个问题，比如我记录单词aa,ab,以及ba,那就会使得tree[‘a’][0],tree[‘b][0],tree[‘a’][1],tree[‘b’][1]=true，然后查询bb时就会出现“bb存在”的错误，然而“bb”是不存在的，所以这种表达方式会产生一些无中生有的交叉错误。 正常的实现方式（数组实现）12345678 ...

简介双向BFS就是在一直当前状态和期望状态时，从当前和期望两个状态同时出发，直到某个状态同时被访问到两次，那么当前状态->被访问两次的状态->目标状态就是当前状态到目标状态的解。那具体会有多块呢？加入每一次搜索都有n个新的状态（比如迷宫问题就是上下左右四个状态），从起点到目标路径长为m，那就要搜索$n+n^{2}+n^{3}+……+n^{m}$个状态，状态数就是$n^{m+1}$数量级的，若是双向广搜呢？在路径中点就能相遇，状态数是$2*n^{m/2+1}$数量级的，比起朴素的BFS，枚举状态数少了很多，所以对于从起始状态和目标状态已知的情况，我们可以使用双向BFS来优化程序的时间复杂度。下面通过一个例子来看看优化的效果。 Q1八数码难题原题传送门->洛谷P1379搜先看一下朴素的单搜 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576 ...

@[toc] 简介单源最短路问题指的是给定一个带边权的图，求其中一个点到所有其他点的最短路是多少。常见的算法有Dijkstra算法，Spfa算法等，这里介绍的是Dijkstra算法。想一想Prim算法求最小生成树，求得的最小生成树其实就是各个点间的最短路径，所以求单源最短路是只要从目标点出发，在最小生成树生长的同时记录下个点到目标点的距离即可。所以其时间复杂度和Prim算法一样，不用堆优化为$O(n^{2})$,用堆优化则为$O((n+m)logn))$，不过会有额外的$O(n)$空间开销。（m为边数量，n为点数量） Q1模板原题的大门->洛谷P4779在代码里说吧 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include<iostream>#include<vector>#include<climits>#include ...

@[toc] 简介Floyd算法是一种区间动态规划，通过不断更新状态的方式来寻求最优解。假如我们有一个图，我们想从其中的A点走到B点，那么最短路一定就是A到B吗，显然不是。可能是A->C->B，也可能是A->D->F->B更短，那么我们怎么求呢？我们可以对每个点都跑一边Dijkstra。不过这样的话时间复杂度就是$O(V(V+E)log_{2}V)$了，如果是稠密图的话，就渐进与$O(V^{3}log_{2}V)$了。而今天介绍的Floyd算法时间复杂度非常简单，就是$O(V^{3})$，而且时间常数非常小，应为它就短短的四行代码： 1234for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j < n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); 其中，这是一个$n*n$的邻接矩阵，而$dis[i][j]$就表示了i到j的最短路。其中k表示目前的中转点编号，而$dis[ ...