AtCoder Beginner Contest 118题解报告

港控/mmm° 2022-03-19 15:56 174阅读 0赞

# A #

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        int a, b;
        cin >> a >> b;
        cout << (b % a ? b - a : b + a) << endl;
    
        return 0;
    }

# B #

#include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        int N, M;
        cin >> N >> M;
        vector<int> cnt(M);
    
        for (int i = 0; i < N; i++)
        {
            int K;
            cin >> K;
            for (int j = 0; j < K; j++)
            {
                int A;
                cin >> A;
                A--;
                cnt[A]++;
            }
        }
    
        int ans = 0;
        for (int i = 0; i < M; i++)
        {
            if (cnt[i] == N)
            {
              ans += 1;
            }
        }
        cout << ans << endl;
    }

# C #

分析：  
逐个求最大公约数就行。

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    
    int gcd(int a,int b)
    {
       return (0 == b) ? a : gcd(b, a % b);
    }
    
    int main()
    {
        int N;
        cin >> N;
        int A[N];
        for(int i=0;i<N;i++)
        {
           cin>>A[i];
        }
    
        int ans = A[0];
        for(int i=1;i<N;i++)
        {
            ans = gcd(ans,A[i]);
        }
        cout << ans << endl;
    
        return 0;
    }

# D #

分析：  
本题可以使用动态规划来解决。以样例1为例 来分析。  
20 4  
3 7 8 4  
（1）可先对Ai按从大到小的顺序进行排序: 8 7 4 3  
（2）数据的对应关系为

0  0 
    1  2
    2  5
    3  5
    4  4
    5  5
    6  6
    7  3
    8  7
    9  6

所以，样例1中数据的对应关系为

8  7
    7  3
    4  4
    3  5

所以，映射前的数组A\[\] = \{8, 7, 4, 3\}，映射后的数组map\[\] = \{7, 3, 4, 5\}  
（3）考虑到string重载了“+”运算符，可以很方便地将数字（字符）连接起来。  
比如”7”+”7”=”77”, 或”77777” + “3” = “777773”。  
可以声明vector dp，刚开始时，dp\[i\]都为””。dp中存放的是结果。  
样例1中N=20，则最终要求的是dp\[20\]。  
（4）  
根据样例1中数据的对应关系，dp\[7\]=”8”, dp\[3\]=”7”, dp\[4\] = “4”, dp\[5\] = “3”。  
接着从1开始枚举dp。  
N = 1时，dp\[1\] = “”, 也就是说，｛8，7，4，3｝无法组成各位数之和为1的数。  
N = 2时，dp\[1\] = “”, 也就是说，｛8，7，4，3｝无法组成各位数之和为2的数。  
N = 3时，dp\[3\] = “7”。  
N = 4时，dp\[4\] = “4”。  
N = 5时，dp\[5\] = “3”。  
N = 6时，6 = 3 + 3。3对应的数是7，所以dp\[6\] = “7” + “7” = “77”。  
N = 7时，dp\[7\] = “7”。另外7 = 3 + 4 = 4 + 3，3对应的是7，4对应的是4。所以dp\[7\] = “74”或dp\[7\] = “47”。取最大值dp\[7\] = “74”。  
N = 8时，dp\[8\] = 3 + 5 = 4 + 4 ＝ 5 + 3。3对应着7，4对应着4，5对应着3，则dp\[8\] = “73”或“44”或“37”，取最大值dp\[8\] = “73”。  
N = 9时，dp\[9\] = dp\[6\] + 3 = “777”。  
……  
最终，dp\[20\]即为所求。

代码：

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    
    vector<int> m = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    
    string getMax(string a, string b)
    {
        if(a.length() > b.length())
        {
            return a;
        }
        else if(a.length() < b.length())
        {
            return b;
        }
        else  //如果长度相等，返回字典序较大的字符串
        {
            return a > b ? a : b;
        }
    }
    
    int main()
    {
        int N, M;
        cin >> N >> M;
        vector<int> A(M, 0);
        for(int i = 0; i < M; i++)
        {
            cin >> A[i];
        }
    
        sort(A.begin(), A.end(), greater<int>());
    
        vector<string> dp(max(N+1,10), "");
    
        for(int i = 0; i < M; i++)
        {
            dp[m[A[i]]] = getMax(dp[m[A[i]]], to_string(A[i]));
        }
    
        for(int j = 0; j <= N; j++)
        {
            for(int i = 0; i < M; i++)
            {
                if(j - m[A[i]] >= 0 && dp[j-m[A[i]]] != "")
                {
                    dp[j] = getMax(dp[j], dp[j-m[A[i]]] + to_string(A[i]));
                }
            }
        }
    
        cout << dp[N] << endl;
    
        return 0;
    }

> TopCoder & Codeforces & AtCoder交流QQ群：648202993