AtCoder Beginner Contest 100 完整解题报告

海天一树

发布于 2018-07-25 12:26:17

3170

发布于 2018-07-25 12:26:17

文章被收录于专栏：海天一树

题目链接

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为正，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;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2018-06-18，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自海天一树微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度