比赛题解
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';
}
}
|