Sophonの博客

Day -1 因疫情原因，PKUSC 2022 改为线上进行。 听教练说审核通过了，好耶。 如果不是线上进行，像你这种菜鸡也不可能报名通过好吧。 听说信息组别的同学报的都是 THUSC……我是不是脑抽（其实是因为 THUSC 的报名信息没时间填写（PKUSC 只有一个简单的报名表格。） Day 0 又是备战中考的一天。 你再怎么准备 PKUSC 也不可能拿奖，你在想什么。 Day 1 雅礼集团好像只有我和 lrj 学长报了 PKUSC（ 试机题不会。 T1 概率期望，T2 计算几何，T3 概率期望。 恰好都是我平时从来不学的技能。 《如果早知道，PKUSC 有三道数学题》 T1 应该是消元但写了半天发现读错题了，读完题之后还是不会。 T2 先写了个暴力，枚举累加每一条线段在长方形区域内的部分的长度。Subtask 3 不懂性质，Subtask 4 中所有线段的斜率都是 -1 然而我还是不会（ T3 Subtask1 考虑每只猫的比值 \(c\) 都相等，就变成了解一个方程，剩下的部分分好像是高斯消元？然而还是不会写（ Day1：0 + 18 + 12 = 30，告辞 晚上打了场 ABC ...

Day -8 打了带花树的板子。 没用的知识增加了。（省选考这种东西吗。） Day -6 在 CodeForces 上和 hzk 组队 VP 了场 ICPC（2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest），打得还不错，应该不会提前用掉 RP？（RP++） 然后一看 QQ 群才发现同学们都在写 Public OJ 的模拟赛。（小丑竟是我自己） Day -4 打了 KD-Tree 的板子（天使玩偶）。 没用的知识又增加了。 Day -1 日常在家里上网课，省选对初中生来说可能不太重要？信息组也没有什么停课之类的安排，初三最重要的还是中考。 Day 0 上午信息组召开动员大会（由于疫情影响，动员大会转为线上在腾讯会议进行。），然后打了 FFT、NTT、MTT 和几个多项式全家桶，中途调试 1h+，然后去打数据结构，线段树、Splay、分块、珂朵莉树（省选真的可能考这玩意吗）。打板子的效率不高，可能本来对省选就没抱什么期望？反正现在连中考都比省选更重要，中考考不好省选有个锤子用。 下午继续打板子，SAM 打完 ...

分析 我们会发现这道题本质上是一个线性规划问题： \[h_i + l_j \ge w_{i,j}\] \[h_i \ge 0 (\forall 1 \le i \le n)\] \[l_j \ge 0 (\forall 1 \le j \le n)\] \[\operatorname{minimize} \sum_{i = 1}^{n} h_i + \sum_{j = 1}^{n} l_j\] 我们考虑它的对偶线性规划。 对偶线性规划 所谓对偶线性规划是指： 原问题中的每个变量都变为对偶问题中的一个限制条件； 原问题中的每个限制条件都变为对偶问题中的一个变量； 原问题若是求目标函数的最大值，则对偶问题是求最小值，反之亦然。 另外还有“强对偶定理”，通俗的来说就是原问题的最优解等于对偶问题的最优解。 例如本题的对偶线性规划为： \[\sum_{j = 1}^{n} y_{i, j} \le 1 (\forall 1 \le i \le n) \] \[\sum_{i = 1}^{n} y_{i, j} \le 1 (\forall 1 \le j \le n) \] \[y_{i, ...

题目分析 可以看出这道题应该用网络流解决，但如果单纯使用网络流的话，“每条隧道需要一天时间来通过”就无法处理了。 在这道题中，我们注意到每台计算机能否移动与图当前的状态有关，而图当前的状态又与“时间”这一参数有关，所以我们建图时就应该考虑时间的影响，换句话说，建分层图。假设一共运送了 \(T\) 天，那么我们就可以将每个点 \(u\) 拆成 \(T + 1\) 个点 \(u_0\)、\(u_2\)、\(u_3\)、……、\(u_T\)，\(u_i\) 表示第 \(i\) 天的节点 \(u\)，具体实现时则使用 \(u_i = u + in\) 的方式来表示。 对于一条无向边 \((u, v)\)，我们从 \(u_i\) 向 \(v_{i + 1}\) 连容量为 \(1\) 的边，从 \(v_i\) 向 \(u_{i + 1}\) 连容量为 \(1\) 的边，表示飞船可以花一天的时间从 \(u\) 到 \(v\) 或从 \(v\) 到 \(u\)。同时，对于每一个节点 \(u\)，我们都从 \(u_i\) 向 \(u_{i + 1}\) 连容量为正无穷的边，表示飞船可以待在原地不动。 首 ...

题目分析 对于第一种情况，可以直接跑一遍最大流，如果最大流大于或等于 \(C\) 就可以直接输出 possible。 如果最大流小于 \(C\)，那么肯定是满流的边将其“卡住了”，所以应该依次枚举每条满流的边（没有满流的边增加容量也一定没用），将这些边的容量一个一个改为 \(C\)，再对于每条边修改后都跑一次最大流，如果这条边的容量改为 \(C\) 后最大流大于或等于 \(C\) 就将其记录到答案中。 除此之外还有两个个必要的优化：一、没必要每次都从头开始跑一遍最大流。在跑完第一遍之后将残量网络备份下来，每次改变边的容量时在残量网络上跑最大流，少做很多无用功；二，不需要每次都把最大流求出来，可以在最大流达到 \(C\) 时停止增广。 代码实现 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919 ...

题目分析 如果我们将要求拍照的人和下属之间按照要求关系连有向边，我们就会发现题目实际上是要求我们求出有向图的最大权闭合子图。即，在一张有向图上选择一个点集，要求点集中的每一个点的后继也都在这个点集中，使点集中点权和最大。 对于这类问题，有一个结论：从源点向所有正权点连边，边权为原点权；从所有负权点向汇点连边，边权为原点权的绝对值；原图中的边权设为正无穷。则最大权闭合子图的权值和 = 所有正权点的权值和 - 新图的最小割。 对结论的证明 我们先做如下约定： 割掉源点与正权点 \(u\) 之间的边，表示不选择点 \(u\) 进入子图。 割掉负权点 \(v\) 与汇点之间的边，表示选择点 \(v\) 进入子图。 则我们跑一遍最小割后得到的一定是闭合子图，证明如下：考虑任意得到的子图内的任意正权点 \(u\)，若存在其后继节点 \(v\) 没有被选择进入子图，分为两种情况：如果 \(v\) 权值为负，按照上述约定，点 \(v\) 与汇点间的边会被保留，源点与汇点联通，与最小割的定义矛盾；如果 \(v\) 权值为正，按照上述约定，源点与点 \(v\) 间的边会被割掉，但点 \(u\) 与点 ...

思路 一道带修莫队模板题。 看到题意中“单点修改，区间查询数字出现次数 \(mex\)” 的操作后，不难想到用带修莫队维护，但时间复杂度的正确性需要证明。 假设区间当前区间的 \(mex\) 为 \(n\)，则这个区间的数的个数至少为 \[\sum\limits_{i = 1}^{n}i = \dfrac{n(n + 1)}{2}\] 所以任何区间的答案肯定在 \(O(\sqrt{n})\) 级别，可以直接暴力查找 \(mex\)。 代码中也有一些要注意的细节：\(x_i\) 最大可以为 \(10^9\)，所以序列中的数和修改中的数都必须离散化。 统计时开两个数组，一个数组 cnt 统计每个数出现了几次，tot 统计这个出现次数出现了几次。由于 add 和 del 操作都会使 tot 数组改变两次，所以每次操作都要更新两遍 \(mex\)。具体操作如下： 123456789101112131415161718192021222324252627282930313233void add(int x) { tot[cnt[x]]--; if(tot[cnt[x]] = ...

A - Make Even 题意 输入一个数 \(n\)，每次操作可以翻转 \(n\) 的前 \(l\) 位，问最少要进行多少次操作才能使 \(n\) 变成偶数。 思路 分情况讨论： 如果这个数是偶数，答案显然为 0。 如果这个数是奇数，第一位为偶数，只需翻转整个数即可，答案为 1。 如果这个数是奇数，其中第 \(l\) 位是偶数，那么先翻转 \(1\) ~ \(l\) 位将它翻转到第一位，再翻转整个数即可。 否则，即如果这个数所有数位上都是奇数，那么不管进行多少次操作都无法变成偶数，输出 -1。 代码 123456789101112131415161718192021222324252627282930313233343536373839#include<cstdio>#include<cstring>using namespace std;int main() { int T; scanf("%d", &T); while(T--) { int n, a[15], l = 0 ...

A - AB Balance 题意 给出一个只由字符 \(a\) 和 \(b\) 组成的字符串 \(s\)，求最少的修改使 \(s\) 中 \(ab\) 的出现次数和 \(ba\) 的出现次数相等。 思路 \(s\) 中 \(ab\) 和 \(ba\) 都只会在连续段之间出现，并且交替出现，所以出现次数最多相差\(1\)。如果一共有奇数段，两者的出现次数肯定相等；如果有偶数段，只需要修改第一个字符就会变成奇数段。 所以只要出现次数不相等就修改第一个字符即可。 代码 1234567891011121314151617181920212223242526272829303132333435363738#include<cstdio>#include<cstring>using namespace std;const int MAXN = 100 + 5;char s[MAXN];int n;int main() { int T; scanf("%d", &T); while(T--) { ...

前言 看到异或便想到 Trie，便想到可持久化 Trie，OIer 的想象力唯在这一层面能如此跃进。——智子 （这篇文章的诞生原因主要其实是 @apple365 上星期说的某句话。） Trie 众所周知，Trie 树是一种用来处理字符串问题的数据结构。 P2580 于是他错误的点名开始了 洛谷 P2580 于是他错误的点名开始了 输入若干个字符串，查询每个字符串是否在给定的字符串中，或者有没有重复查询。 暴力显然会超时，哈希能解决但是非常丑陋，而 Trie 树可以优美地解决这个问题。Trie 树和核心思想是尽可能重复利用相同的前缀，将所有的字符串从前往后作为一条从根节点到叶子的路径插入到树中。 （图片转载自 OI-Wiki，遵循 CC BY-SA 4.0 协议。） 例如这道题，直接建立一棵 Trie 树并在末尾标记是否有字符串结束和是否已经被查询过即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616 ...