Problem A. Maple and Multiplication
解答：
求最小公倍数模板题
\[lcm(a, b) = (a \times b) / gcd(a, b)
\]
核心代码：
int gcd(int a, int b)
{return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{return (a * b) / gcd(a, b);
}void solve()
{int a, b;cin >> a >> b;if(a == b){cout << 0 << '\n';return ;}int x = lcm(a, b);if(a == x || b == x){cout << 1 << '\n';return;}else cout << 2 << '\n';
}
Problem - B. Cake Collection
问题重述：
有 \(n\) 个位置，每个位置都有一个 a[i] 表示每秒该位置的增量，每秒都可以选择一个位置将这个位置的所有值拿走并清零
问 \(m\) 秒的时候一共可以拿走最大多少的值
解答：
正难则反
如果全部拿走，那么总和 sum = (a[1] + a[2] + ... + a[n]) * m
对 a[i] 从小到达排序
- 对于
m秒：我们拿最大的a[n]很显然是最优的，那么剩下的a[i]的和在最后一秒就剩下了，即left = a[1] + a[2] + ... + a[n - 1] - 对于
m - 1秒：我们拿最大的a[n - 1]很显然是最优的，因为a[n]必然会在第m秒被拿完，所以left = a[1] + a[2] + ... + a[n - 2] - 以此类推 ……
那么这个循环到什么时候截止呢？是 m 吗？
应该是 min(m, n - 1)
因为如果 n - 1 < m，那么在前面的 m - (n - 1) 轮中拿的数一定会在后面的 n - 1 轮拿到，可以看作是覆盖了
核心代码：
void solve()
{int n, m;cin >> n >> m;vector<int> a(n + 1);for(int i = 1; i <= n; i++)cin >> a[i];sort(a.begin(), a.end());for(int i = 1; i <= n; i++)a[i] += a[i - 1];int sum = a[n];sum *= m;int re = min(m, n - 1);int idx = n - 1;for(int i = 1; i <= re; i++){sum -= a[idx];idx--;} cout << sum << '\n';
}
Problem - C. Cake Assignment
题目重述：
一开始 c = v = 2 ^ k
有两个操作：
c /= 2, v += c (if c % 2 == 0)v /= 2, c += v (if v % 2 == 0)
最后使得 C = x, v = 2 ^ {k + 1} - x
解答：
对于这种与 2 的幂次有关的数，显然我们需要观察它的二进制形式
我们将 x 写成二进制形式
从 x 二进制中最低位的 1 往高走
- 如果有两个
1是连着的，那么如果c >>= 1，显然就会引入0，中间必然间隔0，所以只能是操作2 - 如果是
10的形式，显然对c进行除2即右移的操作
核心代码：
void solve()
{int k, x;cin >> k >> x;int c = 1ll << k, v = 1ll << k;string e = bitset<64>(x).to_string().substr(64 - k - 1);vector<int> step;int idx = e.size() - 1;while(idx >= 0 && e[idx] == '0') idx--;for(int i = idx - 1; i >= 0; i--){if(c == x)break;if(e[i] == '1'){step.push_back(2);v >>= 1, c += v;if(v > (1 << (k + 1))) v -= (1 << (k + 1));}else{step.push_back(1);c >>= 1, v += c;if(v > (1 << (k + 1))) v -= (1 << (k + 1));}}cout << step.size() << '\n';for(auto t : step){cout << t << " ";}cout << '\n';
}
Problem - D. Antiamuny Wants to Learn Swap
题目重述：
给定一个数组，和多次询问
每次询问，问对于其某个子数组，是否 交换相邻两个位置 和 交换相邻两个位置+交换一次间隔一个的位置 使之变成升序，是一样的步数
解答：
其实题目想问的是是否存在长度大于等于 3 的下降子序列
但是因为每次询问都会更换 [l, r] ，不可能对每一个子数组都求下降子序列，那样会 TLE
我们需要进行预处理：
对于每一个位置 i，在它的坐标找到离他最近的比它大的数，在它的右边找到离他最近的比它小的数（\(\color{red}{\text{可以用倍增加速}}\)）
这三个数构成了长度等于 3 的下降子序列
对于 r 记录 max(l)，表示包括的这个 “坏”区间，存在 L[r] 中
最后需要对 L 数组求前缀最大值⭐⭐
因为假设 L[7] = 5, L[8] = 4
- 当右端点为
8的区间包含5的时候一定是包含7的，也就是说，此时的“坏”区间应该从5开始而不是4 - 当右端点为
8的区间不包含5的时候也一定不会包含4
核心代码：
void solve()
{int n, q;cin >> n >> q;vector<int> a(n + 1);for(int i = 1; i <= n; i++) cin >> a[i];vector<int> lmax(n + 1), rmin(n + 1);for(int i = 1; i <= n; i++){lmax[i] = i - 1;while(lmax[i] > 0 && a[lmax[i]] < a[i])lmax[i] = lmax[lmax[i]];}for(int i = n; i >= 1; i--){rmin[i] = i + 1;while(rmin[i] <= n && a[rmin[i]] > a[i])rmin[i] = rmin[rmin[i]];}vector<int> L(n + 1, 0);for(int i = 1; i <= n; i++){if(rmin[i] <= n){L[rmin[i]] = max(L[rmin[i]], lmax[i]);}}for(int i = 1; i <= n; i++){L[i] = max(L[i], L[i - 1]);}while(q--){int l, r;cin >> l >> r;if(l <= L[r]) cout << "No" << '\n';else cout << "Yes" << '\n';}
}
Problem - E1. Maple and Tree Beauty (Easy Version)
题目重述：
有 k 个 0，n - k 个 1
问对一个树的节点填 0/1，所有从根到叶子的节点组成字符串，问最长公共前缀
解答：
显然需要一层都填一个数才能形成公共前缀
只有这一层的每一个节点都有子节点，才有可能往下扩展最长公共前缀
对于 k 和 n - k 是否够用的问题可以用 dp
dp[d][x] 表示到达 d 层还剩 x 个 0 的状态是否可行
核心代码：
void solve()
{int n, k;cin >> n >> k;vector<vector<int>> tree(n + 1);tree[0].push_back(1);for (int i = 2; i <= n; i++){int p; cin >> p;tree[p].push_back(i);}// 每层节点vector<vector<int>> hnum(n + 1);vector<int> h(n + 1, 0);// BFS 计算层次queue<int> q;q.push(1);h[1] = 0;hnum[0].push_back(1);int maxd = 0;while (!q.empty()){int u = q.front(); q.pop();for (int v : tree[u]){h[v] = h[u] + 1;if ((size_t)h[v] >= hnum.size()) hnum.resize(h[v] + 1);hnum[h[v]].push_back(v);maxd = max(maxd, h[v]);q.push(v);}}vector<int> layer_need(maxd + 2, 0);vector<char> layer_ok(maxd + 2, true);for (int d = 0; d <= maxd; d++){for (int u : hnum[d]){if (tree[u].empty()){layer_ok[d] = false;break;}}if (d + 1 <= maxd) layer_need[d] = (int)hnum[d + 1].size();else layer_need[d] = 0;}vector<vector<char>> dp(maxd + 2, vector<char>(k + 1, 0));dp[0][k] = 1;vector<int> pref(maxd + 2, 0);for (int i = 1; i <= maxd + 1; i++) pref[i] = pref[i - 1] + layer_need[i - 1];int ans = 1;for (int d = 0; d <= maxd; d++){for (int x = 0; x <= k; x++){if (!dp[d][x]) continue;ans = max<int>(ans, d + 1);if (!layer_ok[d]) continue;int need = layer_need[d]; int usedA = k - x; int totalNeededSoFar = pref[d]; int usedB = totalNeededSoFar - usedA; if (usedB < 0) usedB = 0; int leftB = (n - k) - usedB; if (x >= need) dp[d + 1][x - need] = 1;if (leftB >= need) dp[d + 1][x] = 1;}}cout << ans << '\n';
}