题目链接
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 整除一次, 乘以 32 后也只能被 2 整除一次, 乘以 33 后只能被 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;
- }
来源: http://www.jianshu.com/p/18f98c3092a6