|
点击查看《Cookies》题解详情附件1、解法1-dfs 程序填空#include <bits/stdc++.h>
using namespace std;
const int N = ___; // 最大孩子数
___ INF = 1e18; // 无限大值，用于初始化最小怨气
int n, m; // 孩子数、饼干总数
int g[___], idx[___]; // g[i]：孩子i的贪婪度；idx[i]：排序后第i个孩子的原始索引
int c[___]; // 当前分配方案，c[i]表示排序后第i个孩子分到的饼干数
int best_c[___]; // 最优分配方案
long long min_anger = ___; // 最小怨气总和
bool cmp(int a,int b) {
return ___;
}
/*
* 深度优先搜索枚举所有可能的分配方案
* pos：当前正在分配的孩子位置（排序后的索引）
* remaining：剩余的饼干数
* current_anger：当前已经产生的怨气（只考虑前pos-1个孩子）
*/
void dfs(int pos, int remaining, long long current_anger) {
// 如果所有孩子都已分配且饼干刚好用完，检查是否找到更优解
if (pos == ___) { //得到一种分配方案
if (remaining == ___ && current_anger ___ min_anger) {
___ // 更新最小怨气
for (int i = 1; i <= n; ++i) ___; // 保存最优分配方案
}
___
}
// 确定当前孩子饼干数的上限：
// 1. 不能超过剩余饼干数（因为后面每个孩子至少1块饼干，所以剩余饼干数必须至少为n-pos）
// 2. 为了保持分配序列非递增（这是最优解的性质），不能超过前一个孩子的饼干数（如果pos>1）
int max_val = ___; // 至少给后面每个孩子留 1 块饼干
if (pos > 1) max_val = min(___, ___); // 非递增约束
// 枚举当前孩子的饼干数（从大到小枚举，有助于更快找到较优解）
for (int val = ___; val >= 1; --val) {
c[pos] = ___; // 尝试分配 val 块饼干给当前孩子
// 计算当前孩子的怨气：统计前 pos-1 个孩子中饼干数大于 val 的数量
int a_i = ___;
for (int j = 1; j < pos; ++j) {
if (___) ___;
}
long long new_anger = ___ + 1LL * ___;
// 如果新怨气已经超过当前最优解，剪枝，不再继续搜索
if (___) ___;
// 递归搜索下一个孩子，剩余饼干数减少val，怨气更新为new_anger
dfs(___, ___, ___);
}
}
int main() {
freopen("Cookies.in", "r", stdin);
freopen("Cookies.out", "w", stdout);
cin >> n >> m; // 输入孩子数和饼干总数
// 输入每个孩子的贪婪度
for (int i = 1; i <= n; ++i) {
cin >> g[i];
idx[i] = ___; // 记录原始索引
}
// 将孩子按贪婪度降序排序（存在最优解使得分配序列与贪婪度降序对应）
sort(idx ___, idx ___, ___);
// 将贪婪度数组按照排序后的顺序重新排列，便于搜索时使用
int sorted_g[N];
for (int i = 1; i <= n; ++i) {
sorted_g[i] = ___;
}
memcpy(g, sorted_g, sizeof(sorted_g));
// 开始深度优先搜索
dfs(___, ___, ___);
// 输出最小怨气总和
cout << min_anger << endl;
// 将最优分配方案还原到原始孩子顺序
int final_ans[N];
for (int i = 1; i <= n; ++i)
final_ans[___] = ___;
// 输出每个孩子分到的饼干数
for (int i = 1; i <= n; ++i) {
cout << ___ << " ";
}
cout << endl;
return 0;
}
附件2、解法1-dp 程序填空#include <bits/stdc++.h>
using namespace std;
const int N = ___; // 最大孩子数
const int M = ___; // 最大饼干数
const long long INF = ___; // 无穷大，用于初始化DP
struct Child {
int id; // 原始编号
long long g; // 贪婪度
} children[___]; // 存储孩子信息
int n, m; // 孩子数量和饼干总数
long long g[___]; // 排序后的贪婪度数组
long long prefixSum[___]; // 贪婪度前缀和，用于快速计算区间和
long long dp[___][___]; // DP数组：dp[i][j]表示前i个孩子分配j块饼干的最小怨气
// 记录转移路径的结构体
struct Path {
int type; // 转移类型：0-整体加一，1-新增层级
int param; // 参数：type=0 时无用，type=1 时表示层级长度
int prev_i, prev_j; // 前一个状态
} path[___][___];
int allocation[___]; // 最终分配方案（排序后的顺序）
int originalAns[___]; // 最终分配方案（原始顺序）
/**
* 比较函数：按贪婪度降序排序
* 原理：根据交换论证，最优解中贪婪度大的孩子饼干数不少于贪婪度小的孩子
* 所以我们可以将孩子按贪婪度降序排序，然后只考虑非递增的分配方案
*/
bool compareChildren(___ a, ___ b) {
return ___;
}
/**
* 功能：回溯构造分配方案
* i 当前孩子数
* j 当前饼干数
*
* 从最终状态(n, m)开始回溯：
* 1. 如果是从整体加一转移过来的，说明前 i 个孩子的饼干数都加了 1
* 2. 如果是从新增层级转移过来的，说明最后 param 个孩子饼干数设为 1
*/
void reconstruct(int i, int j) {
// 记录每个孩子的基础饼干数（1或0）
vector<int> base(___, ___);
// 记录每个孩子额外加的饼干数（通过整体加一操作）
vector<int> add(___, ___);
// 从最终状态开始回溯，直到处理完所有孩子
while (___) {
Path p = path[___][___];
if (___) { // 类型0：整体加一转移
// 说明当前状态是通过给前 i 个孩子每人加一块饼干得到的
// 所以给前 i 个孩子的 add 值都加 1
for (int ___) {
add___;
}
} else { // 类型1：新增层级转移
// 说明最后 p.param 个孩子（从 i-p.param+1 到 i）饼干数设为 1
int len = ___;
for (int t = ___; t <= ___; t++) {
base[t] = ___; // 这些孩子的基础饼干数为 1
}
}
// 回溯到前一个状态
i = p.___;
j = ___
}
// 合并基础值和额外值，得到最终分配方案
for (int t = 1; t <= n; t++) allocation[t] = ___
}
int main() {
// freopen("Cookies.in", "r", stdin);
// freopen("Cookies.out", "w", stdout);
// 输入孩子数量和饼干总数
cin >> n >> m;
if (m % n == 0) {//特殊情况
___
return 0;
}
// 输入每个孩子的贪婪度
for (int i = 1; i <= n; i++) {
cin >> children[i].___;
children[i].id = ___; // 记录原始编号
}
/****************************************************************
* 第一步：按贪婪度降序排序
*
* 为什么需要排序？
* 1. 根据交换论证，最优解中贪婪度大的孩子饼干数不少于贪婪度小的孩子
* 2. 排序后，我们可以假设分配序列是非递增的，大大减少搜索空间
* 3. 这样我们只需要考虑满足 c[1] >= c[2] >= ... >= c[n] 的方案
****************************************************************/
sort(___, ___, ___);
// 提取排序后的贪婪度，并计算前缀和
for (int i = 1; i <= n; i++) {
g[i] = ___;
prefixSum[i] = ___;
// prefixSum[i] = g[1] + g[2] + ... + g[i]，用于快速计算区间和
}
/****************************************************************
* 第二步：动态规划初始化
*
* dp[i][j] 表示前 i 个孩子（排序后）分配 j 块饼干的最小怨气
* 初始状态：
* dp[0][0] = 0: 0 个孩子分配 0 块饼干，怨气为 0
* 其他状态设为无穷大，表示不可达
****************************************************************/
for (int i = ___; i <= ___; i++) {
for (int j = ___; j <= ___; j++) dp[i][j] = ___; //状态初始化
}
dp[___][___] = ___; //边界状态
/****************************************************************
* 第三步：动态规划状态转移
*
* 考虑两种情况：
* 1. 整体加一转移（对应所有孩子饼干数都大于1）
* 如果给前 i 个孩子每人加一块饼干，怨气不变
* 转移：dp[i][j] = dp[i][j-i] (前提：j >= i)
*
* 2. 新增层级转移（对应最后 len 个孩子饼干数为 1）
* 设最后 len 个孩子饼干数为 1，前面 i-len 个孩子饼干数大于 1
* 这 len 个孩子每人都会产生怨气：每个孩子前面有 (i-len) 个孩子饼干数多于他
* 总怨气增加：(i-len) * (g[i-len+1] + ... + g[i])
* 转移：dp[i][j] = min{ dp[i-len][j-len] + (i-len)*(sum[i]-sum[i-len]) }
*
* 其中len从 1 到 i，表示最后一个层级（饼干数为 1）的孩子数量
****************************************************************/
for (int i ___) { //阶段
for (int j ___) { // j 至少为 i，因为每人至少一块饼干
// 情况1：整体加一转移
// 如果 j>=i，说明可以从前 i 个孩子每人少一块饼干的状态转移过来
if (j ___ i && dp[i][___] ___ dp[i][j]) {
dp[i][j] = dp[___][___];
path[i][j] = {0, 0, ___, ___}; // 记录转移路径
}
// 情况2：新增层级转移
// 枚举最后一个层级的长度 len（即饼干数为 1 的孩子数量）
for (int len = ___; len <= ___; len++) {
if (j >= ___) { // 确保有足够的饼干
// 计算新增的怨气
// (i-len) 是前面饼干数大于 1 的孩子数量
// (prefixSum[i] - prefixSum[i-len]) 是最后 len 个孩子的贪婪度之和
long long newAnger = dp[___][___] + (___) * (prefixSum[___] - prefixSum[___]);
if (newAnger ___ dp[i][j]) {
dp[i][j] = ___;
path[i][j] = {___, ___, ___, ___}; // 记录转移路径
}
}
}//for len
}//for j
}//for i
/****************************************************************
* 第四步：输出最小怨气
*
* dp[n][m] 就是前 n 个孩子（所有孩子）分配 m 块饼干的最小怨气
****************************************************************/
cout << ___;
/****************************************************************
* 第五步：回溯构造分配方案
*
* 通过记录的转移路径，从最终状态(n, m)开始回溯，构造出具体的分配方案
* 有两种类型的转移：
* 1. 整体加一：给前i个孩子每人加一块饼干
* 2. 新增层级：最后len个孩子饼干数设为1
****************************************************************/
reconstruct(n, m);
/****************************************************************
* 第六步：将排序后的分配方案映射回原始顺序
*
* 因为我们是按贪婪度降序排序后进行的DP和方案构造
* 所以需要将分配方案映射回原始的孩子顺序
****************************************************************/
for (int i = 1; i <= n; i++) {
// children[i].id 是排序后第 i 个孩子的原始编号
// allocation[i] 是排序后第 i 个孩子分到的饼干数
originalAns[___] = ___;
}
// 输出每个孩子的饼干数（按原始顺序）
for (int ___) cout << ___ << " ";
___
return 0;
}
题目3155 Cookies
 1
评论
2026-04-09 21:26:17
|
|
|
首先如何刻画重边，每次操作相当于给路径染上不同的颜色，一条边是重边当且仅当满足两个端点颜色相同。初始全是轻边，只需要所有点颜色不一样。 使用树链剖分算法，问题被转化到一个类似区间染色，区间颜色段数的问题，可以用珂朵莉树解决，当然也可以用线段树，合并两个区间时只关注区间的端点颜色和内部颜色段数，可以 $O(1)$。 注意在树上合并若干段区间需要注意合并顺序问题。 时间复杂度为 $O(n\log^2 n)$。
题目3598 [NOI 2021]轻重边
AAAAAAAAAAAAAAAAAAAA
2
评论
2026-04-08 20:25:42
|
|
|
A注意到在矩形内的线段也是一条线段。求出线段的两个端点。 特判掉无解，求线段和矩形四条边的两个交点（注意端点在矩形内部） 时间复杂度为 $O(1)$。 BDAG 上支配树。考虑能支配点 $x$ 的点集和点 $x$ 在支配树上的祖先集合等价。 具体的，插入第 $i$ 个点前，得到 $1\sim i-1$ 个点的支配树。 如果这个点受点集 $S$ 支配，则找到深度最大的点支配点集 $S$，体现在支配树上就是公共 LCA。 找到这个点后插入，因为要动态加叶子求 LCA，所以需要倍增。 按照拓扑排序加入叶子，查询时处理公共最近祖先。时间复杂度为 $O((n+m+q)\log n)$。 C可以先按照大小排序。 然后求差分数组的 $\gcd$，正确性显然。 时间复杂度为 $O(n\log n)$。 D$u_i=a_i-\min(a_i,b_i),v_i=b_i-\min(a_i,b_i)$。 注意到 $u_i,v_i$ 至少一个为 $0$。然后对有值的 $v_i$ 的取前 $k$ 大。 感觉不是很对，可以全取 $b_i$，然后取 $b_i-c_i$ 最小的几个。 时间复杂度为 $O(n\log n)$。 E求出图的任意生成树，$(x,y)$ 的路径为从 $x\to y$ 的树上路径异或权值异或上任意一个环的异或权值。 实际上只需要把经过 $1$ 的环塞进去线性基就能表示所有环，时间复杂度为 $O(n\log V)$。 F省流 $n^2m^2\le q$。 直接预处理出任意位置的答案，时间复杂度为 $O(n^2m^2+q)$。 G$\min(a_i,b_i,c_i)$。 H强强。 显然只需要满足任意 $i+1$ 大小的集合大于任意 $i$ 大小的集合。 显然只需要满足任意前 $i+1$ 大小的集合大于后 $i$ 大小的集合。 感觉一下，$i$ 越大越难满足，只需要让 $i=\left\lfloor\frac{n}{2}\right\rfloor$ 即可。 如何刻画单调递增，只需要令所有 $A_i=m$，每次减去一个前缀。记 $c_i$ 为 $1\sim i$ 减了 $c_i$ 次。 然后不会了，爽贺题解。 记 $d$ 表示前 $k+1$ 个减去后 $k$ 个的值，只需要满足条件 $d>0$。 可以求出 $c_i\gets c_i+1$ 会导致答案的变化 $w_i$。 要使得设 $dp_{i,j}$ 表示让 $c_k$ 变了 $i$ 次，$d=j$ 的方案数。 直接 $O(nm)$ 背包 dp 即可。 I初见杀。 注意到前缀和和 $a_i$ 是双射，对前缀和处理。 已知 $s_0=0$，已知花费 $w_{l,r}$ 的代价可以知道 $s_{l-1},s_r$ 之间关系。 转化为最小生成树模型，Prim 可以 $O(n^2)$。 J怎么感觉可以手算预处理出来当前面经过某种操作后是那个面（。 然后自动机（，时间复杂度为 $O(q)$。 K差分，随便做。 L显然分数规划。 每次一定减去 $[2,n-1]$ 中的最大子段和。 时间复杂度为 $O(n\log V)$。
题目4376 [郑轻校赛 2026] 有人截图了！
1
评论
2026-04-07 19:09:04
|
|
|
Pro4372 区间 题解Sol 1我们从左往右扫描离散化出来的线段 $i$（设当前点权为 $v_i$）。维护一个集合 $S$，表示覆盖这条线段的区间的编号。 对于一个询问 $[L,R]$ 若 $f(L,R)$ 包含这条线段，则存在 $x\in S$ 满足 $x\in [L,R]$。 不妨倒过来，对于当前的 $x\in S$，我们让所有满足 $L\le x,R\ge x$ 的二维点 $(L,R)$ 加上点权 $v_i$。 这样显然会算重，因为可能存在 $x,y\in S,x,y\in [L,R]$，这样 $v_i$ 就被算两次以上了。 考虑去重，对于一个询问 $[L,R]$ 让最小的符合条件的 $x$ 产生贡献，即如果同时存在两个 $x,y\in S$ 产生正贡献，就产生一次负贡献。 具体的，我们用 set 来维护 $S$，每次找到 $x$ 的前倾 $y$，让所有满足 $L\le y,R\ge x$ 的二维点 $(L,R)$ 加上点权 $-v_i$。 我们对于每一个线段都要这样做一次，复杂度就爆炸了，考虑对于每一个元素统一算贡献。 考虑第一类正贡献，设 $x$ 在第 $p$ 条线段加入 $x$，第 $q+1$ 条线段离开 $x$。则对所有 $L\le x,R\ge x$ 的点加上 $\sum_{i=p}^q v_i$。 对于第二类负贡献，我们也可以记录每一对前倾后继产生的时间区间 $[p,q]$，然后减去负贡献即可。在加入新的前倾后继关系。 于是我们转化到这样一个问题： 1. 给定若干 $(x,y,v)$，将所有 $L\le x,R\ge y$ 的点 $(L,R)$ 加上 $v$。（这一类操作的数量是 $O(n)$ 的）。 2. 查询满足 $A\le L\le R\le B$ 的所有点权之和。 不妨考虑一个操作 $(x,y,v)$ 对 $[A,B]$ 的贡献，为 $(x-A+1)(B-y+1)v$，令 $A'\gets A+1,B'\gets B+1$，则 $(x-A)(B-y)v=(Ay+Bx-AB-xy)v$。 因为 $A',B'$ 可以看作常数，所以我们做离线二维数点，同时维护 $\sum v,\sum xv,\sum yv,\sum xyv$ 即可。 时间复杂度为 $O(n\log n)$。 Sol 2将 $[l_i,r_i]$ 称为区间，$[A,B]$ 称为询问。扫描区间的下标。 设当前扫到了 $R$，则当前数组 $v_i$ 表示 $f(i,R)$。则当 $R=B$ 时查询 $[A,B]$ 就是询问所有 $i\in [A,B],v_i$ 的历史和。 考虑如何维护扫描过程中 $v_i$，设 $1\sim R$ 的所有区间中最后一个覆盖线段 $i$ 个编号是 $p_i$，则当前线段 $i$ 会对 $v_{1\sim p_i}$ 做贡献。 每次扫描线的右端点移动，新加入一个区间，会改变一些 $p_i$，设原来 $p_i=x$，后来 $p_i=y$，则这次移动会对 $v_{x+1\sim y}$ 新产生贡献。 每次都是覆盖一段区间，可以用珂朵莉树维护，改变一个颜色段的 $p_i$ 可以用一次区间加完成，而这样的区间加只有 $O(n)$ 次。 然后选择心怡的维护历史和的方法即可，例如维护当前完成的操作数 $T$，当前数组 $A$，设历史和数组为 $B$，再维护一个 $C_i=B_i-A_iT$，则只维护 $A,C$ 即可维护 $B$。 时间复杂度为 $O(n\log n)$。
题目4372 区间
AAAAAAAAAA
1
评论
2026-04-06 20:24:58
|
|
|
Pro4371 大括号 题解设往左走的获胜的概率为 $A$，往右走的获胜的概率为 $B$ 不难发现，最终的方案里，一定存在一个分界点，分界点左侧的点往左走，右侧点往右走。 特判掉 $a=0,b=0$ 的情况，两侧的问题可以对称为一个子问题。以左侧问题为例。 先枚举一个前缀 $n'$。考虑一个贡献延后计算的东西，维护一个栈，从后往前 dp，每次遇到 $L$ 就塞进栈，遇到 $R$ 就随机栈顶的几个 $L$。最后希望栈里有 $a$ 个 $L$。 设 $f_{i,j}$ 表示考虑了 $i\sim n'$，其中还剩下 $j$ 个 $L$ 在栈里，不难列出转移式： $$f_{i,j}=\begin{cases}f_{i+1,j-1} & s_{i}=L \\ f_{i+1,j+x}\times B^x\times A & s_{i}=R\end{cases}$$ 第二个转移式子表示一个 $R$ 连续击败了 $k$ 个 $L$ 后被一个 $L$ 击败，注意转移中间 $j=0$ 的情况是非法的，需要特判掉。 但是因为我们最终计算答案要枚举分界点，而我们目前的 dp 是确定了一个前缀后再从后往前 dp，考虑到过来，确定了一个前缀后再从前往后 dp。 倒过来后，不难发现我们是让一些 $R$ 和后面的 $L$ 去匹配，但是有 $a$ 个 $L$ 没有匹配，我们把这些没有匹配的 $L$ 放在一边。 设 $f_{i,j}$ 表示考虑了 $1\sim i$ 还有 $j$ 个 $L$ 能放在一边。然后转移都反过来即可。 最后发现转移的这个 $k$ 很没用，用前缀和优化掉即可，时间复杂度为 $O(n^2)$。
题目4371 大括号
AAAAAAAAAA
1
评论
2026-04-06 19:28:29
|
|
|
Pro4370 冒泡排序 题解# 1 冒泡排序(bubble) 相信大家做过今年的 NOI（2018）。 众所周知，排列合法当且仅当最长下降子序列不超过 $2$。 为了方便我们将最长下降子序列的限制变成最长上升子序列的限制。 特别地 $( a+b=n-1)$ 的情况。 当 $( a+b<n-1)$ 时，可以将序列和值域都反转，$( a' = n - a - 1, b' = n - b - 1 )$。 将 \((i, p_i)\) 在平面上画出来，(a, b) 将平面分成了四个区域，不难发现左下和右上不能同时有点。 假设左没有点，那么左上有 \( a \) 个点，右下有 \( b \) 个点，右上有 \( n - 1 - a - b < 0 \) 个点，不合法。 不难发现左下的点一定是单调递减的，可以将问题划分成下方和左方两个子问题，相当于要解决 \( b = n - 1 \) 的情况。 一个合法的序列可以唯一对应一条从 \((0, n)\) 到 \((n, 0)\) 的路径，满足任意时刻 \( x + y \leq n \)，路径长成 \( f(x) = \min_{x \leq y} p_x \) 的形式。 那么 \( b = n - 1 \) 的情况相当于一个长度为 \( b \) 的合法序列，前 \( a \) 个位置都是前缀最小值。 前 \( a \) 个位置假设往下走了 \( t(t \geq a) \) 步， 前面就是方程 \( x_1 + x_2 + x_3 + \cdots + x_a = t \) 的正整数解的个数，就是 $C_{t-1}^{a-1}$。 后面是从 \((a, b - t)\) 走到 \((b, 0)\) 的方案数，是 $(C_{2b-a-t}^{b-a} - C_{2b-a-t}^{b-a+1})$。 组合解是相当于从 \( 2b - a \) 个数里面选 \( b \) 个，以第 \( a \) 个数为分界线，枚举左右各有多少个数。 同理 \(\sum_t C_{t-1}^{a-1} C^{2b-a-t}_{b-a+1} = C_{2b-a}^{b+1}\)。 对于左方的子问题，将值和值域倒过来就变成下方的子问题了。 但是这是 NOIP 模拟，所以肯定有更简单的做法。 我们算左下没有点的情况，那么注意到 \((a, b)\) 这个位置是前缀最小值，那么考虑统计前缀最小值序列个数。 还是用路径来刻画这个东西，可以发现这个限制等价于 \((a, b)\) 这里的路径是这样走的：\((a, b + 1) \to (a, b) \to (a + 1, b)\)。 那么两边分开了，用折线法算方案数就行了。
题目4370 冒泡排序
评论
2026-04-04 15:07:59
|