Q779’s Blog

洛谷P6348 [PA2011]Journeys 题解 题目链接：P6348 [PA2011]Journeys 题意： 给定 \(n\) 个结点， \(m\) 次操作 每次操作给出 \(a,b,c,d\) ，表示 \[ \forall x\in [a,b],\forall y\in [c,d], \exist (x,y) \in E\land (y,x) \in E \] 也就是编号在 \([a,b]\) 内的所有结点与编号在 \([c,d]\) 内的结点存在边权为 \(1\) 的无向边 求 \(s\) 到每个点的最短路。 \(1\le n\le 5\times 10^5\)，\(1\le m\le 10^5\)，\(1\le a\le b\le n\)，\(1\le c\le d\le n\)。 线段树优化建图板子（区间连区间），不会单点连区间的戳这里 同样的，我们还是建两棵树，称为「入树」和「出树」 先考虑连有向边的情况。 对于区间的修改，我们只需要把入树和出树中的结点提出来 称出树中提取的结点构成 \(S\) ，入树中提取的结点构成 \(T\) 我们新建一个虚点 \(u...

CF786B Legacy 题解 题目链接：CF786B Legacy 题意： \(n\) 个结点， \(q\) 次操作，问操作后从 \(s\) 出发的单源最短路 操作如下 输入 1 u v w 表示 \(u\) 到 \(v\) 连一条有向边 输入 2 u l r w 表示 \(u\) 到 \([l,r]\) 的每个结点连一条有向边 输入 3 u l r w 表示 \([l,r]\) 的每个结点向 \(u\) 连一条有向边 对于 \(100\%\) 的数据，\(1\le n,q \le 10^5\)，\(1\le w \le 10^9\) 线段树优化建图的板子 考虑建两棵线段树，分别称为「入树」和「出树」 入树的父节点向子结点连一条边权为 \(0\) 的有向边 出树的子节点向父结点连一条边权为 \(0\) 的有向边 两棵树的叶子结点均表示原图中的点 这样每次区间的连边，我们直接在线段树上把管理对应区间的结点当作 \(v\) 即可 具体地， 把 \(u\) 到 \([l,r]\) 的每个结点连一条有向边 我们只要找出在入树上对应的结点，把出树中的 \(u\) 向这些结点都...

洛谷P3311 [SDOI2014] 数数 题解 题目链接：P3311 [SDOI2014] 数数 题意： 我们称一个正整数 \(x\) 是幸运数，当且仅当它的十进制表示中不包含数字串集合 \(s\) 中任意一个元素作为其子串。例如当 \(s = \{22, 333, 0233\}\) 时，\(233\) 是幸运数，\(2333\)、\(20233\)、\(3223\) 不是幸运数。给定 \(n\) 和 \(s\)，计算不大于 \(n\) 的幸运数个数。 答案对 \(10^9 + 7\) 取模。 \(1 \leq n < 10^{1201}\)，\(1 \leq m \leq 100\)，\(1 \leq \sum_{i = 1}^m |s_i| \leq 1500\)，\(\min_{i = 1}^m |s_i| \geq 1\)，其中 \(|s_i|\) 表示字符串 \(s_i\) 的长度。\(n\) 没有前导 \(0\)，但是 \(s_i\) 可能有前导 \(0\)。 关键词：数位dp、AC自动机 可能的前置芝士：P4052 [JSOI2007]文本生成器 （涉及...

洛谷P3193 [HNOI2008]GT考试 题解 题目链接：P3193 [HNOI2008]GT考试 题意： 阿申准备报名参加 GT 考试，准考证号为 \(N\) 位数\(X_1,X_2…X_n(0\le X_i\le9)\)，他不希望准考证号上出现不吉利的数字。 他的不吉利数字\(A_1,A_2…A_m(0\le A_i\le 9)\) 有 \(M\) 位，不出现是指 \(X_1,X_2…X_n\) 中没有恰好一段等于 \(A_1,A_2…A_m\)，\(A_1\) 和\(X_1\) 可以为 \(0\) \(N\leq10^9,M\leq20,K\leq1000\) 显然是矩阵快速幂优化dp（看数据范围）。 设 \(f_{i,j}\) 表示考虑到第 \(i\) 个数，匹配到 \(X\) 的第 \(j\) 位时的方案数，则 \[ f_{i,j} = \sum_{k=0}^{9}f_{i-1,p} \] 注意这里的 \(0\le j < m\) ，因为我们不能让它包含完整的 \(X\) 。 这个 \(p\) 不一定是 \(0\) 或 \(j-1\) ，根据KMP的性质可...

OI数学总结-博弈论 施工中，咕咕咕… 博弈论基础 对于博弈论的题目，重点考虑以下两点 什么时候可以判定胜利者 先手的影响

OI数学总结-其他 本文充满了从各种地方偷学来的东西以及没什么分类的东西 数值积分 定积分 简单来说，函数 \(f(x)\) 在区间 \([l,r]\) 上的定积分 \(\int_{l}^{r}f(x)\mathrm{d}x\) 指的是 \(f(x)\) 在区间 \([l,r]\) 中于 \(x\) 轴围成的区域的面积（其中 \(x\) 轴上方的部分为正值， \(x\) 轴下方的部分为负值） 辛普森法 辛普森公式 对于一个二次函数 \(f(x) = Ax^2 + Bx + C\) ，有 \[ \int_l^rf(x)\mathrm{d}x = \dfrac{(r-l)\left(f(l)+f(r)+4f\left(\frac{l+r}{2}\right)\right)}{6} \] 推导过程： 对于一个二次函数 \(f(x)=Ax^2+Bx+C\) ； 求积分可得 \(F(x)=\int_0^x f(x) {\mathrm d}x = \frac{a}{3}x^3+\frac{b}{2}x^2+cx+D\) 在这里 D 是一个常数，那么 \[ \begin{aligned} \...

OI数学总结-群论 施工中，咕咕咕…. 群的基本概念 群的定义 群公理包含下述四个性质（有时略去封闭性，只有三个性质）。若集合 \(G\neq\varnothing\) 和 \(G\) 上的运算 \(\cdot\) 构成的代数结构 \((G,\cdot)\) 满足以下性质： 封闭性：对于所有 \(G\) 中 \(a, b\) ，运算 \(a·b\) 的结果也在 \(G\) 中。 结合律：对于 \(G\) 中所有的 \(a, b, c\) ，等式 \((a \cdot b)\cdot c = a \cdot (b \cdot c)\) 成立。 标识元（单位元）： \(G\) 中存在一个元素 \(e\) ，使得对于 \(G\) 中的每一个 \(a\) ，都有一个 \(e \cdot a=a\cdot e=a\) 成立。这样的元素是独一无二的。它被称为群的标识元素。 逆元：对于每个 \(G\) 中的 \(a\) ，总存在 \(G\) 中的一个元素 \(b\) 使 \(a \cdot b = b \cdot a = e\) ，此处 \(e\) 为单位元，称 \(b\) 为 \(a\) ...

OI数学总结-数论 注意，本文不同于 OI模板-数学 本文倾向于数学概念，但是包含部分代码，只是因为数论的内容与代码联系紧密，因此显得较为相似。 积性函数 数论中定义：定义域为正整数域的函数 \(f(n)\) ， 且满足 \(\forall a,b \in \mathbb{Z} _+,f(ab)=f(a)f(b) \land \gcd(a,b)=1\) 完全积性函数 数论中定义：定义域为正整数域的函数 \(f(n)\) ， 且满足 \(\forall a,b \in \mathbb{Z} _+,f(ab)=f(a)f(b)\) 最大公约数 gcd 最大公约数指能够整除多个不全为零的整数的最大正整数 常用性质： \(a\times b = \gcd(a,b) \times \mathrm{lcm}(a,b)\) 代码求解 int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } // 注意这份代码对于(+,-)的情况会求出负数 裴蜀定理 设 \(a,b\) 是不全为零的整数，则存在整数，使得 \(ax+...

CF708E Student’s Camp 题解 题目链接：CF708E Student’s Camp 题意： 有一个 \((n+2) \times m\) 的网格。 给定 \(n,m,a,b,k\) ，记 \(p=\frac{a}{b}\) 除了第 \(0\) 行和第 \(n+1\) 行，其他每一行 白天最左边的格子有 \(p\) 的概率被吹走。 夜晚最右边的格子有 \(p\) 的概率被吹走。 如果网格（包括第 \(0\) 行和第 \(n+1\) 行）被分成了两个及以上连通分量，则称网格不连通。 求 \(k\) 天后，网格始终保持连通的概率。 \(n,m \le 1.5 \times 10^3,~k \le 10^5,~a < b \le 10^9\)，答案对 \(10^9+7\) 取模。 特别🐮🍺的一道题，考虑概率dp。 下文中出现的奇怪变量名（因为参考自 link），先给出对应的代码形式 $_i$ pl[i] ，\(\mathtt{pr}_i \to\) pr[i] \(F_{i,j} \to\) F[i][j] ， \(\mathtt{sl}_{i,j...

CF178F3 Representative Sampling 题解 题目链接：CF178F3 Representative Sampling 题意： 有 \(n\) 个字符串 \(a_i\) ，从中选取 \(k\) 个，使它们两两之间的 \(\text{LCP}\)（最长公共前缀）之和最大。输出这个最大值。 \(k\le n\le 2000,|a_i|\le 500\) 看到最长公共前缀我还愣了一下，这不裸的 \(\tt{trie}\) 树吗，然后想了半天不会。。 考虑建 \(\tt{trie}\) 树然后在上面做树上背包 注意这里背包能选的“物品”只有 \(\tt{trie}\) 树上「是字符串结尾的结点」 方便起见，称「是字符串结尾的结点」为「串结点」 两两串结点的贡献，也就是他们的最长公共前缀（LCP）长度，其实就是他们的LCA深度。 记 \(i\) 的子结点 \(c_1,c_2,\cdots,c_{\lambda_i}\) ，设 \(f_{c_k,j}\) 表示以 \(i\) 为根的子树中，只考虑 \(c_1,c_2,\cdots,c_k\) ，选 \(j\) 个串...

BZOJ2141 排队 题解 题目链接：#2141. 排队 题意： 一句话题意： 给定 \(n\) 个数，\(Q\) 次询问，每次交换两个不同位置的数，然后输出逆序对数。 \(1 \le n \le 2\times 10^4,~1\le Q \le 2 \times 10^3\) 排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。 不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为 \(h_i (1\le h_i \le 10^9)\) ，我们定义一个序列的杂乱程度为：满足 \(h_i>h_j\) 的 \((i, j)\) 数量。幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。 这题还是比较水的。 首先朴素的逆序对不会有人不会吧（不会吧不会吧 ，不会的戳这里 考虑一次修改会对答案产生什么影响 设交换 \(a_l\)...

小蓝书 16.1 一、计数原理 1. 加法原理 设完成某件事有 \(m\) 类不同的方法， 第 \(i(1\le i \le m)\) 类方法中有 \(n_i\) 种不同的方法，则完成这件事共有 \[ n_1 + n_2 + \cdots + n_m \] 种方法。 在严格化的数学中，加法原理是有关集合大小的事实。1 断言任意有限多个两两互斥的集合大小之和，等于其并集的大小 以符号表示为，若集合 \(S_1,S_2,\cdots,S_n\) 两两互斥，则有 \[ |S_1|+|S_2| + \cdots + |S_n| = |S_1 \cup S_2 \cup \cdots S_n| \] 容斥原理可以视为加法原理的推广。 2. 乘法原理 设完成某件事需要 \(m\) 个步骤， 做第 \(i\) 步有 \(n_i\) 种不同的方法，则完成这件事共有 \[ n_1 \times n_2 \times \cdots \times n_m \] 在集合论中，乘法原理可以设为基数乘积的定义。2 对于集合 \(S_1,S_2,\cdots,S_n\) ，以 \(|S_i|\) 表示 ...