目录
C. Pigeonhole Query
E. Hierarchical Majority Vote
F. K-th Largest Triplet
C. Pigeonhole Query
首先，肯定不可能每一次操作后，遍历所有的巢，看哪些有多只。
正确思路是用一个数组（大小就是巢数） 实时模拟巢内有几只鸽子，一旦从 2 变 1 或从 1 变 2 答案实时变化。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5, INF = 1e18;int T, n, q, ans, num[N], bir[N];
string s;signed main()
{cin >> n >> q;for (int i = 1; i <= n; i ++)num[i] = 1, bir[i] = i;while (q --){int opt, p, h;cin >> opt;if (opt == 2){cout << ans << '\n';continue;}cin >> p >> h;num[bir[p]] --; // 第 p 只鸽子在哪个巢，那个巢就少一只鸽子if (num[bir[p]] == 1)ans --;bir[p] = h; // 鸽子换巢这一步不能少num[h] ++; // 新巢多一只鸽子if (num[h] == 2) ans ++;}return 0;
}E. Hierarchical Majority Vote
实质上是一个递推，从最底层往上推。
需要明确一点的是，我需要知道第 i 层的某一个位置它现在是 0 还是 1，但不需要知道改变顶层需不需要改变它。也就是说要把原始状态（就像一个金字塔）给写出来因为我在改变一个点的时候由它下方三个扩展得来。
dp[ i ][ j ] : 第 i 层第 j 个若要改变最小花费是多少：
· 下方三个都一样：至少改变两个，也就是在三个点要改变的花费中找最小和次小。转化为三个求和减掉最大
· 下方三个不一样，那就要看它自己是 0 还是 1，若是 0，那下方是必定是 0 0 1，那就是看两个 0 哪个改变的花费更少
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1594323 + 5, INF = 1e18, mod = 1e9 + 7;int T, n, cnt, ans, a[15][N], dp[2][N];
string s;signed main()
{int maxn = 1;cin >> n >> s;s = ' ' + s;for (int i = 1; i <= n; i ++)maxn *= 3;for (int i = 1; i <= maxn; i ++){a[0][i] = s[i] - '0';dp[0 & 1][i] = 1;}for (int i = 1; i <= n; i ++){maxn /= 3;for (int j = 1; j <= maxn; j ++){a[i][j] = a[i - 1][j * 3 - 2] == a[i - 1][j * 3 - 1] ? a[i - 1][j * 3 - 2] : a[i - 1][j * 3];if (a[i - 1][j * 3 - 2] == a[i - 1][j * 3 - 1] && a[i - 1][j * 3 - 2] == a[i - 1][j * 3]){dp[i & 1][j] = dp[(i - 1) & 1][j * 3 - 2] + dp[(i - 1) & 1][j * 3 - 1] + dp[(i - 1) & 1][j * 3];dp[i & 1][j] -= max(max(dp[(i - 1) & 1][j * 3 - 2], dp[(i - 1) & 1][j * 3 - 1]), dp[(i - 1) & 1][j * 3]);}else{dp[i & 1][j] = 1e9;for (int k = j * 3 - 2; k <= j * 3; k ++)if (a[i][j] == a[i - 1][k])dp[i & 1][j] = min(dp[i & 1][j], dp[(i - 1) & 1][k]);}}}cout << dp[n & 1][1];return 0;
}F. K-th Largest Triplet
思路是对 a, b, c 分别从大到小排序，那么三组的第一个相乘肯定是最大的，接下来就像 bfs 一样，a2 * b1 * c1、a1 * b2 * c2、a1 * b1 * c2 分别加入优先队列，一层层扩下去，但要注意可能会出现重复，用 set 去重就可以了。
语法上要会写结构体重载运算符号，并且 set 和 优先队列不能共用一个结构体，set 不含有 val，只看坐标。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;struct node
{int i, j, k, val;bool operator < (const node & other) const{return val < other.val;}
};struct tnode
{int i, j, k;bool operator < (const tnode & other) const{if (i != other.i) return i < other.i;if (j != other.j) return j < other.j;return k < other.k;}
};int T, n, k, cnt, ans, a[N], b[N], c[N];
string s;
priority_queue<node> pq;
set<tnode> se;bool cmp(int a, int b)
{return a > b;
}signed main()
{cin >> n >> k;for (int i = 1; i <= n; i ++) cin >> a[i];for (int i = 1; i <= n; i ++) cin >> b[i];for (int i = 1; i <= n; i ++) cin >> c[i];sort(a + 1, a + n + 1, cmp);sort(b + 1, b + n + 1, cmp);sort(c + 1, c + n + 1, cmp);int val = a[1] * b[1] + b[1] * c[1] + a[1] * c[1];pq.push({1, 1, 1, val}), se.insert({1, 1, 1});while (k --){node p = pq.top(); pq.pop();ans = p.val;if (p.i + 1 <= n){if (se.find({p.i + 1, p.j, p.k}) == se.end()){val = a[p.i + 1] * b[p.j] + b[p.j] * c[p.k] + a[p.i + 1] * c[p.k];pq.push({p.i + 1, p.j, p.k, val});se.insert({p.i + 1, p.j, p.k});}}if (p.j + 1 <= n){if (se.find({p.i, p.j + 1, p.k}) == se.end()){val = a[p.i] * b[p.j + 1] + b[p.j + 1] * c[p.k] + a[p.i] * c[p.k];pq.push({p.i, p.j + 1, p.k, val});se.insert({p.i, p.j + 1, p.k});}}if (p.k + 1 <= n){if (se.find({p.i, p.j, p.k + 1}) == se.end()){val = a[p.i] * b[p.j] + b[p.j] * c[p.k + 1] + a[p.i] * c[p.k + 1];pq.push({p.i, p.j, p.k + 1, val});se.insert({p.i, p.j, p.k + 1});}}}cout << ans;return 0;
}