Atcoder account: x07cky
B: Base 2
题目描述:
给你 63 个数字 , 求出 .
实现:
可以在输入时就开始处理.
下面的代码使用 power = 1 来代替开始的 . 之后每一项只需要 power <<= 1; 即可.
记得使用 unsigned long long
#include <iostream>
int main() {
using namespace std;
unsigned long long power = 1;
unsigned long long result = 0;
for (int i = 0; i <= 63; i++) {
int x;
cin >> x;
result += x * power;
power <<= 1;
}
cout << result << endl;
return 0;
}
C: Centers
题目描述:
给定一个长度为 的数列, 其中 ~ 都会出现 次.
对这个数列进行处理, 找到这个数列里 个数第二次出现的位置, 并按出现位置进行排序, 并输出.
实现:
同样也是输入时就可以处理.
开一个 vector<int> a, a[i] 表示 第 个数出现了多少次. 如果为 次, 就 push 进 order 里.
最后输出这个 order.
#include <iostream>
#include <vector>
int main() {
using namespace std;
int n;
vector<int> a, order;
cin >> n;
a.resize(3 * n + 1, 0);
for (int i = 0, x; i < 3 * n; i++) {
cin >> x;
a[x]++;
if (a[x] == 2) {
order.push_back(x);
}
}
for (auto item : order) {
cout << item << " ";
}
cout << endl;
return 0;
}
D: Poisonous Full-Course
题目描述:
太长了自己看
给你一些有毒或者能解毒的菜, 每个菜都有它自己的美味值.
高桥先森开始时有一个健康的胃. 当他吃了一个有毒的菜之后, 他的胃会变 upset; 反之, 如果吃了一个解毒的菜, 胃就会变好. 如果他的胃是 upset 的并且他吃了一个有毒的菜, 他就会死. 求他在不死的情况下美味值最大是多少?
实现:
可以用 dp 来解决.
开一个数组 dp[_][2] , 其中 dp[i][0] 表示的是他在吃完前 个菜且他的胃是好的时候的美味度的最大值;
dp[i][1] 则代表胃是 upset 的时候的最大值. 死的情况不考虑, 因为高桥先森死了之后不可能再复活.
如果当前要是好的胃, 要么不吃, 要么只能吃解毒的菜. 所以
if 是解毒的菜 dp[i][0] = max(dp[i - 1][0], dp[i - 1][0] + 美味值, dp[i - 1][1] + 美味值)
else dp[i][0] = dp[i - 1][0]
如果当前要是 upset 的胃, 要么不吃, 要么只能吃有毒的菜, 且只能在之前是健康的胃时才能吃. 所以
if 是有毒的菜 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + 美味值)
else dp[i][1] = dp[i - 1][1]
最后在 dp[n][0] 和 dp[n][1] 中选一个最大的数即可.
记得开 long long !!! 否则会报 WA
完整代码:
#include <iostream>
#define ll long long
ll dp[300001][2], di[300001][2], n;
int main() {
using namespace std;
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> di[i][0] >> di[i][1];
}
for (ll i = 1; i <= n; i++) {
// dp[i][0]
dp[i][0] = dp[i - 1][0]; // 不吃
if (di[i][0] == 0) {
dp[i][0] = max(dp[i][0], max(dp[i - 1][0] + di[i][1], dp[i - 1][1] + di[i][1]));
}
// dp[i][1]
dp[i][1] = dp[i - 1][1]; // 不吃
if (di[i][0] == 1) {
dp[i][1] = max(dp[i][1], dp[i - 1][0] + di[i][1]);
}
}
cout << max(dp[n][0], dp[n][1]) << endl;
return 0;
}