这篇文章是关于SDNU_ACM_ICPC_2019_Winter_Practice_5th的题解.

水题欢乐赛,,可惜没赶上,,,去走亲戚错过了寒假礼物,,/(ㄒoㄒ)/~~

这场比赛后面大都是3题下场了,,不好补不好补,,,,

A - Easy Marks

SPOJ - EASYMRKS

题意:给你n个数字,和一个数k问你再加上哪个数字可以让整个序列的平均数等于k;

题解:输出k*(n + 1) - 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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int Ma = 1e4 + 10;
int num[Ma];

int main()
{
int T;
scanf("%d", &T);
int y = 0;
while(T--){
int n, k;
scanf("%d%d", &n, &k);
int sum = 0, ans = k * (n + 1);
for(int i = 0; i < n; i++){
int t;
scanf("%d", &t);
sum += t;
}
printf("Case %d: %d\n", ++y, ans - sum);
}

return 0;
}

B - Candy I

SPOJ - CANDY

题意:你要分糖果,你有n个包裹里面分别装了些糖果,你要让每个包裹里面的糖果都一样多,问你需要的步骤数,如果不能就输出-1;

题解:记录总共有多少个糖果,如果这些糖果不能被n整除直接输出-1,若能,加上所有糖果数小于平均数的糖包和平均数的差值,并输出;

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int Ma = 1e4 + 10;
int num[Ma];

int main()
{
int n;
while(~scanf("%d", &n) && n != -1){
int sum = 0;
for(int i = 0; i < n; i++){
scanf("%d", &num[i]);
sum += num[i];
}
if(sum % n)printf("-1\n");
else {
int a = sum / n;
int ans = 0;
for(int i = 0; i < n; i++){
if(num[i] < a)ans += (a - num[i]);
}
printf("%d\n", ans);
}
}

return 0;
}

C - Rectangles

SPOJ - AE00

题意:给你n个小方块,问你你能堆出多少个不同的矩形;

题解:要让矩形不重样,枚举列到sqrt(n)就行了,再多就能通过列行互换而重样了,直接枚举判断;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;

int main()
{
int n;
scanf("%d", &n);
int a = sqrt(n);
int cont = a;
for(int i = 1; i <= a; i++)
for(int j = i + 1; j * i <= n; j++)
++cont;
cout<< cont << '\n';

return 0;
}

D - Alchemy

URAL - 1573

题意:你是一个炼金术士,给你蓝红黄三种颜色的药水,再给你一个配方,包含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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
int r, y, b;
while(~scanf("%d%d%d", &b, &r, &y)){
int n;
scanf("%d", &n);
int ans = 1;
while(n--){
char s[10];
scanf("%s",s);
if(s[0] == 'R') ans *= r;
if(s[0] == 'B') ans *= b;
if(s[0] == 'Y') ans *= y;
}
cout<< ans << '\n';
}

return 0;
}

E - Genealogical Tree

URAL - 1022

题意:给你n个序列,每个序列以0结尾,下面第i列代表i这个数字前有哪些数字,不计0,请你以此将1到n排序并输出;

题解:拓扑排序裸题,Albert_s的拓扑排序教程里面有;

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
#include<bits/stdc++.h>
using namespace std;

vector<int>top[110];
vector<int>ans;
bool visit[110];

void topu(int x)
{
visit[x] = true;
for(auto i : top[x])
if(!visit[i])topu(i);
vector<int>::iterator it = ans.begin();
ans.insert(it, x);
}

int main()
{
int n;
scanf("%d", &n);
visit[0] = true;
for(int i = 1; i <= n; i++){
int k;
do{
scanf("%d", &k);
top[i].push_back(k);
}
while(k != 0);
}
for(int i = 1; i <= n; i++)
if(!visit[i])topu(i);

for(auto i : ans){
if(i != ans[0]) putchar(' ');
cout<< i ;
}
putchar('\n');

return 0;
}

F - GCD The Largest

UVA - 12708

题意:UVA崩了又,,日常gg,给你一个数n,问你 i, j ∈ [1, n]时,最大的gcd(i, j);

题解:逻辑问题,i和j最大只能为n,设i > j,要gcd最大肯定元素要尽量大,那么设i为n,这时候i分出最小的素因子为2,此时j为n/2便可使gcd(i, j)最大,且等于j,当n为奇数时减一即可;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

int main()
{
int T;
scanf("%d", &T);
while(T--){
ll n;
scanf("%lld", &n);
if(n % 2)--n;
cout<< n / 2 << '\n';
}

return 0;
}

G - Peter's Smokes

UVA - 10346

题意:给Peter n根香烟, 给你一个数k,Peter每抽k根香烟就能再获得一根新的香烟,而你什么都没有 问你Peter能抽多少根香烟;

题解:记录Peter每次能获得多少根香烟和剩余香烟数,模拟;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int Ma = 1e4 + 10;

typedef long long ll;

int main()
{
int n, k;
while(scanf("%d%d", &n, &k) != EOF){
int cia = n, butt = 0, ans = n;
while(n >= k){
ans += (n / k);
n = n / k + n % k;
}
printf("%d\n", ans);
}

return 0;
}

H - Blown Garland

CodeForces - 758B

题意:让你来修灯,!表示坏了的灯,且四个颜色的灯需要满足一个顺序,不能变,问你需要的灯泡数量,并按r b y g的顺序输出;

题解:用一个数组来存四个颜色灯泡的顺序,一个数组来存需要四个灯泡的个数,在最后按r b y g的顺序输出;

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
string light;
map<char, char>m;
while(cin>> light){
char li[5];
int lli[5] = {0, 0, 0, 0};
int n = light.length();
for(int i = 0; i < n; i ++){
if(light[i] == '!')++lli[(i + 1)%4];
else li[(i + 1)%4] = light[i];
}
char ri[] = {'R', 'B', 'Y', 'G'};
for(int i = 0; i < 4; i++){
if(i != 0)putchar(' ');
for(int j = 0; j < 4; j++){
if(li[j] == ri[i])cout<< lli[j];
}
}
putchar('\n');
}

return 0;
}

I - Pythagorean Theorem II

CodeForces - 304A

题意:问你1 ≤ a ≤ b ≤ c ≤ n下有多少个由a, b, c组成的直角三角形;

题解:枚举a, b判断c能否满足条件;

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
int n;
scanf("%d", &n);
int cont = 0;
for(int a = 1; a <= n; a++)
for(int b = a; b <= n; b++){
int c = a * a + b * b;
int C = sqrt(c) + 0.5;
if(C * C == c && C >= b && a + b > C)
++cont;
else if(C >= n)break;
}

printf("%d\n", cont);

return 0;
}

J - Calendar

CodeForces - 304B

题意:给你两个日期,问你差多少天;

题解:模拟 (偷懒打了个表

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
#include<bits/stdc++.h>
using namespace std;

int yea, mon, da;
int year, month, day;

bool judge(int n)
{
return n % 400 == 0 ? true : n % 100 != 0 ? n % 4 == 0 : false;
}

int run[] = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366};
int nian[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};

void change()
{
int t;
t = yea, yea = year, year = t;
t = mon, mon = month, month = t;
t = da, da = day, day = t;
}

int main()
{
while(~scanf("%d:%d:%d", &yea, &mon, &da)){

scanf("%d:%d:%d", &year, &month, &day);
if(year < yea)change();
else if(year == yea && mon > month)change();
else if(year == yea && mon == month && da > day)change();
else if(year == yea && mon == month && da == day){
cout<< 0 << '\n';
continue;
}
if(year != yea){
int ans = 0;
if(judge(yea))ans += (run[12] - run[mon - 1] - da);
else ans += (nian[12] - nian[mon - 1] - da);

for(int i = yea + 1; i < year; i++){
if(judge(i))ans += run[12];
else ans += nian[12];
}

if(judge(year))ans += (run[month - 1] + day);
else ans += (nian[month - 1] + day);

cout<< ans << '\n';
}
else if(month != mon){
if(judge(yea))cout<< (run[month - 1] - run[mon - 1] - da + day) << '\n';
else cout<< (nian[month - 1] - nian[mon - 1] - da + day) <<'\n';
}
else cout<< day - da << '\n';
}

return 0;
}

Comments

⬆︎TOP