Panda2134's Blog

Not only coding

字串距离

链接：Luogu-1279 思路如何实现“插入空格”操作？定义状态为$f(i,j)$，表示字符串A中从第$i$个字符到结尾，字符串B中从第$j$个字符到结尾，所能得到的最小字串距离。显然，可以把$i,j$都前移，也就是转移到$f(i+1,j+1)$。那空格怎么处理呢？我们用$i,j$中的一个加1，另一个不变，来表示在某个字符的前面插入一个空格。如图：实现了插入空格，就可以...

Posted by panda_2134 on July 24, 2017

排列LCS

题目链接：Luogu-P1439 思路按照题目中数据规模，直接跑LCS，复杂度为$O(n^2)$，只有50分。考虑到题目中给定的是两个排列，应该可以利用排列的某些性质。如果其中一个排列是$1,2,3,…,N$，那么显然LCS就是另一个排列的LIS。如果两个排列都不是$1,2,3,…,N$呢？考虑把两个排列，通过同一种映射关系,进行转化，使得其中一个排列变为$1,2,3,…...

Posted by panda_2134 on July 24, 2017

[NOIP2000]方格取数

链接：Luogu-P1004 思路考虑换成两次都从(0,0)出发，向右/下行走。显然两者到达终点时走过的步数相同。因此可以让二者每次都走一步，分4种情况讨论。注意由于步数相同不可能二者位于同一列上下相邻两格。于是唯一的特殊情况就是二者处于同一个格子，这时这个格子的数只能取一次。特判处理即可。状态：$ f[x_1][y_1][x_2][y_2] $：位于 $(x_1,y_...

Posted by panda_2134 on July 23, 2017

[NOIP1999]导弹拦截

链接：Luogu-P1020 思路第一问是裸的最长下降子序列问题。第二问： Dilworth 定理：最长不降子序列长度，等于下降子序列划分数的最小值。其对偶定理，即最长下降子序列长度，等于不降子序列划分数的最小值。同样成立。我也不知道怎么证明的，要用到偏序集。但是因为和LIS问题有关，先记下来。第二问需用到此定理。最少需要的导弹系统数，实际...

Posted by panda_2134 on July 23, 2017

单调数据结构学习笔记

这里的“单调数据结构”，指的就是单调栈和单调队列。单调栈特点先进的元素后出，求前/后缀最值。实现使用一个栈（这不是废话么233），每次在加入栈时维护单调性。不断弹出栈顶元素，直到栈顶元素大于将要加入的元素，此时再将要加入的元素推入栈中。具体地讲，由于需要随机访问单调栈中的元素，以便充分利用其单调的特性，常用一个数组来模拟栈。设s[0]为栈中元素个数，s[1]~s[...

Posted by panda_2134 on July 22, 2017

KMP学习笔记

推荐Menci神犇的Blog，KMP讲的很清晰。在这里把Menci的学习思路复述一遍，以更好地理解KMP。 KMP 学习笔记-Menci 字符串匹配朴素算法字符串匹配就是在目标串中寻找模式串。在朴素算法中，我们穷举每一个可以开始匹配的位置，然后逐一比较，如果无法匹配就向右移动一位模式串,直到找到匹配或者所有位置都无法匹配位置。我们来看一个例子。当匹配到目标串的第7个字符时...

Posted by panda_2134 on July 22, 2017

Todo List

写给自己的话：注意建模能力的训练，掌握每种算法对应题目的特点。学时优先看书。写之前一定要考虑时间复杂度，想好再写！欢迎监督QAQ 1. DP 看入门经典Ch9，训练指南Ch1，把每道题思路想出来，并归纳特点 (至少刷完洛谷历练场30道dp，一天2道) -[x] 序列DP -[x] 划分DP -[ ] 状压DP -[x] 背包DP...

Posted by panda_2134 on July 14, 2017

[NOIP2013]货车运输

题目链接：CodeVS 3287 题意：给出一张无向图，每条边有一个边权，图上可以有重边，没有自环。求这张图上两点$u$,$v$之间所有路径上最小权值的最大值。若不能互相到达输出-1。 1.审题 1. 显然，无向图不一定是连通图，于是两点之间若要互相到达，必须在同一连通子图上。 2. 最小权值的最大值：图上$u$,$v$两点间有着多条路径，需要找到一条路径，这条路径上所求的权值最小的边最大...

Posted by panda_2134 on July 12, 2017

Test

Posted by panda_2134 on January 1, 1970