给出长度为n的数列，只会出现1~k这些正整数。现在有些数写成了-1，这些-1可以变成任何数。　　求把这些-1变成1~k中的正整数之后，最少的逆序对个数为多少。 　　我们可以判断，这些-1中写的数字一定是单调不降的。　　为什么？我们把答案序列的所有-1位抽出来，如果答案序列中有一组是逆序的，那么交换他们，一...

　　给出n个数，每一个数字<1000000，对于每一个数，让你求剩余的n-1个数中有多少是它的约数。 　　用桶计数，弄出每一个数字的出现次数。　　然后用类似筛法的方法，把每一个数字的倍数都加一下即可。 #include<cstring>#include<algorithm&g...

　　有N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但可以同时购买多快土地.这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换.如果FJ买一块3x5的地和...

　　给出数列，求 ∑F[i]，其中F[1]=a[1],F[i]=min(|a[i]-a[j]|) (j<i)　　只需要每次可以求那个东西就可以了。　　那么我们搞一个set，每次把数字放到set里面。　　查询就是lower_bound，这样就可以找到与这个数字差值可能最小的。　　然后只有...

　　给出两个n*n的数字矩阵，问最大公共正方形边长。　　先二分答案一个m，对于每一个m，哈希大矩阵中每一个位置上的边长为m的正方形，然后排序，lower_bound一下判定即可。　　鬼畜的是，我的代码在BZOJ上面过去了，but和hzwer大佬(Orz)的代码对拍没有过去，不知道怎么回事……...

　　两只青蛙，现在分别在x,y的位置，以m,n的速度在周长为L的环形跑道上面跑。　　问他们什么时候可以到同一个位置。（如果永远不能，则输出Impossible）　　扩展欧几里德模板题。　　设a=x-y,b=n-m,　　我们可以列出方程：ax ≡b(modL)   &n...

　　一个n*m的矩阵，现在有2种操作：修改某一个位置的值求一个子矩阵某值的出现次数　　n,m ≤300, 1≤ 元素的值 ≤100,操作次数 ≤200000　　100棵二维树状数组。维护每个值的二维前缀出现次数。　　好像该说的都说了&hellip...

　　求所有数x，满足x<n且x2≡1（mod n）。　　n<=2000000000 　　对于所有的数x，如果 x2 ≡1（mod n），　　那么有 x2 modn-1=0　　可以化为 (x+1)(x-1)...

　　给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。 　　我们找到b的位置，比如为pos。　　然后往左，逐位统计比b小的，比b大的，差记为a。　　对于左边所有的位置，bar[a]++，搞n×2个桶。然后右边一边扫过去，一...

　　有向图有N个节点，从节点0出发，他必须恰好在T时刻到达节点N-1。现在给出该有向图，问总共有多少种不同的路径吗？注意：不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。　　矩阵乘法。　　把一个点拆成9个，分别是time+0,time+1,time+2,...,time+8。　　然后根据输入转移，构建矩阵即可...

　　有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>#...

　　在n*n的区域里，每一个1*1的块都是一个格子。　　有k头牛在里面。　　有r个篱笆把格子分开。　　如果两头牛可以不经过篱笆走到一起（过程中不能出界），那么他们就是不互相远离的，反之就是互相远离的。　　问有多少对牛是互相远离的。注意(x,y)和(y,x)算作同样的。　　对于同一区域的牛，我们可以相同对待。　　所以我们...