AtCoder Beginner Contest 100 完整解题报告

爱被打了一巴掌 2022-05-22 06:35 128阅读 0赞

# 题目链接 #

[https://beta.atcoder.jp/contests/abc100/tasks][https_beta.atcoder.jp_contests_abc100_tasks]

# A题 #

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        int a, b;
        cin >> a >> b;
        cout << ((a <= 8 && b <= 8) ? "Yay!" : ":(") << endl;
        return 0;
    }

# B题 #

n = 100是特例，需要考虑进去。

#include <iostream>
    #include <cmath>
    
    using namespace std;
    
    int qpow(int x, int n)
    {
        int res = 1;
        while (n)
        {
            if (n & 1)
            {
                res *= x;
            }
    
            n >>= 1;
            x *= x;
        }
    
        return res;
    }
    
    
    int main()
    {
        int d, n;
        cin >> d >> n;
        int ans = (n != 100) ? qpow(100, d) * n : qpow(100, d) * (n + 1) ;
    
        cout << ans << endl;
    
        return 0;
    }

# C题 #

只需考虑偶数的情况。  
因为3是奇数，假如一个数原本能被2整除x次，那么无论它乘以3多少次，还是只能被2整除x次。  
比如x = 2，只能被2整除一次，乘以3后只能被2整除一次，乘以3^2后也只能被2整除一次，乘以3^3后只能被2整除一次……  
再比如x = 4，能被2整除两次，乘以3后也只能被2整除两次，乘以3^2的也只能被2整除两次。

这样本题就可以转化为，求输入的数中，能被2整除的次数的累加和。  
以m = 2, n = 4, k = 6为例，  
m能被2整除一次，m / 2的同时，n \* 3, k \* 3  
n能被2整除两次，n / 2的同时，m \* 3, k \* 3  
k能被2整除一次，k / 2的同时，m \* 2, n \* 3  
所以结果为1 + 2 + 1 = 4

#include <iostream>
    
    using namespace std;
    
    int div2cnt(int x)
    {
        int cnt = 0;
        while(0 == x % 2)
        {
            cnt++;
            x /= 2;
        }
    
        return cnt;
    }
    
    int main()
    {
        int n;
        cin >> n;
        int a[n];
        int ans = 0;
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
            ans += div2cnt(a[i]);
        }
    
        cout << ans << endl;
    
    
        return 0;
    }

# D题 #

beauty, tastiness, popularity这三个属性，都可能是正数或负数。所以可取的正负号有8种情况，如下所示

for (int i = 0; i < 8; i++)
        {
            for (int k = 0; k < 3; k++)
            {
                cout << (i / (1 << k)) % 2 << ' ';
            }
            cout << endl;
        }

运行结果：

0 0 0
    1 0 0
    0 1 0
    1 1 0
    0 0 1
    1 0 1
    0 1 1
    1 1 1

这里可取0为正，1为负（当然也可以取0为负，1为正），  
第一行`0 0 0`表示beauty的值为正，tastiness的值为正，popularity的值为正  
第一行`1 0 0`表示beauty的值为负，tastiness的值为正，popularity的值为正  
……

枚举这八种正负号的情况，即可以得到结果

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    long long N, M, a[100009][3], maxn = -(1LL << 60);
    
    int main()
    {
        cin >> N >> M;
        for (int i = 1; i <= N; i++)
        {
            for (int j = 0; j < 3; j++)
                cin >> a[i][j];
        }
    
        for (int i = 0; i < 8; i++)
        {
            vector<long long>vec;
            for (int j = 1; j <= N; j++)
            {
                long long S = 0;
                for (int k = 0; k < 3; k++)
                {
                    if ((i / (1 << k)) % 2 == 0)
                        S += a[j][k];
                    else
                        S -= a[j][k];
                }
                vec.push_back(S);
            }
    
            sort(vec.begin(), vec.end());
            reverse(vec.begin(), vec.end());
    
            long long ans = 0;
            for (int j = 0; j < M; j++)
            {
                ans += vec[j];
            }
    
            maxn = max(maxn, ans);
        }
    
        cout << maxn << endl;
        return 0;
    }

> TopCoder & Codeforces & AtCoder交流QQ群：648202993  
> 更多内容请关注微信公众号  
> ![wechat\_public\_header.jpg][wechat_public_header.jpg]

[https_beta.atcoder.jp_contests_abc100_tasks]: https://beta.atcoder.jp/contests/abc100/tasks
[wechat_public_header.jpg]: /images/20220522/f765c48ff05d4c9ba3d6d45b0d9191da.png