Q779’s Blog

SP2916 GSS5 - Can you answer these queries V 题解 题目链接：SP2916 GSS5 - Can you answer these queries V 题意： 多组数据。每组数据给定一个长度为 \(n\) 的序列 \(a_i\) 。 \(q\) 次询问，查询左端点在 \([x_1, y_1]\) 之间，且右端点在 \([x_2, y_2]\) 之间的最大子段和 数据保证 \(x_1\leq x_2,y_1\leq y_2\) ，但是不保证端点所在的区间不重合。 数据范围： \(1 \le T\le 5, ~1\le n \le 10^4,~ |a_i| \le 10^4,~1\le q \le 10^4\) 。 首先要先做下 GSS1 或 GSS3 ，知道怎么用线段树维护区间最大子段和。 然后这道题其实只是在询问上做了一些修改。 对于 \(r_1 < l_2\) 的情况，很简单，就是 \([l_1,r_1]\) 的 \(\mathtt{pre}\) 加 \([l_2,r_2]\) 的 \(\mathtt{suf}\) 加 \(...

洛谷P4314 CPU 监控 题解 题目链接：P4314 CPU 监控 题意： 维护一个数据结构，支持 询问区间最大值。 询问区间历史最大值。 区间加法。 区间赋值。 数据范围： \(1\le T,E\le 10^5,~1\le X\le Y\lt T,~-2^{31}\leq Z\lt 2^{31}\)。 对于每个结点，我们需要维护 \(6 + 1\) 个值，分别对应 加法标记、历史最大加法标记、赋值标记、历史最大赋值标记、最大值、历史最大值、是否存在赋值标记。 肯定有人和我一样好奇为什么要维护历史最大的标记。 因为修改是基于标记的修改，当标记下传时可能不是历史最大值对应的标记。 打个比方，区间 \(+1\) 再 \(-1\) 。加法标记变成了 \(0\) ，但是我们历史最大加法标记应当是 \(1\) ，历史最大值应为 \(1\) 。 接下来就是维护的细节了。 \(\mathtt{push\_up}\) 函数比较简单，就是合并一下最大值和历史最大值。 询问和修改也没啥特别的，主要难在 \(\mathtt{push\_down}\) 函数。 首先搞清楚我们的标记处理顺序：...

洛谷P6154 游走 题解 题目链接：P6154 游走 题意： S 城可以看作一个有 \(n\) 个点 \(m\) 条边的有向无环图。可能存在重边。 cxy 在 S 城随机游走，她会在所有路径中随机选择一条路径，选择所有路径的概率相等。路径的起点和终点可以相同。 定义一条路径的长度为经过的边数，你需要求出 cxy 走的路径长度的期望，答案对 \(998244353\) 取模。 输入格式： 第一行两个整数 \(n,m\)。 接下来 \(m\) 行，每行两个整数 \(x,y\)，表示存在一条从 \(x\) 到 \(y\) 的有向边。 输出格式： 一行一个整数，表示答案对 \(998244353\) 取模后的值。 数据范围： \(1\le n \le 10^5,~0 \le m \le 7\times 10^5\) 。 期望dp + topo 小清新题~ 设 \(f_u\) 表示以 \(u\) 为终点的路径总长度，\(g_u\) 表示以 \(u\) 为终点的路径总条数。 考虑以拓扑序转移。对于边 \((u,v)\) ，有转移（其中 \(a \uparrow b + c\) 表示 a...

洛谷P1137 旅行计划 题解 题目链接：P1137 旅行计划 题意： 小明要去一个国家旅游。这个国家有 \(N\) 个城市，编号为 \(1\) 至 \(N\) ，并且有 \(M\) 条道路连接着，小明准备从其中一个城市出发，并只往东走到城市 \(i\) 停止。 所以他就需要选择最先到达的城市，并制定一条路线以城市 \(i\) 为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。 现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的 \(i\) ，都需要你为小明制定一条路线，并求出以城市\(i\)为终点最多能够游览多少个城市。 输入格式： 第\(1\)行为两个正整数 \(N, M\) 。 接下来 \(M\) 行，每行两个正整数 \(x, y\) ，表示了有一条连接城市 \(x\) 与城市 \(y\) 的道路，保证了城市 \(x\) 在城市 \(y\) 西面。 输出格式： 共 \(N\) 行，第 \(i\) 行包含一个正整数，表示以第 \(i\) 个城市为终点最多能游览多少个城...

洛谷P1960 郁闷的记者 题解 题目链接：P1960 郁闷的记者 题意： 你是一个体育报社的记者，你接受到一个艰难的任务：有N支足球队参加足球比赛，现在给你一些比赛的结果，需要你给出各支球队的排名，从1到N。 以下是给你的一些信息： (1)没有平局； (2)不同的球队排名不能相同； (3)对于所有满足l≤a<b≤n，第a名的球队一定可以打败第b名的球队。 给你部分比赛结果，要求给出排名，并且判断是否存在另一种排名方法满足给你的比赛结果。 输入格式 第一行输入N(1≤N≤5000)，表示球队的数量，编号为l到N。第二行输入M(1≤M≤100,000)，表示给出的比赛场数。接下来M行，每行两个整数X_i，Y_i，表示X_i能打败Y_i。 输出格式： 输出包含N+1行，前N行描述球队的排名，第i个数表示第i名的球队，第N+1行包含一个整数，如果为0表示不存在其他的排名方法，如果为1表示还有其他的排名方法。 数据范围： \(1\le N\le 5000,~1\le M\le 10^5\) 。 注意到如果某一时刻出现多个度数为 \(0\) 的结点，则拓扑序不唯一。 时间复杂度 ...

洛谷P2767 树的数量 题解 题目链接：P2767 树的数量 题意： 求出包含 \(n\) 个节点（无标号）的有根 \(m\) 叉树的个数，对 \(10\,007\) 取模。 两个有根树相同，当且仅当其根节点相同，且从左到右每一棵子树也相同。特别地，两个有根树均为空树，视为两个有根树相同。 输入格式： 输入两个整数 \(n\)，\(m\)。 输出格式： 输出包含 \(n\) 个节点（无标号）的有根 \(m\) 叉树的个数，对 \(10\,007\) 取模后的值。数据范围： \(n,m \leq 127\) 这题可以 \(\mathcal{O}(p + \log_m n)\) 做，需要用到生成函数&拉格朗日反演。不会，可以看这篇。 这里讲 dp 的做法。 设 \(f_{i,j}\) 表示 \(i\) 个点，根节点有至多 \(j\) 棵子树时的方案数。考虑转移 枚举点数 \(k\) ，把这 \(k\) 个点拆成一个新的子树算。容易发现不会算重。 \[ f_{i,j} = \sum_{k=0}^{i-1}f_{k,m}\times f_{i-k,j-1} \] 时间复杂度...

\(n\) 倍角公式 居然还写过这玩意 \[ \begin{aligned} \sin n\vartheta &= \sum\limits_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^iC_n^{2i+1}\cos^{n-2i-1}\vartheta\sin^{2i+1}\vartheta \\[6pt] \cos n\vartheta &= \sum\limits_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^iC_n^{2i}\cos^{n-2i}\vartheta\sin^{2i}\vartheta \end{aligned} \]

全概率公式&贝叶斯公式 全概率公式 设 \(B_1,B_2 ,\dots B_n\) 为一组两两互斥的事件，且有 \[ \bigcup\limits_{1 \le i \le n} B_i = \Omega \] 则对任意的事件 \(A \in \Omega\) 有 \[ P(A) = \sum_{i=1}^n P(B_i)P(A \mid B_i) \] 贝叶斯公式 设 \(B_1,B_2 ,\dots B_n\) 为一组两两互斥的事件，且有 \[ \bigcup\limits_{1 \le i \le n} B_i = \Omega \] 则对任意的事件 \(A \subseteq \Omega,~A \ne \varnothing\) 有 \[ P(B_i \mid A) = \dfrac{P(B_i)P(A\mid B_i)}{P(A)} = \dfrac{P(B_i)P(A\mid B_i)}{\sum_{i=1}^n P(B_i)P(A \mid B_i)} \]

直线方程 直线方程的几种形式 名称 已知条件 标准方程 适用范围 点斜式 斜率 \(k\) ，直线上一点 \((x_0,y_0)\) \(y-y_0 = k(x-x_0)\) 斜率 \(k\) 存在 斜截式 斜率 \(k\) ，\(y\) 轴上截距 \(b\) \(y=kx+b\) 斜率 \(k\) 存在 两点式 直线上两个定点 \((x_1,y_1),(x_2,y_2)(x_1\ne x_2,y_1\ne y_2)\) \(\dfrac{y-y_1}{y_2-y_1} = \dfrac{x-x_1}{x_2-x_1}\) 不垂直于坐标轴 截距式 \(x,y\) 轴上的截距 \(a,b(ab\ne 0)\) \(\dfrac{x}{a}+\dfrac{y}{b} =1\) 不垂直于坐标轴且不过原点 一般式 \(A,B\) 不同时等于 \(0\) \(Ax+By+C=0\) 通用 点 \((x_0,y_0)\) 到直线 \(Ax+By+C=0\) 的距离公式 \[ d=\dfrac{\left|Ax_0+By_0+C\right|...

线性回归 学习笔记 又是不知道什么时候的，先放在这，待研究。 经验回归直线 \(\bar{y} = \hat{a}\bar{x}+\hat{b}\) ，满足 \[ \begin{cases} \hat{b} = \dfrac{\sum\limits_{i=1}^{n}(x_i-\bar{x})(y_i-\bar{y})}{\sum\limits_{i=1}^{n}(x_i-\bar{x})^2} = \dfrac{\sum\limits_{i=1}^{n}x_iy_i-n\bar{x}\bar{y}}{\sum\limits_{i=1}^{n}x^2-n\bar{x}^2}, \\[8pt] \hat{a} = \bar{y} - \hat{b}\bar{x} \end{cases} \]

辅助角公式及其证明 不知道什么时候写的，属于未发布状态，嗨害嘿。 辅助角公式： \[ a\sin x+b\cos x = \sqrt{a^2+b^2} \sin\left(\textstyle x + \arctan \frac{b}{a}\right) \] 证明： 设 \(-\frac{\pi}{2}<\vartheta<\frac{\pi}{2}\) ，使得 \[ \cos \vartheta =\dfrac{a}{\sqrt{a^2+b^2}} \\ \sin \vartheta = \dfrac{b}{\sqrt{a^2+b^2}} \] 则 \(\vartheta = \arctan \frac{b}{a}\) ，故 \[ \begin{aligned} a\sin x + b\cos x &= \sqrt{a^2+b^2}(\cos \vartheta \sin x + \sin \vartheta \cos x) \\[6pt]&= \sqrt{a^2+b^2} \sin(x + \vartheta) \\[6pt]&= \s...

CF1401D Maximum Distributed Tree 题解 题目链接：CF1401D Maximum Distributed Tree 题意： 给定一棵 \(n\) 个节点，\(n-1\) 条边的树。你可以在每一条树上的边标上边权，使得： 每个边权都为 正整数； 这 \(n-1\) 个边权的 乘积 等于 \(k\)； 边权为 \(1\) 的边的数量最少。 定义 \(f(u,v)\) 表示节点 \(u\) 到节点 \(v\) 的简单路径经过的边权总和。你的任务是让 \(\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} f(i,j)\) 最大。 最终答案可能很大，对 \(10^9+7\) 取模即可。 \(k\) 有可能很大，输入数据中包含了 \(m\) 个质数 \(p_i\)，那么 \(k\) 为这些质数的乘积。 输入格式： 第一行，一个整数 \(t\) \((1\leq t\leq 100)\)，表示多组测试数据个数。对于每一个测试数据： 第一行，一个整数 \(n\) \((2\leq n\leq 10^5)\)，表示树...