解题手记,UESTC暑前集中练习数据结构专项论题解题报告

Training address:
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38966#overview

A.Islands

 

这种联通块的主题素材大器晚成看就通晓是并查集的思维。

A.Count Color — POJ 2777

做法:从高水位到低水位依序进行操作,那样每一回都有新的块浮出水面,能够在前边的底子上进行合併集结的操作。
给各样地点分配叁个数字,方便合併群集。相同的时间将那几个数字也排二个序,收缩枚举的复杂度。合併集适合时宜向周边查询浮出水面可是从未统大器晚成到平等会集的点开展合併。

那题初看不佳出手,再考虑,T<=30,这个时候想到颜色能够用二进制来表示,然后父节点颜色类别为子节点的按位或得出的结果中成为二进制时1的个数,然后正是无脑线段树了。。

代码:

 

爱博体育app 1爱博体育app 2

爱博体育app,代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1007

struct node
{
    int x,y,h;
}p[N*N];

int a[N*N],sh[100005],cnt[100005],fa[N*N];
int n,m;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int cmp(node ka,node kb)
{
    return ka.h < kb.h;
}

int findset(int x)
{
    if(x != fa[x])
        fa[x] = findset(fa[x]);
    return fa[x];
}

inline int ok(int x,int y)
{
    if(x < n && x >= 0 && y < m && y >= 0)
        return 1;
    return 0;
}

int main()
{
    int t,i,j,k,q,ind,pos;
    scanf("%d",&t);
    while(t--)
    {
        memset(cnt,0,sizeof(cnt));
        scanf("%d%d",&n,&m);
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                pos = i*m+j;
                fa[pos] = pos;
                scanf("%d",&a[pos]);
                p[pos].x = i,p[pos].y = j,p[pos].h = a[pos];
            }
        }
        scanf("%d",&q);
        for(i=0;i<q;i++)
            scanf("%d",&sh[i]);
        sort(p,p+n*m,cmp);
        i = n*m-1;
        for(j=q-1;j>=0;j--)
        {
            cnt[j] = cnt[j+1];
            while(sh[j] < p[i].h)  //浮出水面
            {
                cnt[j]++;
                ind = p[i].x*m+p[i].y;
                int fx = findset(ind);
                for(k=0;k<4;k++)
                {
                    int tx = p[i].x + dx[k];
                    int ty = p[i].y + dy[k];
                    if(!ok(tx,ty))
                        continue;
                    int newind = tx*m+ty;
                    int fy = findset(newind);
                    if(fx != fy && sh[j] < a[newind]) //浮出水面且没有合并
                    {
                        fa[fy] = fx;   //不能使fa[fx] = fy.因为本次fx不会再findset.
                        cnt[j]--;
                    }
                }
                i--;
            }
        }
        for(i=0;i<q;i++)
            printf("%d ",cnt[i]);
        printf("\n");
    }
    return 0;
}

爱博体育app 3爱博体育app 4

View Code

#include <iostream>
#include <cstdio>
#include <utility>
#include <cstdlib>
using namespace std;
#define N 100010

struct node
{
    int mark;
    int sum;
}tree[4*N];

void pushup(int rt)
{
    tree[rt].sum = tree[2*rt].sum | tree[2*rt+1].sum;
}

void build(int l,int r,int rt)
{
    tree[rt].sum = 1;
    tree[rt].mark = 1;
    if(l == r)
        return;
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
    pushup(rt);
}

void pushdown(int l,int r,int rt)
{
    if(!tree[rt].mark)
        return;
    if(tree[rt].mark)
    {
        tree[2*rt].sum = tree[2*rt+1].sum = tree[rt].sum;
        tree[2*rt].mark = tree[2*rt+1].mark = tree[rt].mark;
        tree[rt].mark = 0;
    }
}

void make(int l,int r,int aa,int bb,int co,int rt)
{
    if(aa<=l && bb>=r)
    {
        tree[rt].mark = 1;
        tree[rt].sum = 1<<(co-1);
        return;
    }
    pushdown(l,r,rt);
    int mid = (l+r)/2;
    if(aa<=mid)
        make(l,mid,aa,bb,co,2*rt);
    if(bb>mid)
        make(mid+1,r,aa,bb,co,2*rt+1);
    pushup(rt);
}

int query(int l,int r,int aa,int bb,int rt)
{
    if(aa>r||bb<l)
        return 0;
    if(aa<=l&&bb>=r)
    {
        return tree[rt].sum;
    }
    pushdown(l,r,rt);
    int mid = (l+r)/2;
    return query(l,mid,aa,bb,2*rt)|query(mid+1,r,aa,bb,2*rt+1);
}

int main()
{
    int n,t,o;
    int i;
    int aa,bb,co;
    char ss[5];
    scanf("%d%d%d",&n,&t,&o);
    build(1,n,1);
    int cnt;
    for(i=0;i<o;i++)
    {
        scanf("%s",ss);
        if(ss[0] == 'C')
        {
            scanf("%d%d%d",&aa,&bb,&co);
            make(1,n,aa,bb,co,1);
        }
        else if(ss[0] == 'P')
        {
            scanf("%d%d",&aa,&bb);
            int res;
            if(aa<=bb)
                res = query(1,n,aa,bb,1);
            else
                res = query(1,n,bb,aa,1);
            cnt = 0;
            while(res)
            {
                if(res&1)
                    cnt++;
                res>>=1;
            }
            printf("%d\n",cnt);
        }
    }
    return 0;
}

 

View Code

B.母仪天下

 

线段树单点更新,区间查询。模板题,不解释。不会做表达您线段树很水。。

B.Who Gets the Most Candies — POJ 2886

代码:

(题解借鉴: ahfywff卡塔 尔(阿拉伯语:قطر‎

爱博体育app 5爱博体育app 6

   
本题利用反素数的概念。反素数的定义:对于任何正整数x,其约数的个数记做f(x)。举个例子f(1)=1,f(6)=4。假使有个别正整数x满意:对于率性i(0<i<x),都有f(i)<f(x),则称x为反素数。对于核心,设pos为不高于N的反素数,则第pos个出圈的子女得到的糖果最多,为pos的约数个数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
#define INF 1000000007
#define INT 2147483647
#define lll __int64
#define ll long long
using namespace std;
#define N 100007

struct node
{
    ll sum;
}tree[4*N];

void pushup(int rt)
{
    tree[rt].sum = tree[2*rt].sum + tree[2*rt+1].sum;
}

void build(int l,int r,int rt)
{
    if(l == r)
    {
        scanf("%lld",&tree[rt].sum);
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
    pushup(rt);
}

void update(int l,int r,int pos,ll val,int rt)
{
    if(l == r)
    {
        tree[rt].sum += val;
        return;
    }
    int mid = (l+r)/2;
    if(pos <= mid)
        update(l,mid,pos,val,2*rt);
    else
        update(mid+1,r,pos,val,2*rt+1);
    pushup(rt);
}

ll query(int l,int r,int aa,int bb,int rt)
{
    if(aa <= l && bb >= r)
        return tree[rt].sum;
    int mid = (l+r)/2;
    ll res = 0;
    if(aa <= mid)
        res += query(l,mid,aa,bb,2*rt);
    if(bb > mid)
        res += query(mid+1,r,aa,bb,2*rt+1);
    return res;
}

int main()
{
    int m,n,aa,bb;
    int i,pos;
    ll val;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        build(1,n,1);
        while(m--)
        {
            scanf("%d",&i);
            if(i == 0)
            {
                scanf("%d%d",&aa,&bb);
                printf("%lld\n",query(1,n,aa,bb,1));
            }
            else
            {
                scanf("%d%lld",&pos,&val);
                update(1,n,pos,val,1);
            }
        }
    }
    return 0;
}

  
出圈进度有一点点雷同约瑟夫环。借使当前出圈的是多余孩子中的第K个,他手中的数字为A。

View Code

    若A大于零,下叁个出圈的就相应是多余孩子中的第(K-1+A-1)%n+1个;

 

    若A小于零,下贰个出圈的就相应是剩下孩子中的第((K-1+A)%n+n)%n+1个。

C.东风不与周瑜便

   
难题的根本是怎么着求得出圈孩子的庐山真面目目地点,线段树的各样节点的sum存款和储蓄了所在区间还会有多少孩子留住,查询节点rt中第num个子女的原来地方时,纵然num<=st[2*rt].sum,则在左孩子节点中询问第num个儿女的本来地方;不然在右孩子节点中查询第num-st[2*rt].sum个儿女的固有地点。

线段树区间更新,区间查询。也是模板题,比B题较难,可是也是学线段树一定要会的。

 

代码:

  代码:

爱博体育app 7爱博体育app 8

爱博体育app 9爱博体育app 10

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define Mod 1000000007
#define INF 1000000007
#define INT 2147483647
#define lll __int64
#define ll long long
using namespace std;
#define N 100007

struct node
{
    ll sum;
    ll mark;
}tree[4*N];

void pushup(int rt)
{
    tree[rt].sum = tree[2*rt].sum + tree[2*rt+1].sum;
}

void pushdown(int l,int r,int rt)
{
    if(!tree[rt].mark)
        return;
    int mid = (l+r)/2;
    tree[2*rt].sum += tree[rt].mark*(ll)(mid-l+1);
    tree[2*rt+1].sum += tree[rt].mark*(ll)(r-mid);
    tree[2*rt].mark += tree[rt].mark;
    tree[2*rt+1].mark += tree[rt].mark;
    tree[rt].mark = 0;
}

void build(int l,int r,int rt)
{
    if(l == r)
    {
        scanf("%lld",&tree[rt].sum);
        tree[rt].mark = 0;
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
    pushup(rt);
}

void update(int l,int r,int aa,int bb,ll val,int rt)
{
    if(aa <= l && bb >= r)
    {
        tree[rt].sum += val*(ll)(r-l+1);
        tree[rt].mark += val;
        return;
    }
    pushdown(l,r,rt);
    int mid = (l+r)/2;
    if(aa <= mid)
        update(l,mid,aa,bb,val,2*rt);
    if(bb > mid)
        update(mid+1,r,aa,bb,val,2*rt+1);
    pushup(rt);
}

ll query(int l,int r,int aa,int bb,int rt)
{
    if(aa <= l && bb >= r)
        return tree[rt].sum;
    pushdown(l,r,rt);
    int mid = (l+r)/2;
    ll res = 0;
    if(aa <= mid)
        res += query(l,mid,aa,bb,2*rt);
    if(bb > mid)
        res += query(mid+1,r,aa,bb,2*rt+1);
    return res;
}

int main()
{
    int m,n,aa,bb;
    int i;
    ll val;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(tree,0,sizeof(tree));
        build(1,n,1);
        while(m--)
        {
            scanf("%d",&i);
            if(i == 0)
            {
                scanf("%d%d",&aa,&bb);
                printf("%lld\n",query(1,n,aa,bb,1));
            }
            else
            {
                scanf("%d%d%lld",&aa,&bb,&val);
                update(1,n,aa,bb,val,1);
            }
        }
    }
    return 0;
}
/*12152 KB    1079 ms*/
#include <iostream>
#include <cstdio>
using namespace std;
#define N 500010

int anti[37]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,
           55440,83160,110880,166320,221760,277200,332640,498960,500001};
int factor[37]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,160,168,180,192,200,1314521};

int tree[4*N];
char name[N][11];
int num[N];

void build(int l,int r,int rt)
{
    tree[rt] = r-l+1;
    if(l == r)
        return;
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
}

int query(int l,int r,int pos,int rt)
{
    tree[rt]--;
    if(l == r)
        return l;
    int mid = (l+r)/2;
    if(pos<=tree[2*rt])
        return query(l,mid,pos,2*rt);
    else
        return query(mid+1,r,pos-tree[2*rt],2*rt+1);
}

int main()
{
    int n,k,pos,Maxcandy,i;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        i=0;
        int CN = n;
        while(anti[i]<=n)
            i++;
        pos = anti[i-1];
        Maxcandy = factor[i-1];
        build(1,n,1);
        for(i=1;i<=n;i++)
        {
            scanf("%s %d",name[i],&num[i]);
        }
        int flag;
        for(i=1;i<=pos;i++)
        {
            n--;
            flag = query(1,CN,k,1);
            if(n==0)
                break;
            if(num[flag]>0)
                k = (k + num[flag] - 2)%n + 1;
            else
                k = ((k + num[flag] - 1)%n+n)%n + 1;
        }
        printf("%s %d\n",name[flag],Maxcandy);
    }
}

View Code

View Code

 

 

D.长使大侠泪满襟

G.Fast Matrix Operations —UVA 11992

那题是原题,参照他事他说加以考查POJ 2482 Stars In Your Window

  那题其实也不太难搞,关键是各个地区面要维护到,笔者写了七个多钟头啊,最终照旧稍稍地点未有照见到,哎,太弱咯。。认为本身在维护值方面还差相当少时机。
那题看行数不超过20,想到在每黄金时代行都建黄金时代颗线段树,然后就搞吧。。代码有一点长,将就着看吗。

 

(A.M : Attention to Maintain)

E.休生伤杜景死惊开

 

即用线段树求逆序数。(或树状数组卡塔 尔(英语:State of Qatar)
求出每一个数字前边比她小的数字个数以至前边比他大的个数,然后相乘求和即为总的以那一个数字为基本的锁的个数。
这边用线段树来落到实处求逆序数,分别以前方和前面实行查找,查找1~a[i]-1的数的个数。以早前以后查为例,因为是即插即查,所以那时区间内数的个数正是在数组前边比她小的数的个数。从后往前查同理。

代码:

代码:

爱博体育app 11爱博体育app 12

爱博体育app 13爱博体育app 14

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#include <cstdlib>
#define Mod 1000000007
using namespace std;
#define N 1000010

struct node
{
    int mini,maxi,sum;
    int addmark,setmark;
}tree[21][4*N];

int i;

void pushup(int i,int rt)
{
    tree[i][rt].sum = tree[i][2*rt].sum + tree[i][2*rt+1].sum;
    tree[i][rt].mini = min(tree[i][2*rt].mini,tree[i][2*rt+1].mini);
    tree[i][rt].maxi = max(tree[i][2*rt].maxi,tree[i][2*rt+1].maxi);
}

void build(int i,int l,int r,int rt)
{
    tree[i][rt].sum = tree[i][rt].mini = tree[i][rt].maxi = 0;
    tree[i][rt].setmark = -1;
    tree[i][rt].addmark = 0;
    if(l == r)
        return;
    int mid = (l+r)/2;
    build(i,l,mid,2*rt);
    build(i,mid+1,r,2*rt+1);
    pushup(i,rt);
}

void pushdown(int i,int l,int r,int rt)
{
    if(tree[i][rt].setmark == -1 && tree[i][rt].addmark == 0)
        return;
    int mid = (l+r)/2;
    if(tree[i][rt].setmark >= 0)
    {
        tree[i][2*rt].sum = tree[i][rt].setmark*(mid-l+1);
        tree[i][2*rt+1].sum = tree[i][rt].setmark*(r-mid);
        tree[i][2*rt].mini = tree[i][2*rt+1].mini = tree[i][rt].setmark;  //A.M 
        tree[i][2*rt].maxi = tree[i][2*rt+1].maxi = tree[i][rt].setmark;  //A.M
        tree[i][2*rt].addmark = tree[i][2*rt+1].addmark = 0;  // 这个要写 
        tree[i][2*rt].setmark = tree[i][2*rt+1].setmark = tree[i][rt].setmark;
        tree[i][rt].setmark = -1;
    }
    if(tree[i][rt].addmark > 0)
    {
        tree[i][2*rt].sum += tree[i][rt].addmark*(mid-l+1);
        tree[i][2*rt+1].sum += tree[i][rt].addmark*(r-mid);
        tree[i][2*rt].maxi += tree[i][rt].addmark;  //A.M
        tree[i][2*rt].mini += tree[i][rt].addmark;  //A.M
        tree[i][2*rt+1].maxi += tree[i][rt].addmark;  //A.M
        tree[i][2*rt+1].mini += tree[i][rt].addmark;  //A.M
        tree[i][2*rt].addmark += tree[i][rt].addmark;
        tree[i][2*rt+1].addmark += tree[i][rt].addmark;
        tree[i][rt].addmark = 0;
    }
}

void add(int l,int r,int aa,int bb,int val,int rt)
{
    if(aa>r||bb<l)
        return;
    if(aa<=l&&bb>=r)
    {
        tree[i][rt].addmark += val;
                                   //tree[i][rt].setmark = -1;  --不要写这个 
        tree[i][rt].sum += (r-l+1)*val;
        tree[i][rt].maxi += val;
        tree[i][rt].mini += val;
        return;
    }
    pushdown(i,l,r,rt);
    int mid = (l+r)/2;
    if(aa<=mid)
        add(l,mid,aa,bb,val,2*rt);
    if(bb>mid)
        add(mid+1,r,aa,bb,val,2*rt+1);
    pushup(i,rt);
}

void setval(int l,int r,int aa,int bb,int val,int rt)
{
    if(aa>r||bb<l)
        return;
    if(aa<=l&&bb>=r)
    {
        tree[i][rt].setmark = val;
        tree[i][rt].addmark = 0;
        tree[i][rt].sum = val*(r-l+1);
        tree[i][rt].maxi = tree[i][rt].mini = val;
        return;
    }
    pushdown(i,l,r,rt);
    int mid = (l+r)/2;
    if(aa<=mid)
        setval(l,mid,aa,bb,val,2*rt);
    if(bb>mid)
        setval(mid+1,r,aa,bb,val,2*rt+1);
    pushup(i,rt);
}

struct node_ans
{
    int sum;
    int mini,maxi;
};

node_ans query(int l,int r,int aa,int bb,int rt)
{
    node_ans res,ka1,ka2;
    if(aa<=l && bb>=r)
    {
        res.sum = tree[i][rt].sum;
        res.maxi = tree[i][rt].maxi;
        res.mini = tree[i][rt].mini;
        return res;
    }
    pushdown(i,l,r,rt);
    int mid = (l+r)/2;
    if(bb<=mid)
        return query(l,mid,aa,bb,2*rt);
    else if(aa>mid)
        return query(mid+1,r,aa,bb,2*rt+1);
    else
    {
        ka1 = query(l,mid,aa,bb,2*rt);
        ka2 = query(mid+1,r,aa,bb,2*rt+1);
        res.sum = ka1.sum + ka2.sum;
        res.maxi = max(ka1.maxi,ka2.maxi);
        res.mini = min(ka1.mini,ka2.mini);
        return res;
    }
}

int main()
{
    int r,c,m;
    int k,zuo;
    int x1,y1,x2,y2,val;
    int sum,mmax,mmin;
    while(scanf("%d%d%d",&r,&c,&m)!=EOF)
    {
        for(i=1;i<=r;i++)
        {
            build(i,1,c,1);
        }
        for(k=0;k<m;k++)
        {
            scanf("%d",&zuo);
            if(zuo == 1)
            {
                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);
                for(i=x1;i<=x2;i++)
                {
                    add(1,c,y1,y2,val,1);
                }
            }
            else if(zuo == 2)
            {
                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);
                for(i=x1;i<=x2;i++)
                {
                    setval(1,c,y1,y2,val,1);
                }
            }
            else 
            {
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                node_ans la;
                sum = 0;
                mmax = -Mod;
                mmin = Mod;
                for(i=x1;i<=x2;i++)
                {
                    la = query(1,c,y1,y2,1);
                    sum += la.sum;
                    mmax = max(mmax,la.maxi);
                    mmin = min(mmin,la.mini);
                }
                printf("%d %d %d\n",sum,mmin,mmax);
            }
        }
    }
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#define Mod 1000000007
#define INF 1000000007
#define INT 2147483647
#define lll __int64
#define ll long long
using namespace std;
#define N 50007

struct node
{
    ll sum;
}tree[4*N];

ll a[N],k1[N],k2[N];

void build(int l,int r,int rt)
{
    tree[rt].sum = 0;
    if(l == r)
        return;
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
}

ll query(int l,int r,int aa,int bb,int rt)
{
    if(aa > bb)
        return 0;
    if(aa <= l && bb >= r)
        return tree[rt].sum;
    int mid = (l+r)/2;
    ll res = 0;
    if(aa <= mid)
        res += query(l,mid,aa,bb,2*rt);
    if(bb > mid)
        res += query(mid+1,r,aa,bb,2*rt+1);
    return res;
}

void update(int l,int r,int pos,int rt)
{
    tree[rt].sum++;
    if(l == r)
        return;
    int mid = (l+r)/2;
    if(pos <= mid)
        update(l,mid,pos,2*rt);
    else
        update(mid+1,r,pos,2*rt+1);
}

int main()
{
    int n,i,j;
    while(scanf("%d",&n)!=EOF)
    {
        ll sum = 0;
        for(i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        build(1,n,1);
        for(i=1;i<=n;i++)
        {
            k1[i] = query(1,n,1,a[i]-1,1);
            update(1,n,a[i],1);
        }
        build(1,n,1);
        for(i=n;i>=1;i--)
        {
            k2[i] = query(1,n,1,a[i]-1,1);
            update(1,n,a[i],1);
        }
        for(i=1;i<=n;i++)
            sum += k1[i] * k2[i];
        printf("%lld\n",sum);
    }
    return 0;
}

View Code

View Code

 

 

 

F.天下归晋

树状数组能够缓解,每条船的品级即总结每条船的左下方的船只数量。

将船舶坐标由y从小到大排序,y坐标相似的依照x坐标从小到大排序。一句话来讲前面包车型大巴点要保障在前头的点的右上方,那样插入时后边的船只不会潜移默化到后面船只的品级,即日前船舶的级差鲜明。

求和时sum(x)表示x坐标值小于等于x的船只个数
下一场依照相排版序依次将船舶一个二个插入,求和,求出的和的卓殊等第的船舶数加1,最终输出。

(注意树状数组c[]数组下标只可以从1上马,所以具备坐标在处理时都加1卡塔尔国

代码:

爱博体育app 15爱博体育app 16

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 202010

struct point
{
    int x,y;
}a[N];

int n;
int c[N],ans[N];

int cmp(point ka,point kb)
{
    if(ka.y == kb.y)
        return ka.x < kb.x;
    return ka.y < kb.y;
}

int lowbit(int x)
{
    return x&(-x);
}

void modify(int num,int val)
{
    while(num<=N)
    {
        c[num] += val;
        num += lowbit(num);
    }
}

int sum(int x)
{
    int res = 0;
    while(x>0)
    {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

int main()
{
    int i,x,y;
    while(scanf("%d",&n)!=EOF)
    {
        memset(c,0,sizeof(c));
        memset(ans,0,sizeof(ans));
        for(i=0;i<n;i++)
            scanf("%d%d",&a[i].x,&a[i].y);
        sort(a,a+n,cmp);
        for(i=0;i<n;i++)
        {
            ans[sum(a[i].x+1)]++;
            modify(a[i].x+1,1);
        }
        for(i=0;i<n;i++)
        {
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}

View Code

 

G.程序设计竞技

即线段树的区间最罗安达续和难点,作者有生龙活虎篇博文讲过了。

各种节点维护4个值:
max:此区间内的最亚松森续和
sum:该节点以下的节点值得总和
lmax:此区间的从左端起头的最达累斯萨Lamb续和
rmax:此区间的从右端开始的最浦那续和
集结区间时,该间隔的最奥斯汀续和为:max(左子节点的最浦那续和,右子节点的最重庆续和,左子节点的最大右一连和+右子节点的最大左接二连三和)

询问时回来三个整节点。因为每趟要查询左子节点和右子节点,何况要相比较它们的右三回九转最大和和左一连最大和,所以须求再次来到整个节点以便求值。

代码:

爱博体育app 17爱博体育app 18

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 200007

struct node
{
    int maxi,lmaxi,rmaxi,sum;
}tree[4*N];

void pushup(int rt)
{
    tree[rt].sum = tree[2*rt].sum + tree[2*rt+1].sum;
    tree[rt].maxi = max(tree[2*rt].maxi,max(tree[2*rt+1].maxi,tree[2*rt].rmaxi+tree[2*rt+1].lmaxi));
    tree[rt].lmaxi = max(tree[2*rt].lmaxi,tree[2*rt].sum + tree[2*rt+1].lmaxi);
    tree[rt].rmaxi = max(tree[2*rt+1].rmaxi,tree[2*rt+1].sum + tree[2*rt].rmaxi);
}

void build(int l,int r,int rt)
{
    if(l == r)
    {
        scanf("%d",&tree[rt].sum);
        tree[rt].maxi = tree[rt].lmaxi = tree[rt].rmaxi = tree[rt].sum;
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
    pushup(rt);
}

void update(int l,int r,int pos,int val,int rt)
{
    if(l == r)
    {
        tree[rt].maxi = tree[rt].lmaxi = tree[rt].rmaxi = tree[rt].sum = val;
        return;
    }
    int mid = (l+r)/2;
    if(pos <= mid)
        update(l,mid,pos,val,2*rt);
    else
        update(mid+1,r,pos,val,2*rt+1);
    pushup(rt);
}

node query(int l,int r,int aa,int bb,int rt)
{
    if(aa <= l && bb >= r)
        return tree[rt];
    int mid = (l+r)/2;
    node ka,kb,res;
    int flag1 = 0;
    int flag2 = 0;
    if(aa <= mid)
    {
        ka = query(l,mid,aa,bb,2*rt);
        flag1 = 1;
    }
    if(bb > mid)
    {
        kb = query(mid+1,r,aa,bb,2*rt+1);
        flag2 = 1;
    }
    if(flag1 && flag2)
    {
        res.sum = ka.sum + kb.sum;
        res.lmaxi = max(ka.lmaxi,ka.sum+kb.lmaxi);
        res.rmaxi = max(kb.rmaxi,kb.sum+ka.rmaxi);
        res.maxi = max(ka.rmaxi+kb.lmaxi,max(ka.maxi,kb.maxi));
    }
    else
    {
        if(flag1)  //left
            res = ka;
        else
            res = kb;
    }
    return res;
}

int main()
{
    int n,m,op,aa,bb;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while(m--)
    {
        scanf("%d%d%d",&op,&aa,&bb);
        if(!op)
        {
            node res = query(1,n,aa,bb,1);
            printf("%d\n",res.maxi);
        }
        else
            update(1,n,aa,bb,1);
    }
    return 0;
}

View Code

 

H.Cookies Test

线段树解决。每便将数据插入到切合岗位,注意这里的值一点都不小,所以必要哈希,哈希过后就能够开线段树了。

遭遇查询时就询问线段树中第中位数个点(值卡塔尔国,再次回到其值,然后将该点置叁个标志,表示尚未了。同一时候更新其上的节点的sum值(子树的数(有值的叶子节点卡塔尔的个数卡塔 尔(阿拉伯语:قطر‎。

代码不太轻易懂。作者也是头一次写这种嵌套非常多层的数组的代码。
代码:

爱博体育app 19爱博体育app 20

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#define Mod 1000000007
#define INF 1000000007
#define INT 2147483647
#define lll __int64
#define ll long long
using namespace std;
#define N 600007

struct node
{
    int sum;
}tree[4*N];

struct A
{
    int ind,val;
}a[N],b[N];

int hash[N],k[N];

int cmp(A ka,A kb)
{
    return ka.val < kb.val;
}

void build(int l,int r,int rt)
{
    tree[rt].sum = 0;
    if(l == r)
        return;
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
}

int query(int l,int r,int pos,int rt)
{
    tree[rt].sum--;
    if(l == r)
        return l;
    int mid = (l+r)/2;
    if(tree[2*rt].sum >= pos)
        return query(l,mid,pos,2*rt);
    else
        return query(mid+1,r,pos-tree[2*rt].sum,2*rt+1);
}

void update(int l,int r,int pos,int rt)
{
    tree[rt].sum++;
    if(l == r)
        return;
    int mid = (l+r)/2;
    if(pos <= mid)
        update(l,mid,pos,2*rt);
    else
        update(mid+1,r,pos,2*rt+1);
}

int main()
{
    int n,i,j,m;
    char ss[14];
    i = 1;
    while(scanf("%s",ss)!=EOF)
    {
        if(ss[0] == '#')
            a[i].val = b[i].val = INF,a[i].ind = b[i].ind = i++;
        else
            a[i].val = b[i].val = atoi(ss),a[i].ind = b[i].ind = i++;
    }
    m = i-1;
    sort(b+1,b+m+1,cmp);
    int now = 1;
    int pre = -1000000000;
    for(i=1;i<=m;i++)
    {
        if(b[i].val == INF)
            continue;
        if(b[i].val != pre)
        {
            pre = b[i].val;
            b[i].val = now++;
        }
        else
            b[i].val = now-1;
        hash[b[i].val] = b[i].ind;
    }
    for(i=1;i<=m;i++)
        k[b[i].ind] = b[i].val;
    n = 600000;
    build(1,n,1);
    int cnt = 0;
    for(i=1;i<=m;i++)
    {
        if(k[i] == INF)
        {
            if(cnt%2)  //odd
                printf("%d\n",a[hash[query(1,n,(cnt+1)/2,1)]].val);
            else
                printf("%d\n",a[hash[query(1,n,cnt/2+1,1)]].val);
            cnt--;
        }
        else
        {
            update(1,n,k[i],1);
            cnt++;
        }
    }
    return 0;
}

View Code

 

I.方师傅学数字逻辑

 

J.方师傅的01串

字典树,结构node维护多少个值: count 和 deep ,结果即为节点的count * deep
的最大值。

代码:

爱博体育app 21爱博体育app 22

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 50007

struct node
{
    int count,deep;
    node *next[2];
}*root;

char ss[N];
int maxi;

node *create()
{
    node *p;
    p = (node *)malloc(sizeof(node));
    p->count = 0;
    p->deep = 0;
    for(int i=0;i<2;i++)
        p->next[i] = NULL;
    return p;
}

void release(node *p)
{
    for(int i=0;i<2;i++)
    {
        if(p->next[i] != NULL)
            release(p->next[i]);
    }
    free(p);
}

void insert(char *ss)
{
    node *p = root;
    int i = 0,k;
    while(ss[i])
    {
        k = ss[i++] - '0';
        if(p->next[k] == NULL)
            p->next[k] = create();
        p->next[k]->deep = p->deep + 1;
        p = p->next[k];
        p->count++;
        maxi = max(maxi,p->count*p->deep);
    }
}

int main()
{
    int t,n,i;
    root = create();
    scanf("%d",&n);
    maxi = -1000000;
    for(i=0;i<n;i++)
    {
        scanf("%s",ss);
        insert(ss);
    }
    cout<<maxi<<endl;
    release(root);
    return 0;
}

View Code

 

K.方师傅与栈

栈上的模拟题。
据书上说终态来定进度。
终态那时候内需现身什么样值,初始栈中将要一向找到该值,找的进程军长值都压入贰个栈中,然后将该值出栈,如此生生不息,总的来讲要依循终态的次第。
现身以下三种情状则答案是NO:
1.终态的数还未模拟完,原始数组中的数就已经全体压入栈中了。并且栈顶还不对等终态那个时候亟需的数
2.万生机勃勃最后栈不为空,表达还会有未有合营的,自然特别。

代码:

爱博体育app 23爱博体育app 24

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1000007

int a[N],want[N],stk[N];

int main()
{
    int n,i,k,top;
    scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
            scanf("%d",&want[i]);
        k = 1;
        top = 0;
        stk[0] = 0;
        int flag = 1;
        for(i=1;i<=n;i++)
        {
            while(stk[top] != want[i])
            {
                if(k <= n)
                    stk[++top] = a[k++];
                else
                {
                    flag = 0;
                    break;
                }
            }
            if(stk[top] == want[i])
                top--;
            if(!flag)
                break;
        }
        if(!flag || top)
            puts("No");
        else
            puts("Yes");
    return 0;
}

View Code

 

L.冰雪奇缘

 

M.方师傅玩炉石

 

(没做出来的未来更新卡塔 尔(英语:State of Qatar)

相关文章