7.31 基本算法1.2

前缀和与差分

介绍：前缀和与差分是一种互补的状态，给定序列A，设其差分序列为B，则序列A的差分序列B的前缀和序列就是原序列A，A的前缀和序列S的差分序列也是原序列A。

关于一维前缀和，二维前缀和，差分的知识点总结参考：https://blog.csdn.net/K_R_forever/article/details/81775899

例题：

poj3263 Tallest cow（区间修改，差分数组，前缀和）

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<map>
 4 using namespace std;
 5 const int maxn = 10010;
 6 
 7 map<pair<int,int>, bool>existed;
 8 int c[maxn], d[maxn];
 9 
10 int main(){
11     int n, p, h, m;
12     cin>>n>>p>>h>>m;
13     for(int i = 1; i <= m; i++){
14         int a, b;  cin>>a>>b;
15         if(a > b)swap(a, b);
16         if(existed[make_pair(a,b)])continue;
17         d[a+1]--;  d[b]++;
18         existed[make_pair(a,b)] = 1;
19     }
20     for(int i = 1; i <= n; i++){
21         c[i] = c[i-1]+d[i];
22         cout<<h+c[i]<<'
';
23     }
24     return 0;
25 }

View Code

思路：求每头牛的相对大小关系，可以想到运用前缀和与差分这一知识点。假设C[p]=0，表示最高的牛为基准且为0，则其他C[i]表示第i头牛与最高牛的身高差距，则i牛的身高为C[i]+H。又因为时间复杂度问题，重复对C[i]数组的操作时间复杂度更高，所以新建立一个D数组为其差分数组，则D的前缀和序列即为C。注意输入区间如果重复则筛去。

BZOJ1218（二维前缀和）

 1 #include<set>
 2 #include<map>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<queue>
 6 #include<vector>
 7 #include<string>
 8 #include<cstring>
 9 #include<iostream>
10 #include<algorithm>
11 using namespace std;
12 typedef long long ll;
13 const int inf = 0x3f3f3f3f;
14 const int maxn = 5e3 + 10;
15 int m[maxn][maxn];
16 int main()
17 {
18     int n, r;
19     scanf("%d%d", &n, &r);
20     memset(m, 0, sizeof(m));
21     while(n--)
22     {
23         int x, y, v;
24         scanf("%d%d%d", &x, &y, &v);
25         m[x + 1][y + 1] = v;
26     }
27     for(int i = 1; i <= 5001; ++i)
28         for(int j = 1; j <= 5001; ++j)
29             m[i][j] += m[i][j - 1] + m[i - 1][j] - m[i - 1][j - 1];
30     int ans = 0;
31     for(int i = r; i <= 5001; ++i)
32     {
33         for(int j = r; j <= 5001; ++j)
34         {
35             int x = i - r, y = j - r;
36             ans = max(ans, m[i][j] - m[i][y] - m[x][j] + m[x][y]);
37         }
38     }
39     printf("%d
", ans);
40     return 0;
41 }

View Code

思路：

看到块状炸弹式膨胀题型，求某一区域内被计算的个数等，可以考虑矩形二维前缀和，差分方法

二分

介绍：

1.1.最大值最小化：

    //最大值最小化 
    while(l < r){
        int mid = (l + r) >> 1;
        if(a[mid] >= x)  r = mid;   //有可能mid就是答案 
        else  l = mid+1;
    }

1.2.最小值最大化：

    //最小值最大化
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(a[mid] >= x)  l = mid;   //有可能mid就是答案 
        else  r = mid - 1;
    }

2.实数域上的二分：

    while(l + 1e-5 < r){
        double mid = (l + r) / 2;
        if(calc(mid))  r = mid;
        else l = mid;
    }

3.三分求单峰函数极值

4.二分答案转化为判定：把求最优解问题，转化为给定一个值mid，判定是否存在一个可行方案（judge函数）达到mid的问题。

例题：

POJ 2018（二分查询标记）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 double a[100005],b[100005],sum[100005];
 7 
 8 int main(){
 9     int n,L;
10     cin>>n>>L;
11     for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
12     double eps=1e-5;
13     double l=-1e6,r=1e6;
14     while(r-l>eps){
15         double mid=(r+l)/2;
16         for(int i=1;i<=n;i++) b[i]=a[i]-mid;
17         for(int i=1;i<=n;i++) sum[i]=sum[i-1]+b[i];
18         double ans=-1e10,minval=1e10;
19         for(int i=L;i<=n;i++){
20             minval=min(minval,sum[i-L]);
21             ans=max(ans,sum[i]-minval);
22         }
23         if(ans>=0) l=mid; else r=mid;
24     }
25     cout<<int(r*1000)<<endl;
26     return 0;
27 }

View Code

思路：求一个子段，他的和最大，且字段长度不小于L（将数列中的每个数都减去二分的值，通过前缀和判断其其字段和非负）

POJ 1050（矩阵前缀和）

 1 #include<iostream>
 2 #include<cstdio> 
 3 #define ll long long 
 4 #define fo(i,j,n) for(register int i=j; i<=n; ++i)
 5 using namespace std;
 6 int a[105][105],n;
 7 int sum[105][105];
 8 // 矩阵前缀和
 9 void init(){
10     fo(i,1,n){
11         fo(j,1,n){
12             sum[i][j] = sum[i-1][j] + sum[i][j-1] + a[i][j] - sum[i-1][j-1];
13         }
14     }
15 }
16 // 查询矩阵和## 标题
17 int query(int x1, int y1, int x2, int y2){
18     return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
19 }
20 void solve(){
21     int MAX = -1e8;
22     fo(x1,1,n){
23         fo(y1,1,n){
24             fo(x2,x1,n){
25                 fo(y2,y1,n){
26                     int t = query(x1,y1,x2,y2);
27                     if(t>MAX) {
28                         MAX = t;
29                     //    cout<<x1<<" " <<y1<<" " <<x2<<" " <<y2<<endl;
30                     }
31                 }
32             }
33         }
34     }
35     printf("%d
",MAX);
36 }
37 int main(){
38     scanf("%d",&n);
39     fo(i,1,n){
40         fo(j,1,n){
41             scanf("%d",&a[i][j]);
42         }
43     }
44     init();
45     solve();
46     return 0;
47 }

View Code

思考：本题还可以用贪心来优化算法

当字段区间连续序列和sum小于0时sum归零，是上一道题的变形题，但是没有区间长度大于T的要求限制，即求一个子段，他的和最大

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define ll long long
 5 #define fo(i,j,n) for(register int i=j; i<=n; ++i)
 6 using namespace std;
 7 const int maxn = 1e4;
 8 int mp[maxn][maxn],n;
 9 int d[maxn];
10 void solve(){
11     int ans = mp[1][1];
12     fo(i,1,n){ // i行 
13         memset(d,0,sizeof(d)); 
14         fo(j,i,n){ // j行 
15             fo(k,1,n){ // k列 
16                 d[k] += mp[j][k]; // d[k] 表示第k列  第i~j行的和(区间和) 
17             }
18             
19             // 接下来的做法就类似一维数组求最大连续序列和 
20             int sum = 0;
21             fo(k,1,n){
22                 sum += d[k];
23                 ans = max(ans,sum);
24                 if(sum<0) sum=0;
25             } 
26         }
27     }
28     printf("%d
", ans);
29 } 
30 int main(){
31     while(scanf("%d",&n)==1){ // 使程序更加具有鲁棒性 
32         fo(i,1,n){
33             fo(j,1,n)
34                 scanf("%d",&mp[i][j]);
35         }
36         solve();
37     }
38     return 0;
39 }

View Code

AcWing113

倍增

介绍：

如果状态空间很大，可以通过成倍增长的方式，只递推状态空间中在2的整数次幂位置上的值作为代表，当需要其他位置上的值时，通过“任意整数可以表示成若干个2的次幂项的和”这一性质，使用之前的代表值拼成所需的值。

倍增常与二进制划分两个思想互相结合，包括求解RMQ（区间最值）和ST算法（看书）。

例题：

ch601 genius acm（倍增 + 归并排序）

#include <iostream>
#include <set>
#include <cmath>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

LL m, n, t, k;
const int maxn = 5e5 + 5;
LL s[maxn], b[maxn], c[maxn];

bool check(LL l, LL r, LL lr)
{
    LL tot = 0;
    int t = l, len = r - l + 1;
    for(LL i = lr; i <= r; i++){
        b[i] = s[i];
    }
    sort(b + lr, b + r + 1);
    if(l == lr){
        for(int i = l; l <= r; i++){
            c[i] = b[i];
        }
    }
    else{
        int i = l, j = lr;
        while(i < lr && j <= r){
            if(b[i] <= b[j]){
                c[t++] = b[i++];
            }
            else{
                c[t++] = b[j++];
            }
        }
        while(i < lr)c[t++] = b[i++];
        while(j <= r)c[t++] = b[j++];
    }
    LL jiaoyan = 0;
    for(LL i = l; i <= min(l + m - 1, l + (r - l + 1) / 2 - 1); i++){
        jiaoyan += (c[r - i + l] - c[i]) * (c[r - i + l] - c[i]);
    }
    if(jiaoyan <= k){
        for(int i = l; i <= r; i++){
            b[i] = c[i];
        }
        return 1;
    }
    return 0;
}

int main()
{
    scanf("%lld", &t);
    while(t--){
        scanf("%lld%lld%lld", &n, &m, &k);
        for(LL i = 1; i <= n; i++){
            scanf("%lld", &s[i]);
        }

        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        LL sum = 0, l = 1, r = 1, p = 1;
        b[1] = s[1];
        while(r < n){
            if(!p){
                sum++;
                p = 1;r++;
                l = r;
                b[l] = s[l];
                continue;
            }
            if(p){
                if(r + p <= n && check(l, r + p, r + 1)){
                    r += p;
                    p *= 2;
                    if(r == n)break;
                }
                else{
                    p /= 2;
                }
            }
            //cout<<sum<<endl;

        }
        if(r == n)sum++;

        printf("%lld
", sum);
    }
}

View Code

贪心（策略+寻找最优解）

例题：

poj3614 Sunscreen

#include<cstdio>
#include<algorithm>
using namespace std;
#define _rep(i,a,b) for(int i=(a);i<=(b);i++)
const int N=2510; 
int c,l,ans;
struct node{
    int minspf,maxspf;
    bool operator <(const node&rhs)const{
    return minspf>rhs.minspf;}
}cow[N];
struct NODE{
    int spf,cover;
    bool operator <(const NODE&rhs)const{
    return spf>rhs.spf;}
}fss[N];
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&c,&l);
    _rep(i,1,c)scanf("%d%d",&cow[i].minspf,&cow[i].maxspf);
    sort(cow+1,cow+1+c);
    _rep(i,1,l)scanf("%d%d",&fss[i].spf,&fss[i].cover);
    sort(fss+1,fss+l+1);
    _rep(i,1,c)
    {
        _rep(j,1,l)
        {
            if(fss[j].cover>0&&fss[j].spf<=cow[i].maxspf&&fss[j].spf>=cow[i].minspf)
            {
                fss[j].cover--;
                ans++;
                break;
            }
        }
    }
    printf("%d
",ans);
    return 0;
}

View Code

poj3190 stall reservation

#include"iostream"
#include"stdio.h"
#include"queue"
#include"algorithm"
using namespace std;
const int MAXN=50005;
 
struct Node
{
    int s,e,pos;
    friend bool operator<(Node a,Node b)
    {
        if(a.e==b.e) return a.s<b.s;
        return a.e>b.e;
    }
};
 
bool Cmp(Node a,Node b)
{
    if(a.s!=b.s)
        return a.s<b.s;
    else
        return a.e<b.e;
}
 
Node cows[MAXN];
priority_queue<Node>que;
int order[MAXN];
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&cows[i].s,&cows[i].e);
            cows[i].pos=i;
        }
        sort(cows,cows+n,Cmp);
        que.push(cows[0]);
        order[cows[0].pos]=1;
        for(int i=1;i<n;i++)
        {
            if(cows[i].s>que.top().e)
            {
                order[cows[i].pos]=order[que.top().pos];
                que.pop();
                que.push(cows[i]);
            }
            else
            {
                que.push(cows[i]);
                order[cows[i].pos]=que.size();
            }
        }
        cout<<que.size()<<endl;
        for(int i=0;i<n;i++)
        {
            cout<<order[i]<<endl;
        }
    }
    return 0;
}

View Code

思路：区间贪心。把尽量多的牛放在一个棚子里，这样就可以使得用到的棚子数最少。只要任意两头牛的挤奶时间不重合，就可以放在一个棚子里。因为N值比较大，先标记好每一头牛的起始坐标，然后按起始时间从小到大进行排序，然后依次从前往后去遍历每一头牛。这里需要用一个优先队列来维护，以结束时间从小到大来维护，每次将一头牛与队列首的牛进行比较，如果满足它的起始时间大于队列首的那头牛的结束时间，这两头牛就可以使用同一个机器，否则就新加一个机器。这里需要注意牛的入队和出队

poj1328 radar installation

题意：地图的x轴的上方为海，下方为陆地，海中有n个小岛，坐标为(isl[i].x,isl[i].y)。有一种雷达，能探测到的范围为以d为半径的圆。问海岸线上至少造多少雷达可以把所有的小岛都包含在内。注意雷达是建在海岸线上的，也就是x轴上的。

 1     #include<iostream>  
 2     #include<math.h>  
 3     #include<algorithm>  
 4     using namespace std;  
 5     const int Max = 1005;  
 6       
 7     struct  
 8     {  
 9         int x, y;  
10     }isl[Max];    //  小岛的数据。  
11       
12     struct data  
13     {  
14         float sta, end;  
15     }rad[Max];    //  小岛所对应雷达的数据。  
16       
17     bool cmp(data a, data b)  
18     {  
19         if(a.end < b.end)   
20             return true;  
21         else   
22             return false;  
23     }  
24       
25     int main()  
26     {  
27         int n, d, t = 1;  
28         while(cin >> n >> d && n != 0)  
29         {  
30             int i, j, max_y = 0;  
31             for(i = 0; i < n; i ++)  
32             {  
33                 cin >> isl[i].x >> isl[i].y;  
34                 if(isl[i].y > max_y)  
35                     max_y = isl[i].y;  
36             }  
37             getchar();    
38             getchar();  //  PE了两次。  
39               
40             cout << "Case " << t ++ << ": ";  
41             if(max_y > d || d < 0)  
42             {  
43                 cout << -1 << endl;  
44                 continue;  
45             }  
46             float len;  
47             for(i = 0; i < n; i ++)  
48             {   //  求出小岛所对应雷达的可能覆盖范围。  
49                 len = sqrt(1.0 * d * d - isl[i].y * isl[i].y);  
50                 rad[i].sta = isl[i].x - len;  
51                 rad[i].end = isl[i].x + len;  
52             }  
53             sort(rad, rad + n, cmp);   //  根据rad的end值进行排序。  
54               
55             int ans = 0;  
56             bool vis[Max];  
57             memset(vis, false, sizeof(vis));  
58             for(i = 0; i < n; i ++)  
59             {   //  类似的活动选择。  
60                 if(!vis[i])  
61                 {  
62                     vis[i] = true;  
63                     for(j = 0; j < n; j ++)  
64                         if(!vis[j] && rad[j].sta <= rad[i].end)  
65                             vis[j] = true;  
66                         ans ++;  
67                 }  
68             }  
69             cout << ans << endl;  
70         }  
71         return 0;  
72     }

View Code

思路：贪心，从左到右建立雷达，要尽量多地覆盖岛屿。以岛屿为圆心，以d为半径画圆，如果画出的圆与x轴没有交点，则不能实现。存在交点的话，计算出第i个岛屿与x轴的交点坐标保存在结构体数组rad[i].sta与rad[i].end中。对结构体数组排序，按照rad[i].end进行升序排列，然后一次从左到右找雷达。对于rad[i].end为当前最右边的左坐标，对于下一个岛屿，如果rad[j].sta<ran[i].end，则不需要建立新的雷达，需要更新下一个岛屿。否则需要建立新的雷达。

noip2012 国王游戏（洛谷P1080）

poj2054 color a tree

参考：https://www.cnblogs.com/yu-chao/archive/2012/02/19/2358565.html