2019 SDNU Contest 13 题解

发表于 | 更新于 | 分类于 | 阅读次数：

比赛题解

B题

给你两个数字A, C，可以把某一个数字拆成两个数字, 然后就组成新的三个数,比如说A B C。然后可以任意组合（几个数都行），符号也随便。问你某一种拆分方法之后所组合的数的最多种数。第一遍的时候就做的差不多对了，但是看了第一个样例，4 9 输出13，又被混淆了。最后终于改了回来，但是因为考虑的种类不够，还是没法输出正确答案，在队友的提醒下，想到还可以两个数组合（开始我只考虑了1个数和3个数的情况），终于A了，不过代码不忍直视。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
int main()
{
    int t,a ,b,num1 , num2;
    scanf("%d",&t);
    set<int>S;
    int sz;
    while(t--)
    {
        scanf("%d %d",&a,&b);
        int maxer = -1;
        for(int i = 1; i <= a ; ++i)
        {
            num1 = i;
            num2 = a - i;
            S.clear();
            if(num1 > 0 && num2 > 0)
            {
                if(num1 > 0)
                S.insert(num1);
                if(num2 > 0)
                S.insert(num2);
                if(b > 0)
                S.insert(b);
                if(num1 + num2 + b > 0)
                S.insert(num1 + num2 + b);
                if(num1 + num2 - b > 0)
                S.insert(num1 + num2 - b);
                if(num1 - num2 + b > 0)
                S.insert(num1 - num2 + b);
                if(num1 - num2 - b > 0)
                S.insert(num1 - num2 - b);
                if(-num1 + num2 + b > 0)
                S.insert(-num1 + num2 + b);
                if(-num1 + num2 - b > 0)
                S.insert(-num1 + num2 - b);
                if(-num1 - num2 + b > 0)
                S.insert(-num1 - num2 + b);
                if(-num1 - num2 - b > 0)
                S.insert(-num1 - num2 - b);
                if(num2 + num1 > 0)
                S.insert(num1 + num2);
                if(num1 -num2 > 0)
                S.insert(num1 - num2);
                if(num1 + b > 0)
                S.insert(num1 + b);
                if(num1 - b > 0)
                S.insert(num1 - b);
                if(num2 + b > 0)
                S.insert(num2 + b);
                if(num2 -b > 0)
                S.insert(num2 - b);
                if(num2 - num1 > 0)
                S.insert(num2 - num1);
                if(b - num1 > 0)
                S.insert(b -num1);
                if(b - num2 > 0)
                S.insert(b - num2);
                sz = S.size();
                maxer = max(maxer,sz);
            }
        }
        int maxer1 = -1;
           for(int i = 1; i <= b ; ++i)
        {
            num1 = i;
            num2 = b - i;
            S.clear();
            if(num1 > 0 && num2 > 0)
            {
                 if(num1 > 0)
                S.insert(num1);
                if(num2 > 0)
                S.insert(num2);
                if(a > 0)
                S.insert(a);
                if(num1 + num2 + a > 0)
                S.insert(num1 + num2 + a);
                if(num1 + num2 - a > 0)
                S.insert(num1 + num2 - a);
                if(num1 - num2 + a > 0)
                S.insert(num1 - num2 + a);
                if(num1 - num2 - a > 0)
                S.insert(num1 - num2 - a);
                if(-num1 + num2 + a > 0)
                S.insert(-num1 + num2 + a);
                if(-num1 + num2 - a > 0)
                S.insert(-num1 + num2 - a);
                if(-num1 - num2 + a > 0)
                S.insert(-num1 - num2 + a);
                if(-num1 - num2 - a > 0)
                S.insert(-num1 - num2 - a);
                if(num2 + num1 > 0)
                S.insert(num1 + num2);
                if(num1 -num2 > 0)
                S.insert(num1 - num2);
                if(num1 + a > 0)
                S.insert(num1 + a);
                if(num1 - a > 0)
                S.insert(num1 - a);
                if(num2 + a > 0)
                S.insert(num2 + a);
                if(num2 - a > 0)
                S.insert(num2 - a);
                if(num2 - num1 > 0)
                S.insert(num2 - num1);
                if(a - num1 > 0)
                S.insert(a -num1);
                if(a - num2 > 0)
                S.insert(a - num2);
                sz = S.size();
                maxer1 = max(maxer1,sz);
            }
        }
        cout << max(maxer,maxer1) << '\n';
    }
}

D题

给你车站的数目，以及车线的数目，车线是用来连接车站的。但是注意的是，如果有多条车线连接是相同的两个车站，那么只能看成一条车线。然后让你输出密度= 车线的数目/车站的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
const int inf =0x3f3f3f3f;
bool a[501][501];
int A[2001],B[2001];
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        memset(a,0,sizeof(a));
        scanf("%d %d",&n,&m);
        int sum = 0;
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d",&A[i]);
        }
        for(int j = 1; j <= m; ++j)
        {
            scanf("%d",&B[j]);
        }
        for(int i = 1 ;i <= m ;++i)
        {
            if(!a[A[i]][B[i]])
            {
                a[A[i]][B[i]] = a[B[i]][A[i]] = 1;
                sum++;
            }
        }
        double c = (sum*1.0)/n;
        printf("%.3f\n",c);
    }
}

F题

告诉你谁和谁是好朋友，然后如果满足：两个本身不是朋友的人的共同好友大于等于K个，那么这两个人就是好友了。一开始我考虑的不周到，更新了两个人的朋友关系之后，只是把这个更新的关系应用到了后续的判断当中，忘记了可能这个朋友关系也可以更新原本可能未更新的人。但是考虑到如果外边在套上一个N的循环，那么就达到了O（n^4），n是可以达到100的，这样数据很大。所以没敢写。后来看队友宝乐的代码，发现他的优化还是蛮多的，看来有时候小的优化也是需要重视的。这里稍微改动一下队友的代码，发现队友写的挺不错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
const int inf =0x3f3f3f3f;
int main()
{
    int t,n,m,k,A,B;
    bool a[105][105];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&n,&m,&k);
        memset(a,0,sizeof(a));
        for(int i = 0; i < m; ++i)
        {
            scanf("%d %d",&A,&B);
            a[A][B] = 1;
            a[B][A] = 1;
        }
        int sum1 = 0;
        int tem = n;
        while(tem--)
        {
            for(int i = 0; i < n; ++i)
            {
                for(int j = i + 1 ; j < n; ++j)
                {
                    if(a[i][j] == 1)
                        continue;
                    int sum = 0;
                    for(int p = 0; p < n; ++p)
                    {
                        if(a[i][p] && a[j][p])
                        {
                            sum++;
                        }
                        if(sum >= k)
                        {
                            sum1++;
                            a[i][j] = 1;
                            a[j][i] = 1;
                            break;
                        }
                    }
                }
            }
            if(sum1 == 0)
                break;
        }
        cout << sum1 << '\n';
    }
}

H题

看图说话，题目中告诉你公式了，让你输出一个最小值一个最大值，只是简单的排个序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
const int inf =0x3f3f3f3f;
int main()
{
    int t,A,B,C;
    scanf("%d",&t);
    int a[3001],b[3001];
    while(t--)
    {
        scanf("%d %d %d",&A,&B,&C);
        int tot = 0;
        for(int i = 1; i <= A; ++i)
        {
            a[++tot] = 300;
        }
        for(int i = 1; i <= B; ++i)
        {
            a[++tot] = 100;
        }
        for(int i = 1; i <= C; ++i)
        {
            a[++tot] = 50;
        }
        int sum1 = 0;
        for(int i = 1; i <= A + B + C; ++i)
        {
            sum1 += a[i] * ((i - 1)*2+1);
        }
        sort(a + 1, a+ tot + 1);
        int sum2 = 0;
        for(int i = 1; i <= A + B + C; ++i)
        {
            sum2 += a[i] * ((i - 1)*2+1);
        }
        cout << sum1 << ' ' << sum2 << '\n';
    }
}

I题

比赛的时候看不懂题意，后来补过了。给你一个字符串，你首先需要处理他的长度。把他的长度写成一个二进制串，然后从最后的7位挨着看，7位7位的输出16进制，但是如果这7位之前的某个高位是1，那么就不能7位输出了，需要把第8位上补上1再把这8位进行16进制输出。然后再把长度左移7位，继续处理下面的七位，直到这个二进制数字处理完。最后就简单了，直接输出原来字符串每个字符的16进制，注意用%02X输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
   int t;
   string s;
   cin >> t;
   getchar();
   while(t--)
   {
       getline(cin , s);
       int sz = s.size();
       if(sz == 0)
       {
           printf("00\n");
           continue;
       }
       while(sz)
       {
           int k = sz % 128;
           sz /= 128;
           if(sz)
            k += 128;
           printf("%02X",k);
       }
       for(int i = 0; i < s.size(); ++i)
       {
           printf("%02X",s[i]);
       }
       cout << '\n';
   }

}

J题

又是一个circle,同五一假期做的我们感到很茫然的F题一样，用了同样的方法。同时我们注意到M是小于等于N的，那我们就在本身的数组上面再加上一个数组，这样我们就不用什么取余了，直接挨着往后找就行，不管怎么找都不会超过数组大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
const int inf =0x3f3f3f3f;
int main()
{
   int t;
   int a[1001],n,m;
   scanf("%d",&t);
   while(t--)
   {
       scanf("%d %d",&n,&m);
       for(int i = 1; i <= n; ++i)
       {
           scanf("%d",&a[i]);
       }
       for(int j = n + 1; j <= 2*n; ++j)
       {
           a[j] = a[j - n];
       }
       int maxer = -1;
       for(int i = 1; i <= n; ++i)
       {
           int cnt = 0;
           int sum = 0;
           for(int j = i; ;j++)
           {
               sum += a[j];
               maxer = max(maxer,sum);
               cnt++;
               if(cnt == m)
                break;
           }
       }
       cout << maxer << '\n';
   }
}