SDNU_ACM_ICPC_2019_Winter_Practice_2nd题解报告

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

缓慢更新题中，，第二场比赛我就回家了，边吸猫边打的比赛，傻猫现在都瘦了，让我给它买点零食。当初怎么就去阿里云申请域名了呢，，，以为国内实名认证应该很快，，结果一周了还没认证完成，，，不知什么时候才能重启博客域名，，，

还是继续题解系列吧

A - Partition

CodeForces - 946A

题意：给你一个序列，让你把它分为两个序列，让这两个序列的和相减最大；

题解：把正的数加起来，负的数加起来，相减；

B - A/B

HDU - 1576

题意：求（A/B）%9973的值

题解：除法取模，用逆元解决 刚学的东西，求逆元方法还挺多的，等会总结下逆元(我开了多少坑来着？？咕咕咕

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

const int Mod = 9973;
//LL ny(LL n)
//{
//    return n == 1 ? 1 : 1LL * ny(Mod % n) * (Mod - Mod / n)%Mod;
//}

LL ny(LL a, LL b)
{
    LL s = 1;
    while(b)
    {
        if(b & 1)s = s * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return s;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        LL A, B;
        scanf("%lld %lld", &A, &B);
        printf("%lld\n", A * ny(B, Mod - 2) % Mod);
    }

    return 0;
}

C - Rightmost Digit

HDU - 1061

题意：输入n，求n^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
#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;

LL solve(LL n)
{
    LL N = n, sum = 1;
    n = n % 10;
    while(N){
        if(N & 1)
            sum *= n % 10;
        n = n * n % 10;
        N /= 2;
    }
    return sum % 10;
}

int main()
{
    LL t;
    while(~scanf("%d", &t)){
    while(t--){
        LL n;
        scanf("%lld", &n);
        printf("%lld\n", solve(n));
    }
    }

    return 0;
}

D - Tempter of the Bone

HDU - 1010

题意：走二维迷宫，给定一个时间，必须在那个时间走到门

题解：,,,这道题诱惑我用bfs，，，好难受，，，乍一看就是基础迷宫题，再仔细一读题，，只有在t时门才开，所以只能在t时恰好到，那么bfs找出所有路径，如果时间恰好为t就行，行吧，tle了。。。思路没错的话那就是剪枝的问题了，用上百年不变的边界剪枝，超时的也剪一下，以及奇偶剪枝，终于剪到1s以内了，，，多么想+1s

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
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define LL long long
using namespace std;

const int Ma = 10;
char maze[Ma][Ma];
bool visit[Ma][Ma];
int n, m, T, zx, zy;
bool zd = false;

void dfs(int dx, int dy, int dt)
{
    int xzou[] = {1, -1, 0, 0};
    int yzou[] = {0, 0, 1, -1};
    if(zd)return;
    if(dx >= n || dx < 0 || dy >= m || dy < 0 || dt > T)return;
    if(dx == zx && dy == zy && dt == T){
        printf("YES\n");
        zd = true;
        return;
    }
    int lost = abs(zx - dx) + abs(zy - dy);
    if(T - dt < lost)return;
    if((T - dt - lost) % 2)return;

    for(int i = 0; i < 4; i++){
        if(maze[dx + xzou[i]][dy + yzou[i]] != 'X'){
            maze[dx + xzou[i]][dy + yzou[i]] = 'X';
            dfs(dx + xzou[i], dy + yzou[i], dt + 1);
            maze[dx + xzou[i]][dy + yzou[i]] = '.';
        }
    }
    return;
}

int main()
{
    while(~scanf("%d%d%d", &n, &m, &T)){
        zd = false;
        if(n == 0 && m == 0 && T == 0)continue;
        memset(visit, 1, sizeof(visit));
        int xx, yy;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin>> maze[i][j];
                if(maze[i][j] == 'S')xx = i, yy = j;
                else if(maze[i][j] == 'D') zx = i, zy = j;
            }
        }

//        for(int i = 0; i < n; i++, putchar('\n')){
//            for(int j = 0; j < m; j++){
//                cout<< maze[i][j];
//            }
//        }
        maze[xx][yy] = 'X';
        dfs(xx, yy, 0);
        if(!zd)cout<< "NO\n";
    }

    return 0;
}

E - Pie

HDU - 1969

题意：给你n个高度都为1的派，和f个小伙伴，要分给小伙伴和你自己一人一块派，要求没人获得的派一样大

题解：二分，当初没注意一人一块，，我那时想把派加起来平均分就行了嘛，，但有了一人一块的要求后，，每个人获得的派大小的上界就得出了，二分答案可得， 注意把你自己加上，话说二分也得总结，，管挖不管埋

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

const int Ma = 1e4 + 10;
const double TT = acos(-1.0);
double num[Ma];
int n, f;
const double Mi = 1e-7;

bool check(double q)
{
    int s = 0;
    for(int i = 0; i < n; i++){
        s += (int)(TT * num[i] * num[i] / q);
    }
    if(s < f + 1)return true;
    return false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &f);
        double sum = 0;
        for(int i = 0; i < n; i++){
            scanf("%lf", &num[i]);
            sum += (num[i] * num[i] * TT);
        }

        double r = sum / (double)(f + 1);
        double l = 0;
        while(r - l > Mi){
            double mid = (r + l) / 2;
            if(check(mid))r = mid;
            else l = mid;
        }

        printf("%.4f\n", r);

    }

    return 0;
}

F - Ticket to Ride

HDU - 1970

题意：票，路，游戏，火车，轨道；

题解：？？？

G - What Are You Talking About

HDU - 1075

题意：对上一道题的解释首先由一个start和一个end中间给你一个字典，下一个start和end中间给你一串火星文，让你按照字典翻译火星文，翻译不了就直接输出

题解：map记录字典，读入火星文，能在字典上找到就输出翻译的，不能就直接输出，，话说我之前说整理stl来着？？？

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

int main()
{
    string be = "START", en = "END";
    string te;
    map<string, string>m;
    while(cin>> te && te != be);
    while(cin>> te && te != en){
            string huo;
            cin>> huo;
            m[huo] = te;
    }
    map<string, string>::iterator it = m.end();
    while(cin>> te && te != be);
    getchar();
    while(getline(cin, te) && te != en){
        int le = te.length();
        for(int i = 0, j; i < le; i++){
            j = i;
            for(; i < le && te[i] <= 'z' && te[i] >= 'a'; i++);
            if(i != j){
                string tm = te.substr(j, i - j);
//                puts("tm ==");
//                cout<< tm << endl;
                if(m.find(tm) != it){
                    cout<< m[tm];
                    cout<< te[i];
                }
                else for(;j <= i; j++)cout<< te[j];
            }
            else cout<< te[i];
        }
        putchar('\n');
    }

    return 0;
}

H - 水果

HDU - 1263

题意：水果真好吃，话说sd的橙子🍊真的好吃，cq的橙子🍊好小

题解：map的应用，装入map的元素会按字典序排好，stl真好用系列,对了，还有多维map的应用，记录在还在咕咕咕的stl总结里面

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

int main()
{
    int T;
    bool kg = false;
    scanf("%d", &T);
    while(T--){
        if(kg)putchar('\n');
        int M;
        scanf("%d", &M);
        map<string, map<string, int>>m;

        for(int i = 0; i < M; i++){
            string t, tt;
            cin>> t >> tt;
            int num;
            scanf("%d", &num);
            m[tt][t] += num;
        }

        map<string, map<string, int>>::iterator it = m.begin();

        for(it; it != m.end(); it++){
            cout<< it -> first <<'\n';
            map<string, int>::iterator ii = it -> second .begin();
            for(ii; ii != it -> second.end(); ii++)
            cout<<"   |----" << ii -> first << '(' << ii -> second << ')' << '\n';
        }

        if(!kg)kg = true;
    }

    return 0;
}

I - 最大连续子序列

HDU - 1231

题意：中文题意，找到最大连续子序列并输出和以及序列的第一个数和最后一个个数

题解：dp解决，sum记录dp中的最大值，同时记录此时的第一个数和最后一个数,如果dp时第一个数为负数那么直接跳过，以为如果这个序列减去首位数字就能得到比他大的序列，注意找不到输出0和最大和为0的区别

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

int num[10010];
int dp[10010];

int main()
{
    int k;
    while(~scanf("%d", &k)){
    if(k == 0)continue;
    for(int i = 0; i < k; i++)
        scanf("%d", &num[i]);
    memset(dp, 0, sizeof(dp));
    int first = 0, last = 0, sum = -1;
    int i, j;
    for(i = 0; i < k; i++){
        dp[i] = 0;
        if(num[i] < 0)continue;
        for(j = i; j < k; j++){
            dp[i] += num[j];
            if(dp[i] > sum){
                sum = dp[i];
                first = num[i];
                last = num[j];
            }
        }
    }

    if(sum != -1)cout<< sum << ' ' << first << ' ' << last << '\n';
    else cout<< 0 <<' ' << num[0] <<' '<< num[k - 1]<< '\n';
    }


    return 0;
}

J - Unimodal Array

CodeForces - 831A

题意：给你一个长度为n的序列，问你这个序列是否为单增不变单减

题解：走一遍单增，不变，单减，看走了几个单位，若和序列长度一样就输出YES，否则输出NO

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

int num[110];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        cin>> num[i];
    }
    int i = 0;
    while(num[i + 1] > num[i])i++;
    while(num[i + 1] == num[i])i++;
    while(num[i + 1] < num[i])i++;
    if(i >= n)cout<< "YES\n";
    else cout<< "NO\n";

    return 0;
}

最近到处过年，，我要学习，不要红包/(ㄒoㄒ)/~~ 快开学了，，还是菜鸡状态，，什么时候才能升级啊，，，好想回去专心敲代码.jpg

Comments

⬆︎TOP