题意：给出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 …

题目链接 题意：把一个长度为n的只由数字构成的串分成k个不为空的字串，使得最大的串最小（大小是说串所对应的十进制数的大小） 思路：由于长度为x的串肯定大于长度为x-1的串，因此很容易想到，我们要尽可能使得k组串的长度尽可能平均（避免出现某一个串的长度非常大的情况） 我们可以知道，最大值的串的长度一定为 LEN=(n+k-1)/k; 而每一组的长度，只可能是LEN或者LEN-1。 然后build_sa 注意循环串的几个地方记得%n 接下来二分sa数组的下标。 二分check的时候，先枚举断点，断环为链。 由于每部分最长的长度为LEN，所以0..LEN-1中一定存在一个断点。 然后贪心，尽可能取LEN 根据rk值来决定某一段的长度 …

cf689C 题意：给出一个m。。问恰好使得不超过某个n的a*b^3（a,b是正整数）的方案数为m的n是多少。。。 思路：暴力+二分。。。 /* *********************************************** Author :111qqz Created Time :2016年07月18日 星期一 15时58分55秒 File Name :code/2016whust/G.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

1614: [Usaco2007 Jan]Telephone Lines架设电话线 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1325 Solved: 570 [Submit][Status][Discuss] Description Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线， …

poj2452题目链接 题意：给你一组数a[n]，求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。 思路：大概能想到是rmq，然后想出了一个错误复杂度的错误思路，还直到对拍才发现== 转载一篇题解：poj2452解题报告 收获最大的是： 对于最大值和最小值返回val还是位置的转化竟然可以这样容易! 对于最大值和最小值返回val还是位置的转化竟然可以这样容易! 对于最大值和最小值返回val还是位置的转化竟然可以这样容易! 只要 int _min(int l,int r) { if (a[l]<a[r]) return l; return r; } 这样一个函数就可以 …

1650: [Usaco2006 Dec]River Hopscotch 跳石子 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 440 Solved: 290 [Submit][Status][Discuss] Description Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, …

1639: [Usaco2007 Mar]Monthly Expense 月度开支 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 767 Solved: 381 [Submit][Status][Discuss] Description Farmer John是一个令人惊讶的会计学天才，他已经明白了他可能会花光他的钱，这些钱本来是要维持农场每个月的正常运转的。他已经计算了他以后N(1<=N<=100,000)个工作日中每一天的花费moneyi(1<=moneyi<=10,000)，他想要为他连续的M(1<=M<=N)个被叫做“清算月”的结帐时期做一个预 …

题目链接 题意：有n天的旅行，但是只剩下了m天的旅行记录，记录格式为d[i],h[d[i]]，表示第i个记录是第d[i]天的，高度为h[d[i]],相邻两天的高度之差的绝对值不超过1.问满足以上条件的最大的h是多少。无解输出impossible. 思路：为了练习二分。 二分高度，然后check是否合法。注意边界，所以可以添加两个点。 /* *********************************************** Author :111qqz Created Time :2016年03月30日 星期三 16时53分57秒 File Name :code/cf/problem/538C.cpp …

http://codeforces.com/contest/613/problem/B 题意：有n个技能，初始每个技能的level为a[i]，每个技能最大level为A(不妨称为满级技能)，设满级技能个数为maxnum,最小的技能level为minval,问如何将m个技能点分配到n个技能上使得cfmaxsum+cmminval (n<=1E5,a[i],A<=1E9,cf,cm<=1E3,m<=1E15) 思路：贪心。如果让有限的maxsum个技能满级的话，那么一定是让初始最大的maxsum技能满级更优。我们O(n)可以预处理一个c[i]数组，表示将i个技能变成最大值的最小花费。 然后再预处理一个前缀和数 …