题目链接 题意：一个无穷数列，从1开始，初始第i个位置上为i，给出n个swap，每次交换两个位置的数。问交换n次以后得到的数列中，逆序对的数。 思路： 官方题解： At first find the position of each element which is used in swap (using map). Now let's find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They …

题意：给出n个数，两两做差的绝对值，共有m=n*(n-1)/2个，问其中的中位数是多少。特别地，当m为偶数的时候，中位数为第m/2个。 思路：二分中位数。 一开始还觉得由于中位数在整数意义上不连续不能二分。。。。 但是最后结果不可能是那样的答案啊。。。 check的条件是，以k为中位数的时候，绝对值小于k的数要小于(m+1)/2个（也就是中位数所在的位置） check的时候尺取即可。 复杂度 排序O(nlgn) + 二分(lgn)*尺取O(n) ，整体O(nlgn) /* *********************************************** Author :111qqz Created Time :Tue …

题目链接 题意：给出n个x轴上的坐标点，选取其中c个，问c个之中任意两个点的最小距离最大是多少。 思路：二分距离check合法性。 大水题。。。因为想把三分艹掉。。。三分的题又多和二分挂在一起。。。顺便就写了。。。。 /* *********************************************** Author :111qqz Created Time :Mon 19 Sep 2016 10:57:54 PM CST File Name :code/poj/2456.cpp ************************************************ */ #include …

题目链接 题意：圆上，询问任意一段弧中，任意两点的距离+两点的权值和的最大值。 思路： 1.环先拆成串，复制1..n到后面，变成1..2n。 化简公式： 2 * h[u] + 2 * h[v] + dist(u, v) = 2 * h[v] + d[1] + d[2] + ... + d[v-1] + 2 * h[u] - (d[1] + d[2] + ... + d[u-1]). 设A[v] = 2 * h[v] + d[1] + d[2] + ... + d[v-1], B[u] = 2 * h[u] - (d[1] + d[2] + ... + d[u-1]). Another important thing is that …

题目链接 题意：有n个数，每次可以删除掉数值相同并且所在位置成等差数列（只删2个数或者只删1个数应该也是可以的），删掉这些数以后可以将剩下的数重新以任意顺序排列，称为一次操作。现在给出m个询问，每个询问一个区间[l,r]，问删光区间[l,r]中的数最少需要的操作次数。 思路/题解：由于第一次操作之后可以重排，那么把相同的数放在一起得到一个位置的公差为1的等差数列，之后的答案显然是元素个数。所以需要判断初始的时候，是否能一次删光某个数值的数，也就是需要判断初始时刻是否有某个数出现的所有位置组成一个等差数列。 (去icpc-camp的论坛问了一波。。。链接在这里) 之前刚刚学了判断一个区间中不同的数有多少个的姿势。。。 所以问题就在于如 …

题目链接 题意：题意说得一点页不清楚。。。意思在询问在区间[l,r]中满足某条件的数。该条件是，该数的任何一段数字是奇数组成的数串必须有偶数长度，任何一段数字是偶数组成的数串必须由奇数长度。 对于样例1，满足条件的29个数字分别是： 2,4,6,8,11,13,15,17,19,31,33,35,37,39,51,53,55,57,59,71,73,75,77,79,91,93,95,97,99. 对于样例2，满足条件的36的数字分别是： 110,112,114,116,118, 130,132,134,136,138 150,152,154,156,158 170,172,174,176,178 …

题目链接 题意：给出n个数，然后m个询问，每个询问一个区间[l,r],问该区间中不同的数有多少个。 思路：离线处理+线段树的做法不多说了： /* *********************************************** Author :111qqz Created Time :Fri 16 Sep 2016 11:34:32 PM CST File Name :code/spoj/dquery.cpp ************************************************ */ #include <cstdio> #include <cstring> …

题目链接 题意：题意是由伪代码给出的。。手算模拟了一下(noip初赛即视感），题意大概是说，给出两个数组a和b，a数组长度为n,b数组长度为len,然后从a中截取连续的len个元素，称为数组s，如果存在一种方法使得s中元素和b中的元素一一对应且每组和都大于等于h,则称这个s是合法的。现在问a中有多少个合法的s。 具体来说，对于样例 5 2 10 5 3 1 8 5 5 7 s={8,5}和s={5,7}是有解的。 因为对于前者8+3>=10并且5+5>=10,对于后者5+5>=10,7+3>=10,因此答案为2 思路： 最重要的一部是，我们先将b排序，然后维护一个函数f[i],在排序后的b中找到一个最小的j， …

1756: Vijos1083 小白逛公园 Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1078 Solved: 353 [Submit][Status][Discuss] Description 小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。 一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于 …

题目链接 题意：给出n个数,m个修改，每次修改后询问整个区间的最大连续子段。 思路：考虑一段区间，分成左右两个子区间，这段区间的最大子段有三种情况：只在左区间中，只在右区间中，既在左区间中又在右区间中。前两种很好维护，对于后一种，我们新增加线段树的两个域，mxl,mxr，分别表示一个区间中包含左端点在的最大字段和（也就是最大前缀和），和一个区间中包含右端点在的最大子段和（也就是最大后缀和），然后对于最大子段既在左区间又在右区间的情况，只需要合并【左区间的最大后缀和 】和【右区间的最大前缀和】就好。 关于一个区间最大前缀和的维护，取该区间的左区间的最大前缀和和【该区间的左区间和】+【该区间的右区间的最大前缀和】的最大值。 最大后缀和同 …