给定长度为2N的序列，1~N各处现过2次，i第一次出现位置记为ai，第二次记为bi，求满足ai<aj<bi<bj的对数。　　n<=100000(这个数据范围是我凑出来的，但是我没试过更小的范围，BZOJ上没写数据范围(截止2017-08-24)) 　　水题，开一个树状数组在线解决。...

　　一条马路的两边分别对应的序列A、B，长度为n，两序列为1到n的全排列。当Ai=Bj时，两边之间会连一条边。你可以选择序列A或序列B进行旋转（只能使队尾或队头位置上的数字变成队头或队尾上的数字）任意K（0<=K<n）步，如123，可以变成231或312。求旋转后，最少的边的交叉数。 　　两个都可...

　　有上下两行长度为n的数字序列A和序列B，都是1到n的排列，若abs(A[i]-B[j])<=4，则A[i]和B[j]间可以连一条边。现求在边与边不相交的情况下的最大连边数量。　　我们用dp[i][j]表示枚举到A序列的第i个位置，与B序列的第j个位置匹配，所得到的最大效益，这样显然是要超时的，但是不妨去思考一...

　　有上下两行长度为n的数字序列A和序列B，都是1到n的排列，若abs(A[i]-B[j])<=4，则A[i]和B[j]间可以连一条边。现求在边与边不相交的情况下的最大连边数量。 　　我们用dp[i][j]表示枚举到A序列的第i个位置，与B序列的第j个位置匹配，所得到的最大效益，这样显然是要超时的，但是...

　　在一幅n*n的地图上，Amber从左上角走到右下角，每走一步需要花费时间t，每走完3步时，还要加上到达的那个格子的值。这里的3步不包括起动的那个格子。如果刚好3步到达右下角，则右下角格子的值也要算进花费中，否则不用计算进去。求最小花费。n<=100　　最短路写一写就可以了，居然不卡spfa！　　有一个点要注意...

　　小明组建了一支由n名玩家组成的战队，编号依次为1到n。每局游戏开始时，所有玩家都会从飞机上跳伞，选择一个目的地降落。他们发现地面上一共有m间房子，编号依次为1到m。每间房子有一名敌人。第i名玩家有ai发子弹，第i间房子里的敌人有bi发子弹，消灭他可以获得ci点积分。每名玩家必须且只能选择一间房子降落。若第i名玩家选...

　　一个串T是S的循环节，当且仅当存在正整数k，使得S是T^k(即T重复k次)的前缀，比如abcd是abcdabcdab的循环节。给定一个长度为n的仅由小写字符构成的字符串S，请对于每个k(1<=k<=n)，求出S长度为k的前缀的最短循环节的长度per_i。字符串大师小Q觉得这个问题过于简单，于是花了一分钟...

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