divide conquer

Merge Merge_sort实现源码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #define inf 1e9
 4 using namespace std;
 5 
 6 void merge(int A[],int p,int q,int r)
 7 {
 8     int i,j;
 9     int n1=q-p+1;
10     int n2=r-q;
11     int L[n1+2],R[n2+2];
12     for(i=1;i<=n1;i++)
13         L[i]=A[p+i-1];
14     for(i=1;i<=n2;i++)
15         R[i]=A[q+i];
16     L[n1+1]=inf;
17     R[n2+1]=inf;
18     i=1;j=1;
19     for(int k=p;k<=r;k++)
20     {
21         if(L[i]<=R[j])
22         {
23             A[k]=L[i];
24             i++;
25         }
26         else
27         {
28             A[k]=R[j];
29             j++;
30         }
31     }
32 }
33 
34 void merge_sort(int A[],int p,int r)
35 {
36     int q;
37     if(p<r)
38     {
39         q=(p+r)/2;
40         merge_sort(A,p,q);
41         merge_sort(A,q+1,r);
42         merge(A,p,q,r);
43     }
44 }
45 
46 int main()
47 {
48     int A[20];
49     for(int i=1;i<=10;i++)
50         scanf("%d",&A[i]);
51     merge_sort(A,1,10);
52     for(int i=1;i<=10;i++)
53         printf("%3d",A[i]);
54     puts("");
55     return 0;
56 }

View Code

分治与递归：把一个难以解决的问题分解到可以解决的范畴

讲得不错：

1.子问题的解

2.规模增大的状态方程

3.递归的设计

快速乘法取模：a*b%c=(a%c)*b)%c

快速幂取模: a^b%c用下列方法：

考虑：(a^b)%c b=p(n)*2^n+p(n-1)*2^n-1+....+p(0)*1

对于:p(i)=0的部分不用考虑,对于p(i)=1的部分

a^(2^i)%c=((a^(2^(i-1))%c*(a^(2^(i-1))))%c然后分治递归。

uva,374

参考：1111 2222

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 int dfs(int b,int p,int m)
 7 {
 8     if(p==0) return 1;
 9     if(p==1) return b;
10     int a=dfs(b,p>>1,m);
11     a=a*a%m;
12     if(p%2)
13         return a*b%m;
14     return a;
15 }
16 
17 int main()
18 {
19     int b,p,m;
20     while(~scanf("%d%d%d",&b,&p,&m))
21     {
22         printf("%d
",dfs(b%m,p,m));
23     }
24 }

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 int dfs(int b,int p,int m)
 7 {
 8     int pow=1;
 9     int tmp=b;
10     while(p)
11     {
12         if(p&0x1)
13             pow=pow*tmp%m;
14         tmp=tmp*tmp%m;
15         p>>=1;
16     }
17     return pow;
18 }
19 
20 
21 int main()
22 {
23     int b,p,m;
24     while(~scanf("%d%d%d",&b,&p,&m))
25     {
26         printf("%d
",dfs(b%m,p,m));
27     }
28     return 0;
29 }

非递归版

uva,11129

题意：求一个序列，不含有长度大于等于3的等差子列。

解法：每次把奇偶拆分，然后依次分治拆分，

例如: 0 1 2 3 4

奇数项：0 2 4 偶数项： 1 3

奇数项：0 4 偶数项：2 奇数项：1 偶数项：3

然后整个序列就是所求的序列了。

因为：当分到每个奇数项有两个元素，每个偶数项有一个元素，这样组合每三个元素都不为等差子列。

通俗一点：每分出的两个序列中：奇数项的元素之差和偶数项元素之差为2*k，而两个序列的对应奇数项和偶数项之差为2*k+1.(k=1,2,3..)

还不懂的话：就是看整个序列的性质： a1 a2 a3 a4 a5 a6

　　　　　　　　　　　　　　　　　　a1 a3 a5 a2 a4 a6 左边序列的任意两个元素或一个元素和右边的一个元素或两个元素不可能构成等差。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 
 6 using namespace std;
 7 const int maxn=10005;
 8 
 9 int ans[maxn],tmp[maxn];
10 int n;
11 
12 void solve(int l,int r)
13 {
14     int i,j;
15     if(l==r) return;
16     memcpy(tmp,ans,sizeof(ans));  //把ans的值赋给tmp
17     for(i=l,j=l;i<=r;i+=2,j++)
18         ans[j]=tmp[i];    //奇数项拆分
19     for(i=l+1;i<=r;i+=2,j++)
20         ans[j]=tmp[i];    //偶数项拆分
21     solve(l,(l+r)/2);   //分治，左边
22     solve((l+r)/2+1,r);//右边
23 }
24 
25 void output()
26 {
27     printf("%d:",n);
28     for(int i=0;i<n;i++)
29         printf(" %d",ans[i]);
30     puts("");
31 }
32 
33 int main()
34 {
35     while(scanf("%d",&n),n)
36     {
37         for(int i=0;i<n;i++)
38             ans[i]=i;  //初始化
39         solve(0,n-1);
40         output();
41     }
42     return 0;
43 }

View Code

uva,10245 平面上的分治《最近点对》

借此题复习了c＋＋容器

最近点对，分治法求lgn的效率解决每个区域的最小值，然后求两个区域之间的最近点对。

可以把所有的在矩形区域的点对都求出来，其实可以只找7个点就可以了：其实就是高是ans宽为2*ans的一个矩形中最多有8个点，所以只用找一个点的7个点

if(l==r)要加上，要不然每次单个的点都要走一遍，会超时。

最后的直接min1<=10000也可以。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 const int maxn=10005;
 8 
 9 int a[maxn];
10 struct node
11 {
12     double x,y;
13 }p[maxn];
14 
15 bool cmpx(node a,node b)
16 {
17     return a.x<b.x;
18 }
19 
20 bool cmpy(int& a,int& b)
21 {
22     return p[a].y<p[b].y;
23 }
24 
25 double dist(node a,node b)
26 {
27     double dx=a.x-b.x;
28     double dy=a.y-b.y;
29     return sqrt(dx*dx+dy*dy);
30 }
31 
32 double minx(double a,double b)
33 {
34     return a<b?a:b;
35 }
36 
37 double cloest_pair(int l,int r)
38 {
39     if(l==r)
40         return 0xffffffff;//貌似不加这一点会超时
41     if(l+1==r)
42         return dist(p[l],p[r]);
43     if(l+2==r)
44         return minx(dist(p[l],p[r]),minx(dist(p[l],p[l+1]),dist(p[l+1],p[r])));
45     int mid=(l+r)>>1;
46     double ans=minx(cloest_pair(l,mid),cloest_pair(mid+1,r));
47     int cnt=0;
48     for(int i=l;i<=r;i++)
49     {
50         if(fabs(p[i].x-p[mid].x)<=ans)
51             a[cnt++]=i;//只是纪录一下每个在矩形范围的引用
52     }
53     sort(a,a+cnt,cmpy);
54     for(int i=0;i<cnt;i++)
55     {
56         int k=(i+7)>cnt?cnt:(i+7);//找七个点就可以了
57         for(int j=i+1;j<k && p[a[j]].y-p[a[i]].y<=ans;j++)
58             ans=minx(ans,dist(p[a[i]],p[a[j]]));//注意是a[i]
59     }
60     return ans;
61 }
62 
63 int main()
64 {
65     int n;
66     while(scanf("%d",&n),n)
67     {
68         for(int i=0;i<n;i++)
69             scanf("%lf%lf",&p[i].x,&p[i].y);
70         sort(p,p+n,cmpx);
71         double min1=cloest_pair(0,n-1);
72         if(min1-10000<=1e-9)//对以后所有的趋近于，都用一种渐进趋势
73             printf("%.4lf
",min1);
74         else
75             printf("INFINITY
");
76             
77     }
78     return 0;
79 }

View Code

树分治：点分治，边分治，

点分治：找重心然后递归分治求解

边分治：分出两块，比较简单易懂但是时间复杂度较高

Poj,1741

求出树中两个点之间的边长距离不超过k的顶点对数

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <vector>
  6 
  7 using namespace std;
  8 const int maxn=10005;
  9 struct edge
 10 {
 11     int to;
 12     int length;
 13 };
 14 
 15 int N,K;
 16 vector<edge> G[maxn];
 17 bool centroid[maxn];
 18 int subtree_size[maxn];
 19 int ans;
 20 
 21 
 22 int compute_subtree_size(int v,int p)
 23 {
 24     int c=1;
 25     for(int i=0;i<G[v].size();i++)
 26     {
 27         int w=G[v][i].to;
 28         if(w==p || centroid[w])
 29             continue;
 30         c+=compute_subtree_size(G[v][i].to,v);
 31     }
 32     subtree_size[v]=c;
 33     return c;
 34 }
 35 
 36 pair<int,int> search_centroid(int v,int p,int t)
 37 {
 38     pair<int,int> res=make_pair(INT_MAX,-1);
 39     int s=1,m=0;
 40     for(int i=0;i<G[v].size();i++)
 41     {
 42         int w=G[v][i].to;
 43         if(w==p || centroid[w])
 44             continue;
 45         res=min(res,search_centroid(w,v,t));
 46         m=max(m,subtree_size[w]);
 47         s+=subtree_size[w];
 48     }
 49     m=max(m,t-s);
 50     res=min(res,make_pair(m,v));
 51     return res;
 52 }
 53 
 54 void enumerate_paths(int v,int p,int d,vector<int>& ds)
 55 {
 56     ds.push_back(d);
 57     for(int i=0;i<G[v].size();i++)
 58     {
 59         int w=G[v][i].to;
 60         if(w==p || centroid[w])
 61             continue;
 62         enumerate_paths(w,v,d+G[v][i].length,ds);
 63     }
 64 }
 65 
 66 int count_pairs(vector<int>& ds)
 67 {
 68     int res=0;
 69     sort(ds.begin(),ds.end());
 70     int j=ds.size();
 71     for(int i=0;i<ds.size();i++)
 72     {
 73         while(j>0 && ds[i]+ds[j-1]>K)
 74             --j;
 75         res+=j-(j>i?1:0);
 76     }
 77     return res/2;
 78 }
 79 
 80 void solve_subproblem(int v)
 81 {
 82     compute_subtree_size(v,-1);
 83     int s=search_centroid(v,-1,subtree_size[v]).second;
 84     centroid[s]=true;
 85     
 86     for(int i=0;i<G[v].size();i++)
 87     {
 88         if(centroid[G[v][i].to])
 89             continue;
 90         solve_subproblem(G[s][i].to);
 91     }
 92     
 93     vector<int> ds;
 94     ds.push_back(0);
 95     for(int i=0;i<G[s].size();i++)
 96     {
 97         if(centroid[G[s][i].to])
 98             continue;
 99         vector<int> tds;
100         enumerate_paths(G[s][i].to,s,G[s][i].length,tds);
101         
102         ans-=count_pairs(tds);
103         ds.insert(ds.end(),tds.begin(),tds.end());
104     }
105     
106     ans+=count_pairs(ds);
107     centroid[s]=false;
108 }
109 int main()
110 {
111     scanf("%d%d",&N,&K);
112     int a,b,l;
113     for(int i=0;i<4;i++)
114     {
115         scanf("%d%d%d",&a,&b,&l);
116         edge now;
117         now.to=b;
118         now.length=l;
119         G[a].push_back(now);
120         now.to=a;
121         G[b].push_back(now);
122     }
123     ans=0;
124     solve_subproblem(1);
125     printf("%d
",ans);
126     return 0;
127 }

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <map>
  6 #define MP make_pair
  7 using namespace std;
  8 
  9 void read(int& x) {
 10     x = 0;
 11     char c = ' ';
 12     while(c < '0' || c > '9') c = getchar();
 13     while('0' <= c && c <= '9') {
 14         x = x * 10 + c - '0';
 15         c = getchar();
 16     }
 17 }
 18 
 19 typedef pair<int, int> PII;
 20 const int maxn = 10000 + 10;
 21 const int INF = 0x3f3f3f3f;
 22 
 23 struct Edge
 24 {
 25     int v, w, nxt;
 26     Edge() {}
 27     Edge(int v, int w, int nxt): v(v), w(w), nxt(nxt) {}
 28 };
 29 
 30 int n, k, ans;
 31 vector<int> d, d2;
 32 bool del[maxn];
 33 
 34 int ecnt, head[maxn];
 35 Edge edges[maxn * 2];
 36 
 37 void AddEdge(int u, int v, int w) {
 38     edges[ecnt] = Edge(v, w, head[u]);
 39     head[u] = ecnt++;
 40 }
 41 
 42 int fa[maxn], sz[maxn];
 43 
 44 void dfs(int u) {
 45     sz[u] = 1;
 46     for(int i = head[u]; ~i; i = edges[i].nxt) {
 47         int v = edges[i].v;
 48         if(v == fa[u] || del[v]) continue;
 49         fa[v] = u;
 50         dfs(v);
 51         sz[u] += sz[v];
 52     }
 53 }
 54 
 55 PII findCenter(int u, int t) {
 56     PII ans(INF, -1);
 57     int m = 0;
 58     for(int i = head[u]; ~i; i = edges[i].nxt) {
 59         int v = edges[i].v;
 60         if(v == fa[u] || del[v]) continue;
 61         ans = min(ans, findCenter(v, t));
 62         m = max(m, sz[v]);
 63     }
 64     m = max(m, t - sz[u]);
 65     ans = min(ans, MP(m, u));
 66     return ans;
 67 }
 68 
 69 void getDist(int u, int p, int dist, vector<int>& d) {
 70     d.push_back(dist);
 71     for(int i = head[u]; ~i; i = edges[i].nxt) {
 72         int v = edges[i].v, w = edges[i].w;
 73         if(v == p || del[v]) continue;
 74         getDist(v, u, dist + w, d);
 75     }
 76 }
 77 
 78 int cntPiars(vector<int>& d) {
 79     int ans = 0;
 80     sort(d.begin(), d.end());
 81     int j = d.size();
 82     for(int i = 0; i < d.size(); i++) {
 83         while(j && d[i] + d[j-1] > k) j--;
 84         ans += j - (j > i ? 1 : 0);
 85     }
 86     return ans;
 87 }
 88 
 89 void solve(int u) {
 90     fa[u] = 0;
 91     dfs(u);
 92     int s = findCenter(u, sz[u]).second;
 93     del[s] = true;
 94     
 95     for(int i = head[u]; ~i; i = edges[i].nxt) {
 96         int v = edges[i].v;
 97         if(del[v]) continue;
 98         solve(v);
 99     }
100 
101     d.clear();
102     d.push_back(0);
103     for(int i = head[s]; ~i; i = edges[i].nxt) {
104         int v = edges[i].v, w = edges[i].w;
105         if(del[v]) continue;
106         d2.clear();
107         getDist(v, s, w, d2);
108         ans -= cntPiars(d2);
109         d.insert(d.begin(), d2.begin(), d2.end());
110     }
111 
112     ans += cntPiars(d);
113     del[s] = false;
114 }
115 
116 int main()
117 {
118     while(scanf("%d", &n) == 1 && n) {
119         ecnt = 0;
120         memset(head, -1, sizeof(head));
121         for(int u = 1; u <= n; u++) {
122             int v, w;
123             for(read(v); v; read(v)) {
124                 read(w);
125                 AddEdge(u, v, w);
126                 AddEdge(v, u, w);
127             }
128         }
129 
130         for(read(k); k; read(k)) {
131             ans = 0;
132             solve(1);
133             int pre = ans;
134             ans = 0;
135             k--;
136             solve(1);
137             printf("%s
", pre - ans > 0 ? "AYE" : "NAY");
138         }
139         printf(".
");
140     }
141 
142     return 0;
143 }

相减法

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string>
  5 #include <algorithm>
  6 #include <cmath>
  7 
  8 #define maxn 11111
  9 #define maxm 55555
 10 
 11 using namespace std;
 12 
 13 struct edge   //建边
 14 {
 15     int v,w,next;
 16 }E[maxm];
 17 
 18 int head[maxn],e;  //head[]来表示一个点的所有子树
 19 int vis[maxn],n,k,ans,root,num;  //vis用来找重心
 20 
 21 void init()
 22 {
 23     e=0;
 24     memset(head,-1,sizeof(head));
 25 }
 26 
 27 void add(int u,int v,int w)
 28 {
 29     E[e].v=v;  //建边，然后纪录所有的子树节点
 30     E[e].w=w;
 31     E[e].next=head[u];
 32     head[u]=e++;
 33 }
 34 
 35 int mi,dis[maxn],size[maxn],mx[maxn];
 36 
 37 void dfssize(int u,int fa)   //求出每棵子树的节点数
 38 { 
 39     size[u]=1;
 40     mx[u]=0;
 41     for(int i=head[u];i!=-1;i=E[i].next)
 42     {
 43         int v=E[i].v;
 44         if(v!=fa && !vis[v])  //为什么不更新vis了，我一开始不知道这个算法的时候是这么想的，因为下次还要访问。
 45         {
 46             dfssize(v,u);
 47             size[u]+=size[v];
 48             if(size[v]>mx[u])//求出一个节点的子树中最大子树
 49                 mx[u]=size[v];
 50         }
 51     }
 52 }
 53 
 54 void dfsroot(int r,int u,int fa)
 55 {
 56     if(size[r]-size[u]>mx[u])  //如果删除该顶点后，得到最大子树
 57         mx[u]=size[r]-size[u];
 58     if(mx[u]<mi)//得到的最大子树的节点最小
 59         mi=mx[u],root=u;
 60     for(int i=head[u];i!=-1;i=E[i].next)
 61     {
 62         int v=E[i].v;
 63         if(v!=fa && !vis[v])
 64             dfsroot(r,v,u);
 65     }
 66 }
 67 
 68 void dfsdis(int u,int d,int fa)//求出所有的点到重心的距离。
 69 {
 70     dis[num++]=d;
 71     for(int i=head[u];i!=-1;i=E[i].next)
 72     {
 73         int v=E[i].v;
 74         if(v!=fa && !vis[v])
 75             dfsdis(v,d+E[i].w,u);
 76     }
 77     
 78 }
 79 
 80 int calc(int u,int d)
 81 {
 82     int ret=0;
 83     num=0;
 84     dfsdis(u,d,0);
 85     sort(dis,dis+num);//排序后的精髓确保时间复杂度最小
 86     int i=0,j=num-1;
 87     while(i<j)
 88     {
 89         if(dis[i]+dis[j]<k) i++;
 90         else if(dis[i]+dis[j]>k) j--;
 91         else
 92         {
 93             if(dis[i]==dis[j]) //i-j 的任意两点满足情况。一个等差和
 94             {
 95                 ret+=(j-i)*(j-i+1)/2;
 96                 break;
 97             }
 98             int st=i,ed=j;
 99             while(dis[i]==dis[st]) st++;  
100             while(dis[j]==dis[ed]) ed--;
101             ret+=(st-i)*(j-ed);
102             i=st,j=ed;
103         }
104     }
105     return ret;
106 }
107 
108 void dfs(int u)
109 {
110     mi=n;
111     dfssize(u,0);
112     dfsroot(u,u,0);
113     ans+=calc(root,0);  //所有满足情况的对
114     vis[root]=1;
115     for(int i=head[root];i!=-1;i=E[i].next)
116     {
117         int v=E[i].v;
118         if(!vis[v])
119         {
120             ans-=calc(v,E[i].w); //删除重复计算的。
121             dfs(v);
122         }
123     }
124     
125 }
126 void solve()
127 {
128     memset(vis,0,sizeof(vis));
129     ans=0;
130     dfs(1);
131     if(ans>0)
132         printf("AYE
");
133     else
134         printf("NAY
");
135 }
136 
137 int main()
138 {
139     while(scanf("%d",&n),n)
140     {
141         init();
142         int v,w;
143         for(int i=1;i<=n;i++)
144         {
145             while(scanf("%d",&v),v)
146             {
147                 scanf("%d",&w);
148                 add(i,v,w);
149                 add(v,i,w);
150             }
151         }
152         
153         while(scanf("%d",&k),k)
154             solve();
155         printf(".
");
156     }
157     return 0;
158 }

View Code

活在现实，做在梦里。