luogu6381 Odyssey 题解对于 \(ab = c^k\),不难想到把 \(a\) 和 \(b\) 都分解。 \[ a= \prod_{i=1}^{c_a} p^{x_i}_i \] \[ b=\prod_{i=1}^{c_b} p^{y_i}_i \] 对于一个 \(p_i\),一定有 \(x_i + y_i \equiv 0 \pmod{k}\)。 不难想到,一旦 \(a\) 确定了,就可以限定 \(b 2022-10-21 题解 #DP #数论 #拓扑排序
luogu8564 ρars/ey 题解设 \(c(i)\) 为一次删去同一棵子树内不包括根的 \(i-1\) 个节点的代价。 链 将 \(1\) 号节点作为链首,不难想到设 \(f_i\) 为删掉以 \(i\) 为根的子树的最小代价,每次删掉的都是连续的一段,所以 \[ f_i = \min_{j \in [i+1,n]}\{ f_j + c(j-i+1)\} \] 答案 \(f_1\)。 菊花 显然,答案为 \(c 2022-10-21 题解 #DP #树形DP
luogu8231 沈阳大街 2 题解分析 以下部分内容来自洛谷题解 把两个序列看成二分图,对于一个排列 \(p\),左面点 \(i\) 和右面点 \(p_i\) 连一条边,这样就恰好形成一组完美匹配。 现在我们变成这样一个问题:\((i,j)\) 的边权是 \(\min(A_i,B_j)\),定义一个完美匹配权值是所有边权的积,你要求所有完美匹配权值之和。 这样还是不太好做,考虑两个序列都从大到小排序,然后把边定向,定义 2022-10-04 题解 #DP #二分图
杂题选讲3luogu2135 方块消除 分析 把同颜色方块区域转化成同色方块相邻,排成一列。 发现是套路区间 DP。 设 \(f(i,j,k)\) 为区间 \([i,j]\),其中右侧有 \(k\) 个和 \(j\) 同色的东西。 设 \(c_i\) 为 \(i\) 的颜色,\(d_i\) 为和 \(i\) 颜色相同的方块数量。 一个显然的结论:同色方块会被同时删掉。 证明略。 这个结论可以 2022-10-04 题解 #DP #区间DP #贪心 #并查集
CF402D Upgrading Array 题解分析 注意到 \(f\) 的过程就是唯一分解的过程。 考虑 \(g = \gcd\{a_{1 \sim i}\}\),发现除去 \(g\) 之后,相当于原来的总和减去 \(f(g)\),贡献为 \(i \times -f(g)\)。 设 \(F(i)\) 为以 \(i\) 结尾的前缀,能够产生的最大贡献。 由于可以进行多次,所以可能在让 \(a_{1 \sim i}\) 除去 \( 2022-10-02 题解 #DP #数论
CF847E Packmen 题解分析 最小化时间,可以考虑二分答案。 考虑将 Packmen 和物品的位置划分的成两个集合。由于 Packmen 之间互不影响,所以只要分别贪心就好了。 不难想到,每个人去走的物品一定是连续的。 对于一个位置为 \(p_i\) 的人 \(i\) 和一个物品区间 \([l,r]\),能够在时间限制 \(x\) 内完成,当且仅当 \(\Big( \min(|p_i - l|,|p_i - r 2022-10-02 题解 #二分答案
CF1067A Array Without Local Maximums 题解分析 套路题。 注意到值域是 \(200\)。 设 \(f(i,j,0/1)\) 表示前 \(i\) 位,第 \(i\) 位放 \(j\),大于或小于等于第 \(i-1\) 位的方案数。 可以钦定第 \(1\) 位大于第 \(0\) 位,第 \(n\) 位小于等于第 \(n-1\) 位。 转移 \[ f(i,j,0) = \sum_{k=1}^{j-1} \Big( f(i-1,k,0 2022-10-02 题解 #DP
CF1312E Array Shrinking 题解分析 挺有启发意义的题目。 第一眼看上去像一个套路的区间 DP,但是区间想要合并必须满足值相等。 考虑设 \(g(i,j)\) 为区间 \([i,j]\) 最终合并成的值,如果不能合并为 \(1\) 个元素,那么为 \(-1\)。 设 \(f(i)\) 为以 \(i\) 结尾的序列,能够划分的最短长度。 \[ f(i) = \min_{g(j,i) > 0}\{ f(j-1) + 2022-10-02 题解 #DP #区间DP
CF845C Two TVs 题解分析 离散化,然后如果某个时间同时存在至少 \(3\) 个未结束的节目,那么无解。 差分即可。 CODE #include<bits/stdc++.h> using namespace std; #define int long long int read() { int a=0, f=1; char c=getchar(); while(!isdigit(c)) 2022-10-02 题解 #差分
luogu3594 WIL 题解分析 显然,置零的区间长度一定为 \(d\),否则一定不优。 那么答案大于等于 \(d\)。 暴力做法,枚举左右端点 \([i,j]\),贪心地减去区间里长度为 \(d\) 的最大的一块,用前缀和搞一下,\(O(n^3)\)。 考虑一个双指针做法,固定左端点 \(i\),贪心地让右端点在 \([i+d,n]\) 中增长,维护区间内最大的长度为 \(d\) 的块。如果区间和大于 \(p\) 2022-10-01 题解 #单调队列 #双指针