C.Centers
参考算法
统计，排序
\(\rm Syx\) 给你 \(3 \times N\) 个数，其中 \(\rm Syx\) 可以保证：\(1 \sim N\) 之间的所有数都出现了 \(3\) 次，请你将 \(1 \sim N\) 之间的数每个出现在第 \(2\) 个位置的下标进行排序，并从小到大输出原数。
用 \(\rm map\) 记录数出现的次数，当一个数第二次出现时（当 \(\rm map[x]=2\) 时）把 \(x\) 和下标 \(i\) 加入答案，最后按 \(i\) 排序，输出 \(x\)。
参考代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
using PII = pair<int, int>;
int n;
vector<PII> pos;
map<int, int> m;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1, x; i <= n * 3; i++) {
cin >> x;
m[x]++;
if (m[x] == 2) {
pos.push_back(make_pair(x, i));
}
}
sort(pos.begin(), pos.end(), [&](PII a, PII b) {
return a.second < b.second;
});
for (auto &i : pos) {
cout << i.first << ' ';
}
return 0;
}
D.Poisonous Full-Course
参考算法
动态规划，线性 \(\rm dp\)
高桥君决定去一家诡异的饭店，享用包含 $ N $ 道菜的套餐。每道菜有两个属性 $ X, Y $，含义如下：
- $ X_i = 0 $ 表示第 $ i $ 道菜有解毒功效；
- $ X_i = 1 $ 表示第 $ i $ 道菜有毒；
- $ Y_i $ 表示第 $ i $ 道菜的美味程度。
高桥君每品尝一道菜，他的身体状况就会发生如下的变化：
- 起初，高桥君感到舒适。
- 当他感到舒适之时，
- 如果他吃了一道有解毒功效的菜，他依然会感到舒适；
- 如果他吃了一道有毒的菜，他就会感到不适。
- 当他感到不适之时，
- 如果他吃了一道有解毒功效的菜，他就然会感到舒适；
- 如果他吃了一道有毒的菜，他就会当场去世。
菜是一道一道上的，对于第 $ i $ 道菜，用餐流程如下：
- 首先，上菜。
- 然后，高桥君可以选择品尝或选择跳过这道菜。
- 如果他选择品尝这道菜，他的身体状况就会随着前文提及的规则改变。
- 如果他选择跳过这道菜，这道菜不会留在餐桌上，之后也不会再上这道菜（即再也吃不到这道菜）。
- 在做出上述选择后，如果高桥君还活着，
- 如果 $ i \neq N $，上第 $ i + 1 $ 道菜，继续上述流程。
- 如果 $ i = N $，高桥君就可以活着走出饭店。
高桥君还有一个重要的会议要开，所以他必须活着走出饭店。
现在，请你求出高桥君所品尝的菜肴的美味程度之和的最大值（如果他什么也不吃，我们认为答案为 $ 0 $）。
注意题目中 \(1\) 表示有毒。
这是一道动态规划的题，我们用 \(dp[i][0/1]\) 表示高桥君吃完第 \(i\) 道菜后 舒适/不适 的最大值。
当 \(X=0\)：
-
舒适：
- \(1.\) 高桥君感到舒适，跳过了这道菜
- \(2.\) 高桥君感到不适，跳过了这道菜
- \(3.\) 高桥君感到舒适，品尝了这道菜
- \(4.\) 高桥君感到不适，品尝了这道菜
其中 \(2\) 没有感到舒适，舍去。
状态转移方程为 \(dp[i][0]=\max \ \{dp[i-1][0], \ dp[i-1][0]+Y, \ dp[i-1][1]+Y \}\) -
不适：
显然是 $dp[i][1]=dp[i-1][1] $。
当 \(X=1\)：
-
舒适：
显然是 $dp[i][0]=dp[i-1][0] $。
-
不适：
- \(1.\) 高桥君感到舒适，跳过了这道菜
- \(2.\) 高桥君感到不适，跳过了这道菜
- \(3.\) 高桥君感到舒适，品尝了这道菜
- \(4.\) 高桥君感到不适，品尝了这道菜
其中 \(1\) 和 \(4\) 没有感到不适，舍去。
状态转移方程为 $dp[i][1]=\max \ {dp[i-1][1],dp[i-1][0]+Y } $
目标：\(\max \ \{dp[N][0],dp[N][1] \}\)
参考代码 $1$
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int dp[300005][2];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
int X, Y;
for (int i = 1; i <= n; i++) {
cin >> X >> Y;
if (!X) {
dp[i][0] = max({dp[i - 1][0], dp[i - 1][0] + Y, dp[i - 1][1] + Y});
dp[i][1] = dp[i - 1][1];
} else {
dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + Y);
}
}
cout << max(dp[n][0], dp[n][1]) << '\n';
return 0;
}
参考代码 $2$
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int dp[2];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
int X, Y;
for (int i = 1; i <= n; i++) {
cin >> X >> Y;
if (!X) {
dp[0] = max({dp[0], dp[0] + Y, dp[1] + Y});
} else {
dp[1] = max(dp[1], dp[0] + Y);
}
}
cout << max(dp[0], dp[1]) << '\n';
return 0;
}