给出两个长度为5*n的序列，每个序列中，有1~n各5个。　　求其最长公共子序列长度。 　　我们发现这题的序列特殊性是关键！　　我们只需要知道每一种数字在某一个序列中的5个位置，然后对于普通的LCS问题，我们只有在a[i]=b[j]的时候才会+1。　　那么我们可以维护一个树状数组，在a序列中，我们一个一个位...

　　给出n个三角形，求其面积并。　　有一个很经典的扫描线题目：矩形面积并。那个比较简单，建议先去看看——传送门-矩形面积并。　　这个扫描线的算法，我之前就看过。　　之前想了想，还以为是n4logn的，自己以为理解错了，所以就弃坑了一段时间。　　现在再想想，原来之前思考的是对的，只是复杂度想错了。...

　　 　　这种图中，一个三角形的三边如果被其他某一个三角形的一条边包括，那么我们说该三角形和那个三角形相邻。　　给出一个三角形，问与它相邻的三角形编号。 　　我们发现，如果结尾是4，那么很简单，答案就是把结尾改一改，改成1~3.　　如果不是4，那么我们只需要从n~1扫一遍，然后各种判断就可以了。&n...

　　一个矩阵，一坨询问，问矩阵中一个特定方向的等腰直角三角形范围的sum。　　一开始毫无头绪。　　看完9题，一题也不会。　　发现这题A的人多，于是我花了15分钟仔细思考。　　发现可以了。　　对于一个三角形区域，我们可以看下图：　　　　我们把求右下黑色三角形区域转化成一个矩形和3个左上的三角形，然后就OK了。　　矩形只要...

　　给出一个大的矩阵，求边长为r的正方形区域的最大sum。 　　二维前缀和然后暴力就可以了。 #include<cstring>#include<algorithm>#include<cstdio>#include<cstdlib>#include&l...

　　将n写成若干个正整数之和，并且使这些正整数的乘积最大。例如，n=13，则当n表示为4+3+3+3（或2+2+3+3+3）时，乘积=108为最大。 　　设F(n)为n的乘积ans。　　那么有：　　F(n)=3*F(n-3) n>4　　F(n)=n    ...

　　给出立体的n个点。求三维凸包面积。 　　增量法，看了一天，还是没有完全懂。　　上板子！ #include<cstring>#include<cstdio>#include<algorithm>#include<cstdlib>#include<...

　　n*n的方阵上，一开始你可以在任何地方。　　你每秒可以移动一格，接下来有m只地鼠冒出来，给出他们的时间、位置。　　问你最多可以打掉几只地鼠。时间可能重复。　　n<=1000, m<=10000　　时限有10S。　　然而m只有10000。　　那么我们用最大力的动态规划。　　先给所有的地鼠按照时间...

　　有一个数列，共n个数字。　　告诉你m个区间和，问是否矛盾。　　数据组数<=100, n<=100, m<=1000　　网上都说的并查集的，貌似挺快的。　　我这里给出一个特殊的做法，复杂度O(T(m+n))，T为数据组数。　　我们根据题目给出的信息建图，然后spfa判断。　　对于...

　　　　n3跑过去了，大力出奇迹！简单的，不多说了。 #include<cstring>#include<cstdio>#include<algorithm>#include<cstdlib>#include<cmath>usingnamespace...

　　一堆线段，现在取出最多条数，使其互不覆盖，并输出字典序最小的方案。 　　这题好坑。　　首先，注意一点，最后不能有多余的空格。　　第一问就是基础的线段覆盖。　　关键在于第二问。　　我们要准备一个函数——Get_Ans(L,R)，用来求解L~R这个区间内，最多可以取多少线段。　　这个可...

　　在一个n*m的矩阵中，每一个位置一个数字。　　现在让你选出3个k*k的矩阵，它们互不相交，问最大数值和为多少。　　注意：n,m<=1500　　一开始总想着dp，发现不大可能。　　暴搜也不行。　　然后突然发现，很简单，情况总数非常的少。　　只有以下6种，从3个区域中各选择一个最大的。　　然后就很简单了，我们只需...

　　数轴上面有一堆数字。　　取出两个数字的代价是他们的距离。　　现在要取出k对数，（一个数字被取出之后就不可再取），问最小代价。 　　这题貌似哪里做过。　　如果取了可以再取，那么我们肯定贪心的选择最短的。　　于是我们考虑先把所有的n个点变成n-1条线段，然后取这些线段。　　我们贪心的来。　　每次要取掉最短的线...

　　给出一个有向图。求最小链覆盖。 　　首先说两个概念：　　　　链：一条链是一些点的集合，链上任意两个点x,y，满足要么x能到达y，要么y能到达x。　　　　反链：一条反链是一些点的集合，链上任意两个点x,y，满足x不能到达y，且y也不能到达x。　　这题就是求最长反链长度。　　有两个定理：　　最长反链长度=最小...

　　一棵树上，一开始所有的边权值为1，我们要支持两种操作：　　1.　修改某一条边的权值为0　　2.　询问根节点到某一节点的路径权值和 　　前置技能-dfs序相关　　然后差不多你就会了。　　dfs序+线段树搞定了。 #include<cstring>#include<algorith...