A Flower_Rainbow_and_Magic
知识点：构造、平均数性质、坐标
令输入点为 $P=(x,y,z)$。直接取
$$A=(x-1,y-1,z-1),\qquad B=(x+1,y+1,z+1).$$
两点显然不同，且它们每一维坐标的平均值都恰为对应的 $P$ 坐标，因此中点就是 $P$。
时间复杂度 $\mathcal{O}(1)$。
void solve() {
int x, y, z;
cin >> x >> y >> z;
cout << x - 1 << " " << y - 1 << " " << z - 1 << " "
<< x + 1 << " " << y + 1 << " " << z + 1 << endl;
}B Flower_Rainbow_and_Pets
知识点：枚举、分类讨论、最优化
设 $i,j$ 分别为用于狗粮与猫粮的优惠券数。
每张狗粮券必须对应 $3$ 袋食物：其中 $2$ 袋付费、$1$ 袋免费。若使用 $i$ 张狗粮券，则有 $3i$ 袋参与活动，其余 $n-3i$ 袋原价购买，因此狗粮花费为
$$(n-3i)x+2ix=(n-i)x.$$
同理，猫粮的一张券对应 $4$ 袋食物：其中 $3$ 袋付费、$1$ 袋免费。若使用 $j$ 张猫粮券，则猫粮花费为
$$(m-4j)y+3jy=(m-j)y.$$
两类优惠互不影响，唯一的耦合是它们共用 $k$ 张券。故 $i,j$ 必须满足
$$0\le i,\quad 3i\le n,\quad 0\le j,\quad 4j\le m,\quad i+j\le k.$$
前两项保证每张券都能凑满对应的活动份数，最后一项保证优惠券总数不超限。对于任意一组合法的 $i,j$，总花费就是
$$(n-i)x+(m-j)y.$$
因此直接枚举狗粮券数 $i$ 与猫粮券数 $j$，在所有合法组合中取最小值即可。由于条件是“最多”使用 $k$ 张，枚举 $i+j\le k$ 即可自然覆盖不使用全部优惠券的情况。
时间复杂度 $\mathcal{O}(k^2)$。
constexpr int inf = 2e18 + 9;
void solve() {
int n, m, x, y, k;
cin >> n >> m >> x >> y >> k;
int ans = inf;
for (int i = 0; i <= k && 3 * i <= n; ++i)
for (int j = 0; i + j <= k && 4 * j <= m; ++j)
ans = min(ans, (n - i) * x + (m - j) * y);
cout << ans << endl;
}C Flower_Rainbow_and_Farness
知识点：贪心、曼哈顿距离、构造
横纵坐标可以独立处理。若 $x_1<x_2$，就把 $\texttt{L}$ 交给 Alice、$\texttt{R}$ 交给 Bob；反之交换分配。这样每条水平指令都会使 $|x_1-x_2|$ 增加 $1$；相等时固定任选一侧作为外侧即可。
竖直方向同理：根据 $y_1<y_2$ 决定 $\texttt{U},\texttt{D}$ 分别交给谁。于是每个指令都在其对应维度上把两人向外推，最终距离达到最大值，同时输出记录下来的 $\texttt{A}/\texttt{B}$ 分配串即可。
时间复杂度 $\mathcal{O}(n)$。
void solve() {
int n, x1, y1, x2, y2;
string s;
cin >> n >> x1 >> y1 >> x2 >> y2 >> s;
bool f1 = x1 < x2, f2 = y1 < y2;
string ans = "";
for (auto v : s) {
if (v == 'L') f1 ? (ans += 'A', x1--) : (ans += 'B', x2--);
if (v == 'R') f1 ? (ans += 'B', x2++) : (ans += 'A', x1++);
if (v == 'U') f2 ? (ans += 'B', y2++) : (ans += 'A', y1++);
if (v == 'D') f2 ? (ans += 'A', y1--) : (ans += 'B', y2--);
}
cout << llabs(x1 - x2) + llabs(y1 - y2) << endl;
cout << ans << endl;
}D Flower_Rainbow_and_Grid
知识点：二分答案、阈值计数、平方和
记第 $i$ 行第 $j$ 列的数为
$$a_{i,j}=i^2-j^2.$$
若能知道第 $k$ 大数的值 $p$，那么所有大于 $p$ 的数一定要选，剩余位置只需从等于 $p$ 的数中补足。对任意候选阈值 $x$，定义统计函数
$$C(x)=\left|{(i,j)\mid i^2-j^2\ge x}\right|.$$
随着阈值 $x$ 增大，满足条件的元素只会减少，所以 $C(x)$ 单调不增。二分最大的 $p$，满足
$$C(p)\ge k.$$
此时 $p$ 就是第 $k$ 大元素的值。
接下来考虑如何计算 $C(x)$。固定第 $i$ 行，需要满足
$$i^2-j^2\ge x\iff j^2\le i^2-x.$$
令 $d=i^2-x$。当 $d\le0$ 时，本行没有合法列；否则 $j$ 最大可以取到 $\lfloor\sqrt d\rfloor$，同时不能超过列数 $m$。故本行贡献为
$$r_i=\begin{cases}\min\left(m,\left\lfloor\sqrt{i^2-x}\right\rfloor\right),&i^2-x>0,\\0,&i^2-x\le0.\end{cases}$$
枚举所有行并累加 $r_i$，即可得到 $C(x)$。二分阶段只关心计数是否达到 $k$，因此达到 $k$ 后可以直接返回。
求出阈值 $p$ 后，再计算所有不小于 $p$ 的元素和。第 $i$ 行有 $r_i$ 个这样的元素，分别对应 $j=1,2,\dots,r_i$，其贡献为
$$\begin{aligned}\sum_{j=1}^{r_i}(i^2-j^2)&=r_i i^2-\sum_{j=1}^{r_i}j^2\\&=r_i i^2-\frac{r_i(r_i+1)(2r_i+1)}{6}.\end{aligned}$$
将各行贡献相加，得到所有不小于 $p$ 的元素之和 $S$。此时可能多取了一些元素：由于 $p$ 是满足 $C(p)\ge k$ 的最大阈值，有 $C(p+1)<k$，因此多出的 $C(p)-k$ 个元素只能都等于 $p$。最终答案为
$$S-(C(p)-k)p.$$
时间复杂度 $\mathcal{O}\left(n\log(n^2+m^2)\right)$。
int mysqrt(int n) {
assert(n >= 0);
int ans = sqrtl(n);
while ((__int128)(ans + 1) * (ans + 1) <= n) ans++;
while ((__int128)ans * ans > n) ans--;
return ans;
}
void solve() {
int n, m, k;
cin >> n >> m >> k;
int lo = 1 - m * m, hi = n * n - 1, ans = lo;
auto calc = [&](int x, bool f) {
int cnt = 0;
for (int i = 1; i <= n; ++i) {
int d = i * i - x, t = (d > 0 ? min(m, mysqrt(d)) : 0);
cnt += t;
if (f && cnt >= k) return k;
}
return cnt;
};
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (calc(mid, 1) >= k)
ans = mid, lo = mid + 1;
else
hi = mid - 1;
}
int cnt = calc(ans, 0), sum = 0;
for (int i = 1; i <= n; ++i) {
int d = i * i - ans, t = (d > 0 ? min(m, mysqrt(d)) : 0LL);
sum += t * i * i - t * (t + 1) * (2 * t + 1) / 6;
}
cout << sum - (cnt - k) * ans << endl;
}E Flower_Rainbow_and_Aurora
知识点：反图建边、BFS、状态图
定义状态 $(i,j,p)$：当前位于格子 $(i,j)$，且序列相对初始序列已经循环左移 $p$ 次，其中 $p\in{0,1,2}$。若以步长 $\ell\in{1,2,3}$ 移动到格子 $(i’,j’)$，则必须满足
$$g_{i’,j’}=s_{(p+\ell-1)\bmod3},$$
且操作结束后的状态变为 $(i’,j’,(p+1)\bmod3)$。
令 $dis_{i,j,p}$ 表示状态 $(i,j,p)$ 到终点的最少操作次数。终点 $(n,m)$ 在任意移位状态下都已经完成，因此令全部 $dis_{n,m,p}=0$ 并作为反图 $\texttt{BFS}$ 的起点。
考虑反向转移。若当前状态为 $(i,j,q)$，其中 $q$ 为该状态的移位量，则其前驱状态的移位量为 $p=(q+2)\bmod3$；枚举步长 $\ell$ 与方向后，前驱格子就是从 $(i,j)$ 向反方向走 $\ell$ 步得到的格子。字符条件检查 $g_{i,j}$，因为 $(i,j)$ 正是正向操作的落点。
反图中的每条边都对应一次原操作，故 $\texttt{BFS}$ 得到的 $dis_{i,j,p}$ 就是最少操作次数，所求答案为每个格子的 $dis_{i,j,0}$。
时间复杂度 $\mathcal{O}(nm)$。
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
void solve() {
int n, m;
string s;
cin >> n >> m >> s;
vector<string> g(n);
for (auto &v : g) cin >> v;
vector<vector<array<int, 3>>> dis(
n, vector<array<int, 3>>(m, array<int, 3>{-1, -1, -1}));
queue<array<int, 3>> q;
for (int p = 0; p < 3; ++p) {
dis[n - 1][m - 1][p] = 0;
q.push({n - 1, m - 1, p});
}
auto check = [&](int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; };
while (q.size()) {
auto [x, y, now] = q.front();
q.pop();
int pre = (now + 2) % 3;
for (int len = 1; len <= 3; ++len) {
if (g[x][y] != s[(pre + len - 1) % 3]) continue;
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k] * len, ny = y + dy[k] * len;
if (check(nx, ny) && dis[nx][ny][pre] == -1) {
dis[nx][ny][pre] = dis[x][y][now] + 1;
q.push({nx, ny, pre});
}
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << dis[i][j][0] << " \n"[j + 1 == m];
}
}
}F Flower_Rainbow_and_Sweet
知识点：LCA、树上贪心、可并堆、后序遍历
将树以 $1$ 为根，并令节点 $u$ 的深度为 $dep_u$，其中根的深度为 $1$。对每种颜色 $x$，记其出现次数为 $cnt_x$，并记该颜色所有出现节点的最近公共祖先为
$$h_x=\operatorname{LCA}\left({v\mid c_v=x}\right),\qquad cnt_x=\left|{v\mid c_v=x}\right|.$$
固定节点 $u$ 后，颜色 $x$ 能作为一个完整种类被选择，当且仅当该颜色的全部出现位置都在 $u$ 的子树中。这个条件恰好等价于 $h_x\in\operatorname{subtree}(u)$：若所有出现位置都在其中，它们的 $\operatorname{LCA}$ 也必然在其中；反过来，$h_x$ 是所有出现位置的祖先，若 $h_x$ 在 $u$ 的子树中，则所有出现位置也都在其中。
于是将代价 $cnt_x$ 挂在 $h_x$ 上。设
$$\mathcal{C}_u={x\mid h_x\in\operatorname{subtree}(u)}.$$
那么固定 $u$ 时，需要解决的就是
$$\max_{T\subseteq\mathcal C_u} \left\{|T|\ \middle|\ \sum_{x\in T}cnt_x\le W\right\}.$$
其中 $T$ 表示最终保留的颜色集合。也就是说，在所有可选颜色中，以出现次数为代价，选出尽量多种颜色。
按后序遍历处理节点。对每个节点 $u$，维护一个可并大根堆 $\mathcal{H}_u$ 与其元素和 $\sigma_u$；堆中存放的是已经保留的颜色代价。处理 $u$ 时，先合并所有儿子 $v$ 的 $\mathcal{H}_v$，再将所有满足 $h_x=u$ 的 $cnt_x$ 加入其中。此时该堆的候选元素恰好对应集合 $\mathcal{C}_u$。
对 $\mathcal{C}_u$ 的候选代价从小到大排序，$w_r$ 表示第 $r$ 小候选代价。令 $q_u$ 表示节点 $u$ 能保留的最大颜色数，$q$ 表示待检验的保留颜色数，则
$$q_u=\max\left\{q\ \middle|\ \sum_{r=1}^{q}w_r\le W\right\}.$$
因此只需保留最小的若干代价。每次加入或合并候选后，若 $\sigma_u>W$，就从 $\mathcal{H}_u$ 删除最大代价并同步减少 $\sigma_u$。这样留下的集合在相同颜色数量下总代价最小；若连这些最小代价都无法容纳，就不可能保留更多颜色。
这种局部删弃不会影响祖先。对于儿子 $v$，$\mathcal{H}_v$ 保留的是该子树中代价最小的 $q_v$ 个可行颜色；任意可行方案从该子树选出的颜色数都不可能超过 $q_v$。若祖先需要从该子树保留 $r\le q_v$ 种颜色，直接取 $\mathcal{H}_v$ 中代价最小的 $r$ 种一定不劣于取任何被删去的颜色，因此合并这些堆后继续执行同样的删除操作仍然正确。
于是 $|\mathcal{H}_u|=q_u$，节点 $u$ 的贡献为 $dep_u\cdot q_u$，答案为
$$\max_u\left(dep_u\cdot q_u\right).$$
配对堆支持高效合并儿子的堆；每种颜色只会被压入 $1$ 次、弹出至多 $1$ 次。
时间复杂度 $\mathcal{O}(n\log n)$。
struct Tree {...} // LCA
#include <ext/pb_ds/priority_queue.hpp>
using Heap = __gnu_pbds::priority_queue<int, less<int>, __gnu_pbds::pairing_heap_tag>;
void solve() {
int n, W;
cin >> n >> W;
vector<int> c(n + 1);
for (int i = 1; i <= n; ++i) cin >> c[i];
Tree tr(n);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
tr.add(u, v);
}
tr.work(1);
vector<int> hub(n + 1), cnt(n + 1);
for (int i = 1; i <= n; ++i) {
int x = c[i];
++cnt[x];
if (!hub[x])
hub[x] = i;
else
hub[x] = tr.lca(hub[x], i);
}
vector<vector<int>> add(n + 1);
for (int x = 1; x <= n; ++x) {
if (cnt[x]) add[hub[x]].push_back(cnt[x]);
}
vector<int> ord = {1};
for (int i = 0; i < (int)ord.size(); ++i) {
int u = ord[i];
for (auto v : tr.ver[u]) {
if (tr.val[v][0] == u) ord.push_back(v);
}
}
vector<Heap> hp(n + 1);
vector<int> sum(n + 1);
int ans = 0;
for (int i = n - 1; i >= 0; --i) {
int u = ord[i];
for (auto v : tr.ver[u]) {
if (tr.val[v][0] != u) continue;
hp[u].join(hp[v]);
sum[u] += sum[v];
sum[v] = 0;
}
for (int x : add[u]) {
hp[u].push(x);
sum[u] += x;
}
while (sum[u] > W) {
sum[u] -= hp[u].top();
hp[u].pop();
}
ans = max(ans, tr.dep[u] * (int)hp[u].size());
}
cout << ans << endl;
}约定
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int, 2>
#define endl "\n"
void solve() {
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(20);
int t = 1;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}使用到的算法模板见 $\texttt{github}$ 仓库 林月的XCPC模板库