Q779’s Blog

Codechef REBXOR 题解 题目链接：Nikitosh and xor 题意： 给定 \(n\) 个数 ，求 \[ \max_{1 \le l_1 \le r_1 < l_2 \le r_2 \le n}\left\{\left(\bigoplus_{i=l_1}^{r_1} a_i\right) + \left(\bigoplus_{i=l_2}^{r_2} a_i\right)\right\} \] \(2 \le n \le 4\times 10^5,~0\le a_i \le 10^9\) 先考虑只有 \(\bigoplus_{i=l_1}^{r_1} a_i\) 该怎么求 u1s1，我觉得目前能看到我博客的人应该都会求 \(\bigoplus_{i=l_1}^{r_1} a_i\) 的最大值吧 那就直接建一个 \(\mathtt{01trie}\) 把异或前缀和全插入 然后在树上贪心找较大异或值就好啦 那么两个的情况其实是一样的 其实难在选第二个可能会与第一个有交集，以及不好枚举之类的问题 考虑从左往右依次插入每个串，这样枚举第一个是不重不漏的 此时...

CF526G Spiders Evil Plan 题解 题目链接：CF526G Spiders Evil Plan 题意： 二次魔改自 link 最近 q779 迷上了一个叫做割绳子 3 的yúsì（游戏）。 这个游戏的要求是你要扮演蜘蛛去吃掉一个糖果。 那是一个像割绳子游戏一样的界面，共有 \(n\) 个节点，和 \(n-1\) 条有长度的边，组成了一个树状结构。一共有 \(q\) 关，第 \(i\) 关，糖果在第 \(x_i\) 个节点上，共有 \(y_i\) 只蜘蛛。 每只蜘蛛可以用它的网去覆盖任意不同两点 \(a\) 和 \(b\) 之间的路径，因此，\(y\) 只蜘蛛可以覆盖 \(y\) 条树上路径的并。当然，不同的蜘蛛选择的路径可以相交。并且，具有如下的要求： \(y\) 条路径必须包含糖果所在的节点 \(x\)。 \(y\) 条路径的并是连通的。 使 \(y\) 条路径所经过的边的长度总和最大。 可是蜘蛛们好像都非常智障，所以它们需要你帮忙求出最大值。 本题强制在线 ，数据范围： \(1 \le x_i,y_i \le n,~1\le n,q \le 10^5...

LOJ6269 烷基计数 加强版 题解 题目链接：#6269. 烷基计数 加强版 题意：众所周知，大连 24 中是一所神奇的学校，在那里，化竞的同学很多都擅长写代码。 有一天，化学不及格的胡小兔向化竞巨佬晴岚请教化学题： “\(n\) 个碳原子的烷基共有多少种同分异构体？” 刚刚得了化竞全市第一的晴岚听了，认为这道题十分简单，建议胡小兔写个程序解决这个问题。但胡小兔弱得连什么是同分异构体都不知道，于是晴岚给胡小兔画了个图——例如 \(n=4\) 时 (即丁基)，有 \(4\) 种同分异构体： 同理，其他常见烷基同分异构体数目如下表： n 1 2 3 4 5 6 同分异构体数目 1 1 2 4 8 17 现在已知碳原子个数 \(n\)，求对应的烷基有多少种同分异构体。 答案对 \(10^9 + 7\) 取模。 数据范围： \(n \le 5\times 10^3\) 注意：这里的烷基计数不用考虑空间异构，能否稳定存在等各种特殊情况。也就是说，你要求的是 \(n\) 个点的每个点度数不超过 \(4\) 且根的度数不超过 \(3\) 的有根树的数目。 据说这种...

洛谷P3825 [NOI2017] 游戏 题解 题目链接：P3825 [NOI2017] 游戏 题意： 小 L 计划进行 \(n\) 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。 小 L 的赛车有三辆，分别用大写字母 \(A\)、\(B\)、\(C\) 表示。地图一共有四种，分别用小写字母 \(x\)、\(a\)、\(b\)、\(c\) 表示。 其中，赛车 \(A\) 不适合在地图 \(a\) 上使用，赛车 \(B\) 不适合在地图 \(b\) 上使用，赛车 \(C\) 不适合在地图 \(c\) 上使用，而地图 \(x\) 则适合所有赛车参加。 适合所有赛车参加的地图并不多见，最多只会有 \(d\) 张。 \(n\) 场游戏的地图可以用一个小写字母组成的字符串描述。例如：\(S=\texttt{xaabxcbc}\) 表示小L计划进行 \(8\) 场游戏，其中第 \(1\) 场和第 \(5\) 场的地图类型是 \(x\)，适合所有赛车，第 \(2\) 场和第 \(3\) 场的地图是 \(a\)，不适合赛车 \(A\)，第 \(4\) 场和第 \(7\)...

洛谷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+...