专栏首页海天一树AtCoder Beginner Contest 100 完整解题报告

AtCoder Beginner Contest 100 完整解题报告

题目链接

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;
}

本文分享自微信公众号 - 海天一树(gh_de7b45c40e8b)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-06-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员必须掌握的8大排序算法

    分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)...

    海天一树
  • Codeforces 977D 题解报告

    http://codeforces.com/contest/977/problem/D

    海天一树
  • AtCoder Beginner Contest 101 完整解题报告

    分析:因为最小的数为1,最终所有的数必然全变为1。计算1左边和右边的数各分为多少段,加起来即可得到结果。 假设1位于第i个位置,则左边的分段为(i - 1) /...

    海天一树
  • 程序员面试金典 - 面试题 10.10. 数字流的秩(map/树状数组)

    假设你正在读取一串整数。每隔一段时间,你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。

    Michael阿明
  • 【Codeforces 723C】Polycarp at the Radio 贪心

    n个数,用最少的次数来改变数字,使得1到m出现的次数的最小值最大。输出最小值和改变次数以及改变后的数组。

    饶文津
  • MCU SPI屏也能跑这么炫酷的特效?来,移植起来秀一秀

    最近智能小车的项目还在加功能调试中,等后续调试完毕后更文。今天咱们就来分享一个在Github上看到的非常有意思的GUI开源项目。

    morixinguan
  • C++初始化

    Qt君
  • POJ 刷题系列:1753. Flip Game

    POJ 刷题系列:1753. Flip Game 传送门:POJ 1753. Filp Game 题意: 一个4*4的矩阵,每一格要么是白色,要么是黑色。现在...

    用户1147447
  • 程序员进阶之算法练习(三十五)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的...

    落影
  • 程序员进阶之算法练习(三十五)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的边...

    落影

扫码关注云+社区

领取腾讯云代金券