ACM实训-分治算法（二分，递归分治，归并排序）

A (1). 金块问题（递归，分治）

#include<bits/stdc++.h>
using namespace std;int n;
int a[100001];int F_mx(int l,int r){if(l==r)return a[l];if(r-l==1)return max(a[l],a[r]);int mid=(l+r)/2;int l_mx=F_mx(l,mid);//向左查找int r_mx=F_mx(mid+1,r);//向右查找return max(l_mx,r_mx);
}
int F_mi(int l,int r){if(l==r)return a[l];if(r-l==1)return min(a[l],a[r]);int mid=(l+r)/2;int l_mi=F_mi(l,mid);//向左查找int r_mi=F_mi(mid+1,r);//向右查找return min(l_mi,r_mi);
}int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cout<<F_mx(1,n)<<" "<<F_mi(1,n);return 0;
}

B (2). 求先序遍历（二叉树的递归，分治）详细可见：

传送门传送门2

#include<bits/stdc++.h>
using namespace std;string mid,post;void Dfs(string mid,string post) {if(post.empty())return;char root=post[post.size()-1];post.erase(post.size()-1,1);int k=mid.find(root);string l_mid=mid.substr(0,k);string r_mid=mid.substr(k+1);string l_post=post.substr(0,k);string r_post=post.substr(k);cout<<root;Dfs(l_mid,l_post);Dfs(r_mid,r_post);
}int main() {cin>>mid>>post;Dfs(mid,post);return 0;
}

C (3). 循环赛问题（递归，分治）详细可见：传送门

#include<bits/stdc++.h>
using namespace std;int a[101][101];
int n;void copy(int x,int y,int cx,int cy,int form) {//拷贝函数//x y 初始位置//cx cy 目标位置//form 规模for(int i=0; i<form; i++)for(int j=0; j<form; j++)a[cx+i][cy+j]=a[x+i][y+j];
}
void part(int form,int x,int y) {//分割函数if(form==1)return;int t=form>>1;part(t,x,y);//先割后拷part(t,x,y+t);copy(x,y,x+t,y+t,t);copy(x,y+t,x+t,y,t);
}int main() {cin>>n;for(int i=1; i<=n; i++)a[1][i]=i;part(n,1,1);for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++)printf("%5d",a[i][j]);cout<<"\n";}return 0;
}

D (4). 找礼物（二分查找）详细可见：传送门

#include<bits/stdc++.h>
using namespace std;int n,k;
double x,y;
struct node {char name[20];long long l;
} a[100001];
bool cmp(node a,node b) {return a.l<b.l;
}
int f_ind(int l,int r,int t) {int mid;while(l!=r) {mid=(l+r)/2;if(a[mid].l==t)l=mid+1;elser=mid;}return l;
}int main() {cin>>n>>k;for(int i=1; i<=n; i++)cin>>a[i].name>>x>>y,a[i].l=10000*sqrt(x*x+y*y);sort(a+1,a+1+n,cmp);int top=1;while(--k) {top=f_ind(top,n,a[top].l);if(top==n)return printf("555...");}int t=a[top].l;int cnt=f_ind(top,n,t)-top;cout<<t/10000<<" "<<cnt<<"\n";for(int i=top; cnt; cnt--,i++) {cout<<a[i].name<<"\n";}return 0;
}

E (5). 排序工作量（归并排序，逆序对，分治）

#include<bits/stdc++.h>
using namespace std;
int n,a[1000010],c[1000010];
long long ans;void msort(int l,int r) { //归并排序if(l==r)return;int mid=(l+r)/2,i=l,j=mid+1,k=l;msort(l,mid),msort(mid+1,r);while(i<=mid&&j<=r)if(a[i]<=a[j])c[k++]=a[i++];else {c[k++]=a[j++];ans+=mid-i+1;//统计答案}while(i<=mid)c[k++]=a[i++];while(j<=r)c[k++]=a[j++];for(int i=l; i<=r; i++)a[i]=c[i];
}int main() {scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d",&a[i]),a[i]+=n-i;msort(1,n);printf("%lld",ans);return 0;
}

F (6). 基因编码（递归，分治）

//定义0000这样的序列为0序列 1111这样的序列为1序列 0110这样的为01序列#include<bits/stdc++.h>
using namespace std;string s,c;char t(string s) {char ch=s[0];for(int i=1; i<s.size(); i++)if(s[i]!=ch)return 'C';//01序列为Creturn ch-'0'+'A';0序列回归A 1序列回归B
}
void f(string s) {//递归迭加字母c+=t(s);if(s.size()==1||t(s)!='C')return;//非01序列不在参与迭加如0100 会分成01和00 01会进一步分从0和1而00应该直接变成Af(s.substr(0,s.size()/2));f(s.substr(s.size()/2));
}int main() {cin>>s;f(s);cout<<c;return 0;
}

H (8). 考分鄙视（归并排序，逆序对，分治）

#include<bits/stdc++.h>
using namespace std;
int n,a[1000010],c[1000010];
long long ans;void msort(int l,int r) { //归并排序if(l==r)return;int mid=(l+r)/2,i=l,j=mid+1,k=l;msort(l,mid),msort(mid+1,r);while(i<=mid&&j<=r)if(a[i]<=a[j])c[k++]=a[i++];else {c[k++]=a[j++];ans+=mid-i+1;//统计答案}while(i<=mid)c[k++]=a[i++];while(j<=r)c[k++]=a[j++];for(int i=l; i<=r; i++)a[i]=c[i];
}int main() {scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d",&a[i]),a[i]+=n-i;reverse(a+1,a+1+n);msort(1,n);printf("%lld",ans%12345);return 0;
}

I (9). 桐桐查单词（二分查找）

#include<bits/stdc++.h>
using namespace std;struct node {int page;char name[210];
} a[20001];
int n,m;
char s[210];bool cmp(node a,node b) {return strcmp(a.name,b.name)<0;
}
int f_ind(int l,int r,char* t) {int mid;while(l!=r) {mid=l+r>>1;if(strcmp(a[mid].name,t)>0)r=mid;else if(strcmp(a[mid].name,t)<0)l=mid+1;elsereturn mid;}return l;
}int main() {cin>>n;for(int i=1; i<=n; i++)cin>>a[i].name>>a[i].page;sort(a+1,a+1+n,cmp);cin>>m;while(m--) {cin>>s;cout<<a[f_ind(1,n,s)].page<<"\n";}
}

J (10). 猪八戒吃西瓜（二分查找）

#include<bits/stdc++.h>
using namespace std;int n,m,k;
int a[100001];int f_ind(int l,int r,int t) {int mid;while(l!=r) {mid=l+r>>1;if(a[mid]>=t)r=mid;elsel=mid+1;}return l;
}int main() {cin>>n;for(int i=0; i<n; i++)cin>>a[i];sort(a,a+n);cin>>m;while(m--) {cin>>k;cout<<f_ind(0,n-1,k)+1<<"\n";}
}

K (11). 化妆晚会（二分查找）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;int n,s,ans,cnt;
int a[N];int Find(int l,int r,int t) {int mid;while(l!=r) {mid=l+r>>1;if(a[mid]<=t)l=mid+1;elser=mid;}return l;
}int main() {cin>>n>>s;for(int i=0; i<n; i++)cin>>a[i];sort(a,a+n);while(a[cnt]<=s/2) {ans+=Find(cnt,n,s-a[cnt])-cnt-1;cnt++;}cout<<ans;
}

L (12). 珍珠项链（二分查找）

#include<bits/stdc++.h>
using namespace std;int a[100001];
int n,m,l,r;int find_L(int l,int r,int t) {int mid;while(l!=r) {mid=l+r>>1;if(a[mid]>=t)r=mid;elsel=mid+1;}return l;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(int i=0; i<n; i++)cin>>a[i];sort(a,a+n);cin>>m;while(m--) {cin>>l>>r;if(l>r)swap(l,r);cout<<find_L(0,n,r+1)-find_L(0,n,l)<<"\n";}return 0;
}

M (13). 木材加工（二分答案）

#include<bits/stdc++.h>
using namespace std;int n,k,l,r;
int a[100001];bool judge(int l){int ans=0;for(int i=0;i<n;i++)ans+=a[i]/l;return ans>=k;
} //判断当木板长度为l时，能够得到的木板数是否符合条件
int fin_D(int l,int r){int mid;while(l!=r){mid=l+r>>1;if(judge(mid))l=mid+1;//若可以符合，说明此时木板可能还不是最长，继续向右逼近else                           //                             ^r=mid;//若不符合，则需要向左 //                    如上_   ^ ^ }return l-1;//在向右逼近过程中，会得到答案，但是为了试探该答案是不是最优解会向右+1试探一下
}int main()
{cin>>n>>k;for(int i=0;i<n;i++)cin>>a[i],r+=a[i];if(k>r)//若总长不足以满足k个木板长度为1return printf("0");cout<<fin_D(l,r);
}

N (14). 探险（待补）

O (15). 奇怪的函数（二分答案）

#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
const int N=2e9+5e8;int n;int main() {cin>>n;ll l=1,r=N,mid;while(l!=r) {mid=l+r>>1;ll t=trunc(log10(mid)/mid)+1;if(t<n)l=mid+1;elser=mid;}cout<<l;
}