第六届浙江省赛题解（部分）

不念不忘少年蓝@ 2022-05-26 01:48 201阅读 0赞

## 第六届浙江省赛题解 ##

### A. Second-price Auction ###

[题目链接][Link 1]

#### 题目大意 ####

有n个投标者,投标最高的获得物品,需要支付第二投标者的价格.

#### 解题思路 ####

使用结构体,保存投标的价格和一开始的排序.  
然后根据投标价格排序,使用sort就可以了

#### AC代码 ####

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn = 110;
    struct node
    {
        int n, w;
    }a[maxn];
    bool cmp (node a, node b){
        if(a.w != b.w)
            return a.w < b.w;
        else
            return a.n > b.n;
    }
    int main()
    {
        int T;
        int n;
        cin >> T;
        while(T--)
        {
            memset(a, 0 ,sizeof(a));
            cin >> n;
            for(int i=1; i<=n; i++){
                cin >> a[i].w;
                a[i].n = i;
            }
            sort(a+1, a+n+1, cmp);
            cout << a[n].n << ' ' << a[n-1].w << endl;
        }
        return 0;
    }

--------------------

### B.Light Bulb ###

[题目链接][Link 2]

#### 题目大意 ####

![5adb1e1e52965.png][]  
给你H  H ，h h，D  D ，求阴影部分L L的最大长度

#### 解题思路 ####

![5add18d9da334.png][]  
因为H  H ，h h，是固定的长度的，首先延长边，根据边的比例能够退出x+y的函数表达式（用θ表示）  
列出两个极端的情况，人在最左边和最右边，这就是θ的取值范围，然后对上面的函数表达式求导，得到函数是先增后减的，有极大值  
求出零点θ的值（二分），然后判断3点的值的最值即可

#### AC代码 ####

#include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<iostream>
    using namespace std;
    double H,D,h;
    double mid;
    bool judge(double mid) {
        double Sin = sin(mid);
        Sin = Sin * Sin;
        double Cos = 1.0-Sin;
        double ans = D/Sin - (H-h)/Cos;
        if(ans < 0) return false;
        return true;
    }
    
    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
            scanf("%lf%lf%lf",&H,&h,&D);
            double l = atan(D/H), r = atan(D/(H-h));
            for(int i=0; i<1000; i++) {
                mid = (l+r)/2.0;
                if(judge(mid))
                    l = mid;
                else r = mid;
            }
            double ans = max( (D*h/H), h);
            double tanx = H - (D/tan(mid)) + (tan(mid)*(h-H)) + D;
            ans = max(ans, tanx);
            printf("%.3f\n", ans);
        }
        return 0;
    }

--------------------

### C.Connect them ###

[题目链接][Link 3]

#### 题目大意 ####

有N  N 台计算机，要建立小型局域网，所有连接都是双向的。两台计算机的链接成本是Cij Ci j，找到最小的成本的连接方法

#### 解题思路 ####

一个最小生成树的模板题目。但是他要输出最小的字典序。  
最简单的方法是输出边的时候排序。  
但是,如果生成树不是一条的话就很难弄了。  
所以我们可以吧输入的数据，先排序，首先根据费用排序，然后根据起点排序，最后根据终点排序。

#### AC代码 ####

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 10000+10;
    struct Node{
        int s,e;
        int sum;
    }node[maxn];
    struct MP{
        int x,y;
    }mp[maxn];
    bool cmd1(MP a,MP b){
        if(a.x == b.x) return a.y < b.y;
        else return a.x<b.x;
    }
    bool cmd(Node a,Node b){
        if(a.sum != b.sum) return a.sum < b.sum;
        if(a.s != b.s) return a.s < b.s;
        return a.e < b.e;
    }
    int pre[maxn];
    int p=0,n,pp=0;
    int Find(int root){
        return pre[root]==root?root:Find(pre[root]);
    }
    int kruskal() {
        int ans = 0;
        for(int i = 1; i <=n ; i++) pre[i] = i;
        sort(node,node+p,cmd);
        pp = 0;
        for(int i = 0; i < p; i++) {
            int x = Find(node[i].s);
            int y = Find(node[i].e);
            if(x != y) {
                mp[pp].x = node[i].s;
                mp[pp++].y = node[i].e;
                ans ++;
                pre[y] = x;
            }
        }
        return ans;
    }
    
    int main(){
        int t;
        while(~scanf("%d",&t)){
            while(t--){
                scanf("%d",&n);
                p = 0;
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++){
                        int x;
                        scanf("%d",&x);
                        if(x!=0){
                            node[p].s = i;
                            node[p].e = j;
                            node[p++].sum = x;
                        }
                    }
                }
                int q = kruskal();
                if(q == 0 || q != n-1){
                    printf("-1\n");
    
                }else{
                    sort(mp,mp+pp,cmd1);
                    for(int i=0;i<pp;i++){
                        printf("%d %d%c",mp[i].x,mp[i].y,i==pp-1?'\n':' ');
                    }
                }
            }
        }
        return 0;
    }

--------------------

### F.80ers’ Memory ###

[题目链接][Link 4]

#### 题目大意 ####

看输入输出就可以看出.问每个人有几个关键字在典型的80年代关键词中

#### 题解思路 ####

使用map直接存储字符串，然后直接找就好了

#### AC代码 ####

#include<cstdio>
    #include<algorithm>
    #include<map>
    #include<string>
    #include<iostream>
    using namespace std;
    map<string,int> mp;
    int main(){
        int t;
        scanf("%d",&t);
        string s;
        for(int i=0;i<t;i++){
            cin>>s;
            mp[s] = 1;
        }
        int n,p;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&p);
            int sum=0;
            for(int j=0;j<p;j++){
                cin>>s;
                if(mp[s]==1) sum++;
            }
            printf("%d\n",sum);
        }
        return 0;
    }

--------------------

### I.A Stack or A Queue? ###

[题目链接][Link 5]

#### 题目大意 ####

给你一个输入序列一个输出序列，问是queue还是stack，还是都不或者都不是

#### 解题思路 ####

直接模拟，拿输出序列和queue还有stack输出对比

#### AC代码 ####

#include<cstdio>
    #include<algorithm>
    #include<queue>
    #include<stack>
    using namespace std;
    const int maxn = 100+10;
    int a[maxn],b[maxn];
    queue<int> q;
    stack<int> s;
    int main(){
        int t;
        while(~scanf("%d",&t)){
            while(t--){
            while(!q.empty()) q.pop();
            while(!s.empty()) s.pop();
                int n;
                scanf("%d",&n);
                for(int i=0;i<n;i++){
                    int x;
                    scanf("%d",&x);
                    q.push(x);
                    s.push(x);
    
                }
                int flag1,flag2;
                flag1=flag2=1;
                for(int i=0;i<n;i++){
                    int x;
                    scanf("%d",&x);
                    if(x==q.front()){
                        q.pop();
                    }else{
                        flag1=0;
                    }
                    if(x==s.top()){
                        s.pop();
                    }else{
                        flag2=0;
                    }
                }
                if(flag1==1 && flag2==1){
                    printf("both\n");
                }else if(flag1==1 && flag2==0){
                    printf("queue\n");
                }else if(flag1==0 && flag2 == 1){
                    printf("stack\n");
                }else{
                    printf("neither\n");
                }
            }
        }
        return 0;
    }

--------------------

### K.K-Nice ###

[题目链接][Link 6]

#### 题目大意 ####

构造出一个点的值等于周围四个点的值的和(注:一定是四个点，挨着边的都不算

#### 解题思路 ####

构造题一般都不是一个解，只要符合题目就行。  
因为一个点的值等于周围四个点的值的和，所以当都是0时也是符合条件的，题目的样例中也给出了这种情况，这种也是最好构造的.  
我们可以从上到下，除了边上点，其余的符合条件的地方使用0，后面不符合条件的用1来填充。  
注意最后的空格和换行，不然会WA

#### AC代码 ####

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 17;
    int num[maxn][maxn];
    
    void tian(int n, int m, int k)
    {
        if(m < 3){
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    num[i][j] = 0;
                }
            }
        }
        else{
            int number = k/(m-2);
            int i;
            for(i=1; i<=number+1; i++){
                for(int j=0; j<m; j++){
                    num[i][j] = 0;
                }
            }
            if(k % (m-2) != 0){
                for(int j=0; j<= (k%(m-2)); j++){
                    num[i][j] = 0;
                }
                for(int j=(k%(m-2))+1; j < m; j++){
                    num[i][j] = 1;
                }
                i++;
            }
            for(;i < n; i++){
                for(int j=0; j<m; j++){
                    num[i][j] = 1;
                }
            }
        }
    
    }
    
    int main()
    {
        int T;
        int n, m , k;
        scanf("%d", &T);
        while(T--)
        {
            scanf("%d %d %d", &n, &m, &k);
            tian(n, m, k);
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    printf("%d%c", num[i][j],j==m-1?'\n':' ');
                }
    
            }
        }
        return 0;
    }

[Link 1]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3202
[Link 2]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3203
[5adb1e1e52965.png]: https://i.loli.net/2018/04/21/5adb1e1e52965.png
[5add18d9da334.png]: https://i.loli.net/2018/04/23/5add18d9da334.png
[Link 3]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3204
[Link 4]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3207
[Link 5]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3210
[Link 6]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3212