Hi there 👋

数据结构题单 208. 实现 Trie (前缀树) 总共有 $3 \cdot 10^4$ 次插入，每个单词长度 $2000$，字母个数最多是 $6 \cdot 10^7$ 个，考虑到前缀重复的情况，估算字典树中的节点是 $3 \cdot 10^5$ 个 const int N = 300100; struct TrieTree { int n, idx; vector<VI> son; VI cnt; TrieTree() {} TrieTree(int _n) : n(_n), idx(0) { son = vector<VI>(n, VI(26, -1)); cnt = VI(n, 0); } void insert(string &s) { int p = 0; for (auto c : s) { int u = c - 'a'; if (son[p][u] == -1) son[p][u] = ++idx; p = son[p][u]; } cnt[p]++; } bool search(string &s) { int p = 0; for (auto c : s) { int u = c - 'a'; if (son[p][u] == -1) return false; p = son[p][u]; } return cnt[p] > 0; } bool starts_with(string &s) { int p = 0; for (auto c : s) { int u = c - 'a'; if (son[p][u] == -1) return false; p = son[p][u]; } return true; } }; class Trie { public: TrieTree tr; Trie() { tr = TrieTree(N); } void insert(string word) { tr.insert(word); } bool search(string word) { return tr.search(word); } bool startsWith(string prefix) { return tr.starts_with(prefix); } }; 更好的做法是使用动态创建节点的方式，避免估算不准确。 ...

数据结构题单 2102. 序列顺序查询 维护一个小顶堆 q1，代表前 k 大的元素。 维护一个大顶堆 q2，代表其它元素。 当新加一个元素的时候，首先加入 q2，当 q1 中不足 k 个元素的时候，把 q2 的最大元素移动到 q1。如果 q1 的堆顶小于 q2 的堆顶，此时应该交换堆顶，这个交换操作在一次函数调用中最多会发生一次，因为新加入元素的时候，只会产生一个元素的变化。 另外需要注意自定义对象的比较函数的时候，因为是求第 k 大，并且字典序最小，应该让分数正序排序，名字逆序排序，这样当分数相同的时候，靠后的是字典序更小的。 class SORTracker { public: struct node { int val; string name; bool operator<(const node &rh) const { if (val != rh.val) return val < rh.val; return name > rh.name; } bool operator>(const node &rh) const { if (val != rh.val) return val > rh.val; return name < rh.name; } }; pqg<node> q1; pq<node> q2; int cur; SORTracker() : q1{}, q2{}, cur{1} {} void add(string name, int score) { node tmp = {score, name}; q2.push(tmp); while (SZ(q1) < cur && nemp(q2)) { q1.push(q2.top()); q2.pop(); } while (nemp(q1) && nemp(q2) && q1.top() < q2.top()) { auto t1 = q1.top(); q1.pop(); auto t2 = q2.top(); q2.pop(); q1.push(t2); q2.push(t1); } } string get() { while (SZ(q1) < cur && nemp(q2)) { auto t = q2.top(); q1.push(t); q2.pop(); } cur++; return q1.top().name; } }; 题解区的神奇思路。 ...

位运算题单 477. 汉明距离总和 先考虑两个数字的情况，按位考虑，如果二进制位不同，那么对答案的贡献是 1. 接下来考虑多个数字的情况，同样按位考虑，对于某一位来说，设 0 的个数是 $c_1$，1 的个数是 $c_2$，那么这一位对答案的贡献是 $c_1 \cdot c_2$ int totalHammingDistance(vector<int> &a) { int ans{}; For1(i, 0, 30) { int c1{}, c2{}; for (auto x : a) { if ((x >> i) & 1) c1++; else c2++; } ans += c1 * c2; } return ans; } 1863. 找出所有子集的异或总和再求和 因为数组长度只有 12，考虑暴力，枚举所有的子集，暴力计算每个子集的异或和。 int subsetXORSum(vector<int> &a) { int n{SZ(a)}, ans{}; For(i, 0, (1 << n)) { int cur{}; For(j, 0, n) { if ((i >> j) & 1) { cur ^= a[j]; } } ans += cur; } return ans; } 题解区的神奇做法。 按位考虑，先考虑第 $i$ 位，如果一个集合中，第 $i$ 位是 1 的数字的个数是奇数，那么这个集合在第 $i$ 位对答案有贡献，并且贡献等于 $2^i$。 接下来考虑有多少个集合在第 $i$ 位对答案有贡献。也就是求有多少个集合，满足集合内的所有数字在第 $i$ 位是 1 的个数是奇数。设数组内所有数字在第 $i$ 位是 1 的个数是 $m$，那么包含至少一个 1 的集合的个数是 $2^m - 1$ 个。其中包含奇数个 1 的集合的个数是 $\sum{2^{n - m} {m \choose k}}$ 其中 $k$ 是奇数。根据二项式公式，能够得到当 $k$ 是奇数的二项式系数之和是 $2^{m - 1}$，因此上面的和是 $2^{n - 1}$. ...

滑动窗口题单 3. 无重复字符的最长子串 维护一个不定长的滑动窗口： 加入右端点 当不满足条件的时候不断移动左端点 维护答案 int lengthOfLongestSubstring(string s) { int ans{}, n = SZ(s); map<char, int> m; for (int i = 0, j = 0; i < n; ++i) { m[s[i]]++; while (m[s[i]] > 1 && j < i) m[s[j++]]--; ckmax(ans, i - j + 1); } return ans; } 题解区的另外一种写法。 当右端点在窗口中已经存在的时候，不断移动左指针，直到窗口中不存在右端点。 插入右端点 维护答案 int lengthOfLongestSubstring(string s) { int ans{}, n = SZ(s); set<char> vis; for (int i = 0, j = 0; i < n; ++i) { while (has(vis, s[i])) { vis.erase(s[j++]); } vis.insert(s[i]); ckmax(ans, i - j + 1); } return ans; } 3090. 每个字符最多出现两次的最长子字符串 当窗口中的右端点对应的字符出现了至少两次的时候，移动左指针，直到它出现小于两次 加入右端点 维护答案 int maximumLengthSubstring(string s) { VI a(26); int n{SZ(s)}, ans{}; for (int i = 0, j = 0; i < n; ++i) { while (a[s[i] - 'a'] >= 2) { a[s[j++] - 'a']--; } a[s[i] - 'a']++; ckmax(ans, i - j + 1); } return ans; } 1493. 删掉一个元素以后全为 1 的最长子数组 维护一个滑动窗口，满足窗口内部的 0 的个数最多有 1 个，求窗口内部去掉 1 个数字之后的连续的 1 的个数。 ...

二叉树题单 104. 二叉树的最大深度 深度从根开始往下递增，到达叶子的时候，深度达到最深，更新答案。 int ans; void dfs(TNP root, int d) { if (!root) return; auto [_, l, r] = *root; if (!l && !r) ckmax(ans, d); dfs(l, d + 1); dfs(r, d + 1); } int maxDepth(TreeNode *root) { ans = 0; dfs(root, 1); return ans; } 111. 二叉树的最小深度 从根往下访问，访问到孩子节点的时候，深度加一。到达叶子节点的时候更新答案。 int ans; void dfs(TNP root, int d) { if (!root) return; auto [_, l, r] = *root; if (!l && !r) ckmin(ans, d); dfs(l, d + 1); dfs(r, d + 1); } int minDepth(TreeNode *root) { ans = INF; dfs(root, 1); if (ans == INF) ans = 0; return ans; } 112. 路径总和 从根开始累加当前路径的和，如果到叶子的和与目标值相等，那么找到答案。 如果不是叶子，那么分别递归的左右子树。 int target; bool ans; void dfs(TNP root, int cur) { if (ans) return; if (!root) return; int val = root->val; auto left = root->left, right = root->right; if (!left && !right) { if (cur + val == target) { ans = true; return; } } else if (!left) { dfs(right, cur + val); } else if (!right) { dfs(left, cur + val); } else { dfs(left, cur + val); dfs(right, cur + val); } } bool hasPathSum(TreeNode *root, int targetSum) { target = targetSum; ans = false; dfs(root, 0); return ans; } 另外一种更好的思路：从根节点到叶子节点的过程中，不断从 targetSum 中减去当前节点的值，如果到达叶子的时候 targetSum 恰好等于叶子节点的值，那么找到了答案。否则递归左子树或者右子树。 ...

链表题单 206. 反转链表 p1 指向前一个节点，p2 指向当前节点，p3 指向下一个节点。 每次只修改 p2 节点，使它指向 p1，然后向右移动 p1, p2，p3 的作用是记录下一个 p2 的位置。 当 p2 为空时，说明整个链表反转结束。记得把原链表头的 next 指针置为空。 ListNode *reverseList(ListNode *head) { if (!head) return head; LNP p1 = head; LNP p2 = p1->next; LNP p3{NULL}; while (p2) { p3 = p2->next; p2->next = p1; p1 = p2; p2 = p3; } head->next = NULL; return p1; } 92. 反转链表 II 这道题目使用一次遍历看起来复杂，其实只要观察到边界条件，其实是不难，多使用几个变量保存需要保存的信息更清晰。 首先我们需要找到要反转区间的前一个位置 st，然后找到反转区间的起点和终点 q1, q2，然后找到反转区间的下一个节点 en。找到 st 需要从 ro 节点走 left - 1 步，找到 q2 节点需要从 ro 节点走 r 步。这两步可以使用一次遍历得到。接下来就是常规的反转链表。 ListNode *reverseBetween(ListNode *head, int left, int right) { LNP ro{new LN(0, head)}; LNP p1{ro}; int cnt{}; while (cnt < left - 1) { cnt++; p1 = p1->next; } LNP st = p1; LNP q1{st->next}; LNP p2{p1->next}; LNP p3{}; while (cnt < right) { p3 = p2->next; p2->next = p1; p1 = p2; p2 = p3; cnt++; } LNP q2{p1}; LNP en{p2}; st->next = q2; q1->next = en; LNP res = ro->next; delete ro; return res; } 24. 两两交换链表中的节点 这道题和反转一个区间内的链表类似，只不过区间长度是 2。 ...

最长公共后缀查询 要求最长的公共后缀字符串，可以把每个字符串逆序，存到字典树里面，在字典树的节点上保存到达当前节点并且原字符串长度最短的字符串长度和下标。对于给定字符串，直接从字典树中查找当前字符串，把树上能够找到的最后一个节点上的信息返回即可。 初始化的时候，先找到字典树使用到的节点的最大值，只初始化使用到的节点，如果 memset 整个数组会超时。 // Date: Sun Mar 24 22:48:03 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif // For LeetCode #define LN ListNode #define LNP ListNode * #define TN TreeNode #define TNP TreeNode * #ifdef _DEBUG struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int val) : val(val), next(nullptr) {} ListNode(int val, ListNode *next) : val(val), next(next) {} }; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; #endif // End of LeetCode const int N = 500100; int idx, son[N][26]; struct po { int len, i; }; po val[N]; void Insert(string s, int i) { int p = 0, cur = SZ(s); auto &t = val[p]; if (!t.len || ckmin(t.len, cur)) { t = po{cur, i}; } for (auto c : s) { int u = c - 'a'; if (!son[p][u]) son[p][u] = ++idx; p = son[p][u]; auto &t = val[p]; if (!t.len || ckmin(t.len, cur)) { t = po{cur, i}; } } } int Find(string s) { int p = 0; for (auto c : s) { int u = c - 'a'; if (!son[p][u]) { break; } p = son[p][u]; } return val[p].i; } class Solution { public: vector<int> stringIndices(vector<string> &a, vector<string> &b) { int sum{}; for (auto s : a) sum += SZ(s); idx = 0; For1(i, 0, sum) { For(j, 0, 26) son[i][j] = 0; val[i] = po{0, 0}; } int n = SZ(a); VI res; For(i, 0, n) { string s = a[i]; reverse(all(s)); Insert(s, i); } for (auto s : b) { reverse(all(s)); res.pb(Find(s)); } return res; } }; #ifdef _DEBUG int main(void) { std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); Solution a; return 0; } #endif

Tree Cutting 考虑从叶子节点开始切割，每次切割的时候只能切掉整颗子树，因此从叶子节点统计当前子树的节点的个数，当子树大小至少为 $x$ 的时候进行一次切割，最后切掉的子树的数量不少于 $k$。因为是从叶子节点考虑，所以可以考虑拓扑排序的过程，用 BFS 的思想从叶子开始切割。 更好的实现方式是从子树节点个数的角度考虑，这是一个经典的 DFS 问题，当子树的大小至少为 $x$ 时，此时进行一次切割，这个子树的大小不贡献给父节点。 DFS 实现，DFS 的过程中只需要记录上一次访问的节点就可以保证不重复访问。 // Date: Sat Mar 23 09:39:02 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } // int128 input and output #ifdef _DEBUG using lll = __int128; istream &operator>>(istream &is, lll &v) { string s; is >> s; v = 0; for (auto &it : s) if (isdigit(it)) v = v * 10 + it - '0'; if (s[0] == '-') v *= -1; return is; } ostream &operator<<(ostream &os, const lll &v) { if (v == 0) return (os << "0"); lll num = v; if (v < 0) os << '-', num = -num; string s; for (; num > 0; num /= 10) s.pb((char)(num % 10) + '0'); reverse(all(s)); return (os << s); } #endif // end of int128 void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 100100, M = 2 * N; int n, k, u, v, h[N], cnt; int idx, e[M], ne[M]; void Init() { idx = 0; memset(h, -1, sizeof h); } void Add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } int dfs(int u, int pre, int x) { int sum = 1; ForE(i, u) { int j = e[i]; if (j == pre) continue; sum += dfs(j, u, x); } if (sum >= x) { cnt++; sum = 0; } return sum; } bool check(int x) { cnt = 0; dfs(1, -1, x); return cnt >= k + 1; } void solve() { cin >> n >> k; Init(); For(i, 1, n) { cin >> u >> v; Add(u, v); Add(v, u); } int l = 1, r = 1e5 + 10, mid; while (l < r) { mid = (l + r + 1) / 2; if (check(mid)) l = mid; else r = mid - 1; } cout << l << '\n'; } int main(void) { #ifdef _DEBUG freopen("1946c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; } BFS 实现，类似拓扑排序的思想，把度数为 $1$ 的叶子节点加入队列，此时需要记录节点是否已经被访问过。 ...

Even-Odd XOR 很有意思的一道构造题。奇数位和偶数位的异或和相等，那么整个数组的异或和是 $0$。考虑简单的做法，如果 $a_1, a_2, \ldots, a_{n-1}$ 使用 $[1,n-1]$，那么 $a_n = 1 \oplus 2 \oplus \ldots \oplus (n-1)$，问题是 $a_n$ 可能会和 $[1,n-1]$ 中的某个数字相等。考虑异或运算的性质，令 $a_{n-2} = 2^{23}$，因为 $[1, n-3]$ 的异或和小于 $a_{n-2}$，这可以保证 $a_{n-2}$ 不和前面的数字重复。 同理令 $a_{n-1} = 2^{24}$，那么 $a_n$ 设置成前面所有数字的异或和。这样可以保证所有数字不同，并且所有数字的异或和是 $0$。 // Date: Tue Mar 5 21:55:44 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif void solve() { int n, cur = 0; cin >> n; For1(i, 1, n - 3) { cout << i << ' '; cur = cur ^ i; } int x = (1 << 23), y = (1 << 24); cout << x << ' '; cur = cur ^ x; cout << y << ' '; cur = cur ^ y; cout << cur << '\n'; } int main(void) { #ifdef _DEBUG freopen("1722g.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

Min-Max Array Transformation 第一问求 $d_{min}$ 很简单，只需要把 $b$ 排序，然后对 $a_i$ 找到最小的 $b_i \ge a_i$ 即可。 第二问很有意思，对于 $a_i$，需要找到尽量大的 $b_j \ge a_i$，同时满足 $a_{i+1}, \ldots, a_n$ 都能找到对应的匹配，同时尽可能小。我们可以对于每个 $a_j (j \ge i+1)$ 都找到最小的 $b_j \ge a_j$，然后从数组中删除这些 $b_j$，此时数组中剩余的最大值就可以匹配 $a_i$。我们可以发现，这样做不会让 $a_{i - 1}$ 的结果变差，在这个基础上，删除掉 $\ge a_i$ 的最小的 $b_j$ 之后，这恰好是 $a_{i - 1}$ 想要的 $b$ 数组。因此可以从右往左处理。 // Date: Fri Feb 2 23:06:22 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 200100; int n, a[N], b[N], d[N], d1[N]; multiset<int> s; void solve() { cin >> n; For1(i, 1, n) { cin >> a[i]; } sort(a + 1, a + 1 + n); s.clear(); For1(i, 1, n) { cin >> b[i]; s.insert(b[i]); } sort(b + 1, b + 1 + n); For1(i, 1, n) { int l = 1, r = n, mid; while (l < r) { mid = (l + r) / 2; if (b[mid] >= a[i]) r = mid; else l = mid + 1; } d[i] = r; } For1(i, 1, n) cout << b[d[i]] - a[i] << ' '; NL; Rof1(i, 1, n) { auto it = s.lower_bound(a[i]); d1[i] = *prev(s.end()) - a[i]; s.erase(it); } For1(i, 1, n) cout << d1[i] << ' '; NL; } int main(void) { #ifdef _DEBUG freopen("1721c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

Color the Picture 观察可以发现，最终答案中连续的相同颜色的列的数量一定大于等于 $2$。按照行染色同理。设颜色 $a_i$ 能够染色的列数是 $b_i = \lfloor \frac{a_i}{m} \rfloor$，需要构造 $b_1 + b_2 + \ldots + b_j = n, b_i \ge 2$。 考虑分解的思想，如果 $n$ 是偶数，设 $b_1 + b_2 + \ldots + b_k = sum$，如果有解，那么要求 $sum \ge n$。如果 $sum$ 是偶数，这意味着，奇数 $b_j$ 的个数为偶数个，如果 $sum > n$，那么把偶数 $b_j$ 拆分成 $2$，奇数 $b_j$ 拆分成若干个 $2$ 和一个 $1$，最后 $1$ 的个数是偶数个，先去掉偶数个 $1$，然后再考虑去掉 $2$，直到 $sum = n$。 用类似的方法可以解决 $n$ 和 $sum$ 的奇偶性的其它三种情况，最终得到答案。这种奇偶性转换和分解的构造思想很常见。 // 2024/1/30 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 100100; ll n, m, a[N], k, b[N]; void solve() { cin >> n >> m >> k; For1(i, 1, k) { cin >> a[i]; } sort(a + 1, a + 1 + k); ll tot = n * m; if (a[k] >= tot) { cout << "Yes\n"; return; } auto check = [&](ll n, ll m) -> bool { ll cnt = 0; bool found = false; For1(i, 1, k) { b[i] = a[i] / n; if (b[i] >= 2) cnt += b[i]; if (b[i] >= 3) found = true; } if (cnt < m) return false; if (m % 2 == 0) return true; return found; }; if (check(n, m) || check(m, n)) { cout << "Yes\n"; } else cout << "No\n"; } int main(void) { #ifdef _DEBUG freopen("input.txt", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

Turtle Fingers: Count the Values of k 枚举 $a^i$ 中的 $i$，然后枚举 $b^j$，求出对应的 $k$ 即可，由于 $l$ 的范围只有 $10^6$，暴力即可。 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } using lll = __int128; istream &operator>>(istream &is, lll &v) { string s; is >> s; v = 0; for (auto &it : s) if (isdigit(it)) v = v * 10 + it - '0'; if (s[0] == '-') v *= -1; return is; } ostream &operator<<(ostream &os, const lll &v) { if (v == 0) return (os << "0"); lll num = v; if (v < 0) os << '-', num = -num; string s; for (; num > 0; num /= 10) s.pb((char)(num % 10) + '0'); reverse(all(s)); return (os << s); } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif void solve() { ll a, b, l; cin >> a >> b >> l; set<int> s; int a1 = 1; while (a1 <= l) { if (l % a1 != 0) { a1 *= a; continue; } int l1 = l / a1, b1 = 1; while (l1 % b1 == 0) { s.insert(l1 / b1); b1 *= b; } a1 *= a; } cout << SZ(s) << '\n'; } int main(void) { std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

Qpwoeirut And The City 对于奇数长度的数组，为了让合法的元素最多，只有一种情况。 对于偶数长度的数组，如果把合法的点标记为 $1$，其它点标记为 $0$，可以发现 $0$ 和 $1$ 的排列规律，首先不能出现连续的 $1$，并且最多出现一次连续的两个 $0$，连续的两个 $0$ 出现的位置决定了最终的结果。 从 $a_2$ 开始，假设 $a_2 = 1, a_3 = 0, \ldots$ 这是一种情况。从 $a_{n - 1}$ 开始，假设 $a_{n - 1} = 1, a_{n - 2} = 0, \ldots$ 这是对称的另外一种情况。对这两种情况分别求出前缀和与后缀和，然后枚举 $i$，就可以求出答案。 // 2024/1/29 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 300100; int n; ll a[N], p[N], p1[N]; void solve() { cin >> n; For1(i, 1, n) { cin >> a[i]; } ll ans{}; auto check = [](int start) { ll ans = 0; for (int i = start; i <= n - 1; i += 2) { if (a[i] > a[i - 1] && a[i] > a[i + 1]) continue; ll top = max(a[i - 1], a[i + 1]) + 1; ans += top - a[i]; } return ans; }; if (n & 1) { ans = check(2); cout << ans << '\n'; return; } p[1] = 0; for (int i = 2; i <= n; i += 2) { ll top = max(a[i - 1], a[i + 1]) + 1, delta = max(top - a[i], 0LL); p[i] = p[i + 1] = delta + p[i - 1]; } p1[n] = 0; for (int i = n - 1; i >= 1; i -= 2) { ll top = max(a[i - 1], a[i + 1]) + 1, delta = max(top - a[i], 0LL); p1[i] = p1[i - 1] = delta + p1[i + 1]; } ans = -1; for (int i = 2; i <= n; i += 2) { ll tmp = p[i - 1] + p1[i]; if (ans == -1) ans = tmp; else ckmin(ans, tmp); } cout << ans << '\n'; } int main(void) { #ifdef _DEBUG // freopen("1706c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

Schedule Management 如果一个任务不能由最擅长它的员工完成，那么其他任何一个员工都是可以的，花费的时间都是 $2$，为了让总时间最小，应该让剩余时间多的员工优先完成，对于给定的总时间，尽量让每个员工的工作量是饱和的。可以发现判定某个总时间是否合法是可以通过上面的贪心思想 $O(n)$ 完成，因此可以二分答案。 // 2024/1/29 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 200100; int n, m, a[N], b[N]; bool check(int top) { int cnt {}; For1(i, 1, n) { if (b[i] > top) { cnt += (b[i] - top); } else if (cnt) { int rem = top - b[i]; rem /= 2; if (rem >= cnt) cnt = 0; else cnt -= rem; } } return !cnt; } void solve() { cin >> n >> m; fill(b, b + 1 + n, 0); For1(i, 1, m) { cin >> a[i]; b[a[i]]++; } sort(b + 1, b + 1 + n, greater<int>()); int l = 1, r = m, mid; while (l < r) { mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid + 1; } cout << r << '\n'; } int main(void) { #ifdef _DEBUG freopen("input.txt", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

awoo’s Favorite Problem 通过观察可以发现对于任何一个位置满足 $s(a) \ge t(a), s(c) \le t(c)$，这是因为字符 $a$ 可以通过任意次操作跨过字符 $b$ 往右移动，字符 $c$ 可以通过任意次操作跨过字符 $b$ 往左移动，同时字符 $a, c$ 的相对顺序并不会改变。因此，当把两个字符串中的 $b$ 字符全部去掉之后，两个字符串相等。 // Date: Wed Jan 24 23:26:41 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif void solve() { int n; string s, t, s1, t1; cin >> n >> s >> t; bool flag = true; int a1{}, a2{}, c1{}, c2{}; For(i, 0, n) { if (s[i] != 'b') s1 += s[i]; if (t[i] != 'b') t1 += t[i]; } if (s1 != t1) flag = false; For(i, 0, n) { if (s[i] == 'a') a1++; else if (s[i] == 'c') c1++; if (t[i] == 'a') a2++; else if (t[i] == 'c') c2++; if (a1 < a2 || c1 > c2) { flag = false; break; } if (a1 && a1 == a2) a1 = a2 = 0; if (c1 && c1 == c2) c1 = c2 = 0; } if (c1 || c2 || a1 || a2) flag = false; cout << (flag ? "YES" : "NO") << '\n'; } int main(void) { #ifdef _DEBUG freopen("1697c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }