XUPT_ACM2021寒假训练第一周练习记录

Dear 丶 2023-01-12 04:19 121阅读 0赞

> 试题链接：[第一周训练题 - Virtual Judge][- Virtual Judge]

### 目录 ###

*   *  A - 查成绩
     *  B - 放暑假
     *  C - 展开字符串
     *  D - 回文数猜想
     *  E - 宇航员
     *  F - 买鸡问题
     *  G - 水贴
     *  H - 最小新整数
     *  I - 赶时间
     *  J - 暖气坏了
     *  K - 完美立方
     *  L - N对数的排列问题
     *  M - 母牛的故事
     *  N - 无限的路
     *  O - 统计元音
     *  P - 求数列的和
     *  Q - 数字游戏
     *  R - 轻重搭配
     *  S - Powered Addition
     *  T - Puzzle From the Future

## A - 查成绩 ##

**方法1**  
语言：C++

#include <iostream>
    #include <string>
    #include <map>
    using namespace std;
    
    int main() { 
        string command;
        string name;
        int score;
        map<string, int> info;
        while (cin >> command && command != "end") { 
            cin >> name;
            if (command == "insert") { 
                cin >> score;
                info[name] = score;
            } else { 
                if (info.count(name)) { 
                    cout << info[name] << endl;
                } else { 
                    cout << -1 << endl;
                }
            }
        }
        return 0;
    }

**方法2**  
语言：Python 3

info = { }
    cmd = input().split()
    while cmd[0] != 'end':
        if cmd[0] == 'insert':
            info[cmd[1]] = cmd[2]
        else:
            if cmd[1] in info.keys():
                print(info[cmd[1]])
            else:
                print(-1)
        cmd = input().split()

## B - 放暑假 ##

语言：Python 3

> 懒得动脑子就写了个暴力法，不提倡。

n = int(input())
    a = list(map(int, input().split()))
    m = 0
    for i in range(len(a)):
        s = a[i]
        for j in range(i - 1, -1, -1):
            if a[j] >= a[i]:
                s += a[j]
            else:
                break
        for j in range(i + 1, len(a)):
            if a[j] >= a[i]:
                s += a[j]
            else:
                break
        if s * a[i] > m:
            m = s * a[i]
    print(m)

## C - 展开字符串 ##

语言：C++

#include <iostream>
    #include <string>
    
    using namespace std;
    
    int main() { 
        int N;
        cin >> N;
        while (N--) { 
            string expr;
            string ans = "";
            cin >> expr;
            while (true) { 
                bool flag = false;
                for (int i = 0; i < expr.length(); i++) { 
                    if (expr[i] >= 'a' && expr[i] <= 'z') { 
                        ans += expr[i];
                    } else if (expr[i] >= '0' && expr[i] <= '9') { 
                        int cnt = 0;
                        while (expr[i] >= '0' && expr[i] <= '9') { 
                            cnt *= 10;
                            cnt += expr[i] - '0';
                            i++;
                        }
                        if (expr[i] != '(') { 
                            while (cnt--) { 
                                ans += expr[i];
                            }
                        } else { 
                            int t = 1;
                            int tmp = i + 1;
                            while (t) { 
                                if (expr[tmp] == '(') { 
                                    t++;
                                }
                                if (expr[tmp] == ')') { 
                                    t--;
                                }
                                tmp++;
                            }
                            for (int j = 0; j < cnt; j++) { 
                                for (int k = i + 1; k < tmp - 1; k++) { 
                                    ans += expr[k];
                                    if (expr[k] == '(' || expr[k] == ')' || (expr[k] >= '0' && expr[k] <= '9')) { 
                                        flag = true;
                                    }
                                }
                            }
                            i = tmp - 1;
                        }
                    }
                }
                expr = ans;
                if (!flag) { 
                    break;
                }
                ans = "";
            }
            cout << ans << endl;
        }
        return 0;
    }

## D - 回文数猜想 ##

语言：C

#include <stdio.h>
    #include <stdbool.h>
    
    bool isPalindrome(int n, int* n_pal);
    
    int main(void) { 
        int n;
        while (scanf("%d", &n) != EOF) { 
            int p[200] = { n};
            int cnt = 0;
            int temp = 0;
            while (true) { 
                if (isPalindrome(n, &temp)) { 
                    break;
                } else { 
                    n += temp;
                    p[++cnt] = n;
                }
            }
            printf("%d\n", cnt);
            for (int i = 0; i <= cnt; i++) { 
                if (i == 0) { 
                    printf("%d", p[i]);
                } else { 
                    printf("--->%d", p[i]);
                }
            }
            printf("\n");
        }
        return 0;
    }
    
    bool isPalindrome(int n, int* n_pal) { 
        int n_copy = n;
        * n_pal = 0;
        while (n > 0) { 
            * n_pal = * n_pal * 10 + n % 10;
            n /= 10;
        }
        return n_copy == * n_pal;
    }

## E - 宇航员 ##

语言：C++

> 这题不难，但是真的好恶心啊……

#include <iostream>
    #include <string>
    using namespace std;
    
    typedef struct direction { 
        int forward;
        int back;
        int left;
        int right;
        int up;
        int down;
    } direction;
    direction di;
    
    int main() { 
        int m;
        cin >> m;
        while (m--) { 
            di.forward = 0;
            di.right = 1;
            di.up = 2;
            di.back = 3;
            di.left = 4;
            di.down = 5;
            int n;
            int x = 0, y = 0, z = 0;
            cin >> n;
            while (n--) { 
                string move;
                int step;
                cin >> move >> step;
                if (move == "back") { 
                    swap(di.forward, di.back);
                    swap(di.left, di.right);
                } else if (move == "left") { 
                    int t = di.forward;
                    di.forward = di.left;
                    di.left = di.back;
                    di.back = di.right;
                    di.right = t;
                } else if (move == "right") { 
                    int t = di.forward;
                    di.forward = di.right;
                    di.right = di.back;
                    di.back = di.left;
                    di.left = t;
                } else if (move == "up") { 
                    int t = di.forward;
                    di.forward = di.up;
                    di.up = di.back;
                    di.back = di.down;
                    di.down = t;
                } else if (move == "down") { 
                    int t = di.forward;
                    di.forward = di.down;
                    di.down = di.back;
                    di.back = di.up;
                    di.up = t;
                }
                if (di.forward == 0) { 
                    x += step;
                } else if (di.forward == 1) { 
                    y += step;
                } else if (di.forward == 2) { 
                    z += step;
                } else if (di.forward == 3) { 
                    x -= step;
                } else if (di.forward == 4) { 
                    y -= step;
                } else if (di.forward == 5) { 
                    z -= step;
                }
            }
            cout << x << " " << y << " " << z << " " << di.forward << endl;
        }
        return 0;
    }

## F - 买鸡问题 ##

语言：C

> 这题因为看错题和马虎大意居然WA了两次，大意了。下次一定仔细读题。

#include <stdio.h>
    #include <stdbool.h>
    
    int main(void) { 
        bool flag = false;
        int n;
        scanf("%d", &n);
        for (int i = 0; i <= n / 5; i++) { 
            for (int j = 0; j <= n / 3; j++) { 
                int k = n - i - j;
                if (i * 5 + j * 3 + k / 3 == n && k % 3 == 0) { 
                    printf("%d %d %d\n", i, j, k);
                    flag = true;
                }
            }
        }
        if (!flag) { 
            printf("No Answer.\n");
        }
        return 0;
    }

## G - 水贴 ##

语言：C++

#include <bits/stdc++.h>
    #define MAXSIZE 100005
    using namespace std;
    
    ifstream fcin("board.in");
    ofstream fcout("board.out");
    
    int a[MAXSIZE];
    int b[MAXSIZE];
    
    int main() { 
        int n, m, k;
        int ans = 0;
        fcin >> n >> m >> k;
        for (int i = 1; i <= n; i++) { 
            fcin >> a[i];
        }
        for (int i = 0; i < m; i++) { 
            fcin >> b[i];
        }
        int t = 1, num = 0, cnt = 0;
        for (int i = 1; i <= n; i++) { 
            if (i == b[cnt] && cnt < m) { 
                cnt++;
                ans += t;
            }
            t += a[i] / k;
            num += a[i] % k;
            t += num / k;
            num %= k;
        }
        fcout << ans << endl;
        return 0;
    }

## H - 最小新整数 ##

语言：C

#include <stdio.h>
    #include <string.h>
    
    int main(void) { 
        int t;
        scanf("%d", &t);
        while (t--) { 
            char n[20];
            int k;
            scanf("%s%d", n, &k);
            int len = strlen(n);
            for (int i = 0; i < k; i++) { 
                for (int j = 0; j < len - 1; j++) { 
                    if (n[j] > n[j + 1]) { 
                        for (int m = j; m < len - 1; m++) { 
                            n[m] = n[m + 1];
                        }
                        break;
                    }
                }
                len--;
            }
            for (int i = 0; i < len; i++) { 
                printf("%c", n[i]);
            }
            printf("\n");
        }
        return 0;
    }

## I - 赶时间 ##

语言：C

#include <stdio.h>
    
    int main(void) { 
        int h1, m1, s1, h2, m2, s2;
        scanf("%d:%d:%d", &h1, &m1, &s1);
        scanf("%d:%d:%d", &h2, &m2, &s2);
        int time1 = h1 * 3600 + m1 * 60 + s1;
        int time2 = h2 * 3600 + m2 * 60 + s2;
        printf("%d\n", time1 - time2);
        return 0;
    }

## J - 暖气坏了 ##

**方法1**  
语言：C++

#include <bits/stdc++.h>
    using namespace std;
    
    int main() { 
        int n, m, a;
        cin >> n >> m;
        int ans = 0;
        int tmp = 0;
        for (int i = 0; i < n; i++) { 
            cin >> a;
            if (ans != 0 && tmp >= a) { 
                ans -= tmp - a + 1;
                tmp = a - 1;
            }
            ans += m;
            tmp = a + m - 1;
        }
        cout << ans << endl;
        return 0;
    }

**方法2**  
语言：C++

#include <bits/stdc++.h>
    #define MAXSIZE 10005
    using namespace std;
    
    int a[MAXSIZE];
    
    int main() { 
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; i++) { 
            cin >> a[i];
        }
        int ans = 0;
        for (int i = 0; i < n - 1; i++) { 
            if (a[i] + m - 1 >= a[i + 1]) { 
                ans += a[i + 1] - a[i];
            } else { 
                ans += m;
            }
        }
        cout << ans + m << endl;
        return 0;
    }

## K - 完美立方 ##

语言：C++

#include <bits/stdc++.h>
    using namespace std;
    
    int main() { 
        int a = 3, b = 2, c = 2, d = 2;
        int N;
        cin >> N;
        for (; a <= N; a++) { 
            while (!(b == N && c == N && d == N)) { 
                if (b * b * b + c * c * c + d * d * d == a * a * a && (b <= c && c <= d && d <= a)) { 
                    cout << "Cube = " << a << ", Triple = (" << b << "," << c << "," << d << ")" << endl;
                }
                if (d == N || b == a) { 
                    d = 2;
                    if (c == N || c == a) { 
                        c = 2;
                        if (b == N || b == a) { 
                            b = 2;
                            break;
                        } else { 
                            b++;
                        }
                    } else { 
                        c++;
                    }
                } else { 
                    d++;
                }
            }
        }
        return 0;
    }

## L - N对数的排列问题 ##

这道题是一个数学问题，下面简单给出证明过程：  
假设共有 N N N对双胞胎，那么年龄序列的长度即为 2 N 2N 2N，设年龄序列中相同的两个数的位置为 a k , b k ( a k , b k ∈ \[ 1 , 2 N \] ) a\_k,b\_k (a\_k,b\_k \\in \[1,2N\]) ak,bk(ak,bk∈\[1,2N\])，且 a k > b k a\_k>b\_k ak>bk，则有 a k − b k = k + 1 a\_k-b\_k=k+1 ak−bk=k\+1  ∑ k = 1 N ( a k + b k ) = ( 1 + 2 N ) 2 N 2 = ( 1 + 2 N ) N \\sum\_\{k=1\}^\{N\}(a\_k+b\_k)=\\frac\{(1+2N)2N\}\{2\}=(1+2N)N k=1∑N(ak\+bk)=2(1\+2N)2N=(1\+2N)N所以有 ∑ k = 1 N ( a k − b k ) = ( 1 + 2 + . . . + N ) + N = N ( N + 1 ) 2 + N \\sum\_\{k=1\}^\{N\}(a\_k-b\_k)=(1+2+...+N)+N=\\frac\{N(N+1)\}\{2\}+N k=1∑N(ak−bk)=(1\+2\+...\+N)\+N=2N(N\+1)\+N  ∑ k = 1 N ( a k + b k ) = ∑ k = 1 N ( b k + b k + k + 1 ) = ∑ k = 1 N ( 2 b k + a k − b k ) = 2 ∑ k = 1 N b k + ∑ k = 1 N ( a k − b k ) = 2 ∑ k = 1 N b k + N ( N + 1 ) 2 + N \\sum\_\{k=1\}^\{N\}(a\_k+b\_k)=\\sum\_\{k=1\}^\{N\}(b\_k+b\_k+k+1)=\\sum\_\{k=1\}^\{N\}(2b\_k+a\_k-b\_k)=2\\sum\_\{k=1\}^\{N\}b\_k+\\sum\_\{k=1\}^\{N\}(a\_k-b\_k)=2\\sum\_\{k=1\}^\{N\}b\_k+\\frac\{N(N+1)\}\{2\}+N k=1∑N(ak\+bk)=k=1∑N(bk\+bk\+k\+1)=k=1∑N(2bk\+ak−bk)=2k=1∑Nbk\+k=1∑N(ak−bk)=2k=1∑Nbk\+2N(N\+1)\+N易得 ∑ k = 1 N a k = 5 4 N ( N + 1 ) \\sum\_\{k=1\}^\{N\}a\_k=\\frac\{5\}\{4\}N(N+1) k=1∑Nak=45N(N\+1)  ∑ k = 1 N b k = 1 4 N ( 3 N − 1 ) \\sum\_\{k=1\}^\{N\}b\_k=\\frac\{1\}\{4\}N(3N-1) k=1∑Nbk=41N(3N−1)依题意 ∑ k = 1 N a k , ∑ k = 1 N b k ∈ Z \\sum\_\{k=1\}^\{N\}a\_k,\\sum\_\{k=1\}^\{N\}b\_k \\in \\mathbb\{Z\} k=1∑Nak,k=1∑Nbk∈Z 只需令 \{ N m o d    4 = 0 或 ( N + 1 ) m o d    4 = 0 N m o d    4 = 0 或 ( 3 N − 1 ) m o d    4 = 0 \\left\\\{ \\begin\{aligned\} N\\mod 4=0或(N+1)\\mod4=0 \\\\ N\\mod 4=0或(3N-1)\\mod4=0 \\end\{aligned\} \\right. \{ Nmod4=0或(N\+1)mod4=0Nmod4=0或(3N−1)mod4=0成立，容易求得 N N N需要满足条件 N m o d    4 = 0 或 N m o d    4 = 3 N\\mod4=0或N\\mod4=3 Nmod4=0或Nmod4=3  
语言：C++

#include <iostream>
    using namespace std;
    
    int main() { 
        int n;
        while (cin >> n && n != 0) { 
            if (n % 4 == 0 || n % 4 == 3) { 
                cout << "Y" << endl;
            } else { 
                cout << "N" << endl;
            }
        }
        return 0;
    }

## M - 母牛的故事 ##

语言：C++

#include <bits/stdc++.h>
    using namespace std;
    
    int fun(int n);
    
    int main() { 
        int n;
        cin >> n;
        cout << fun(n) << endl;
        return 0;
    }
    
    int fun(int n) { 
        if (n <= 4) { 
            return n;
        }
        return fun(n - 1) + fun(n - 3);
    }

## N - 无限的路 ##

语言：C++

#include <iostream>
    #include <cmath>
    using namespace std;
    
    double dist(int x, int y);
    
    int main() { 
        double N;
        cin >> N;
        while (N--) { 
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            double ans = fabs(dist(x1, y1) - dist(x2, y2));
            printf("%.3lf\n", ans);
        }
        return 0;
    }
    
    double dist(int x, int y) { 
        double ret = 0;
        for (int i = 0; i <= x + y; i++) { 
            ret += i * sqrt(2.0);
        }
        ret -= y * sqrt(2.0);
        for (int i = 0; i < x + y; i++) { 
            ret += sqrt(double(i * i) + double((i + 1) * (i + 1)));
        }
        return ret;
    }

## O - 统计元音 ##

语言：C

#include <stdio.h>
    #include <string.h>
    #define MAXSIZE 101
    
    int main(void) { 
        int n;
        scanf("%d", &n);
        getchar();
        for (int i = 0; i < n; i++) { 
            char s[MAXSIZE];
            int a_num = 0, e_num = 0, i_num = 0, o_num = 0, u_num = 0;
            gets(s);
            int len = strlen(s);
            for (int j = 0; j < len; j++) { 
                if (s[j] == 'a' || s[j] == 'A') { 
                    a_num++;
                } else if (s[j] == 'e' || s[j] == 'E') { 
                    e_num++;
                } else if (s[j] == 'i' || s[j] == 'I') { 
                    i_num++;
                } else if (s[j] == 'o' || s[j] == 'O') { 
                    o_num++;
                } else if (s[j] == 'u' || s[j] == 'U') { 
                    u_num++;
                }
            }
            printf("a:%d\n", a_num);
            printf("e:%d\n", e_num);
            printf("i:%d\n", i_num);
            printf("o:%d\n", o_num);
            printf("u:%d\n", u_num);
            if (i != n - 1) { 
                printf("\n");
            }
        }
        return 0;
    }

## P - 求数列的和 ##

语言：C

#include <stdio.h>
    #include <math.h>
    
    int main(void) { 
        double n, m;
        while (scanf("%lf%lf", &n, &m) != EOF) { 
            double s = n;
            for (int i = 1; i < m; i++) { 
                n = sqrt(n);
                s += n;
            }
            printf("%.2lf\n", s);
        }
        return 0;
    }

## Q - 数字游戏 ##

语言：C

#include <stdio.h>
    
    int main(void) { 
        char s[10];
        scanf("%s", s);
        int cnt = 0;
        for (int i = 0; i < 8; i++) { 
            if (s[i] == '1') { 
                cnt++;
            }
        }
        printf("%d\n", cnt);
        return 0;
    }

## R - 轻重搭配 ##

语言：C++

#include <bits/stdc++.h>
    #define MAXSIZE 500005
    using namespace std;
    
    int a[MAXSIZE];
    bool flag[MAXSIZE];
    
    int main() { 
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) { 
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);
        int mid = n / 2;
        int high = n;
        int ans = 0;
        while (mid) { 
            if (a[mid] * 2 <= a[high]) { 
                ans++;
                flag[mid] = true;
                flag[high] = true;
                mid--;
                high--;
            } else { 
                mid--;
            }
        }
        for (int i = 1; i <= n; i++) { 
            if (!flag[i]) { 
                ans++;
            }
        }
        cout << ans << endl;
        return 0;
    }

## S - Powered Addition ##

语言：C++

#include <iostream>
    using namespace std;
    
    int main() { 
        int t;
        cin >> t;
        while (t--) { 
            int ans = 0;
            int n;
            cin >> n;
            int num;
            cin >> num;
            int max_num = num;
            int difference = 0;
            for (int i = 1; i < n; i++) { 
                cin >> num;
                max_num = max(max_num, num);
                difference = max(difference, max_num - num);
            }
            while (difference) { 
                difference /= 2;
                ans++;
            }
            cout << ans << endl;
        }
        return 0;
    }

## T - Puzzle From the Future ##

语言：C++

#include <iostream>
    #include <string>
    using namespace std;
    
    int main() { 
        int t;
        cin >> t;
        while (t--) { 
            int n;
            string b;
            cin >> n >> b;
            string a = "1";
            for (int i = 1; i < n; i++) { 
                if ('1' + b[i] != a[i - 1] + b[i - 1]) { 
                    a += "1";
                } else { 
                    a += "0";
                }
            }
            cout << a << endl;
        }
        return 0;
    }

[- Virtual Judge]: https://vjudge.net/contest/419649