P3572 [POI2014] PTA-Little Bird - DP 单调队列
题面 https://www.luogu.com.cn/problem/P3572 题解 首先，不难列出方程：$f[i]$ 代表跳到 $i$ 的最小疲劳值 $$ f[i] = \min_{i - k \leq j < i} \{f[j] + (a[i] \geq a[j])\} $$ 时间复杂度为 $O(qn^2)$，不理想。但是不难发现，这道题可以用单调队列进行优化。为什么？ 如下状态一定是更优的：随着 index 递增 $f$ 不下降（第一维比较） $f$ 若相同，同时有 $a$ 不上升（第二维比较） 所以我们就可以用单调队列来维护 index，时间复杂度为 $O(qn)$ 注意： 初值的设定，详见代码 写的顺序和单调队列的模板稍微有一点不同，因为 $i - k \leq j < i$，右边的小于号不是小于等于号，即 $f[i]$ 不能被自己更新，所以调整了一下逻辑块的顺序。 代码 #include <iostream> using namespace std; const int maxn = 1e6+5; int qq, n, k, head, tail, a[maxn], f[maxn], q[maxn]; int main() { cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; cin >> qq; while (qq --> 0) { cin >> k; head = 1; tail = 1; q[1] = 1; for (int i = 2; i <= n; i ++) { while (head <= tail && q[head] < i - k) head ++; f[i] = f[q[head]] + (a[i] >= a[q[head]]); while (head <= tail && ( f[i] < f[q[tail]] || ( f[i] == f[q[tail]] && a[i] >= a[q[tail]] ) )) tail --; q[++ tail] = i; } cout << f[n] << endl; } return 0; }
Preface 三年前的四月，第一次接触 OI。初三下，小教室里听着 fcx 讲着滑动窗口单调队列，放学后去本部蹭了第一节斜率优化的课，随即拉开了我长达两年的竞赛摆烂之旅。 记忆犹新。第一个注册的 OJ 账户就是 POJ，第一道 AC 的题便是 POJ 2823 滑动窗口。 多年过去，今天再看这个基础中的基础，茫然。只能说这是究极摆烂的下场罢。总之就好好写一下题解。 题面 https://www.luogu.com.cn/problem/P1886 题解 接下来只讨论求最小值的情况。设 $f[i]$ 代表终止于位置 $i$ 的滑动窗口的最小值： $$ f[i] = \min_{i - k < j \leq i} a[j] $$ 如果暴力做的话时间复杂度为 $O(n^2)$。这里我们需要使用单调队列来优化。 对于最小值：单调队列内的元素值递增，同时 index 也是递增的。为什么这样做？思考一个情况：index 递增的情况下，如果一个 $a[i] > a[j], i < j$，那么在 $i,j$ 都有效的范围内，$a[i]$ 永远不可能作为答案。 这里有一句经典的话：如果一个选手年龄比你小，但却比你强，那你就可以退役了。我们把 index 比作出生年份，$a[]$ 比作能力，那么这句话就维护了一个求最大值的单调队列。 接下来是代码中需要注意的一些问题： head, tail 不是左闭右开，而是 $[head, tail]$。这样做的原因是访问 head 和 tail 的元素就可以简单的：q[head], q[tail] 队列里存的是 index （pos） 注意：第二个 while 可以修改为 if，因为每次 i ++ 且 q 内的 pos 递增，写成 while 是习惯。 代码 #include <iostream> using namespace std; const int maxn = 1e6+5; int n, k, a[maxn], q[maxn], head, tail; int main() { cin >> n >> k; for (int i = 1; i <= n; i ++) cin >> a[i]; // min head = 1, tail = 0; for (int i = 1; i <= n; i ++) { while (head <= tail && a[i] <= a[q[tail]]) tail --; q[++ tail] = i; while (head < tail && q[head] <= i - k) head ++; if (i >= k) cout << a[q[head]] << " "; } cout << endl; // max head = 1, tail = 0; for (int i = 1; i <= n; i ++) { while (head <= tail && a[i] >= a[q[tail]]) tail --; q[++ tail] = i; while (head < tail && q[head] <= i - k) head ++; if (i >= k) cout << a[q[head]] << " "; } cout << endl; return 0; }
leetcode 1787 使所有区间的异或结果为零 - DP - 随机跳题计划
Preface 好耶，少见的难题。 题面 https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/ 题解 大部分题解已经提到了：就是下面这个结论。 结论：最终构造出来的数列以 $k$ 为一个周期 证明： 由题设： $$ a[1] \oplus a[2] \oplus \cdots \oplus a[k] = a[2] \oplus a[3] \oplus \cdots \oplus a[k + 1] $$ 所以我们有： $$ (a[1] \oplus a[2] \oplus \cdots \oplus a[k]) \oplus (a[2] \oplus a[3] \oplus \cdots \oplus a[k + 1]) = 0 $$ 根据异或的交换律与结合律： $$ a[1] \oplus a[k + 1] = 0 $$ 故 $a[1] = a[k + 1]$。易证，此结论可以将 $1$ 替换为任意定义域内的数。 接下来思考一下最终构造出来的数列满足什么特征： 以 $k$ 为一个周期 第一个周期异或和为 0 接下来看图说话: 在上图中 $n = 13, k = 3$，我们就是需要让 $$ a[1] = a[4] = a[7] = a[10] = a[13] $$ $$ a[2] = a[5] = a[8] = a[11] $$ $$ a[3] = a[6] = a[9] = a[12] $$ $$ a[1] \oplus a[2] \oplus a[3] = 0 $$ 那么我们不妨一组一组按列处理，接下来是状态的设法：$f[i][j]$ 代表处理完第 $i$ 列，使得前 $i$ 列的异或和为 $j$ 的最少修改次数。 思考转移方程：都是从上一列转移，但是有两种转移方式： 第 $i$ 列全部修改 第 $i$ 列部分修改，部分保留 设 $cnt$ 为第 $i$ 列的个数，$t[j]$ 代表第 $i$ 列 $j$ 出现的次数，那么： $$ f[i][j] = \min (f[i][j], cnt + \min_{k} f[i - 1][k]) $$ $$ f[i][j] = \min_{k \in \text{column }i} \{f[i][j], f[i - 1][j \oplus k] + cnt - t[k]\} $$ 注意：全部修改仍然有可能比部分修改更优，这是因为本题不是简单的贪心。具体可以见下一小节，我们可以构造出反例，证明贪心是错误的。 此外，我们还需要注意初值的设定。 构造贪心的反例 贪心？怎么贪心？那当然是每一列选择相同数量最多的，再把这个数量排序，相同数量最少的一列全部改变，使得最后异或值为 0。 但是这个反例是非常容易构造的。 第一列： $$ a, a, b, b, b, c, c $$ 第二列： $$ d, d, d, d, e, e, e $$ 第三列： $$ f,f,g,g,h,h,i $$ 按照之前说的贪心，我们会选保留 $b, d$，然后第三列适应答案使得异或为 $0$。但是如果很不巧，我们的构造在这样的情况下其他元素全部需要改变，那么此时的改动数量为 $4 + 5 + 7 = 16$。然而如果 $a \oplus e \oplus f = 0$，那么如果我们选择 $a, e, f$，改动的数量就是 $5 + 4 + 5 = 14 < 16$，更优。构造完毕。 代码 const int maxn = 2e3+5; const int maxl = 10; class Solution { int f[maxn][1 << maxl]; int g[maxn], a[maxn], t[1 << maxl]; public: int minChanges(vector<int>& nums, int k) { int n = nums.size(); for (int i = 0; i < n; i ++) a[i + 1] = nums[i]; memset(f, 0x7f, sizeof(f)); memset(g, 0x7f, sizeof(g)); memset(t, 0, sizeof(t)); int cnt = 0; for (int j = 1; j <= n; j += k) t[a[j]] ++, cnt ++; for (int j = 0; j < 1024; j ++) { f[1][j] = min(f[1][j], cnt - t[j]); g[1] = min(g[1], f[1][j]); } for (int i = 2; i <= k; i ++) { memset(t, 0, sizeof(t)); cnt = 0; for (int j = i; j <= n; j += k) t[a[j]] ++, cnt ++; for (int j = 0; j < 1024; j ++) { f[i][j] = g[i - 1] + cnt; for (int m = 0; m < cnt; m ++) { f[i][j] = min(f[i][j], f[i - 1][j ^ a[m * k + i]] + cnt - t[a[m * k + i]]); } g[i] = min(g[i], f[i][j]); } } return f[k][0]; } };
题面 https://www.luogu.com.cn/problem/P2210 题解 一开始没反应出来是状压，看了少数题解才知道可以状压。今天姑且 A 掉状压的写法，明天写写看模拟退火。 首先，我们来设状压的状态方程： $$ f[i] $$ $i$ 代表 $i$ 表示成二进制的时候有 $1$ 那些位所代表的牛组成的集合 比方说 $i = 6 = (110)_2$ 代表有 $2, 3$ 号牛组成的集合 $f[i]$ 代表牛的集合为 $i$ 时对答案产生的贡献。 什么是贡献？这个说法很模棱两可。其实是这样的：两个朋友都在集合里面，那答案必然要包括这对朋友连线的贡献。但是如果只有一头牛在集合里呢？很简单，贡献就是：按照某种最佳排列时，这头牛所处的位置到集合队尾的距离。这么说很抽象，我们举个例子： $$ ~ * ~ * ~ * ~ \triangle ~ * ~ * $$ 上图中，$*$ 代表无所谓的某头牛，$\triangle$ 代表我们现在考察的单个朋友，在这个状态下，$\triangle$ 对答案的贡献就是 $2$，因为 $\triangle$ 之后还有两头牛. 而如果在这个队列之后紧跟就是 $\triangle$ 的朋友：另一个 $\triangle$，那么在增加前 $\triangle$ 给出的贡献 $2$ 就是这对朋友对答案的贡献了： $$ ~ * ~ * ~ * ~ \triangle ~ * ~ * ~ \triangle $$ 好。赘述完关于状态的定义，我们来思考状态怎么转移。对于集合 $i$，我们可以枚举位于队列尾端的到底是哪头牛。每次转移我们只需要加上原来的集合中孤立朋友的数量即可。最终给出的代码是做了一些小的优化，稍微难以理解，所以下面给出一个等价的形式，但是时间复杂度多一个 $n$，为 $O(n^22^n)$： for (int i = 1; i < (1 << n); i ++) { for (int j = 0; j < n; j ++) { if ((1 << j) & i) { int pending_links = 0; int ii = i & ~(1 << j); for (int k = 0; k < n; k ++) if ((1 << k) & ii) pending_links += 3 - (((ii >> nbr[k][0]) & 1) + ((ii >> nbr[k][1]) & 1) + ((ii >> nbr[k][2]) & 1)); f[i] = min(f[i], f[ii] + pending_links); } } } 代码 最终给出的代码时间复杂度为 $O(n2^n)$： #include <iostream> #include <cstring> using namespace std; const int maxn = 12; int f[1 << maxn], nbr[maxn + 5][3]; int main() { int n; cin >> n; for (int i = 0; i < n; i ++) { cin >> nbr[i][0] >> nbr[i][1] >> nbr[i][2]; nbr[i][0] --; nbr[i][1] --; nbr[i][2] --; } memset(f, 0x7f, sizeof(f)); f[0] = 0; for (int i = 1; i < (1 << n); i ++) { int pending_links = 0; for (int j = 0; j < n; j ++) if ((1 << j) & i) pending_links += 3 - (((i >> nbr[j][0]) & 1) + ((i >> nbr[j][1]) & 1) + ((i >> nbr[j][2]) & 1)); for (int j = 0; j < n; j ++) { if ((1 << j) & i) { f[i] = min(f[i], f[i & ~(1 << j)] + pending_links - (3 - (((i >> nbr[j][0]) & 1) + ((i >> nbr[j][1]) & 1) + ((i >> nbr[j][2]) & 1))) + ((i >> nbr[j][0]) & 1) + ((i >> nbr[j][1]) & 1) + ((i >> nbr[j][2]) & 1)); } } } cout << f[(1 << n) - 1] << endl; return 0; }
Preface 被录取的喜悦冲昏了头脑，停了几天跳题，今天又开始跳了。 题面 https://leetcode-cn.com/problems/split-array-with-same-average/ 题解 一开始做的时候想假了，一眼就觉得是普通的子集和，就是说看能不能找到一个子集使得和为一个定值。写了一发才发现这题目说的是均值。 但是问题不大，因为 $n$ 很小，所以我们可以枚举所有的自己大小，然后魔改一下子集和这个 01 背包。 其实写到一半发现写假了不想做了，但是一看题解让我大失所望。那些提到 01 背包的竟然复杂度要上指数级？这显然不能接受。 接下来讲一下思路： 首先讲一下均值的处理问题。算除法显然不是一个好的选择，所以这里我们用乘法代替。设 $x, y$ 为整个和的两个部分： $$ x + y = \text{sum} = \sum_i a[i] $$ 满足下面的条件： $$ \frac {x} {y} = \frac {|x|} {|y|} $$ $$ |x| + |y| = n $$ 其中 $|x|, |y|$ 代表 $x, y$ 代表的子集的大小。这里我们不妨枚举 $|x|$，记作 $m$，那么 $$ y = \frac {\text {sum} \times (n - m)} {n} $$ 我们只需要判断有没有可能通过选择 $n-m$ 个数使得和为 $y$ 也就是上式。 接下来讲一下魔改的子集和。 常规的子集和：设 $f[i]$ 代表 $i$ 能否成为一个子集和： $$ f[i] = f[i] \text { or } f[i - a[j]] $$ $$ f[0] = 1 $$ 从后往前更新 $i$。这个是子集和的惯用套路。 这里我们定义 $c[i][t]$，意为 $i$ 能否用 $t$ 个数表示，作为一个子集和。 $$ c[i][t] = c[i][t] \text { or } c[i - a[j]][t - 1] $$ $$ c[0][0] = 1 $$ 这里需要注意一下更新条件：$f[i - a[j]] = 1$ 才能更新 $c[i][t]$，理由无需多说。 代码 const int maxn = 150005; class Solution { int sum = 0; bool f[maxn], c[maxn][31]; public: bool judgeSubset(vector<int>& nums, int n, int s) { memset(f, 0, sizeof(f)); memset(c, 0, sizeof(c)); f[0] = 1; c[0][0] = 1; for (int i = 0; i < nums.size(); i ++) for (int j = s; j >= nums[i]; j --) { f[j] = f[j] || f[j - nums[i]]; if (f[j - nums[i]]) for (int t = 30; t > 0; t --) c[j][t] = c[j - nums[i]][t - 1] || c[j][t]; } return c[s][n]; } bool d(int n, int d) { return !(n % d); } bool splitArraySameAverage(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; i ++) sum += nums[i]; for (int m = 1; m < n; m ++) { if (!d((n - m) * sum , n)) continue; if (judgeSubset(nums, n - m, (n - m) * sum / n)) return true; } return false; } };
SJTU SPEIT OJ 009 Write the tape - 朴素 DP
Preface 做了一道可靠大仙贝给的 SJTU 巴院的题。出题人 ****** 啊。题目表述不清。smallest to largest 不是 size 而是 index，所以这句话有什么说的必要吗😅。 题面 DescriptionIn modern data centers, people often use tape drives to store large amounts of data. There are now a total of N files numbered from 1 to N that need to be written to a single tape. The files are written in order from smallest to largest on different locations on the tape, with zero spacing between files. The size of i-the file is a_i byteSuppose we use a tape drive with m read/write heads, any one of which can write from any position on the tape. The writing speed of the tape head is C bytes per second. These heads can not cross each other, so each read-write head can only select a continuous interval of files to write. The head is allowed to stay idle in the whole process. But one head may not halt until it has completely written all the files initiated by it to write.We would like to know the minimum completion time for this batch of files to be completely written. Input The first line contains 3 integers seperated by space. They aren,mandCas described.The second line contains n integers where the i-th integer isa_i1<=n,m<= 1e2, 1 <=C<= 1e2, 1 <=a_i<= 1e4 Output The integer which is the rounding up of the completion time (unit: second)Sample Input 1 5 3 45 8 3 10 7Sample Output 14 题解 设 $f[i][j]$ 表示前 $i$ 个文件分为 $j$ 组的最小的所有区间的最大值。 $$ f[i][j] = \min_{0 \leq k \leq i} \{\max (f[i - k][j - 1], \sum_{p=i-k+1}^i a[p])\} $$ 后面的 sigma 可以用前缀和优化 $$ \sum_{p=i-k+1}^i a[p] = s[i] - s[i - k] $$ 代码 #include <iostream> #include <cstring> using namespace std; const int maxn = 1e2+5; int a[maxn], s[maxn], f[maxn][maxn]; int up(int n, int d) { if (n % d) return n / d + 1; return n / d; } signed main() { int n, m, C; cin >> n >> m >> C; for (int i = 1; i <= n; i ++) cin >> a[i]; memset(f, 0x7f, sizeof(f)); for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i]; for (int i = 0; i <= n; i ++) f[i][1] = s[i]; for (int i = 1; i <= n; i ++) for (int j = 2; j <= m; j ++) for (int k = 0; k <= i; k ++) f[i][j] = min(f[i][j], max(f[i - k][j - 1], s[i] - s[i - k])); cout << up(f[n][m], C) << endl; return 0; }
题面 https://www.luogu.com.cn/problem/P1717 题解 以五分钟为一个单位，设状态方程：$g[i][j]$ 表示第 $i$ 个时间单位到达 $j$ 农场钓到的鱼。 $$ g[i][j] = \max_{0 \leq k \leq i - t[j]} \{g[i - t[j] - k][j-1] + \sum_{p = 0}^{k-1} \max (0, f[j] - p \times d[j])\} $$ 注意：这里的 $t[i]$ 和原题中不一样，是偏移过一位的。 值得注意的是 $$ f[j] - p \times d[j] $$ 需要保证大于零。 以及我们还需要保证状态是可达的才行。所以代码中要 memset -1. 代码 #include <iostream> #include <cstring> using namespace std; const int maxn = 30; const int maxt = 1e5+5; int f[maxn], d[maxn], t[maxn], g[maxt][maxn]; int calc(int i, int j, int k) { int ret = g[i - t[j] - k][j - 1]; if (ret == -1) return ret; for (int i = 0; i < k; i ++) ret += max(0, f[j] - i * d[j]); return ret; } int main() { int n, h; cin >> n >> h; h *= 12; for (int i = 1; i <= n; i ++) cin >> f[i]; for (int i = 1; i <= n; i ++) cin >> d[i]; for (int i = 2; i <= n; i ++) cin >> t[i]; memset(g, -1, sizeof(g)); g[0][0] = 0; for (int i = 1; i <= h; i ++) for (int j = 1; j <= n; j ++) for (int k = 0; k <= i - t[j]; k ++) g[i][j] = max(g[i][j], calc(i, j, k)); int ans = 0; for (int i = 1; i <= n; i ++) ans = max(ans, g[h][i]); cout << ans << endl; return 0; }
题面 https://www.luogu.com.cn/problem/P1364 题解 复杂度 $O(n)$ 高赞题解中说带权树的重心。其实关系不是最大，我们直接嗯推方程其实就可以了。 首先定义: $sz[u]$ 是以 $u$ 为根的子树大小 $f[u]$ 是将 $u$ 设置为医院时的总距离 我们不妨以 $1$ 为根。 第一遍 dfs 初始化 $sz$ 与 $f[1]$: $$ sz[u] = w[u] + \sum_{v} sz[v] $$ $$ f[1] = \sum_{u} w[u] \times depth[u] $$ 第二遍 dfs 更新贡献，而且是从上往下更新贡献，因为我们首先求出了 $f[1]$ (根的贡献)： $$ f[v] = f[u] + (sz[1] - sz[v]) - sz[v] $$ 理由： 这是 $f[u]$: 这是 $f[v]$: 也就是说要给 $v$ 以及其子树减去一个贡献，而整棵树除了 $v$ 及其子树的节点都要加上一个贡献，所以就有了 $$ (sz[1] - sz[v]) - sz[v] $$ 代码 #include <iostream> using namespace std; const int maxn = 1e5; struct edge { int next, to; } g[maxn << 1]; int head[maxn], w[maxn], f[maxn], sz[maxn], ecnt = 2; int ans = 2e9+5; void add_edge(int u, int v) { g[ecnt] = (edge) {head[u], v}; head[u] = ecnt ++; } void dfs1(int u, int fa, int dep) { sz[u] = w[u]; for (int e = head[u]; e; e = g[e].next) { int v = g[e].to; if (v == fa) continue; dfs1(v, u, dep + 1); sz[u] += sz[v]; } f[1] += w[u] * dep; } void dfs2(int u, int fa) { for (int e = head[u]; e; e = g[e].next) { int v = g[e].to; if (v == fa) continue; f[v] = f[u] + sz[1] - 2 * sz[v]; dfs2(v, u); } ans = min(ans, f[u]); } int main() { int n; cin >> n; for (int i = 1; i <= n; i ++) { int ww, u, v; cin >> ww >> u >> v; if (u) add_edge(u, i), add_edge(i, u); if (v) add_edge(v, i), add_edge(i, v); w[i] = ww; } dfs1(1, 0, 0); dfs2(1, 0); cout << ans << endl; return 0; }
Preface 刷 leetcode 好有成就感，毕竟在其他 OJ 直接被虐爆。 题面 https://leetcode-cn.com/problems/delete-columns-to-make-sorted-iii/ 题解 这不就是最长递增子序列吗...只不过现在多了点字符串。很容易可以得到转移方程： $$ f[i] = \max_{j < i, \forall s \Rightarrow s[j] \leq s[i]} f[j] + 1 $$ 其中 $f[i]$ 代表以 $i$ 为结尾的时候的最长递增子序列的长度。 $$ ans = s.length - \max f $$ 代码 const int maxn = 105; class Solution { int f[maxn]; public: int minDeletionSize(vector<string>& strs) { int n = strs.size(); int m = strs[0].size(); f[0] = 1; int ans = m - 1; for (int i = 1; i < m; i ++) { f[i] = 1; for (int j = 0; j < i; j ++) { bool cap = true; for (int p = 0; p < n; p ++) if (strs[p][j] > strs[p][i]) cap = false; if (!cap) continue; f[i] = max(f[i], f[j] + 1); } ans = min(ans, m - f[i]); } return ans; } };
Preface 随机跳题。 我现在真的暴怒。leetcode 这勾八 OJ 每组数据每次不会重新编译，而是会反复调用一个方法 😅。导致我的全局数组从来不清零。😅 题面 https://leetcode-cn.com/problems/longest-arithmetic-subsequence/ 题解 先推个朴素的方程。设 $f[i][d]$ 为以 $i$ 为结尾，以 $d$ 为公差的数列的最长长度： $$ f[i][d] = \max_{a[j] =a[i] - d} f[j][d] + 1 $$ 可以发现这个复杂度是 $O(n^2d)$，太大了，稍做优化，令 $d = a[i] - a[j]$，我们就可以顺序更新。 $$ f[i][d] = \max {f[i][d], f[j][d] + 1}, d = a[i] - a[j] $$ 还有一些细节，比方说 d 的范围，我们可以做一个线性变换，把负的映射成正的。 代码 const int maxn = 1e3+5; class Solution { int f[maxn][maxn], n, a[maxn]; public: int longestArithSeqLength(vector<int>& nums) { n = nums.size(); for (int i = 0; i < n; i ++) a[i + 1] = nums[i]; int ans = 0; for (int i = 1; i <= n; i ++) for (int j = 1; j < i; j ++) { int d = a[i] - a[j] + 500; f[i][d] = max(f[i][d], f[j][d] + 1); ans = max(ans, f[i][d]); } return ans + 1; } };