有两个序列a[1..n],b[1..n],其编号为1..n，设为s序列。现在我们要求出最长的满足条件的s的子序列s'，设va=min(a[s[i]]),vb=min(b[s[i]]),满足对于所有的j=s'[i],A*(a[j]-va)+B*(b[j]-vb)<=C。 　　设v[i]=A*a[i]+...

　　假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。用尽...

　　给出两个长度为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条线段，然后取这些线段。　　我们贪心的来。　　每次要取掉最短的线...