SDNU_ACM_ICPC_2019_Winter_Practice_5th题解报告

这篇文章是关于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