Arkweedy's Blog

3月过完了再写3月的题解不是很正常吗 1. CF2075F 一道扫描线的题目。 题意 定义好序列为序列左右两端分别为序列唯一最小值/最大值的序列，求给定数组中最长的好序列。 数组长 \(n = 5\times 10^5\),值域 \(a \leq 10^6\). 分析 可以发现如果答案中一个数作为左端点，那么这个数左边一定没有小于等于它的数，否则我们我们选择左边小于等于它的数一定是更优的(有可能增加序列长度)。对于右端点同理，右边应该没有大于等于它的数。 称这些左端点备选点/右端点备选点为左关键点/右关键点。我们可以用单调栈\(O(n)\)预处理出这些点。这些点的规模都可以达到\(O(n)\)。 把数组元素的索引看成 \(x\),值看成...

Möbius inversion, Möbius transformation and Inclusion-Exclusion on Posets pre 在算法竞赛中，Möbius反演主要出现在:一类推式子题用于数论分块优化/偏序集上的容斥/求解积性函数和Dirichlet卷积相关问题。而Möbius变换经常是解决位运算卷积之类的问题。 这篇blog主要用于梳理数论上这Möbius反演这及一些前置的知识，进一步的运用，以及Möbius变换的部分内涵，两种操作之间的联系。以及一些习题和其中的trick。 Part 1. Möbius inversion 前置知识 1. 积性函数 在数论中，算术函数（或称数论函数）指定义域为正整数、陪域为复数的函数，每个算术函数都可视为复数的序列。 这篇blog讨论的所有函数都是数论函数 积性函数： 如果一个函数\(f\)具有性质\(\forall( a,b,\gcd(a,b) = 1), f(ab)...

作用在排列上的异或运算 也不知道这一部分放在哪个类别下比较好,姑且放在数论下面了 前置知识 排列和置换 引入 偶尔在做算法题的时候会遇到需要研究一个区间的数都异或上一个数之后，这个区间的数的情况(这里情况指各种各样的性质)。不过我们可以把任意区间\([l,r]\)转化成两个排列\(P_{r},P_{l-1}\)的差。所以我们试图借助几个例题来研究排列异或一个数之后具有的性质。 以下是3个例题： CF1979B XOR Sequences CF2075E XOR Matrix CF Group:0x3f vp Group FireflyCup H Simple XOR Problem 分析 我们考虑一个无穷序列\(0,1,2,...\)异或上一个数\(x\)的情况。 显然，我们应该把\(x\)拆成不同二进制位来分析，或者说异或\(x\)的效果实际上是异或上\(x\)不同二进制位的效果的叠加。 于是我们可以转而分析异或\(2\)的自然数次幂的作用。 1. 如果\(xor...

DSU on tree 即树上启发式合并。 算法流程通常是通过dfs处理出树上每个点的重儿子，然后通过一个dfs算法来计算答案。对于一个节点，我们从重儿子继承信息，暴力合并轻儿子的信息，同时处理出每个点/点对/...对答案的贡献。 如果我们暴力合并轻儿子的时间复杂度和轻子树的大小成线性关系，那么由重链剖分的性质，一个点到根的路径最多有\(\log n\)条轻边，那么每个点的贡献实际上是\(logn\)级的，那么总的合并轻子复杂度为\(O(n\log n)\)(实际上这个常数很小，因为每个点最多只有\(\log n\)次贡献，很多点取不到这么大) 我们继承重子的操作数量级是\(O(n)\)的，如果我们可以确保每次继承重子的复杂度在\(O(1)\)或者\(O(\log n)\)的话，那么启发式合并总的时间复杂度在\(O(n\log...

CF 近期题解 鸽了好久，感觉还是多谢题解会更有提高 2056D 算法： 偏序，枚举，二值化(中位数的常见方法)， 前缀和 题意 求给定数组的所有子数组中，前中位数和后中位数相等的子数组的数量。数组值域\(\Omega\)为\(1 \sim 10\)。数组长\(10^5\)。 分析 由于值域很小，可以枚举中位数，将小于中位数的数赋值为\(-1\)，大于的赋值为\(1\)。 考虑某个区间小于,等于，大于所枚举的中位数的分别有\(l,m,r\)个，合法区间满足约束条件： \[\begin{cases} l + m > r \\ r + m > l \\ \end{cases}\] 方法一：正向统计 由此我们得到了合法区间满足的两个偏序关系： 对区间\([1,i]\),令$ f_i = l + m - r , g_i = r + m - l$ 对合法区间\([l,r]\)(l,r含义与前文不同，这里是区间端点)有偏序关系 \[\begin{cases} f_{l-1} < f_{r} \\ ...

ABC376 G - Treasure Hunting 相关算法：贪心，组合数学 Part 1 题意简述 给定一颗\(n+1\)个节点的以\(0\)为根的树,每个点有点权\(v\),每个点有宝藏的概率为\(\frac{v_i}{\sum v}\)。认为根已搜寻，可以搜寻一个节点当且仅当搜寻过它的父节点。求搜寻到宝藏的步数的最小期望。 当然，这个题意可以变换一下，即求一个访问序列\(p\)(这是一个长为\(n\)的排列)最小化\(\sum_{i = 1}^{n} i\cdot v_{p_i}\)(这里我们提出来公因子\(\frac{1}{\sum v}\)),\(p\)中父节点的下标严格小于子节点的下标。 数据范围: \(1≤N≤2×10^5\), \(\sum v \leq 1 \times 10^8\) Part 2...

CF Round988 div3 C 很简单的构造。 \(n \leq 4\)的时候是不可能的，很容易试探出来。 对于剩下的情况，由于偶数除了2都是合数，而两个不同的大于1的数的和均大于2，所以我们可以把奇数放一起，偶数放一起，此时只有分界处两数奇偶性不同，可能为质数。而此时我们可以选取4，5作为分界点的数。于是很容易构造出符合题意的排列。 code: 123456789101112131415161718192021222324252627282930313233void solve(){ int n; cin >> n; if (n <= 4) { cout << -1 << endl; } else { vector<int>ans(n); ans[(n-1) / 2] = 5; ans[(n-1) / 2 + 1] = 4; int p = 0; ...

ABC377 G - Edit to Match (3rd) (挺简单的，不过看来得好好学一下字符串算法了) 相关算法： 字典树 Part 1.题目概述 按顺序给出\(N\)个字符串，对于每个字符串，有两种操作，代价均为1： 1. 删掉最后一个字母 2. 在最后加上任意一个字母 求让每个字符串变成前面任一字符串或者空串的最小代价。 Part 2.分析 由于对第 \(i\) 个串 \(S\) 处理时，要考虑前面 \(i-1\) 个串的匹配问题，很自然想到对前面的串建一棵字典树(trie)。建立字典树时，我们同时记录每个节点到叶子节点的最小距离，那么我们遍历 \(S\) 时，很容易就可以统计出答案。 Part 3.实现 第一次写字典树，前后写了很多很dirty的代码。最后是用链表实现的trie，感觉比数组慢了不少。 对于插入操作，我们递归建树，同时返回与叶子节点的距离，以更新父节点与叶子节点最短距离的信息。对于查询答案的操作，我们遍历字符串，用 \(f[p]\) 表示删除 \(S\) 为字串...

ABC379 G - Count Grid 3-coloring (2nd) (G题之间亦有差距) 相关算法 : dp,枚举，复杂度估计 Part 1.题目概述 一个 \(n \times m\) 的矩阵，里面只有 \(1，2，3，?\),其中 \(?\) 为不确定的数。问有多少种可能使矩阵相邻元素不相同。其中 \(n\cdot m <= 200\)。 Part 2.分析 我们考虑从上到下从左到右逐格dp来确定每格的不同状态可能的情况。 dp设计 设 \(dp[i][val]\) 为填到第 \(i\) 个格子值为 \(val\)...

ABC378 G - Everlasting LIDS (1st) (是每日一寄的开始，虽然好像做不到每日一寄啦) 相关算法：序理论，杨表，钩长公式，dp Part 1.题目概述 题意很简单，给定限定\(A,B\)，要求构造出长为\(A\cdot B-1\)的且具有以下性质的排列\(P\)： 1. 最长上升子序列(LIS)为\(A\). 2. 最长下降子序列(LDS)为\(B\). 3. 存在一个整数\(n\)使得在\(P\)的末尾添加\(n+0.5\)不会改变最长递增子序列和最长递减子序列的长度 求可行的构造方案数，结果输出方案数模素数\(M\)。 Part 2.杨表 解决这题需要一些前置知识：杨表 英式画法的杨表由有限个相邻的方格排列而成，其中，各横行的左边对齐，长度从上到下递增。 标准杨表：在杨表的 n个方格中任意填入1到n中的相异正整数，各行和各列中的数字皆严格递增。 显然，杨表代表着一种二维表示的偏序。而这种拓扑序可以与一个排列的LIS和LDS相关联。 引入RSK算法(杨表的插入算法)： 令 \(S\) 是一个杨表，定义 \(S...