Tag Archives: 分治法

hihoCoder 1128-二分·二分查找

hihoCoder 1128-二分·二分查找 #1128 : 二分·二分查找 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 Nettle最近在玩《艦これ》,因此Nettle收集了很多很多的船(这里我们假设Nettle氪了很多金,开了无数个船位)。去除掉重复的船之后,还剩下N(1≤N≤1,000,000)种不同的船。每一艘船有一个稀有值,任意两艘船的稀有值都不相同,稀有值越小的船越稀有,价值也就越高。 Nettle现在通过大建又造出了一艘船,他想知道这艘船是不是重复的。如果是重复的,那么这艘船在Nettle所有的船里面稀有值排多少位。 问题一 Nettle已经先把自己所有船按照稀有值从小到大排列好了(a[1..N]),我们要做的是看看新得到的船(假设稀有值为K)是否在这个序列中,且有对应的a[i]=K时,i为多少? 提示一:有序数组的二分查找 问题二 因为Nettle的船太多了,他不愿意去给所有船按照稀有值排序,而是直接告诉了我们每一艘船的稀有值。在这种情况下我们该如何解决这个问题呢? 提示二:非有序数组的二分查找 输入 第1行:2个整数N,K。N表示数组长度,K表示需要查找的数; 第2行:N个整数,表示a[1..N],保证不会出现重复的数,1≤a[i]≤2,000,000,000。 输出 第1行:一个整数t,表示K在数组中是第t小的数,若K不在数组中,输出-1。 样例输入 10 5180 2970 663 5480 4192 4949 1 1387 4428 5180 2761 样例输出 9


给出一串数字,问某个数字K在该序列中是第几小的。 最简单的解法,遍历一遍数组,找出比K小的数的个数n,则K是第n+1小的数。完整代码如下: [cpp] #include<iostream> #include<cstdio> #include<vector> using namespace std; vector<int> a; int n, k; int main() { scanf("%d %d", &n, &k); a.resize(n); bool is_exist = false; int ans = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] == k) is_exist = true; if (a[i] < k) ans++; } if (!is_exist) printf("-1\n"); else printf("%d\n", ans + 1); return 0; } [/cpp] 本代码提交AC,用时58MS,内存3MB。 但是题意显然不是用这种方法,为了配合下一题的求第k小数,提示使用快排的中间步骤,依次将序列划分成比某个数大和比某个数小的两部分,再在其中某个子序列中递归求解。完整代码如下: [cpp] #include<iostream> #include<cstdio> #include<vector> using namespace std; vector<int> a; int n, k; int GetOrder(int p, int q) { int m = a[p]; int i = p, j = q; while (i < j) { while (i < j&&a[j] > m) j–; a[i] = a[j]; while (i < j&&a[i] < m) i++; a[j] = a[i]; } if (k == m) return i; else if (k < m) return GetOrder(p, i – 1); else return GetOrder(i + 1, q); } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &k); a.resize(n); bool is_exist = false; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] == k) is_exist = true; } if (!is_exist) printf("-1\n"); else printf("%d\n", GetOrder(0, n – 1) + 1); return 0; } [/cpp] 本代码提交AC,用时57MS,内存3MB。]]>

hihoCoder 1070-RMQ问题再临

hihoCoder 1070-RMQ问题再临 #1070 : RMQ问题再临 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 终于,小Hi和小Ho踏上了回国的旅程。在飞机上,望着采购来的特产——小Hi陷入了沉思:还记得在上上周他们去超市的时候,前前后后挑了那么多的东西,都幸运的没有任何其他人(售货员/其他顾客)来打搅他们的采购过程。但是如果发生了这样的事情,他们的采购又会变得如何呢? 于是小Hi便向小Ho提出了这个问题:假设整个货架上从左到右摆放了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量。但是在这个过程中,可能会因为其他人的各种行为,对某些位置上的商品的重量产生改变(如更换了其他种类的商品),面对这样一个问题,小Ho又该如何解决呢? 提示:平衡乃和谐之理 输入 每个测试点(输入文件)有且仅有一组测试数据。 每组测试数据的第1行为一个整数N,意义如前文所述。 每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。 每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数与商品的重量被更改的次数之和。 每组测试数据的第N+4~N+Q+3行,每行分别描述一次操作,每行的开头均为一个属于0或1的数字,分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行,如果该行描述一个询问,则接下来为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri];如果该行描述一次商品的重量的更改,则接下来为两个整数Pi,Wi,表示位置编号为Pi的商品的重量变更为Wi 对于100%的数据,满足N<=10^4,Q<=10^4, 1<=Li<=Ri<=N,1<=Pi<=N, 0<weight_i, Wi<=10^4。 输出 对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。 样例输入 10 618 5122 1923 8934 2518 6024 5406 1020 8291 2647 6 0 3 6 1 2 2009 0 2 2 0 2 10 1 1 5284 0 2 5 样例输出 1923 2009 1020 1923


本题的数据量比hihoCoder Problem 1068: RMQ-ST 算法这题要小,虽然
用O(N)的时间进行计算——扫描一遍整个区间找到最小值,然后对于每一个更改操作,使用O(1)的时间直接进行修改,这样也就是O(NQ)的总时间复杂度!在这种数据量下完全是可以通过的!
但是本题希望我们用线段树来解决。 我曾在《数据结构》的改造红黑树中看到过区间树,但是本题的线段树和书中的区间树有所区别,区间树由红黑树改造而来,结构更复杂些,这里只需要使用线段树即可。 常规的线段树如下图所示: 从图中可以看到构造线段树的过程就是一个二分的过程,不断将区间分成两半,直到只有一个元素。图中的线段树每一个节点是一个区间[l,r],本题我稍微改造了一下,改成了数组int seg_tree[left][length],比如seg_tree[i][j]表示从下标i开始,长度为j的这样一个区间上的最小值,这样就可以利用线段树来解决RMQ问题了。比如改造后的线段树就成了下面的样子: 因为树形这种特殊的结构,我们可以用一个DFS来对树实现二分构造,当DFS到某个节点长度为1时,其最小值就是w[i]本身,在回溯到父节点时,父节那个区间的最小值又是所有子节点最小值中的最小值。因为树的总节点数大约为2*n,所以复杂度O(n)。 当需要查询区间[l,r]的最小值时,只需对数组seg_tree二分搜索。具体来说,假设我们搜索到了节点[s_l,s_len],如果r<(s_l+s_len/2),说明区间[l,r]全在[s_l,s_len]的左边,我们递归在[s_l,s_len/2]区间找;如果l>=(s_l+s_len/2),说明区间[l,r]全在[s_l,s_len]的右边,我们递归在[s_l+s_len/2,s_len-s_len/2]区间找;如果以上两者都不是,说明[l,r]跨界了,而且中点下标一定是s_l+s_len/2,所以我们分别在二两半区间找,然后求这两者的最小值。复杂度O(lgn)。 当需要更新某个下标为pos的值为value时,也是DFS查找线段树,直到找到叶子seg_tree[pos][1],更新它的值,以及所有我们在查找过程经过的父节点的值。复杂度O(lgn)。 所以线段是的性质使得无论是构造、查询、更新操作,复杂度都只要O(lgn),这就是题目中所说的把总的复杂度平均分配到不同操作:平衡乃和谐之理。 完整代码如下: [cpp] #include<iostream> using namespace std; const int MAX_N=1e4+2; int w[MAX_N];//每个商品重量 int n,m; int seg_tree[MAX_N][MAX_N];//seg_tree[i][j]:起点为i,长度为j的区间的最小值 inline int get_min(int a,int b) { return a<b?a:b; } //深度优先遍历以构造线段树 void dfs(int left,int length) { if(length==1) { seg_tree[left][1]=w[left]; return; } dfs(left,length/2); dfs(left+length/2,length-length/2); seg_tree[left][length]=get_min(seg_tree[left][length/2],seg_tree[left+length/2][length-length/2]);//取最小值 } //在区间[s_left,s_len]搜索区间[left,length]的最小值 int search_min(int s_left,int s_len,int left,int length) { if((s_left==left)&&(s_len==length)) return seg_tree[s_left][s_len]; if((left+length-1)<(s_left+s_len/2))//全在左半部分 { return search_min(s_left,s_len/2,left,length); } else if(left>=(s_left+s_len/2))//全在右半部分 { return search_min(s_left+s_len/2,s_len-s_len/2,left,length); } else//左右分开搜索 { int left_len=s_left+s_len/2-left; int right_len=length-left_len; int min_left=search_min(s_left,s_len/2,left,left_len); int min_right=search_min(s_left+s_len/2,s_len-s_len/2,s_left+s_len/2,right_len); return get_min(min_left,min_right); } } //从区间[s_left,s_len]开始更新下标pos的值为value void update(int s_left,int s_len,int pos,int value) { if((s_left==pos)&&(s_len==1)) { seg_tree[s_left][1]=value; return ; } int mid=s_left+s_len/2; if(pos<mid) update(s_left,s_len/2,pos,value); else update(mid,s_len-s_len/2,pos,value); seg_tree[s_left][s_len]=get_min(seg_tree[s_left][s_len/2],seg_tree[mid][s_len-s_len/2]);//更新父节点 } int main() { //freopen("input.txt","r",stdin); cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; dfs(1,n); cin>>m; int p,l,r; for(int i=0;i<m;i++) { cin>>p>>l>>r; if(p==0)//查询 { cout<<search_min(1,n,l,r-l+1)<<endl; } else//修改 { update(1,n,l,r); } } return 0; } [/cpp] 本代码提交AC,用时151MS,内存42MB。 ]]>

POJ 1019-Number Sequence

POJ 1019-Number Sequence Number Sequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34278 Accepted: 9835 Description A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2…Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. For example, the first 80 digits of the sequence are as follows: 11212312341234512345612345671234567812345678912345678910123456789101112345678910 Input The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647) Output There should be one output line per test case containing the digit located in the position i. Sample Input 2 8 3 Sample Output 2 2 Source Tehran 2002, First Iran Nationwide Internet Programming Contest


做这一题需要细心,我们先分析一下题意。给出一串数字,问你这个数字串中第i个位置的数字是什么。其中数字串是形如112123123412345123456123456712345678123456789123456789101234567891011123456789101112这样的。 仔细分析一下就是1、12、123、1234,…,123456789、12345678910、1234567891011,… 串联起来的。我们定义单个数字串1234…i的长度为single_len[i],总的数字串1,12,123,…,123…i.的长度为total_len[i]。因为1,12,123,…,123…i.=1,12,123,…,123…(i-1).+123…i.所以我们可以得出一个等式:total_len[i]=total_len[i-1]+single_len[i]。那么怎么来求解single_len[i]呢? single_len[0]=0; single_len[1]=1; single_len[2]=2; single_len[10]=11. 因为single_len[i]为123…(i-1)i的长度,single_len[i-1]为123…(i-1)的长度。很显然,single_len[i]=single_len[i-1]+数字i的长度。这有点类似动态规划的状态转移方程。求数字i的长度可以用下面的函数求解: [cpp] //求数字i的位数 int get_digits_num(int i) { int rs=1; while(i>=10) { rs++; i/=10; } return rs; } [/cpp] 当然也可以用stringstream先将int转换为string再求string.size(),但是这种方法更慢。 当我们求到了single_len和total_len,就可以分两步求解总的数字串中第i个位置的数字了。首先在total_len中找到位置i在哪一个内部串中,然后再在内部串中找到位置i的确切位置。这就有点像信号调节中的粗调和微调,首先找到大致的位置,然后在某个局部找细节的位置。 比如给定数字串112123123412345123456123456712345678123456789123456789101234567891011123456789101112。问i=18位置处的数字是什么。我们已经求到total_len[0]=0; total_len[1]=1; total_len[2]=3; total_len[3]=6; total_len[4]=10; total_len[5]=15; total_len[6]=21; 。18正好在total_len[5]和total_len[6]之间。因为total_len[5]=15表示以5结束的总的数字串的长度为15<18,所以我们取total_len[6],也就是i=18必定在以6结尾的总的数字串中,即在112123123412345123456中,且在以6结尾的单个数字串中的第i-total_len[6-1]=18-15=3个位置,也就是在123456的第3个位置即3,所以最终结果就是3。 所以总结一下求解的步骤就是: 1. 计算single_len和total_len。 2. 在total_len中二分查找位置i在以last_num为末尾数字的总的串中。 3. 计算出在以last_num为末尾数字的单个内部串中位置i所在的相对位置inner_index。 4. 在以last_num为末尾数字的单个内部串中二分查找出相对位置为inner_index的数字。 其中要数第4步最难,其二分搜索函数如下: [cpp] //(单组数字串)内部二分搜索 char bin_search_inner(int i) { int s=1,t=MAX_N,mid; while(s<t) { mid=(s+t)/2; if(single_len[mid]<i) s=mid+1; else if(single_len[mid]==i) { string s=int2string(mid); return s[s.size()-1]; } else t=mid-1; } if(single_len[t]<i) t++; string rs=int2string(t); return rs[rs.size()-(single_len[t]-i)-1]; } [/cpp] 其中的single_len[mid]==i分支:比如single_len[12]=15; single_len[13]=17;如果mid==12; i==15.结果是多少呢?single_len[12]=15表示以12结尾的数字串的长度为15,而i正好为15,所以结果应该为123456789101112的最后一个数字2。 假设single_len[1234]=9843; i=9841; 这时t=1234,结果又是多少呢?假设我们到了rs[rs.size()-(single_len[t]-i)-1];这一步。通过直观观察,i=9841的位置是2,因为single_len[1234]=9843表示1234末尾的数字4的i=9843,往前推自然得到i=9841时数字为2;怎样写成一个公式呢?single_len[t]-i=2表示位置i离末尾数字的距离为2,那么它离开头的距离为多少呢?很显然用t(也就是rs=int2string(t))的总长度减去离末尾的距离再减1就行了。也就是rs[rs.size()-(single_len[t]-i)-1];,所以我们是从这个数字的末尾往前推的。 还要注意一下i最大为2147483647,2147483647刚好是int的正整数最大极限值,所以total_len要用unsigned int。其他的就没有太多要解释的了。具体看代码: [cpp] #include<iostream> #include<string> #include<sstream> #include<cstdlib> using namespace std; const static int MAX_N=31269;//数字串中最大的数 int single_len[MAX_N]={0};//single_len[i]表示1,2,3,…,i.这个数字串中总的数字位数 unsigned int total_len[MAX_N]={0};//total_len[i]表示1,12,123,…,123…i.这个数字串中总的数字位数 //将int转换为string string int2string(int i) { stringstream ss; string s; ss<<i; ss>>s; return s; } //求数字i的位数 int get_digits_num(int i) { int rs=1; while(i>=10) { rs++; i/=10; } return rs; } //初始化单组数字串 void init_single_len() { for(int i=1;i<MAX_N;i++) { single_len[i]=single_len[i-1]+get_digits_num(i); } } //初始化总体数字串 void init_total_len() { for(int i=1;i<MAX_N;i++) { total_len[i]=total_len[i-1]+single_len[i]; } } //外部(总体)二分搜索 int bin_search_outer(int i) { int s=1,t=MAX_N-1,mid; while(s<t) { mid=(s+t)/2; if(total_len[mid]<i) s=mid+1; else if(total_len[mid]==i) return mid; else t=mid-1; } if(total_len[t]<i) return t+1; else return t; } //(单组数字串)内部二分搜索 char bin_search_inner(int i) { int s=1,t=MAX_N,mid; while(s<t) { mid=(s+t)/2; if(single_len[mid]<i) s=mid+1; else if(single_len[mid]==i) { string s=int2string(mid); return s[s.size()-1]; } else t=mid-1; } if(single_len[t]<i) t++; string rs=int2string(t); return rs[rs.size()-(single_len[t]-i)-1]; } int main() { int t,i; cin>>t; init_single_len(); init_total_len(); //cout<<total_len[31268]<<endl; while(t–) { cin>>i; int last_num=bin_search_outer(i); int inner_index=i-total_len[last_num-1]; cout<<bin_search_inner(inner_index)<<endl; } return 0; } [/cpp] 本代码提交AC,用时16MS,内存464K。]]>

POJ 1005-I Think I Need a Houseboat

POJ 1005-I Think I Need a Houseboat I Think I Need a Houseboat Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 87833 Accepted: 38137 Description Fred Mapper is considering purchasing some land in Louisiana to build his house on. In the process of investigating the land, he learned that the state of Louisiana is actually shrinking by 50 square miles each year, due to erosion caused by the Mississippi River. Since Fred is hoping to live in this house the rest of his life, he needs to know if his land is going to be lost to erosion. After doing more research, Fred has learned that the land that is being lost forms a semicircle. This semicircle is part of a circle centered at (0,0), with the line that bisects the circle being the X axis. Locations below the X axis are in the water. The semicircle has an area of 0 at the beginning of year 1. (Semicircle illustrated in the Figure.) Input The first line of input will be a positive integer indicating how many data sets will be included (N). Each of the next N lines will contain the X and Y Cartesian coordinates of the land Fred is considering. These will be floating point numbers measured in miles. The Y coordinate will be non-negative. (0,0) will not be given. Output For each data set, a single line of output should appear. This line should take the form of: “Property N: This property will begin eroding in year Z.” Where N is the data set (counting from 1), and Z is the first year (start from 1) this property will be within the semicircle AT THE END OF YEAR Z. Z must be an integer. After the last data set, this should print out “END OF OUTPUT.” Sample Input 2 1.0 1.0 25.0 0.0 Sample Output Property 1: This property will begin eroding in year 1. Property 2: This property will begin eroding in year 20. END OF OUTPUT. Hint 1.No property will appear exactly on the semicircle boundary: it will either be inside or outside. 2.This problem will be judged automatically. Your answer must match exactly, including the capitalization, punctuation, and white-space. This includes the periods at the ends of the lines. 3.All locations are given in miles. Source Mid-Atlantic 2001


这题也不难,常规数学题,侵蚀面积以每年50平方米的速度进行,可以由此算出每年之后总的侵蚀面积的半径,然后通过比较给出的x、y到原点的距离判断是否在侵蚀面积之内。具体代码如下: [cpp] #include<iostream> #include<string> #include<cmath> using namespace std; double R[100];//Fred is hoping to live in this house the rest of his life.余生最多设为100年 //初始化 void init() { for(int i=0;i<100;i++) { R[i]=sqrt(2*50*(i+1)/3.14); } } //二分查找 int bin_search(double r) { int start=0,end=99,mid; while(start<=end) { mid=(start+end)/2; if(R[mid]>r) end=mid-1; else start=mid+1; } //这个时候start==end if(R[start]<r) return start+1; else return start; } int main() { init(); int n; double x,y; cin>>n; for(int i=1;i<=n;i++) { cin>>x>>y; double r=sqrt(x*x+y*y); cout<<"Property "<<i<<": This property will begin eroding in year "<<bin_search(r)+1<<"."<<endl; } cout<<"END OF OUTPUT."; return 0; } [/cpp] 本代码提交AC,用时0MS,内存220K。]]>