|
Pro4516 地铁 题解以下提供三种模板供您选择,发布题解时请删除模板中提示语等多余文字。【模板一:多解法题解模板】一、 解法概览
二、 详细解析解法一:[名称,如:暴力搜索]
[简要说明核心思路]
[请点击上面 解法二:[名称,如:动态规划]
[简要说明核心思路]
[请点击上面 解法三:[名称,如:贪心算法]
[简要说明核心思路] [策略描述] [简要证明或说明]
[请点击上面 三、 对比总结
[各解法在时间和空间上的表现对比] 四、 推荐题目
【模板二:思维演进题解模板】一、 初始思路(第一反应)
[描述最初想到的方法] [分析该方法的缺陷] [基于缺陷提出的改进思路] 二、 优化过程版本1.0:基础实现
[描述基础版本的思路]
[请点击上面 [分析性能瓶颈] 版本2.0:算法优化
题目4516 地铁
2026-11-19 19:49:13
|
||||||||||||||||
|
Pro4515 能量水晶 题解以下提供三种模板供您选择,发布题解时请删除模板中提示语等多余文字。【模板一:多解法题解模板】一、 解法概览
二、 详细解析解法一:[名称,如:暴力搜索]
[简要说明核心思路]
[请点击上面 解法二:[名称,如:动态规划]
[简要说明核心思路]
[请点击上面 解法三:[名称,如:贪心算法]
[简要说明核心思路] [策略描述] [简要证明或说明]
[请点击上面 三、 对比总结
[各解法在时间和空间上的表现对比] 四、 推荐题目
【模板二:思维演进题解模板】一、 初始思路(第一反应)
[描述最初想到的方法] [分析该方法的缺陷] [基于缺陷提出的改进思路] 二、 优化过程版本1.0:基础实现
[描述基础版本的思路]
[请点击上面 [分析性能瓶颈] 版本2.0:算法优化
题目4515 能量水晶
2026-11-19 19:49:05
|
||||||||||||||||
|
比较经典的计数题。 考虑 $\sum a_i^2$ 的组合意义,等价于枚举两个取球方案,且两个方案最终取得的序列相同的方案数。 设 $f_{i,j,k}$ 表示取了 $i$ 个球,枚举的两个方案中,第一个方案在上侧取了 $j$ 个球,第二个方案在上侧取了 $k$ 个球。且目前两种取球的方案得到的序列一样的方案数。 枚举第 $i+1$ 个球取上面还是下面,转移即可,滚动数组优化空间,即可做到 $O(n^3+n^2m))$ 的时间复杂度和 $O(n^2)$ 的空间复杂度。
题目411 [NOI 2009]管道取珠
AAAAAAAAA
3
评论
2026-09-16 08:34:53
|
||||||||||||||||
|
这是一道好题。 首先对于 $x_i=y_i$ 的部分,这是一个经典的点分治问题,可以直接用点分治解决。 对于 $x_i\ne y_i$ 的部分,假设 $x_i$ 为 $y_i$ 祖先,可以把符合条件的点分为 $x_i$ 子树外的和 $x_i$ 子树内的。 令 $f_{i,j}$ 表示子树 $i$ 内距离 $i$ 不超过 $j$ 的节点个数,前者可以通过点分治和 $f_{x_i,d}$ 作差求得。 对于后者,首先链上的点一定符合条件,其次考虑枚举链上某个点 $u$,并枚举 $u$ 的一个不在链上的儿子 $v$,加上 $f_{v,d-1}$。即为答案。 对于 $x_i$ 不为 $y_i$ 祖先的情况,考虑先求出 LCA 然后拆成两条竖直的链来做。综上,现在有了一个不知道什么复杂度的暴力做法了,考虑优化。 注意到:对于链上的 $u$ 以及想要计算的 $v$,绝大部分 $v$ 是 $u$ 的轻儿子。换句话说,对树进行轻重链剖分,则一条路径上只有 $\log n$ 条轻边。 考虑设 $g_{i,j}$ 表示 $i$ 的所有轻儿子子树中,距离 $i$ 不超过 $j$ 的节点个数,先求出竖直链上的 $g_{u,d}$ 之和,对于一条位于查询路径上的轻边 $(u,v)$,其中 $u$ 为 $v$ 的父亲,只需要减去 $f_{v,d-1}$ 然后加上 $f_{son(u),d-1}$ 即可正确处理这条轻边的贡献。 链上的 $g_{i,j}$ 之和可以通过树上差分求出,令 $G_{i,j}$ 表示 $1\to i$ 路径上所有点 $u$ 的 $g_{u,j}$ 之和。
现在我们要做的是: 2. $O(n\log n)$ 次查询 $x$ 子树内距离点 $x$ 不超过 $k$ 的点个数。 3. $O(n)$ 次查询 $G_{i,j}$。 第一个可以点分治做到 $O(n\log^2 n)$,第二个可以用 dfs 序转化为二维数点做到 $O(n\log^2 n)$,第三者可以先离线询问,dfs 时暴力遍历轻子树做到 $O(n\log^2 n)$,所以整个题就可以做到 $O(n\log^2 n)$。 因为本题的边边权均为 $1$,可以做到 $O(n\log n)$ 完成第 $1,3$ 个部分(具体的,我们直接维护前缀和,加入一个子树可以用 $O(siz)$ 的复杂度求出对前缀和数组 $O(siz)$ 个位置的影响),第二个部分使用长链剖分应该也能做到 $O(n\log n)$。所以本题应该是可以 $O(n\log n) $ 的。 当然我比较懒,所以只实现了 $O(n\log^2 n)$ 的,不过感觉 1log 可能也挺好写的?
题目3827 举办乘凉州喵,举办乘凉州谢谢喵
AAAAAAAAAAAAAAAAAAAAAAAAA
评论
2026-09-14 21:05:01
|
||||||||||||||||
|
Pro4483 彩色卡牌 题解用 $n=rc$ 指代地图大小。 首先一个地方到另外一个地方一定是沿着路径最大值最小的那个路径去的,显然是最小生成树,边权设置为两个端点的权值较大值。 考虑 kruskal 重构树,这样从 $x$ 出发不经过路径权值超过 $v$ 能得到的原图的点一定是一个子树的叶子节点。 现在问题就是单点改颜色和子树数颜色,其实有一个非常经典的 trick 叫树链求并。 具体的,当所有叶子颜色都不相同时,让每个叶子 $x$ 都对 $root\to x$ 的路径上权值加 $1$,一个点子树内的颜色数就是这个权值。 注意到,当两个叶子颜色相同时,有一部分点会算重两次,所以需要减去。 推广到一般形式,把颜色相同的所有叶子按照 dfs 序排序,对任意相邻两个节点的 LCA $x$ 执行 $root\to x$ 的路径减 $1$,即可完成去重。 用 set 维护同一种颜色的叶子的 dfs 序,只需要 $O(n)$ 次树状数组修改,复杂度为 $O(n\log n)$。
题目4483 彩色卡牌
AAAAAAAAAA
评论
2026-09-12 16:25:16
|
||||||||||||||||
|
Pro4480 分饼干 题解考虑dp,用$f_i$表示$A$集合比$B$集合多$i$个饼干时$A$集合的最大饼干数(然后按状态定义转移),因为$i$可能是负数所以加一个$5e5$: #include<bits/stdc++.h>
#define int long long
using namespace std;
const int V = 1e6 + 5;
const int base = 5e5;
const int N = 55;
int n;
int f[V],g[V];
signed main()
{
freopen("cookie.in","r",stdin);
freopen("cookie.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
memset(f,-0x3f,sizeof(f));
memset(g,-0x3f,sizeof(g));
g[base] = 0;
for(int i = 1;i <= n;i++){
int x;cin>>x;
for(int j = 0;j <= V - 5;j++) if(j + x <= V - 5) f[j + x] = max(f[j + x],g[j] + x);
for(int j = 0;j <= V - 5;j++) if(j - x >= 0) f[j - x] = max(f[j - x],g[j]);
for(int j = 0;j <= V - 5;j++) g[j] = f[j];
}
cout<<f[base]<<'\n';
return 0;
}
题目4480 分饼干
AAAAAAAAAA
评论
2026-09-12 15:24:27
|