A. Maple and Multiplication
题意：给你\(a, b\)，每次可以让\(a\)乘以任何数或者让\(b\)乘以任何数，求\(a, b\)相等的最小操作数。
显然\(a, b\)都变成\(lcm(a, b)\)最优。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int a, b;std::cin >> a >> b;int c = std::lcm(a, b);std::cout << (a != c) + (b != c) << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
B. Cake Collection
题意：第\(i\)个位置每秒产生\(a_i\)价值，你每秒可以拿走一个位置累计的价值。求\(k\)秒后最大价值和。
如果\(k \leq n\)，那么按\(a_i\)从小到大拿最优，因为这样越大的数累计的次数越多。
如果\(k > n\)，多余的部分都拿最大的就行。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {i64 n, m;std::cin >> n >> m;std::vector<int> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}std::ranges::sort(a.begin(), a.end());i64 c = std::max(0ll, m - n);i64 ans = 0;m -= c;for (int i = 0; i < n; ++ i) {if (i >= n - m) {++ c;ans += c * a[i];}}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
C. Cake Assignment
题意：一开始两个人都有\(2^k\)，每次你让其中一个人分一半给另一个人，最后使得第一个人有\(x\)，第二个人有\(2^{k+1} - x\)。求方案。
从\((x, 2^{k+1} - x)\)这个状态\(bfs\)，找到\((2^k, 2^k)\)这个状态就结束，中间记录路径。
时间复杂度不会算，猜的。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {i64 k, x;std::cin >> k >> x;std::queue<std::pair<i64, i64>> q;q.emplace(x, (1ll << (k + 1)) - x);std::map<std::pair<i64, i64>, int> pre;std::map<std::pair<i64, i64>, int> d;pre[{x, (1ll << (k + 1)) - x}] = -1;d[{x, (1ll << (k + 1)) - x}] = 0;while (q.size()) {auto [a, b] = q.front(); q.pop();if (a == (1ll << k)) {break;}if (d[{a, b}] >= 120) {continue;}if (b > a) {i64 na = a * 2, nb = b - a;if (!pre.count({na, nb})) {pre[{na, nb}] = 1;d[{na, nb}] = d[{a, b}] + 1;q.emplace(na, nb);} } if (a > b) {i64 na = a - b, nb = b * 2;if (!pre.count({na, nb})) {pre[{na, nb}] = 2;d[{na, nb}] = d[{a, b}] + 1;q.emplace(na, nb);} }}std::vector<int> ans;i64 a = (1ll << k), b = (1ll << k);while (a != x) {ans.push_back(pre[{a, b}]);if (pre[{a, b}] == 1) {a /= 2;b += a;} else {b /= 2;a += b;}}std::cout << ans.size() << "\n";for (auto & x : ans) {std::cout << x << " ";}std::cout << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
D. Antiamuny Wants to Learn Swap
题意：对于一个数组，有两种操作方式，一种是每次交换\(a_i, a_{i+1}\)，使得数组升序的最小操作次数；一种是可以交换\(a_i, a_{i+1}\)或\(a_i, a_{i+2}\)使得数组升序的最小操作次数。如果两种操作的最小次数相等，这个数组就是好的。给你一个排列，每次问一个子数组是不是好的。
观察发现，如果有\(a_i \geq a_j \geq a_k\)，那么可以把\(a_i\)交换到\(a_{j-1}\)，\(a_i\)交换到\(a_{j+1}\)，然后交换\(a_{j-1}, a_{j+1}\)，这样就比只交换相邻两个数少一次操作。于是问题变为对于一个区间\([l, r]\)，有没有这样的\(i, j, k\)。
那么可以求出\(maxl_i, minr_i\)，分别表示大于\(a_i\)在\(i\)前面的最大位置和小于\(a_i\)在\(i\)后面的最小位置。
那么如果一个区间包含\([maxl_i, minr_i]\)，这个区间就不是好的。
这两个都可以用单调栈求，记\(R_i\)为\([maxl, minr]\)中\(maxl = i\)的最小的\(minr\)。那么对于一个子区间\([l, r]\)，如果有一个\(R_i\)小于等于\(r\)这个区间就不是好的，可以用\(st\)表预处理区间最值。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;template <class T>
struct ST {const T inf = std::numeric_limits<T>::max();;std::vector<std::vector<T>> min, max;ST(const std::vector<T> & a) {init(a);}void init(const std::vector<T> & a) {int n = a.size();int lg = std::__lg(n) + 1;min.assign(n, std::vector<T>(lg + 1, inf));max.assign(n, std::vector<T>(lg + 1, -inf));for (int i = 0; i < n; ++ i) {min[i][0] = max[i][0] = a[i];}for (int j = 1; j <= lg; ++ j) {for (int i = 0; i + (1 << j - 1) < n; ++ i) {min[i][j] = std::min(min[i][j - 1], min[i + (1 << j - 1)][j - 1]);max[i][j] = std::max(max[i][j - 1], max[i + (1 << j - 1)][j - 1]);}}} std::pair<T, T> query(int l, int r) {if (l > r) {return {inf, -inf};}int lg = std::__lg(r - l + 1);return {std::min(min[l][lg], min[r - (1 << lg) + 1][lg]), std::max(max[l][lg], max[r - (1 << lg) + 1][lg])};}
};void solve() {int n, q;std::cin >> n >> q;std::vector<int> a(n + 2);for (int i = 1; i <= n; ++ i) {std::cin >> a[i];}a[0] = a[n + 1] = 2e9;std::vector<int> stk;stk.push_back(0);std::vector<int> maxl(n + 2), maxr(n + 2);for (int i = 1; i <= n + 1; ++ i) {while (a[stk.back()] < a[i]) {maxr[stk.back()] = i - 1;stk.pop_back();}maxl[i] = stk.back() + 1;stk.push_back(i);}stk.clear();std::vector<int> minl(n + 2), minr(n + 2);a[0] = a[n + 1] = -2e9;stk.push_back(0);for (int i = 1; i <= n + 1; ++ i) {while (a[stk.back()] > a[i]) {minr[stk.back()] = i - 1;stk.pop_back();}minl[i] = stk.back() + 1;stk.push_back(i);}std::vector<int> R(n + 1, n + 1);for (int i = 1; i <= n; ++ i) {int l = maxl[i] - 1, r = minr[i] + 1;if (l >= 1 && r <= n) {R[l] = std::min(R[l], r);}}ST<int> st(R);while (q -- ) {int l, r;std::cin >> l >> r;if (st.query(l, r).first <= r) {std::cout << "NO\n";} else {std::cout << "YES\n";}}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
E1. Maple and Tree Beauty (Easy Version)
题意：一棵有根树，每个点的颜色要么是\(0\)要么是\(1\)，只知道有\(k\)个\(0\)和\(n-k\)个\(1\)。记一个点的名字为从根到这个点的路径上经过的点组成的\(01\)序列。求所有叶子的\(01\)序列的最长公共子序列。\(n \leq 1000\)。
记\(d_u\)为\(u\)的深度，那么答案肯定不超过叶子中的最小\(d\)。
对于每个\(01\)序列，如果其最长公共子序列某一位的位置在各自原序列里不是相同的，可以让它们的位置相同，例如\(00011\)和\(00101\)的最长公共子序列为\(000\)，发现第三个\(0\)在\(00011\)中是第\(3\)个位置，而在\(00101\)中是第\(4\)个位置，那么不妨把\(00101\)变为\(00011\)，这样最长公共子序列中每个元素的位置都能相同。
这就说明，对于某些深度\(d\)，我们可以让深度为\(d\)的点的颜色相同，能取到最优解。
那么\(cnt_i\)表示深度为\(i\)的点的个数，把所有\(cnt\)存入\(w\)中，然后从小到大排序。现在我们只需要从小到大枚举答案，如果答案是\(i\)，那么我们肯定选个数最少的前\(i\)层，然后背包\(dp\)，每层的个数看作体积，总共有\(k\)的容量，\(f[s]\)表示凑出\(s\)是否可行。记前\(i\)个最小的层点数总和为\(pre\)，那么我们选出作为\(0\)的点最少有\(max(0, pre - (n - k)\)个，最多有\(min(k, pre)\)个，看这个范围内有没有可行的。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k;std::cin >> n >> k;std::vector<int> p(n), leaf(n, 1);for (int i = 1; i < n; ++ i) {std::cin >> p[i];-- p[i];leaf[p[i]] = 0;}std::vector<int> d(n);for (int i = 1; i < n; ++ i) {d[i] = d[p[i]] + 1;}int m = n;for (int i = 0; i < n; ++ i) {if (leaf[i]) {m = std::min(m, d[i]);}}std::vector<int> cnt(m + 1);for (int i = 0; i < n; ++ i) {if (d[i] <= m) {cnt[d[i]] += 1;}}std::vector<int> w(m + 1);for (int i = 0; i <= m; ++ i) {w[i] = cnt[i];}std::ranges::sort(w);std::vector<int> f(k + 1, 0);f[0] = 1;int pre = 0;int ans = 0;for (int i = 0; i <= m; ++ i) {pre += w[i];for (int j = k; j >= w[i]; -- j) {f[j] |= f[j - w[i]];}for (int j = std::max(0, pre - (n - k)); j <= std::min(k, pre); ++ j) {if (f[j]) {ans = i + 1;break;}}}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
E2. Maple and Tree Beauty (Hard Version)
题意：和\(e1\)一样，不过\(n\)可以达到\(2e5\)。
还是一样的思路，考虑加速\(dp\)计算。可以分块，记块长为\(b=64\)，\(f[i]\)表示\(b*i\)到\(b*(i+1)-1\)这\(64\)个\(dp\)值的状态。
转移过程就可以位运算加速。然后可以让\(k=min(k, n -k)\)，这样时间复杂度为\(O(n\times\frac{k}{64})\)，\(k\)最多为\(\frac{n}{2}\)，最终就是\(O(n\times \frac{n}{128})\)。\(6s\)内可以通过。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;
using ui64 = unsigned long long;void solve() {int n, k;std::cin >> n >> k;k = std::min(k, n - k);std::vector<int> p(n), leaf(n, 1);for (int i = 1; i < n; ++ i) {std::cin >> p[i];-- p[i];leaf[p[i]] = 0;}std::vector<int> d(n);for (int i = 1; i < n; ++ i) {d[i] = d[p[i]] + 1;}int m = n;for (int i = 0; i < n; ++ i) {if (leaf[i]) {m = std::min(m, d[i]);}}std::vector<int> cnt(m + 1);for (int i = 0; i < n; ++ i) {if (d[i] <= m) {cnt[d[i]] += 1;}}std::vector<int> w(m + 1);for (int i = 0; i <= m; ++ i) {w[i] = cnt[i];}std::ranges::sort(w);int M = (k + 64) / 64;std::vector<ui64> f(M);f[0] = 1;int pre = 0;int ans = 0;for(int i = 0; i <= m; ++ i) {pre += w[i];int sw = w[i] >> 6;int sb = w[i] & 63;if(w[i] <= k){if(sb == 0){for(int j = M - 1; j >= sw; -- j){f[j] |= f[j - sw];}} else {for(int j = M - 1; j >= sw + 1; -- j){f[j] |= (f[j - sw] << sb) | (f[j - sw - 1] >> (64 - sb));}f[sw] |= (f[0] << sb);}}i64 LB = std::max(0, pre - (n - k));i64 HB = std::min(pre, k);if(LB <= HB){int L = LB >> 6, R = HB >> 6;ui64 maskL = (~0ULL) << (LB & 63);ui64 maskR = (~0ULL) >> (63 - (HB & 63));if(L == R){if(f[L] & (maskL & maskR)) {ans = i + 1;}} else {if(f[L] & maskL) {ans = i + 1;} else if(f[R] & maskR) {ans = i + 1;} else {for(int j = L + 1; j < R; ++ j){if (f[j]) {ans = i + 1;break;}}}}}}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}