首页 > 代码库 > 分治算法小总结 x
分治算法小总结 x
其实这个题用冒泡排序做的，但用归并排序也能做出来（分析一下此题与逆序对是有相同之处的）
由于两者的代码完全一样，就只放一个啦 ~\(≧▽≦)/~啦啦啦
1.洛谷 P1116 车厢重组
题目描述
在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。
输入输出格式
输入格式：
输入文件有两行数据，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。
输出格式：
一个数据，是最少的旋转次数。
输入输出样例
44 3 2 1
/*----------------------分割线---------------------*/
2.洛谷 P1908 逆序对
题目描述
猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。
输入输出格式
输入格式：
第一行，一个数n，表示序列中有n个数。
第二行n个数，表示给定的序列。
输出格式：
给定序列中逆序对的数目。
输入输出样例
65 4 2 6 3 1
11
说明
对于50%的数据，n≤2500
对于100%的数据，n≤40000。
思路：代码酱来也~
#include<iostream>#include<algorithm>#define M 111111using namespace std;int n,ans;int a[M],b[M];void merge_sort(int l,int r){ if(l == r) return; int m = (l+r) / 2 ;//中间值 merge_sort(l,m);//左边 merge_sort(m+1,r); //右边 int i=l,j=m+1,k=l; for(;i<=m&&j<=r;) { if(a[i]<=a[j]) b[k++]=a[i++]; else { ans+=m-i+1;//统计产生逆序对的个数 b[k++]=a[j++]; } } for(;i<=m;b[k++]=a[i++]); for(;j<=r;b[k++]=a[j++]); for(int i=l;i<=r;i++) a[i]=b[i];}int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; merge_sort(1,n); cout<<ans; return 0;}
/*----------------------分割线---------------------*/
3.Codevs 1688 求逆序对给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目
数据范围：N<=105。Ai<=105。时间限制为1s。
第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
所有逆序对总数.
4
3
2
3
2
3
代码酱来也~#include<iostream>#include<algorithm>#define M 111111#define LL long longusing namespace std;LL ans;int n;int a[M],b[M];void merge_sort(int l,int r){ if(l == r) return; int m = (l+r) / 2 ;//中间值 merge_sort(l,m);//左边 merge_sort(m+1,r); //右边 int i=l,j=m+1,k=l; for(;i<=m&&j<=r;) { if(a[i]<=a[j]) b[k++]=a[i++]; else { ans+=(LL)m-(LL)i+1; //统计产生逆序对的个数 b[k++]=a[j++]; } } for(;i<=m;b[k++]=a[i++]); for(;j<=r;b[k++]=a[j++]); for(int i=l;i<=r;i++) a[i]=b[i];}int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; merge_sort(1,n); cout<<ans; return 0;}
4.洛谷 P1115 最大子段和
题目描述
给出一段序列，选出其中连续且非空的一段使得这段和最大。
输入输出格式
输入格式：
输入文件maxsum1.in的第一行是一个正整数N，表示了序列的长度。
第2行包含N个绝对值不大于10000的整数A[i]，描述了这段序列。
输出格式：
输入文件maxsum1.out仅包括1个整数，为最大的子段和是多少。子段的最小长度为1。
输入输出样例
72 -4 3 -1 2 -4 3
4
说明
【样例说明】2 -4 3 -1 2 -4 3
【数据规模与约定】
对于40%的数据，有N ≤ 2000。
对于100%的数据，有N ≤ 200000。
思路:
这道题真的就是一道模板题，但是为什么我交了好几遍就是没有AC呢？原因出在第二个点上，因为第二个点里的数据似乎全部都是负的，所以在进行初始化的时候需要赋值为一个极小数(ans,lmax,rmax这三个)，不然按一般的话，一定是从0开始，所以负数就出不来，所以……
代码酱来也~
#include <cstdio>#include <iostream>#include <algorithm>#define LL long long using namespace std;const int N = 2e5 + 6;int n;int a[N];LL calc(int l, int r){ if(l==r) return a[l]; int m = (l+r) / 2; LL ret = max(calc(l, m), calc(m+1, r)); int lmax = -1000000, rmax = -1000000; for(int i=m, s=0; i>=l; i--) s+=a[i], lmax=max(lmax, s); for(int i=m+1, s=0; i<=r; i++) s+=a[i], rmax=max(rmax, s); ret = max(ret, (LL)(lmax) + (LL)(rmax)); return ret;}int main(){ scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &a[i]); LL ans=-1000000; ans = max(ans, (LL)calc(1, n)); cout<<ans; return 0;}
5.洛谷P1010 幂次方
题目描述
任何一个正整数都可以用2的幂次方表示。例如
137=2^7+2^3+2^0 同时约定方次用括号来表示，即a^b 可表示为a(b)。
由此可知，137可表示为：
2(7)+2(3)+2(0)进一步：7= 2^2+2+2^0 (2^1用2表示)
3=2+2^0 所以最后137可表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)又如：
1315=2^10 +2^8 +2^5 +2+1所以1315最后可表示为：
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)输入输出格式
输入格式：
一个正整数n(n≤20000)。
输出格式：
符合约定的n的0，2表示(在表示中不能有空格)
输入输出样例
1315
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
思路:
如果遇到2或者1,特判一下,直接输出,其余的如果能够继续分解,就将其分解(分治~)
代码:
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std;void work(int n){ if(n==1) { printf("2(0)"); return; } if(n==2) { printf("2"); return; } else { int j=1,i=0; do { j*=2; if(j>n)///超出该数n { j/=2; if(i==1) printf("2");///特判 else { printf("2(");///输出形式 work(i); printf(")"); } if(n-j!=0)///若还能够继续分解 { printf("+");///用+连接 work(n-j);///继续分解 } return; } else i++;///如果还不够大,继续加 }while(1); }}int main(){ int n; cin>>n; work(n); return 0;}
分治算法小总结 x