分治 即分而治之 将大问题化解为小问题逐一求解
这种题没有固定的模板 只有分治的思想 所以在做题的时候应当多想如何将一个大问题化解成若干个子问题进行求解
直接上题了

P1226 【模板】快速幂||取余运算

非常经典的分治问题
常规算法求$a^b$要$O(b)$的时间复杂度 我们运用分治的思想
观察到如果$2|b，$那么$a^b=(a^2{)}^{b/2}$这样就降低了一半的幂次 时间复杂度降到了$O(lo{g}_{2}b)$
所以 当$b$是偶数时，$a^b=(a^2{)}^{b/2}$
当$b$时奇数时，$a^b=(a^2{)}^{b/2}\ast a$
上代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quickpow(ll x, ll y, ll mod){ll re=1LL;while(y!=0){if(y%2==1)re=re*x%mod;x=x*x%mod,y=y/2;}return re;
}
ll n,m,p;
int main(){cin>>n>>m>>p;printf("%lld^%lld mod %lld=%lld\n",n,m,p,quickpow(n,m,p));
}

我们用位运算简化一下 就会得到非常好看的快速幂

（我觉得还挺好看的

P1010 [NOIP1998 普及组] 幂次方

一个递归题 没想到居然一遍过了
对于一个数 从他的二进制最高位开始判断 如果有$1,$那么就输出$2($位数$)，$位数再进行操作 依次递归
对于$2、1、0$要单独判断 如果是$0$直接输出 $1/2$

#include<bits/stdc++.h>
using namespace std;
void op(int x){if(x==0){putchar(48);return ;}bool flag=0;for(int i=18;i>=2;i--){if(x&(1<<i)){if(!flag)flag=1;else putchar('+');printf("2(");op(i);printf(")");}}if(x&(1<<1)){if(!flag)flag=1;else putchar('+');putchar('2');}if(x&1){if(!flag)flag=1;else putchar('+');printf("2(0)");}
}
int main(){int x;cin>>x;op(x);puts("");
}

P1429 平面最近点对（加强版）

传送门
加强版的加强版
利用分治的思想 每次将整个区间分为两部分求解 分别求出左右两部分的最小值 再将两部分合并求最小值
细节部分 首先区间缩小到只剩两个点时显然结果为这两个点的最小值
其次将一个区间的左右两部分求解出来时 对于中间的点 我们找到距离$mid$左右两侧距离最小值的点 对于这些点暴力求解更新最小值 显然这些点不会有太多 因此这个暴力的时间复杂度是常数级别的
上代码↓

#include<bits/stdc++.h>
#define N int(2e6+10)
#define INF ((1LL<<62)-1+(1LL<<62))
#define ll long long
using namespace std;
inline void read(ll &x){ll s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}x=s*w;
}
struct node{ll x,y;
}p[N],op[N];
bool cmp(node a, node b){if(a.x!=b.x)return a.x<b.x;else return a.y<b.y;
}
bool opcmp(node a, node b){if(a.y!=b.y)return a.y<b.y;else return a.x<b.x;
}
ll dis(node i, node j){return (i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y);
}
ll n,px,py,mn=INF,mx,pnt;
ll merge(ll l, ll r){if(l>=r)return INF;if(r-l==1)return dis(p[l],p[r]);ll mid=l+r>>1;ll le=merge(l,mid),ri=merge(mid+1,r);mn=(min(le,ri),mn),pnt=0;for(ll i=l;i<=r;i++)if((p[mid].x-p[i].x)*(p[mid].x-p[i].x)<mn)op[++pnt]=p[i];sort(op+1,op+1+pnt,opcmp);for(ll i=1;i<=pnt;i++){for(ll j=i+1;j<=pnt;j++){if((op[i].y-op[j].y)*(op[i].y-op[j].y)>=mn)break;if(dis(op[i],op[j])<mn)mn=dis(op[i],op[j]);}}return mn;
}
int main(){read(n);for(ll i=1;i<=n;i++)read(p[i].x),read(p[i].y);sort(p+1,p+1+n,cmp);printf("%.4lf\n",sqrt(merge(1,n)));
}

P3612 [USACO17JAN]Secret Cow Code S

传送门
题意大概是给你一个字符串 对这个字符串进行以下操作
先将最后一位复制到后面 再把除了最后一位剩下的字符串复制到后面 然后就变成了一个新的字符串
以此类推 一直复制下去 给你一个位数 求这个位数上的字符是啥
刚开始还以为是一直回文 后来才发现是直接把前面的字符整体复制过来 那就简单了
对于每个位数 找到上一次复制操作时所对应的位数就行了

#include<bits/stdc++.h>
using namespace std;
char str[50];
long long n;
int main(){scanf("%s%lld",str,&n);int len=strlen(str);int now=62;while((1LL<<now)>n*2/len)now--;while(now!=0){if(n==(1LL<<now-1)*len+1)n--;else if(n>(1LL<<now-1)*len)n-=(1+(1LL<<now-1)*len);now--;}putchar(str[n-1]);
}

总结

分治算法是算法竞赛中经常用到的算法 非常玄学 当处理大数据无从下手的时候不妨试试分治算法