欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018中国大学生程序设计竞赛 - 网络选拔赛

程序员文章站 2022-03-13 10:47:05
...

1001.Buy and Resell

2018中国大学生程序设计竞赛 - 网络选拔赛

2018中国大学生程序设计竞赛 - 网络选拔赛

思路:贪心,以前见过不少类型的,队友做的,直接上代码了;

代码:

#include<bits/stdc++.h>
using namespace std;
struct sell
{
    long long int  val;
    bool operator<(const sell &aa)const
    {
        return val<aa.val;
    }
};
multiset<sell>Sell,REsell;
multiset<sell>::iterator it,itt;
long long int ans,num;
int main()
{
    long long t,i,j,n,x,now,next;
    sell tt;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        Sell.clear();
        REsell.clear();
        ans=num=0;
        for(i=0;i<n;i++)
        {
            scanf("%lld",&x);

            if(REsell.size()!=0){
                it=REsell.begin();
                now=(*it).val;
                //NOw=REsell.top().val;
                if(Sell.size()!=0)
                    itt=Sell.begin();
                if(now<x&&Sell.size()!=0&&(*itt).val<now)
                {
                    num++;
                    ans+=x;
                    tt.val=x;
                    REsell.insert(tt);
                    Sell.erase(itt);
                    //printf("1ans=%lld num=%lld\n",ans,num);
                }
                else
                if(now<x)
                {
                    REsell.erase(it);
                    tt.val=now;
                    Sell.insert(tt);
                    ans-=2*now;
                    ans+=x;
                    tt.val=x;
                    REsell.insert(tt);
                    //printf("2ans=%lld num=%lld\n",ans,num);
                }
                else
                if(Sell.size()!=0&&(*itt).val<x)
                {
                    num++;
                    tt.val=x;
                    REsell.insert(tt);
                    ans+=x;
                    Sell.erase(itt);
                }
                else
                {
                    tt.val=x;
                    Sell.insert(tt);
                    ans-=x;
                    //printf("5ans=%lld num=%lld\n",ans,num);
                }
            }
            else
            {
                it=Sell.begin();
                if(Sell.size()!=0&&(*it).val<x)
                {
                    itt=Sell.begin();
                    num++;
                    ans+=x;
                    tt.val=x;
                    REsell.insert(tt);
                    Sell.erase(itt);
                    //printf("3ans=%lld num=%lld\n",ans,num);
                }
                else
                {
                    tt.val=x;
                    Sell.insert(tt);
                    ans-=x;
                    //printf("4ans=%lld num=%lld\n",ans,num);
                }
            }
        }
        while(!Sell.empty())
        {
            it=Sell.begin();
            ans+=(*it).val;
            Sell.erase(it);
        }
        printf("%lld %lld\n",ans,num*2);
    }
}

 

1003.Dream

2018中国大学生程序设计竞赛 - 网络选拔赛

2018中国大学生程序设计竞赛 - 网络选拔赛

 

思路:题解是费马小定理。。很优秀,但是自己推也能推出来,,因为等式左右两边都有加法操作,所以让加法矩阵全部为0 即可,然后又有p次方,保证0*0=0和1*0=0即刻,其他位置随意填,均可满足等式,但是题意还有要求,要存在q使得题意所述的两个集合相等,所以随意设定一个q(1<=q<=n-1),设定使其满足题意即可,最后就是某一列里有1--n-1个数字即可,我的是让q=1

代码:

#include<iostream>
#include<cstdio>
using namespace std;
int T,p;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&p);
        for(int i=0;i<p;i++)
        {
            printf("0");
            for(int j=1;j<p;j++)
                printf(" 0");
                printf("\n");
        }

        printf("0 0");
        for(int i=2;i<p;i++)
            printf(" 0");
        printf("\n");

        for(int i=1;i<p;i++)
        {
            if(i==p-1)
                printf("0 1");
            else
            printf("0 %d",i+1);
            for(int j=2;j<p;j++)
            {
                printf(" 1");
            }
            printf("\n");
        }
    }
}

1004.Find Integer

2018中国大学生程序设计竞赛 - 网络选拔赛

思路:数学方面的,传说中的费马大定理。。。,队友牛批

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1000000000;

int n,a,b,c;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&a);
        if(n==1)
        {
            printf("%d %d\n",1,a+1);
        }else if(n==2){
            int tn;
            if(a&1)
            {
                tn=(a-1)/2;
                b=2*tn*tn+2*tn;
                c=2*tn*tn+2*tn+1;
            }else{
                tn=a/2;
                b=tn*tn-1;
                c=tn*tn+1;
            }
            printf("%d %d\n",b,c);
        }else{
            printf("%d %d\n",-1,-1);
        }
    }
    return 0;
}

1009.Tree and Permutation

2018中国大学生程序设计竞赛 - 网络选拔赛

思路:简单图论,将每条边取出来 每次用到此边的情形是 当且仅当排列的相邻的两点分布在这条边的两边,也就是此边两边的点数的乘积,而每种情形即将这两点捆绑,有(n-1)!个排列中含有对应的情形,还有顺序,所以要乘以2,再乘上边的价值。

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define mod 1000000007
long long n,a[100005],X,Y,L,num,f[100005],ans;
long long IN[100005];
struct AA
{
    long long v,next,l,k;
}pos[200005];
int dfs(int rt,int fa)
{
    int v,numm=1;
    for(int i=f[rt];i!=-1;i=pos[i].next)
    {
        v=pos[i].v;
        if(fa==v) continue;
        pos[i].k=0;
        pos[i].k+=dfs(v,rt);
        numm+=pos[i].k;
        ans+=((((IN[n-1]*pos[i].l*2)%mod)*pos[i].k)%mod*(n-pos[i].k))%mod;
        ans%=mod;
    }
    return numm;
}
int main()
{
    IN[1]=1;
    for(int i=2;i<=100000;i++)
    {
        IN[i]=IN[i-1]*i;
        IN[i]%=mod;
    }
    while(~scanf("%lld",&n))
    {
        memset(f,-1,sizeof(f));
        num=0;
        ans=0;
        for(int i=1;i<n;i++)
        {
            scanf("%lld%lld%lld",&X,&Y,&L);
            pos[++num].v=Y;
            pos[num].next=f[X];
            pos[num].l=L;
            f[X]=num;

            pos[++num].v=X;
            pos[num].next=f[Y];
            pos[num].l=L;
            f[Y]=num;
        }
        dfs(1,-1);
        printf("%lld\n",ans);
    }
}

1010.YJJ's Salesman

思路:线段树+dp,队友做的,就是维护左上的最优状态,每次取最大值,但是队友已经A了,那就线段树吧。。这个题就贡献 了,给大佬找了两组样例。。

代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 100010
using namespace std;
long long num[maxn];
long long dp[maxn];
struct point{
    long long x;
    long long y;
    long long z;
}p[maxn];
bool cmp1(point a,point b){
    if (a.x<b.x)return 1;
    else if(a.x==b.x){
        if(a.y<b.y)return 1;
        return 0;
    }
    return 0;
}
bool cmp2(point a,point b){
    if (a.y<b.y)return 1;
    else if (a.y==b.y){
        if (a.x<b.x)return 1;
        return 0;
    }
    return 0;
}
struct xtree{
    long long l,r;
    long long maxx;
    long long mid(){
        return (l+r)/2;
    }
}tree[4*maxn];
void pushup(long long id){
    tree[id].maxx=max(tree[id*2].maxx,tree[id*2+1].maxx);
}
void build(long long id,long long l,long long r){
    tree[id].l=l;
    tree[id].r=r;
    if (l==r){
        tree[id].maxx=0;
        return ;
    }
    long long mid=tree[id].mid();
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    pushup(id);
}
void update(long long id,long long pos,long long val){
    if (tree[id].l==tree[id].r){
        tree[id].maxx=max(val,tree[id].maxx);
        return ;
    }
    long long mid=tree[id].mid();
    if (pos<=mid){
        update(id*2,pos,val);
    }
    else {
        update(id*2+1,pos,val);
    }
    pushup(id);
}
long long query(long long id,long long l,long long r){
    if (tree[id].l>=l&&tree[id].r<=r){
        return tree[id].maxx;
    }
    long long mid=tree[id].mid();
    if (r<=mid){
        return query(id*2,l,r);
    }
    else if (l>mid){
        return query(id*2+1,l,r);
    }
    else {
        return max(query(id*2,l,mid),query(id*2+1,mid+1,r));
    }
}
int main(){
    long long t;
    long long n;
    long long i,j;
    scanf("%lld",&t);
    while (t--){
        scanf("%lld",&n);
        queue<long long>qq;
        for (i=1;i<=n;i++)scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].z);
        sort (p+1,p+n+1,cmp2);
        num[p[1].y]=1;
        for (i=2;i<=n;i++){
            if (p[i].y!=p[i-1].y){
                num[p[i].y]=num[p[i-1].y]+1;
            }
        }
        build(1,1,num[p[n].y]);
        sort (p+1,p+n+1,cmp1);
        long long maxx=0;
        p[0].x=0;
        p[0].y=0;
        p[0].z=0;
        long long temp=0;
        for (i=1;i<=n;i++){
            if (p[i].x!=p[i-1].x){
                while (!qq.empty()){
                    long long fuck=qq.front();
                    qq.pop();
                    update(1,num[p[fuck].y],dp[fuck]);
                }
                if (num[p[i].y]!=1){
                    dp[i]=p[i].z+query(1,1,num[p[i].y]-1);
                }
                else {
                    dp[i]=p[i].z;
                }
                qq.push(i);
            }
            else {
                if (num[p[i].y]!=1){
                    dp[i]=p[i].z+query(1,1,num[p[i].y]-1);
                }
                else {
                    dp[i]=p[i].z;
                }
                qq.push(i);
            }
            if (dp[i]>maxx)maxx=dp[i];
        }
        printf("%lld\n",maxx);
    }
}