|
Pro4359 淘汰赛 题解淘汰赛：区间最大值贪心解法一、 题目大意
一共有 2n 个国家参加单场淘汰赛，两两配对比赛，能力值高的一方必胜，一直比赛直到决出冠军。比赛顺序：1 和 2 比、3 和 4 比…… 相邻编号两两对决，胜者晋级继续淘汰赛。已知所有国家的能力值互不相同，求最终亚军的国家编号 样例输入 n=3，总共有 23=8 个国家。8 个国家能力依次为：1 号：4，2 号：2，3 号：3，4 号：1，5 号：10，6 号：5，7 号：9，8 号：7整个赛程里冠军是 5 号，和冠军在决赛对战的对手就是亚军，也就是1 号，所以输出 1 二、 思路解析（核心部分）第一层：解题基石
本题不需要模拟完整淘汰赛全过程，仅用基础遍历即可解决 1.淘汰赛的赛程结构是严格的完全二叉树，所有队伍被均匀分成左右两个半区 2.冠军必然是两个半区各自的最强者之一 3.亚军一定是另外一个半区里的最强队伍 4.数据范围 n≤7，总人数最多 2^7=128，数据极小，暴力遍历完全足够 第二层：思维脉络
1.计算总参赛队伍数量:tot=2^n 2.将所有队伍平均划分为左半区、右半区两部分 3.分别遍历两个半区，找出左半区能力最强的编号、右半区能力最强的编号 4.两个最强队伍中，能力较弱的那一个，就是最终亚军 本题无动态规划，无需 DP 数组定义 可设： maxL = 左半区最大能力值，idL = 对应编号 maxR = 右半区最大能力值，idR = 对应编号决赛对决 则： max(maxL,maxR) 对应编号为冠军 min(maxL,maxR) 对应编号为亚军 第三层：难点与陷阱
1.浮点数精度使用错误：使用 pow(2,n) 计算队伍总数，pow 是浮点函数，会出现 128 变成 127.9999 的误差，导致数组越界 2.错误模拟全程比赛：当一层层模拟晋级时，代码写复杂还容易写错 3.混淆能力值和国家编号，只存数值忘记记录原始编号 4.数组下标混乱，左右半区分割错误 观察淘汰赛树形结构发现规律：亚军只会是决赛输家，而决赛双方分别是左右两大区的最强者，因此完全不需要模拟全程比赛，只需要找两个大区最大值，弱者即为答案，思路大幅简化。 三、 代码实现
四、 总结与反思（升华部分）
1.透过赛程结构找规律，不用死板模拟全过程，淘汰赛树形结构有固定结论：亚军是决赛对手，即另一半区最强者 2.规避 pow() 函数浮点误差的技巧：用位运算 1<<n 计算 2n 3.理解单胜者淘汰赛、完全二叉树比赛模型的通用性质 本题结论可以迁移到所有相邻配对、强者必胜、单败淘汰赛题目： 1.求决赛两支队伍 2.求四强、八强分别是谁 3.同类体育竞赛赛程推理题目。 1.可以封装函数实现通用区间最大值查找，代码复用性更高 2.可以扩展写法，模拟完整每一轮晋级过程，输出每一轮晋级名单，验证规律 3.若题目改为弱者获胜，只需修改大小比较符号即可，整体思路不变。 五、 推荐题目
题目4359 淘汰赛
AAAAAAAAAA
 4
评论
2026-04-18 14:50:46
|
|
|
3139. [HSOI 2019] HS的新题 - COGS显然随机数据, 考虑珂朵莉树.
以下均在
注意要开
操作
|
|
|
点击查看《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
|