2018中国大学生程序设计竞赛 - 网络选拔赛（部分）（补题）

1001

可反悔的贪心

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;

int main(){

    priority_queue<P,vector<P>,greater<P> > que;
    int T;
    scanf("%d",&T);
    while(T--){

        int n;
        while(!que.empty()) que.pop();
        scanf("%d",&n);
        long long Max=0;
        int cnt=0;
        for(int i=1;i<=n;i++){

            int val;
            scanf("%d",&val);
            if(!que.empty() && que.top().first<val){

                cnt++;
                P p=que.top();
                que.pop();
                Max+=val-p.first;
                if(p.second==1) cnt--;
                else cnt++;
                que.push(P(val,1));//反悔操作 
                que.push(P(val,2));//反悔后可以买
            }
            else que.push(P(val,2));//可以买
        }
        printf("%lld %d\n",Max,cnt);
    }
} 

1003

读懂题就ok了

#include<bits/stdc++.h>
using namespace std;

int main(){

    int T;
    scanf("%d",&T);
    while(T--){

        int p;
        scanf("%d",&p);
        for(int i=1;i<=p;i++) for(int j=1;j<=p;j++) printf("%d%c",(i+j-2)%p,j==p?'\n':' ');
        for(int i=1;i<=p;i++) for(int j=1;j<=p;j++) printf("%d%c",(i-1)*(j-1)%p,j==p?'\n':' ');
    }
} 

1004

费马大定理

1）当a为大于1的奇数2n+1时，b=2n^2+2n, c=2n^2 +2n+1（2）当a为大于4的偶数2n时，b=n^2-1, c=n^2+1

#include<bits/stdc++.h>
using namespace std;

int main(){

    int T;
    scanf("%d",&T);
    while(T--){

        int n,a;
        scanf("%d%d",&n,&a);
        if(n==0 || n>2) printf("-1 -1\n");
        else{

            if(n==1) printf("%d %d\n",a,2*a);
            else{

                if(a%2){ //c%2!=b%2

                    int c=(a*a+1)/2;
                    int b=c-1;
                    printf("%d %d\n",b,c);
                }
                else{ //c%2==b%2

                    int c=a*a/4+1;
                    int b=c-2;
                    printf("%d %d\n",b,c);

                }
            }
        }
    }
} 

1009

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn=100000+100;
const LL mod=1e9+7;

struct Edge{

    int to,next,len;
}edge[maxn<<1];
int head[maxn],son[maxn],tot;
LL sum;
int n;

void DFS(int u,int fa){

    son[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next){

        Edge e=edge[i];
        int v=e.to;
        if(v==fa) continue;
        DFS(v,u);
        son[u]+=son[v]; 
        sum=(sum+2LL*son[v]*(n-son[v])%mod*e.len%mod)%mod;
    }
}

int main(){

    while(scanf("%d",&n)==1){

        for(int i=1;i<=n;i++) head[i]=-1;
        tot=0;
        for(int i=1;i<n;i++){

            int u,v,len;
            scanf("%d%d%d",&u,&v,&len);
            edge[tot].to=v;
            edge[tot].len=len;
            edge[tot].next=head[u];
            head[u]=tot++;
            edge[tot].to=u;
            edge[tot].len=len;
            edge[tot].next=head[v];
            head[v]=tot++;
        }
        sum=0;
        DFS(1,-1);
        for(int i=2;i<n;i++) sum=sum*i%mod;
        printf("%lld\n",sum);
    }
} 

1010

#include<bits/stdc++.h>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ls rt<<1
#define rs rt<<1|1
const int maxn=100000+100;

struct Node{

    int x,y,w;
}node[maxn];
int tree[maxn<<2],indx[maxn],dp[maxn];

inline bool cmp(Node a,Node b){

    if(a.y==b.y) return a.x>b.x;
    return a.y<b.y;
}

void update(int rt,int l,int r,int ind,int v){

    if(l==r){

        tree[rt]=max(tree[rt],v);
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=ind) update(lson,ind,v);
    else update(rson,ind,v);
    tree[rt]=max(tree[ls],tree[rs]); 
}

int query(int rt,int l,int r,int L,int R){

    if(L<=l && R>=r) return tree[rt];
    int mid=(l+r)>>1;
    if(mid>=R) return query(lson,L,R);
    else if(mid<L) return query(rson,L,R);
    else return max(query(lson,L,R),query(rson,L,R));
}

int main(){

    int T;
    scanf("%d",&T);
    while(T--){

        memset(tree,0,sizeof(tree));
        memset(dp,0,sizeof(dp)); 
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].w),indx[i]=node[i].x;
        sort(node+1,node+1+n,cmp);
        sort(indx+1,indx+1+n);
        int len=unique(indx+1,indx+1+n)-(indx+1);
        int Max=0;
        for(int i=1;i<=n;i++){

            int ind=lower_bound(indx+1,indx+1+len,node[i].x)-indx;
            dp[i]=node[i].w+((ind-1<1)?0:query(1,1,n,1,ind-1));
            update(1,1,n,ind,dp[i]);
            Max=max(Max,dp[i]);
        }
        printf("%d\n",Max); 
    }
}