2018燕山大学大学生程序设计大赛

傷城~ 2023-06-19 07:25 108阅读 0赞

### 2018燕山大学大学生程序设计大赛 ###

*   *   *  ysu小吃街
         *   *  参考代码
         *  ysu -Inner Product
         *   *  参考代码
         *  ysu-Odd
         *   *  参考代码
         *  ysu-投票
         *   *  参考代码
         *  ysu-情报
         *   *  参考代码

### ysu小吃街 ###

燕大食堂为了改善学生伙食，新开了一条小吃街。这里共有n个摊位，剁椒鱼头、水煮肉片、牛奶冻、红烧狮子头……各种各样的美食数不胜数，散发着诱人的香气。 SueJane和swoky非常开心地走进小吃街。这里有一条神奇的规定，如果能回答出所有小吃的价格，就可以获得免单的优惠。swoky贿赂了入口处卖可乐鸡翅的大妈，得知了标号为1的摊位（可乐鸡翅）的价格为a\_1。此后SueJane和swoky每走到一个摊位，都可以获得一条信息，内容为这个摊位的小吃与另外某一个摊位的差价。现在SueJane和swoky大快朵颐之后来到出口处，发现由于她们吃了太多美食，钱不够了qwq。因此，她们必须猜出所有小吃的价格来获得免单的优惠。你这位神犇能帮她们的忙吗？

输入格式:  
输入第一行为三个正整数，为n,m,a\_1，分别表示摊位个数、SueJane和swoky获得的信息条数、摊位1的价格。 接下来共有m行，每行包括三个整数x,y,z，表示x摊位的价格比y摊位贵z元钱。

输出格式:  
第一行为一个字符串，“QWQ”表示你太强了觉得这个问题非常简单，可以帮她们解决；“QAQ”表示由于SueJane和swoky太蠢了收集到了错误的信息或者没有收集全信息，你对此爱莫能助。 如果第一行输出了"QWQ"，那么接下来输出n行每行一个整数，分别表示1～n个摊位的小吃价格。

输入样例:

5 5 10
    1 2 3
    4 3 2
    1 3 2
    3 5 1
    4 5 3

输出样例:

QWQ
    10
    7
    8
    10
    7

#### 参考代码 ####

/* 根据题意将问题的关系描述为图，利用遍历来求解 这里采用bfs 在遍历的过程并判断是否上下一致 */
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long  ll;
    typedef pair<int,int> pa;
    const int MAXN=1e5+5;
    
    vector <pa> a[MAXN];
    int n , m ,b;
    bool reach[MAXN];
    int p[MAXN];
    
    bool bfs(int i){ 
        queue<int>q;
        q.push(i);
        reach[i]=true;
        int k=1;
        while(!q.empty()){ 
            int j=q.front(),len=a[j].size();
            q.pop();
            for(int i=0;i<len;i++){ 
                int f=a[j][i].first,s=a[j][i].second;
                if(p[f]&&p[j]!=p[f]+s)return  false;
                if(p[f]==0) p[f]=p[j]-s;
                if(!reach[f]){ 
                    reach[f]=true;
                    k++;
                    q.push(f);
                }
            }
        }
        if(k!=n)return false;
        return true;
    }
    
    int main()
    { 
        int v1,v2,w;
        scanf("%d%d%d",&n,&m,&b);
        p[1]=b;
        for(int i=0;i<m;i++){ 
            scanf("%d%d%d",&v1,&v2,&w);
            a[v1].emplace_back(pa(v2,w));
            a[v2].emplace_back(pa(v1,-w));
        }
        if(bfs(1)){ 
            printf("QWQ\n");
            for(int i=1;i<=n;i++)printf("%d\n",p[i]);
        } else printf("QAQ");
    }

### ysu -Inner Product ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]  
输入样例:

3
    1 2 3
    2 2 2

输出样例:

#### 参考代码 ####

/* 利用高中的排序不等式的性质可知：反序和≤乱序和≤顺序和 */
    #include <iostream>
    #include <algorithm>
    #include <stdio.h>
    using namespace std;
    
    
    void solve();
    
    int main(){ 
    	solve();
    	return 0;
    }
    
    bool cmp(int a,int b){ 
    	return a>b;
    }
    
    void solve(){ 
    	int n;
      cin>>n;
     long long a[100000],b[100000];
    	for(int i=0;i<n;i++)cin>>a[i];
    	for(int i=0;i<n;i++)cin>>b[i];
    	sort(a,a+n);
    	sort(b,b+n,cmp);
    	long long sum=0;
    	for(int i=0;i<n;i++)sum=sum+a[i]*b[i];
    	cout<<sum<<endl;
    }

### ysu-Odd ###

现在有一个长度为n的正整数序列，其中只有一种数值出现了奇数次，其他数值均出现偶数次，请你找出那个出现 奇数次的数值。

输入格式:  
第一行：一个整数n，表示序列的长度。 第二行：n个正整数ai，两个数中间以空格隔开。

输出格式:  
一个数，即在序列中唯一出现奇数次的数值。

输入样例:

5
    2 1 2 3 1

输出样例:

#### 参考代码 ####

/* 利用异或的性质 1^1=0,0^0=0,1^0=1; 可知a^a=0 a^0=a; */
    #include <iostream>
    #include<stdio.h>
    using namespace std;
    
    void solve(){ 
    	int n=0;
    	cin>>n;
    	int a=0,b;
    	for(int i=0;i<n;i++){ 
    	   scanf("%d",&b);
    	   a=a^b;
    	}
    	cout<<a<<endl;
    }
    int main(){ 
    	solve();
    	return 0;
    }

### ysu-投票 ###

“燕大要选ACM校队啦。” ABC在燕鸣湖畔看着湖面上的微光如是说道… 作为大一ACM萌新的小A，小B，小C幸运的得到了命运女神的青睐，三人被成功分到了一个团队。别看三人平常在宿舍里团结的很，但是到了竞赛场上却互相争执了起来。原来作为三人小队，不选以为队长实在是让另外听指挥的选手心里很不开心。但是三个人都想当上队长，这样就可以在赛场上一展身手给观众。如果观众里面有同学，也许自己就可以得到认可，如果观众里面有教授，也许自己的隐藏已久的洪荒之力就能得到发现，如果观众里面有…说罢小A，小B，小C三人又为了队长的头衔开始争执。突然ABC提出了一个建议，为什么不让计算机系全体同学来投票决定队长呢？ 队长请吃啵波鱼！ 游戏规则：投票

获胜规则：票数超过一半的获胜（毕竟队长是要服众的）

这时，场边看热闹的人也要参与进来（可怜的小A，小B，小C，凭空多了这么多的竞争者）。于是他们刚好有n个人，每个人从1到n编号，当然每个人也有一个选票，ai表示第i个人的投票对象。

但是实际上大家早就在各自的心里有了人选，而且是众望所归。所以一定会有人的选票超过一半的。换句话说：数据保证有唯一可行解

可爱的ABC看到作为大神的你正悠闲的在湖畔吟诗作赋等吃啵波鱼，所以就让你来计算选票。

输入格式:  
有多组测试用例，请一直处理到文件结束，每组数据第一行包含一个正整数n，接下来的一行有n个正整数，表示选票。

输出格式:  
对于每组测试用例，输出一个正整数x到标准输出中，表示编号为x的人胜出。

输入样例:

4
    1 1 1 1

输出样例:

#### 参考代码 ####

//sort排序 取中间值即可
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <stdio.h>
    #include <string>
    #include <stdio.h>
    using namespace std;
    
    void solve();
    
    int main(){ 
    	solve();
    	return 0;
    }
    
    void solve(){ 
    	int n,b;
    	while(cin>>n){ 
    	  int *a=new int[n];
    		for(int i=0;i<n;i++){ 
    			scanf("%d",&b);
    			a[i]=b;
    		}
    		sort(a,a+n);
    		cout<<a[n/2]<<endl;
    		delete []a;
    	}
    	
    }

### ysu-情报 ###

Brotherhood在燕大建立了分部，但由于燕大人杰地灵，不是什么人都能够任意进出的，于是现在一个棘手的问题摆在了Ezio面前：情报的传递。

已知燕大内的Brotherhood一共有n个团体，有些团体之间有一些关系，你可以把它们看作一条边，每条边连接了两个不同的团体，现在一共有m条边。

现在前辈Jumbo要求Ezio将一个情报传递给燕大内的所有团体。已知Ezio亲自去向团体i告知情报的代价为val\[i\]。Ezio当然不想一个一个去找啦，他还有很多任务要完成，于是他发现他可以利用团体之间的关系，让某一个已经被传达过情报的团体去告知另一与之有关系团体。

但是团体内部的人懒癌发作，自然不想白白地去帮Ezio跑腿。具体来说，针对关系(u,v)，如果Ezio想要利用它，应该付出的代价为cost(u,v)。

现在Ezio想要花费最少的代价，你能帮帮他吗？  
输入格式:  
注意：输入包括多组测试用例。

第一行一个整数t，表示测试用例组数。

对于每组测试用例：

第一行两个用空格隔开的整数n和m，分别表示团体个数和关系数量。

接下来一行n个用空格隔开的数，第i个数表示val\[i\]。

接下来m行，每行三个用空格隔开的整数u,v和cost(u,v)。

输出格式:  
对于每组测试用例，你的程序需要输出一行一个整数表示询问的答案。

输入样例:

2
    5 8
    2 8 5 1 10
    1 2 5
    1 3 9
    3 4 5
    2 5 6
    3 2 2
    1 3 8
    5 3 4
    4 1 8
    5 8
    7 2 9 10 3
    1 2 8
    1 3 6
    1 4 4
    2 5 3
    4 5 2
    2 4 9
    3 5 3
    5 4 2

输出样例:

14
    14

样例说明  
第一组测试用例中，Ezio可以直接将情报传递给1,4号团体，花费分别为2,1。

然后利用关系(4,3),(3,5),(3,2)，花费分别为5,4,2。

#### 参考代码 ####

/* 由题意知，建立图关系，利用最小生成树的算法即可 注意，本题数据量适用于Kruskal ，prim算法会超时 */
    #include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const int maxn=1e5+4;
    int f[maxn];
    
    int find(int x){ 
        return x==f[x]?x:f[x]=find(f[x]);
    }
    
    struct node{ 
        int u,v,w;
        node(int u,int v,int w):u(u),v(v),w(w){ }
    };
    
    bool cmp(const node&A, const node&B){ 
        return A.w<B.w;
    }
    vector<node>edge;
    
    int main(){ 
        int t, n , m,a,b,w,x,y;
        scanf("%d",&t);
        while(t--){ 
            edge.clear();
            scanf("%d%d",&n,&m);
            for(int i=0;i<=n;++i)f[i]=i;
            for(int i=1;i<=n;++i){ 
                scanf("%d",&w);
                edge.push_back(node(0,i,w));
            }
            for(int i=1;i<=m;++i){ 
                scanf("%d%d%d",&a,&b,&w);
                edge.push_back(node(a,b,w));
            }
            sort(edge.begin(),edge.end(),cmp);
            int c=0;
            ll ans=0;
            for(int i=0;i<edge.size();++i){ 
                a=edge[i].u,b=edge[i].v,w=edge[i].w;
                x=find(a);
                y=find(b);
                if(x!=y){ 
                    ans+=w;
                    f[x]=y;
                    c++;
                }
               
            }
            printf("%lld\n",ans);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191205113108369.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70