有N条木板需要被粉刷。每条木板被分为M个格子。每个格子要被刷成红色或蓝色。windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。如果windy只能粉刷T次，他最多能正确粉刷多少格子？一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。 　　对于每一个木板，我们...

　　有一块矩形土地，被分为N*M块1*1的小格子。有的格子含有障碍物。如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子A不可以走到格子B，就没有距离。如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。如果可以移走T块障碍物，求所有格子间的最大距离。保证移走T...

　　彩珠有N个，分为K种。每一个彩珠有一个对应的坐标。坐标上可以没有彩珠，多个彩珠也可以出现在同一个位置上。小西希望一段彩带中能包含所有种类的彩珠。帮助小西计算这段彩带这个最短的长度。彩带的长度即为彩带开始位置到结束位置的位置差。 　　水题。　　对于读入的，先离散化一下。　　然后L和R卡过去就可以了。直接看代...

　　一个无向图，第一问：从1~n的最短路。　　第二问，删除价值总和最小的边，使得1~n的最短路变长。 　　第一问floyd跑一跑就可以了。　　第二问，最小割就可以了。　　最小割相关可以看这里（往后翻就有）。 #include<cstring>#include<cstdio>#...

　　有两个序列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...

　　给出一个大的矩阵，求边长为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...