G. 收集

由于稀有度相同的物品需要一起處理，我們先把他們聚集到一起。
類似這樣：

vector<int> g[maxn];
...
{cin >> x >> c;g[c].push_back(x);
}

那么我們需要一個貪心的思路：

• 肯定是按 $c$ 從小往大收集的；
• 對于相同的 $c$ 收集完最后一個肯定是要么停留最左邊要么停留在最右邊。

故設 $dp(i,0)$ 表示收集完稀有度為 $i$ 的物品后停留在最左邊，$dp(i,1)$ 則表示停留在最右邊。

對于轉移，則是討論一下：

• 收集完第 $i?1$ 層的物品后，在最左邊還是最右邊，將來要停留在這一層的最左邊還是最右邊，即 $dp(i?1,0/1)$ 轉移到 $dp(i,0/1)$。

注意的是，可能存在某一層是沒有物品的，而下一層是有物品的，需要存儲上一層的 c，設其為 pre。則狀態轉移使用 $dp[pre][]$ 而不是 $dp[i?1][]$

#include <bits/stdc++.h>
using namespace std;
#define ll long longll a[200010][2], x;
ll dp[200010][2]; // dp[i][0]: 從小到大走；dp[i][1]：從大往小走
bool vis[200010];
int main() {int n, c;cin >> n;for (int i = 1; i <= n; ++i) {a[i][0] = INT_MAX; // c == i 的位置最小值a[i][1] = INT_MIN; // c == i 的位置最大值}for (int i = 1; i <= n; ++i) {cin >> x >> c;a[c][0] = min(a[c][0], x);a[c][1] = max(a[c][1], x);vis[c] = 1;}int p = 0; // 前一個 cvis[n + 1] = 1; // 最后一層回到位置 0, a[n+1][0] = a[n+1][1] = 0for (int i = 1; i <= n + 1; ++i) {if (!vis[i]) continue;for (int j = 0; j < 2; ++j) {dp[i][j] = min(abs(a[p][0] - a[i][j]) + dp[p][1], abs(a[p][1] - a[i][j]) + dp[p][0]) + a[i][1] - a[i][0]; }p = i;}cout << dp[n + 1][0] << endl;return 0;
}

H. 選擇

對于每一個 $i$，我們考慮讓 $a_i$ 和 $b_i$ 之間建一條邊，則這些邊之間形成了若干個環
則原問題等價于對于每個環，任意兩條相鄰的邊至少選一條，不同的環之間沒有限制
dp 算出每個環選點的方案數，然后再乘起來，就是總的方案數

• 相信大家都會做一排物品，相鄰兩件至少選一件，求方案數記作 f[i]

• 現在處理環記作 g[i]，將下面兩個方案相加

  • 最后一個不選：f[i-3]
  • 最后一個選：f[i-1]

可以先遞推計算 f，再遞推計算 'g'

也可以整理得到： g[i] = f[i-3] + f[i-1] = (f[i-4]+f[i-5]) + (f[i-2]+f[i-3]) = (f[i-2]+f[i-4]) + (f[i-3]+f[i-5]) = g[i-1] + g[i-2]

#include <bits/stdc++.h>
using namespace std;using ll = long long;
const ll M = 998244353;
const int maxn = 2e5 + 10;// 相鄰的數至少選一個
// 線性：f[i] = f[i-2] + f[i-1]
// 環形：g[i] = f[i-3] + f[i-1] --> g[i] = g[i-1] + g[i-2]
ll g[maxn];
int a[maxn], bi, nxt[maxn];
bool vis[maxn];
int main() {g[1] = 1, g[2] = 3;for (int i = 3; i < maxn; ++i) {g[i] = (g[i - 1] + g[i - 2]) % M;}int n, x, b;cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= n; ++i) {cin >> bi;nxt[a[i]] = bi;}ll res = 1;for (int i = 1; i <= n; ++i) {if (!vis[i]) {int p = i, cnt = 0;while (!vis[p]) {vis[p] = 1, ++cnt;p = nxt[p];}res = res * g[cnt] % M;}}cout << res << endl;return 0;
}