挑战程序设计竞赛3.3活用各种数据结构

forever97‘sblog forever97‘sblog     2022-08-21     596

关键词:

 

【Summarize】 

  1. 线性维护只能处理部分问题的时候要想到数据拆分,容斥解决问题

  2. 在不断有人被淘汰的序列问题中,查找左右第几个人是谁的时候可以考虑线段树优化

  3. 当问题结果并不同时依赖与两个维度的操作的时候,二维问题可拆分为两个一维问题分别解决

 

POJ 1990:MooFest

/*
    题目大意:给出每头奶牛的位置和至少要多少分贝的音量才能听到谈话
    现在求奶牛两两交流成功需要的距离*分贝的总和。
    题解:我们将奶牛对于需要的分贝排序,那么在计算的时候,
    每头奶牛只要计算和序列前面所有奶牛的答案即可
    那么只要维护前面所有奶牛和其距离之差的绝对值之和即可
    将其拆分为坐标小于该奶牛的坐标之和,和大于该奶牛的部分
    发现只要用线段树维护区间和和区间数的个数即可。
*/
#include <cstdio>
#include <algorithm>
#include <cstring> 
using namespace std;
const int N=20010;
int T[N*4],C[N*4],n,t,c,M;
struct data{int v,x;}p[N];
long long ans;
bool cmp(data a,data b){return a.v<b.v;}
void add(int x,int y){
    T[x+=M]+=y; C[x]++;
    for(x/=2;x;x/=2){
        T[x]=T[x<<1]+T[(x<<1)^1];
        C[x]=C[x<<1]+C[(x<<1)^1];
    }
}
void query(int x,int y){
    t=c=0;
    x+=M-1;y+=M+1; 
    while(x^y^1>0){ 
        if(~x&1)t+=T[x+1],c+=C[x+1]; 
        if(y&1)t+=T[y-1],c+=C[y-1]; 
        x>>=1;y>>=1; 
    }
}
int main(){
    for(M=1;M<N;M<<=1);
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)scanf("%d%d",&p[i].v,&p[i].x);
        sort(p+1,p+n+1,cmp);
        memset(T,0,sizeof(T));
        memset(C,0,sizeof(C));
        for(int i=1;i<=n;i++){
            query(1,p[i].x);
            ans+=1LL*p[i].v*(p[i].x*c-t);
            query(p[i].x,20000);
            ans+=1LL*p[i].v*(t-p[i].x*c);
            add(p[i].x,p[i].x);
        }printf("%lld
",ans);
    }return 0;
}

POJ 3109:Inner Vertices

/*
    题目大意:在一个棋盘上放满白子,现在把一些白子变成黑子,
    如果一个白子上下左右都有黑子,就会变成黑子,问最终黑子个数
    题解:首先我们在每列的开头和结尾做标记,之后对行线扫描,
    如果是列的开头,那么在该列中标记,如果是列的结尾,则在该列中去除标记
    那么我们只要统计行的开头到行的结尾之间夹着多少列标记,且该列下该行没有原来的黑子
    就是该行新增的黑子数量,对于总的黑子数量,可以用树状数组统计,之后容斥一下列标记即可。
*/
#include <cstdio>
#include <algorithm>
#include <utility>
#define cx first
#define cy second
using namespace std;
typedef long long LL; 
const int MAX_N=100010;
typedef pair<int,int> P;
int t,c[MAX_N],r[MAX_N],N,ys[MAX_N],d[MAX_N],vis[MAX_N];
P p[MAX_N];
bool cmp(int a,int b){return p[a].cy<p[b].cy||p[a].cy==p[b].cy&&p[a].cx<p[b].cx;}
int sum(int x){int s=0;while(x)s+=c[x],x-=(x&-x);return s;}
void add(int x,int v){while(x<=t)c[x]+=v,x+=x&-x;}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)scanf("%d%d",&p[i].cx,&p[i].cy),r[i]=i;
    sort(p,p+N); sort(r,r+N,cmp);
    ys[r[0]]=1; d[r[0]]=1;
    for(int i=1;i<N;i++){
        ys[r[i]]=ys[r[i-1]];
        if(p[r[i]].cy==p[r[i-1]].cy)continue;
        d[r[i-1]]--; d[r[i]]++;
        ys[r[i]]++;
    }LL ans=N; d[r[N-1]]--; t=ys[r[N-1]];
    for(int i=0,j=0;i<N;){
        for(j=i;j<N&&p[j].cx==p[i].cx;j++)
            if(d[j]<0){vis[ys[j]]=0;add(ys[j],-1);}
        if(ys[i]<ys[j-1]-1){
            ans+=sum(ys[j-1]-1)-sum(ys[i]);
            for(int k=i+1;k<j-1;k++)if(vis[ys[k]])ans--;
        }for(;i<j;i++)if(d[i]>0){add(ys[i],1);vis[ys[i]]=1;}
    }printf("%lld
",ans);
    return 0;
}

POJ 2155:Matrix

/*
    题目大意:要求维护两个操作,矩阵翻转和单点查询
    题解:树状数组可以处理前缀和问题,前缀之间进行容斥即可得到答案。
*/
#include <cstring>
#include <cstdio>
const int N=1010;
using namespace std;
int c[N][N],n,m,T;
char op[2];
void add(int x,int y){
    int i,j,k;
    for(i=x;i<N;i+=i&-i)
    for(j=y;j<N;j+=j&-j)
    c[i][j]^=1;
}
int sum(int x,int y){
    int i,j,ret=0;
    for(i=x;i;i-=i&-i)
    for(j=y;j;j-=j&-j)
    ret^=c[i][j];
    return ret;
}
int main(){
    scanf("%d",&T);
    for(int cas=0;cas<T;cas++){
        if(cas)puts("");
        memset(c,0,sizeof(c));
        scanf("%d%d",&n,&m);
        while(m--){
            int x,y,x1,y1;
            scanf("%s%d%d",op,&x,&y);
            if(op[0]==‘Q‘)printf("%d
",sum(x,y));
            else{
                scanf("%d%d",&x1,&y1);
                add(x,y); add(x1+1,y);
                add(x,y1+1); add(x1+1,y1+1);
            }
        }
    }return 0;
}

POJ 2886:Who Gets the Most Candies

/*
    题目大意:一些人站成一个圈,每个人手上都有一个数字,
    指定从一个人开始淘汰,每次一个人淘汰时,将手心里写着的数字x展示
    如果x是正数,则淘汰右手边第x个人,否则淘汰左手边地-x个人。
    每个人淘汰的时候将获得积分,积分的多少取决于他是第几个淘汰的,
    积分为淘汰的顺序数拥有的因子数量
    输出积分最高的人和其积分
    题解:首先,我们计算出第几个淘汰的人分数最高,那么我们只要模拟到这个人淘汰即可
    在处理中,寻找下一个人时我们可以用线段树求kth的方法求出这个人的位置,顺序处理即可。
*/
#include <cstdio>
#include <cstring> 
using namespace std;
const int N=500010;
int n,k,T[N*4],m,id,ans[N];
struct data{int val;char name[20];}p[N];
void build(int x,int l,int r){
    T[x]=r-l+1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}
int update(int key,int x,int l,int r){
    T[x]--; if(l==r)return l;
    int mid=(l+r)>>1;
    if(T[x<<1]>=key)return update(key,x<<1,l,mid);
    return update(key-T[x<<1],x<<1|1,mid+1,r);
}
void GetID(){   
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j+=i)ans[j]++;
    }int mx=ans[id=1];
    for(int i=2;i<=n;i++)if(ans[i]>mx){mx=ans[i];id=i;}
}
int main(){
    while(~scanf("%d%d",&n,&k)){
        build(1,1,n); GetID();
        for(int i=1;i<=n;i++)scanf("%s%d",p[i].name,&p[i].val);
        int mod=T[1],pos=0;
        p[0].val=0; m=id;
        while(m--){
            if(p[pos].val>0)k=((k-1+p[pos].val-1)%mod+mod)%mod+1;
            else k=((k-1+p[pos].val)%mod+mod)%mod+1;
            pos=update(k,1,1,n); mod=T[1];
        }printf("%s %d
",p[pos].name,ans[id]);
    }
}

POJ 3264:Balanced Lineup

/*
    题目大意:求区间最大值和最小值的差值
    题解:线段树维护区间极值即可。
*/
#include <cstdio>
#include <algorithm>
#include <cstring> 
#include <climits>
using namespace std;
const int N=1000010;
int T[N*4],C[N*4],n,M,m;
struct data{int v,x;}p[N];
long long ans;
bool cmp(data a,data b){return a.v<b.v;}
void add(int x,int y){
    T[x+=M]=y; C[x]=y;
    for(x/=2;x;x/=2){
        T[x]=max(T[x<<1],T[(x<<1)^1]);
        C[x]=min(C[x<<1],C[(x<<1)^1]);
    }
}
int query(int x,int y){
    int t=INT_MIN,c=INT_MAX;
    x+=M-1;y+=M+1; 
    while(x^y^1>0){ 
        if(~x&1)t=max(T[x+1],t),c=min(C[x+1],c); 
        if(y&1)t=max(T[y-1],t),c=min(C[y-1],c); 
        x>>=1;y>>=1; 
    }return t-c;
}
int main(){
    scanf("%d%d",&n,&m);
    for(M=1;M<n;M<<=1);
    for(int i=0;i<=M+n;i++)C[i]=INT_MAX,T[i]=INT_MIN;
    for(int i=1;i<=n;i++){
        int x; scanf("%d",&x);
        add(i,x); 
    }
    while(m--){
        int l,r; scanf("%d%d",&l,&r);
        printf("%d
",query(l,r));
    }return 0;
}

POJ 3368:Frequent values

/*
    题目大意:有一个有序序列,要求区间查询出现次数最多的数
    题解:维护每个区间左端点和右端点,以及左右的长度,还有区间的答案
    每次线段合并的时候,对区间数据进行合并即可。
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
struct data{int a,b,l,r,val;}T[N*4];
int num[N],n,q,l,r;
data combine(data &l,data &r){
	  data ans; 
    ans.a=l.a; ans.b=r.b;
    ans.l=l.a==r.a?l.l+r.l:l.l;
    ans.r=r.b==l.b?l.r+r.r:r.r;
    ans.val=max(l.val,r.val);
    if(l.b==r.a)ans.val=max(ans.val,l.r+r.l);
    return ans;
}
void build(int x,int l,int r){
    if(l==r){T[x]=(data){num[l],num[r],1,1,1};return;}
    int mid=(l+r)>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    T[x]=combine(T[x<<1],T[x<<1|1]);
}
data query(int L,int R,int x,int l,int r){
    if(r<L||R<l){data u;return u;}
    if(L<=l&&r<=R)return T[x];
    int mid=(l+r)>>1;
    data vl=query(L,R,x<<1,l,mid),vr=query(L,R,x<<1|1,mid+1,r);
    if(mid<L)return vr;
    if(mid>=R)return vl;
    return combine(vl,vr);
}
int main(){
    while(scanf("%d",&n)&&n){
        scanf("%d",&q);
        for(int i=1;i<=n;i++)scanf("%d",&num[i]);
        build(1,1,n);
        while(q--){
            scanf("%d%d",&l,&r);
            printf("%d
",query(l,r,1,1,n).val);
        }
    }return 0;
}

POJ 3470:Walls

/*
    题目大意:给出几面墙,均垂直于x轴或者y轴,给出一些鸟的位置(二维坐标点),
    鸟只会垂直x轴或者y轴飞行,并且会撞上最近的墙,问每面墙最后会有几只鸟撞上去。
    题解:我们将所有的二维坐标离散,对xy方向分别进行扫描线,
    以y轴方向为例,我们先从y最小的线开始扫,
    如果是墙,那么在线段树中更新其在x轴上的分布位置
    如果是鸟的坐标,那么在线段树中查找其位置,更新其答案。
    之后从y最大的开始反向扫描,更新,x方向也同理。
*/
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <climits>
using namespace std;
const int N=50010;
int n,m,wall,tot,dis[N],v[N],w[N],T[10*N],*arr;
int x[3*N],y[3*N],ry[3*N],rx[3*N],r[3*N],xs[3*N],ys[3*N],px[3*N],py[3*N];
bool cmp(int a,int b){return arr[a]<arr[b];}
void compress(int *x,int *r,int n,int *a,int *mp){
    for(int i=0;i<n;i++)r[i]=i; 
    arr=x; sort(r,r+n,cmp);
    int m=-1; a[r[0]]=++m; mp[m]=x[r[0]];
    for(int i=1;i<n;i++){
        int cur=r[i],lst=r[i-1];
        if(x[cur]==x[lst])a[cur]=m;
        else a[cur]=++m,mp[m]=x[cur];
    }
}
int query(int q,int x,int l,int r){
    if(T[x]!=-2)return T[x];
    int mid=(l+r)>>1;
    if(q<mid)return query(q,x<<1|1,l,mid);
    return query(q,x+1<<1,mid,r);
}
void update(int a,int b,int x,int l,int r,int val){
    if(r<=a||b<=l)return;
    else if(a<=l&&r<=b)T[x]=val;
    else{
        if(T[x]!=-2){
            T[x+1<<1]=T[x<<1|1]=T[x];
            T[x]=-2;
        }int mid=(l+r)>>1;
        update(a,b,x<<1|1,l,mid,val); 
        update(a,b,x+1<<1,mid,r,val);
    }
}
void scan(int k,int *ys,int *xs,int *py,int W){
    if(k<wall){
        int _k=k^1;
        if(xs[_k]>=xs[k])update(xs[k],xs[_k]+1,0,0,W,k/2); 
    }else{
        int t=query(xs[k],0,0,W);
        if(~t){
            int d=min(abs(py[ys[k]]-py[ys[t*2]]),abs(py[ys[k]]-py[ys[t*2+1]]));
            k-=wall; if(d<dis[k])dis[k]=d,v[k]=t;
        }
    }
}
void fly(int *ry,int *ys,int *xs,int *py,int W){
    T[0]=-1; for(int i=0;i<tot;i++)scan(ry[i],ys,xs,py,W);
    T[0]=-1; for(int i=tot-1;i>=0;i--)scan(ry[i],ys,xs,py,W); 
}
int main(){
    scanf("%d%d",&n,&m);
    wall=2*n; tot=wall+m;
    for(int i=0;i<tot;i++)scanf("%d%d",x+i,y+i);
    compress(x,rx,tot,xs,px);
    compress(y,ry,tot,ys,py);
    fill(dis,dis+m,INT_MAX);memset(w,0,n);
    fly(ry,ys,xs,py,xs[rx[tot-1]]+1);
    fly(rx,xs,ys,px,ys[ry[tot-1]]+1);
    for(int i=0;i<m;i++)++w[v[i]];
    for(int i=0;i<n;i++)printf("%d
",w[i]);
    return 0;
}

POJ 1201:Intervals

/*
    题目大意:告诉你一个区间至少要选定的数字的个数,给出n个区间的需求
    问最少选取几个数字可以满足所有的需求
    题解:对于区间[a,b]建立不等式Sb+1-Sa>=c,最后要求最小化Smax,
    结合基础条件Si+1-Si>=0,Si-Si+1>=-1,构造差分约束系统求最长路就是答案。
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=200010,inf=~0U>>2,M=200000;
int time[N],q[N],size,h,t,n,ed,dis[N],in[N],nxt[N],w[N],v[N],g[N],ma,mi,u,e,cost;
void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
int spfa(int S){
    for(int i=0;i<=n;i++)dis[i]=-inf,in[i]=0,time[i]=0;
    time[S]=1,dis[S]=0,in[S]=1;
    int i,x,size; q[h=t=size=1]=S;
    while(size){
        for(i=g[x=q[h]],h=(h+1)%M,size--;i!=-1;i=nxt[i])if(dis[x]+w[i]>dis[v[i]]){
            dis[v[i]]=dis[x]+w[i];
            if(!in[v[i]]){
                time[v[i]]++,t=(t+1)%M,size++,in[q[t]=v[i]]=1;
                if(time[v[i]]>n)return -1;
            }
        }in[x]=0;
    }if(dis[n]==-inf)return -2;
    return dis[n];
}
int main(){
    while(~scanf("%d",&n)){
        ed=0;memset(g,-1,sizeof(g));
        ma=-inf; mi=inf;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&u,&e,&cost);
            add(u,e+1,cost);
            ma=max(e+1,ma); mi=min(u,mi);
        }for(int i=mi;i<ma;i++)add(i,i+1,0),add(i+1,i,-1); 
        n=ma; printf("%d
",spfa(mi));
    }return 0;
}

UVA11990:”Dynamic“ Inversion

/*
    题目大意:给出一个数列,每次删去一个数,求一个数删去之前整个数列的逆序对数。
    题解:一开始可以用树状数组统计出现的逆序对数量
    对于每个删去的数,我们可以用线段树求出它在原序列中的逆序对贡献
    在线段树的每个区间有序化数据,就可以二分查找出这个数在每个区间的位置,
    这样就处理出了划分出的区间的贡献,先用答案减去这一部分
    接下来考虑已经删去部分的容斥,我们发现只要对删去部分再做一次类似的操作,
    将这一部分跟当前删去数求一次贡献就是刚才多减去的部分,将这部分的答案再加回去。
    这个可以在线段树上查找的同时用树状数组维护。
    这样子就能处理每一次的删数操作了。
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=200010;
int n,m,c[30][N],a[30][N],arr[N],id[N];
long long ans;
void add(int c[],int x,int v,int n){while(x<=n)c[x]+=v,x+=x&-x;}
int sum(int c[],int x,int n=0){int s=0;while(x>n)s+=c[x],x-=x&-x;return s;}
void build(int x,int l,int r,int d){
    int mid=(l+r)>>1;
    for(int i=l;i<=r;i++)a[d][i]=a[d-1][i],c[d][i]=0;
    if(l==r)return;
    build(x<<1,l,mid,d+1);
    build(x<<1|1,mid+1,r,d+1);
    sort(a[d]+l,a[d]+r+1);
}
int find(int L,int R,int d,int v){
    int l=L,r=R;
    while(l<r){
        int mid=(l+r)>>1;
        if(a[d][mid]>=v)r=mid;
        else l=mid+1;
    }if(a[d][l]>v)l--;
    return l;
}
void query(int x,int l,int r,int L,int R,int v,int d,int f){
    int mid=(l+r)>>1;
    if(L<=l&&r<=R){
        int k=find(l,r,d,v),t=sum(c[d],k,l-1);
        if(!f){k=r-k;t=sum(c[d],r,l-1)-t;}
        else k-=l-1;
        ans-=k-t; return;
    }if(l>=r)return;
    if(L<=mid)query(x<<1,l,mid,L,R,v,d+1,f);
    if(R>mid)query(x<<1|1,mid+1,r,L,R,v,d+1,f);
}
void update(int x,int l,int r,int s,int v,int d){
    int mid=(l+r)>>1;
    if(l==r){add(c[d],l,1,r);return;}
    if(l>=r)return;
    if(s<=mid)update(x<<1,l,mid,s,v,d+1);
    else update(x<<1|1,mid+1,r,s,v,d+1);
    int k=find(l,r,d,v);
    add(c[d],k,1,r);
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        ans=0; memset(arr,0,sizeof(arr));
        for(int i=1;i<=n;i++){
            scanf("%d",&a[0][i]); id[a[0][i]]=i;
            ans+=i-1-sum(arr,a[0][i]);
            add(arr,a[0][i],1,n);
        }build(1,1,n,1);
        while(m--){
            int k;
            scanf("%d",&k);
            printf("%lld
",ans);
            if(ans){
                query(1,1,n,1,id[k]-1,k,1,0);
                query(1,1,n,id[k]+1,n,k,1,1);
                update(1,1,n,id[k],k,1);
            }
        }
    }return 0;
}

挑战程序设计竞赛(算法和数据结构)——3.6希尔排序的java实现

题目&思路:代码:importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Scanner;publicclassShellSortpublicstaticlongcnt;publicstaticintA[]=newint[1000000];publicstaticintn;publ 查看详情

挑战程序设计竞赛(算法和数据结构)——4.5java中对应c++stl的数据结构类

查看详情

挑战程序设计竞赛(算法和数据结构)——3.6希尔排序的java实现(代码片段)

题目&思路:代码:importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Scanner;publicclassShellSortpublicstaticlongcnt;publicstaticintA[]=newint[1000000];publicstaticintn;publ 查看详情

挑战程序设计竞赛(算法和数据结构)——7.7最小成本排序的java实现(代码片段)

题目&思路:代码:importjava.util.*;publicclassMinimumCostSortpublicstaticfinalintMAX=1000;publicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();in 查看详情

挑战程序设计竞赛2.4加工并存储数据的数据结构

 【Summarize】  1.求满足条件的情况下最大化中位数可以枚举中位数再验证条件  2.对于种类并查集,可以利用拆点的方式,用x-A表示x属于A类,将种类归属关系作为节点进行运算 POJ3614:Sunscreen/*每个奶牛各自能够忍受... 查看详情

挑战程序设计竞赛(算法和数据结构)——17.4最大正方形的java实现(代码片段)

题目&思路:代码:importjava.util.Scanner;publicclassLargestSquarepublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intH=cin.nextInt();intW=cin.nextInt();intmap[] 查看详情

挑战程序设计竞赛(算法和数据结构)——5.4散列法习题java代码实现(代码片段)

题目:散列法相关的代码可以参考之前一篇博文https://blog.csdn.net/weixin_42887138/article/details/121254659importjava.lang.ref.PhantomReference;importjava.util.Scanner;publicclass_5_4publicstaticvoidmain(String[]arg 查看详情

挑战程序设计竞赛(算法和数据结构)——5.5迭代器和二分查找的java实现(代码片段)

迭代器代码:importjava.util.Arrays;importjava.util.Iterator;publicclassIteratorDemopublicstaticvoidmain(String[]args)int[]arr=newint[]1,2,3,4,5,6,7,8,9,8,2,6,5,7,1,3,4,5,6;Iterator<Integer 查看详情

挑战程序设计竞赛(算法和数据结构)——4.6数据结构的应用——计算面积java代码实现(代码片段)

题目:代码及实现思路如下:importjava.io.BufferedInputStream;importjava.util.Scanner;importjava.util.Stack;importjava.util.Vector;publicclass_4_6publicstaticvoidmain(String[]args)/*设计两个栈,S1和S 查看详情

《挑战程序设计竞赛》学习笔记

2.2贪心法贪心法是遵循某种规则,不断贪心选取当前最优策略的算法设计方法。贪心法的求解思想是通过迭代地选取当前问题的局部最优解法来达成总体最优解,在迭代的过程中不断地产生局部最优解和下一个与之前问题同构的... 查看详情

38天刷完挑战程序设计竞赛&数论概论计划

...er6线性方程与最大公因数的习题时,粗略地翻了一下挑战程序设计竞赛,感觉相见恨晚;遂决定38天刷完挑战程序设计竞赛和数论概论。时间:2017年12月7日00:00:00--2018年1月15日00:00:00目前进度:数论概论完成前6章,挑战程序设计... 查看详情

挑战程序设计竞赛(算法和数据结构)——4.4链表习题的java实现(代码片段)

链表有初始化、插入元素、删除元素、查找元素等方法。在创建链表的过程中,最关键的是搞清楚链表的几个关键数据构成:链表由一个个节点互相串联构成,节点作为一个基础的对象,可由类Node(随便取个... 查看详情

挑战程序设计竞赛(算法和数据结构)——4.3队列习题的java实现(代码片段)

题目:基本思路:将任务定义为一个包含名称和时间的Task类,定义一个Task类型的队列,并循环下列算法:用时间sum_time来记录处理情况,只要队列不为空,就不断执行当处理一个队头任务时,首先... 查看详情

挑战程序设计竞赛(算法和数据结构)——分割(下)&快速排序的java实现(代码片段)

在《挑战程序设计竞赛(算法和数据结构)——7.2分割(上)JAVA实现》中实现了将任一数组的元素以最后一个元素为界,小的排在前,大的排在后的功能,参照以下链接:https://blog.csdn.net/weixin_42887... 查看详情

挑战程序设计竞赛(第2版)的目录

参考技术A《挑战程序设计竞赛(第2版)》第1章 蓄势待发——准备篇 1  1.1 何谓程序设计竞赛 2  1.2 最负盛名的程序设计竞赛 5  1.2.1 世界规模的大赛——googlecodejam(gcj) 5  1.2.2 向高排名看齐!——topcoder... 查看详情

挑战程序设计竞赛(算法和数据结构)——12.2图的表示java实现(代码片段)

题目:importjava.util.Scanner;publicclassGraphImplementpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();//建立图的邻接矩阵intM[][]=newint[n][n];for(inti=0;i<n;i++)intid=cin.nextInt();intdegree=cin.nextInt();for(i... 查看详情

挑战程序设计竞赛(算法和数据结构)——7.2分割(上)java实现(代码片段)

题目:思路:示例1:示例2:代码如下:importjava.io.BufferedInputStream;importjava.util.Scanner;publicclassPartitionpublicstaticvoidmain(String[]args)Scannercin=newScanner(newBufferedInputStream(System.in));intn=cin.nextInt();int[]A=newint[n];for(inti=... 查看详情

挑战程序设计竞赛(算法和数据结构)——12.5连通分量的java实现(代码片段)

题目:讲解:注意:定义了一个Vector类型的数组,不仅需要初始化Vector类型的数组,还需初始化每一个Vector类型的容器。否则会出现以下异常:Exceptioninthread“main”java.lang.NullPointerException:Cannotinvoke“java.uti... 查看详情