panyyer

时间限制:1000ms单点时限:1000ms内存限制:256MB描述This is the logo of PKUACM 2016. More specifically, the logo is generated as follows:1. Put four points A0(0,0), B0(0,1), C0(1,1), D0(1,0)

LIS（Longest increasing subsequence） 主要有O(nlogn)和O(n^2)两种解法，本博文主要介绍O(nlogn)解法，顺便提一下O(n^2)。首先说一下O(n^2)解法的思路，假设一个数组a[n]，定义dp[i]为以a[i]结尾的LIS的值，那么对于a[i]，有dp[i]=max{dp[k],k∈[1,i-1]且a[k]}+1，迭代求解，dp[n]就

线段树一：线段树基本概念1：概述线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!性质：父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]，线段树需要的空间为数组大小的四倍

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1272这道题考察的是并查集的应用之一，判断无向连通图是否存在环对并查集不熟悉的话，这里有模板：http://blog.csdn.net/qq_22497299/article/details/52602094简化题目的意思：1，保证图是连通的，且连通分量为1（ 即

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1213模板题，没什么好说的。.这里整合了并查集的模板，也有一些并查集的说明：http://blog.csdn.net/qq_22497299/article/details/526020940ms代码：#include#include#include

大意：给出n个在一条直线上的点，允许移动其中的k个点，求移动k个点后，其余所有点到重心的距离的平方和最小。思路：首先，5w个点，暴力解会超时。可以看出，k个点肯定是移动到最后 的重心处，所以这k个点就不用再考虑了。关于重心，因为所有点的质量都是1，因此将所有点的平均值就是重心。接下来就是解这一题的关键了，留下哪些点才能使公式 I 的值最小，试想一下，如果将n个点排序，那么，取连续的n-

题目链接：http://hihocoder.com/problemset/problem/1385题目大意：给出一串字符，两个单词组成一个短语，求出现次数最多的短语以次数，被逗号和换行分割的两个单词不能组成短语。思路：我用了strtok函数来分割单词，用法可以百度。大体思路就是将一个用例的每一行字符串存起来，对于每一行字符串先通过逗号分隔成好几个子串，每个子串再分别以空格分

LCS（longest common subsequent），暴力求解的复杂度为O(2^m*2^n)，用dp求解的时间复杂度为O(m+n)，本博文主要介绍LCS的dp求法，并且给出一点对应的模板题。LCS的思想很简单，声明一个dp数组，用dp[i][j]表示一个长度为i的字符串和一个长度为j的字符串的LCS，很容易得到转移方程：dp[i,j]=⎧⎩⎨⎪⎪0dp[i−

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5878题意：输入一个n，要求找出比n大的，因子只有2,3,5,7的最小的数。题解：首先说一下什么是丑数，因子只有2,3,5,7的数就是丑数。。。。然后，该怎么做呢？肯定不能从n开始，一个一个暴力找，从题目的样例来看，当n是10的9次方时，要找两万多遍，会超时。如果做过丑数相关的

KMP算法是一种字符串匹配算法，由三个老外发现的，因此算法就用三个老外名字首字母命名了。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。KMP算法的关键是next数组的求解，并根据实际情况next数组可以进行各种活用。next数组是什么？例如有一个字符串n，和一个字符串m，需要在n中匹配m，那么就需要对m进行next数组求解，