Posts by hostmaster

清晰版 前置知识 全微分 偏微分 积分 概述 拉格朗日乘数（Lagrange multiplier，又称 拉格朗日乘数法）用来解决 存在关系的多变量中的最值问题。 其实感觉在 OI 中使用得比较少。但是在数学填空题里或许可以发挥一些作用。还有可以在朋友面前装逼。 公式 众所周知，函数微分之后可以求出极值，但很多时候找到该函数的显式表达是很…

题意 定义斐波那契数列（Fibonacci sequence) $F\left(x\right) = F\left(x - 1\right) + F\left(x - 2\right)$，特别 $F\left(1\right) = F\left(2\right) = 1$。 给定长度为 $n$ 的数组 $a$，维护 $m$ 个操作，对于每…

更早 摸鱼 教练把给我的密码打错两个字母 Day -1 颓废 + 摆烂，反正 CSP 考得还算行，NOIP 不是很重要。 Day 1 在长郡考的欸。 长郡机器看起来挺好的，一个 i5。 T1 8: 58 调完。写的是一个 777777773 为模数 以及 一个 int64 自然溢出的双哈希。 T2 我印象中应该写了有两个小时，但最终得分…

题意 给定一个 01 串 $s$。每次操作你可以在任意位置插入一个字符串 $\texttt{01}$，问是否能在 $300$ 次操作以内，使得 $s$ 与 $s'$ 的对应位置都不相同（其中 $s'$ 表示 $s$ 首位翻转后的字符串，即 ${s'}_i = s_{\left\lvert s\right\rvert - i + 1}$）。…

题意 给定 $n$ 个点，$m$ 条线段。你可以删除其中的 $k$ 条线段，问最终最多有多少点可以不被任何区间覆盖。 $1 \leq n \leq 2 \times 10^5, 2 \leq m \leq 2 \times 10^5, 2 \leq k \leq 10$ 在简单版本中，$k = 2$。 题解 首先看简单版本。如果有一个点被…

开始学文化课了，这个计划会鸽一鸽 放寒假了，这个计划会加快进度 这个计划废弃了，因为有了新计划 刷题！ 1. 规划 展开 题意 给定一棵大小为 $n$ 的树。 给定两个长度为 $n$ 的数组 $a$ 与 $b$。在 $1$ 到 $n$ 中选出 $m$ 个点，使得选出的点联通，求选出的点的 $a_i$ 之和 除以 选出的点的 $b_i$ 之…

概述 exBSGS（扩展大步小步法，ex Baby Step Giant Step）可以在 $\Theta\left(\sqrt p \log p\right)$ 的时间内求解关于 $x$ 的方程 $a^x \equiv b \pmod p$ （不要求 $a$ 与 $p$ 互质）的最小整数解。 前置知识 BSGS exBSGS 我们知道，…

概述 BSGS（大步小步法，Baby Step Giant Step）可以在 $\Theta\left(\sqrt p\right)$ 的时间内求解关于 $x$ 的方程 $a^x \equiv b \pmod p$ （要求 $a$ 与 $p$ 互质）的最小整数解。 BSGS 为了方便，我们设 $t = \left\lfloor \sqrt p \right\rfloor$…

概述 圆方树（Block forest）是一种将图变成树的方法。 极大点双连通子图 一个图的 点双连通分量 是一个 极大点双连通子图，注意到，同时包含两个节点的 极大点双连通子图 如果存在，那么它是唯一的。 圆方树 在圆方树中，原来的每个点对应一个 圆点，每一个 点双连通分量 对应一个 方点。 不难发现，圆方树的点数小于 $2n$。 建树…

图片看不清的可以在这里下载矢量图。 前言 ZKW 线段树由清华大学张昆玮在 2011 年发明。 网络上讲述 ZKW 的文章少，讲得明白的又是少之又少，因此整个 ZKW 线段树我都是半学半发明的，可能跟原本 ZKW 的想法不一样，但一定是对的（AC 证明 :D） 概述 ZKW 线段树不需要递归，常数极小，空间是普通线段树的一半。比较好写。可…