Q779’s Blog

洛谷P10199 [湖北省选模拟 2024] 时与风 / wind 题解 题目链接：P10199 [湖北省选模拟 2024] 时与风 / wind 题意： 风带来故事的种子，时间使之神话。 你在 \(N\) 个锚点间，沿着 \(M\) 条有向航道，使用风之翼进行飞行。锚点依次编号为 \(1,2,\cdots,N\)，有向航道依次编号为 \(1,2,\cdots,M\)。第 \(i\) 条航道的出发锚点为 \(u_i\)，到达锚点为 \(v_i\)。 由于巴巴斯托与时间存在神秘的联系，第 \(i\) 条航道将在时刻 \(O_i\) 开启，在时刻 \(C_i\) 后关闭。也就是说，对于任意的 \(O_i \le t \le C_i\)，你可以在时刻 \(t\) 由锚点 \(u_i\) 进入航道 \(i\)。进入航道后，空间上，你将直接到达锚点 \(v_i\)，时间上，时间将等概率的变化为 \([L_i,R_i]\) 中的一个实数对应的时刻。注意到达一个锚点后，你必须在同一时刻立刻进入下一段航道，否则你必须在此结束飞行。 你将从锚点 \(S\) 出发，尝试访问锚点 \(i(1\le ...

洛谷P10184 [YDOI R1] whk 题解 题目链接：P10184 [YDOI R1] whk 题意： 小 Z 一共要卷 \(n\) 门科目，第 \(i\) 门科目他有且只有 \(a_i\) 道题。有无数天时间，每天小 Z 可以做无数道题。 如果小 Z 认为一天是有趣的，仅当他在这一天至少做了 \(t\) 门科目的题。 小 Z 想知道最多有多少天是有趣的。 输入格式： 第一行，\(2\) 个正整数 \(n,t\)。 接下来一行，有 \(n\) 个整数，分别 \(a_1,a_2,a_3,\dots,a_{n-1},a_n\)。 输出格式： 一个整数，输出小 Z 认为有趣的天数的最大值。 数据范围： \(1\le t\le n\le5\times10^5\)，\(1\le a_i \le 10^6\)。 一开始想到的是贪心，即用堆维护最多的 \(t\) 种题，答案的增量为这 \(t\) 个中最小的那个。 不过这样的复杂度是 \(\mathcal{O}(nt\log n)\) 的，因为每次减去最小值最少只会去掉一个种类 实际上，我们只需要二分一下这个天数 \(x\) 就可以...

洛谷P2783 有机化学之神偶尔会做作弊 题解 题目链接：P2783 有机化学之神偶尔会做作弊 题意： 给你一个 \(n\) 个点，\(m\) 条边的无向图。 把图中所有的环变为一个点，求变化后某两个点之间有多少个点。 输入格式： 第一行两个整数 \(n,m\)。表示有 \(n\) 个点，\(m\) 根键。 接下来 \(m\) 行每行两个整数 \(u,v\) 表示 \(u\) 号碳和 \(v\) 号碳有一根键。 接下来一个整数 \(q\) 表示询问次数。 接下来 \(q\) 行每行两个整数，\(a,b\) 表示询问的两个碳的编号。 输出格式： 共 \(q\) 行，每行一个二进制数，表示答案。 数据范围： 对于 \(100\%\) 的数据，\(1<n\le10 ^ 4\)，\(1<m\le5\times 10 ^ 4\)。 还以为是什么好玩的化学题，搞了半天就是个板子题 思路是缩点以后维护前缀和，查询用 LCA 。 给不知道这个 trick 的同学讲一下吧，因为缩点以后一定是无环的，但不一定是链 所以我们钦定一个根，从叶子递归到根求出前缀和 \(d_i\) 。 那么...

洛谷P2558 [AHOI2002] 网络传输 题解 题目链接：P2558 [AHOI2002] 网络传输 题意： 在计算机网络中所有数据都是以二进制形式来传输的。但是在进行较大数据的传输时，直接使用该数的二进制形式加以传输则往往传输的位数过多。譬如要传输 \(1024\) 就需要 \(11\) 位二进制数。于是小可可提出了一种数据优化传输的设想，并打算对这一设想进行试验。 该设想是：正整数的所有方幂以及任意多个互不相等的 \(k\) 的方幂之和排成一个递增数列 \(\{a(k)n\}\)，例如当 \(k=3\) 时，\(\{a(k)n\}\) 的前 \(7\) 项为 \(1(=3^0)\) 、 \(3(=3^1)\) 、 \(4(=3^0+3^1)\) 、 \(9(=3^2)\) 、 \(10(=3^0+3^2)\) 、 \(12(=3^1+3^2)\) 、 \(13(=3^0+3^1+3^2)\)。 如果数 \(d\) 是数列 \(\{a(k)n\}\) 中的第 \(p\) 项，则可以通过传送 \(k\) 和 \(p\) 这两个数来表示数 \(d\)。由于 \(k\) 和 ...

洛谷P2441 角色属性树 题解 题目链接：P2441 角色属性树 题意： 绪萌同人社是一个有趣的组织，该组织结构是一个树形结构。有一个社长，直接下属一些副社长。每个副社长又直接下属一些部长……。 每个成员都有一个萌点的属性，萌点属性是由一些质数的萌元素乘积构成（例如，猫耳的值是 \(2\)，弱气的值是 \(3\)，黄毛的值是 \(5\)，病娇的值是 \(7\)，双马尾的值是 \(11\) 等等） 举个例子，正妹是双份的猫耳，而且有一份弱气，她的属性值为 \(2\times 2\times 3=12\)。 现在组员关心一个问题，希望知道离自己最近且有相同萌元素上司是谁，例如，属性值为 \(2、4、6、45\) 这样的属性值都算是和正妹有相同的属性。 然而，组员可能会随时变化自己的属性。啊。。感觉好麻烦啊。。 输入格式： 第一行，\(n,k\) 表示成员数与询问的次数 第二行，\(n\) 个数，分别是 \(1\) 到 \(n\) 号成员的属性值 接下来 \(n-1\) 行，\(x_i,y_i\) 表示 \(x_i\) 是 \(y_i\) 的上司。 接下来来 \(k\) 行，有两种...

欧拉乘积公式 \[ \zeta(z)=\prod_{p \in \mathbb{P}} \frac{1}{1-p^{-z}} \] 其中 \(\mathbb{P}\) 为全体质数，\(\zeta(z)\) 是黎曼函数。 证明： \[ \zeta(z)=1+\frac{1}{2^z}+\frac{1}{3^z}+\frac{1}{4^z}+\frac{1}{5^z}+\cdots\tag{1} \] \((1)\) 乘上 \(\frac{1}{2^z}\) 得 \[ \frac{1}{2^z} \zeta(z)=\frac{1}{2^z}+\frac{1}{4^z}+\frac{1}{6^z}+\frac{1}{8^z}+\frac{1}{10^z}+ \cdots\tag{2} \] \((1)\) 减 \((2)\) 得 \[ \left(1-\frac{1}{2^z}\right) \zeta(z)=1+\frac{1}{3^z}+\frac{1}{5^z}+\frac{1}{7^z}+\frac{1}{9^z}+\frac{1}{11^z}+\frac{1}{13^z}+\...

洛谷P2734 [USACO3.3] 游戏 A Game 题解 题目链接：P2734 [USACO3.3] 游戏 A Game 题意： 有如下一个双人游戏：\(N (2 \leq N \leq 100)\) 个正整数的序列放在一个游戏平台上，游戏由玩家 \(1\) 开始，两人轮流从序列的任意一端取一个数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。 编一个执行最优策略的程序，最优策略就是使玩家在与最好的对手对弈时，能得到的在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。 输入格式： 第一行: 正整数 \(N\)，表示序列中正整数的个数。 第二行至末尾: 用空格分隔的 \(N\) 个正整数（\(1\le N \le 200\)）。 输出格式： 只有一行，用空格分隔的两个整数: 依次为玩家一和玩家二最终的得分。 先讲 dp 解法，还是很巧妙的，需要对博弈论理解深刻。 如果我们设 \(f_{i,j}\) 表示区间 \([i,j]\) 先手的最优方案，那么有 \[ f_{i,j} = S_j - S_{i-1}-\m...

洛谷P2667 [TJOI2012] 防御 题解 题目链接：P2667 [TJOI2012] 防御 题意： 在一个塔防小游戏中，有很多防线。每条防线由一排 \(n\) 个独立的防御体 \([1 : n]\) 进行防御。 游戏过程中，会不断有敌人对防线进行攻击，每次攻击会指定防御体 \([l : r]\) 进行攻击力为 \(a\) 的攻击。第一防线具有护甲，护甲承受攻击后，对应的防御体所受到的伤害为攻击力，但护甲承受的伤害总量到达一定程度后就会破碎，此时防御体所受的伤害加倍。目前第一防线的力量充足，玩家致力于对后面的防线的建设，不过为确认游戏进度和第一防线的情况，玩家会不时地将鼠标移动到第一防线的某个防御体上，以查看其所受到的伤害。 输入格式： 第一行，两个整数 \(n\) 和 \(q\)，分别表示防御体个数以及攻击和查询的总数。 第二行，\(n\) 个数，表示每个防御体护甲的承受能力 \(p_i\) 。 接下来 \(q\) 行，每行可能具有如下形式： A l r a 表示对防御体 \(l,l+1,\cdots,r\) 进行攻击力为 \(a\) 的攻击； Q x 表示查询防御体 ...

洛谷P2411 [USACO07FEB] Silver Lilypad Pond S 题解 题目链接：P2411 [USACO07FEB] Silver Lilypad Pond S 题意： 为了让奶牛们娱乐和锻炼，Famer John 建造了一个美丽的池塘。这个长方形的池子被分成了 \(M \times N\) 个方格（\(1 \le M,N \le 30\)）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。 Bessie 正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。 Bessie 的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向移动两格，再横向移动一格。最多时，Bessie 会有八个移动方向可供选择。 约翰一直在观看 Bessie 的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。 于是他想要添加几朵莲花来帮助 Bessie 完成任务。一贯节俭的 John 只想添加最少数量的莲花，当然，莲花不能放在石头上。 请帮助 John...

洛谷P1242 新汉诺塔 题解 题目链接：P1242 新汉诺塔 题意： 设有 \(n\) 个大小不等的中空圆盘，按从小到大的顺序从 \(1\) 到 \(n\) 编号。将这 \(n\) 个圆盘任意的迭套在三根立柱上，立柱的编号分别为 \(A,B,C\)，这个状态称为初始状态。 现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。 移动时有如下要求： 一次只能移一个盘； 不允许把大盘移到小盘上面。 输入格式： 第一行一个整数，状态中圆盘总数 \(n\)。 接下来三行每行若干个整数，分别代表初始状态下 \(A,B,C\) 柱子上的圆盘从上到下的编号，如果只有一个数 \(0\) 就代表这根柱子上没有数。 接下来三行每行若干个整数，分别代表目标状态下 \(A,B,C\) 柱子上的圆盘从上到下的编号，如果只有一个数 \(0\) 就代表这根柱子上没有数。 输出格式： 若干行每行一个字符串，格式为 move I from P to Q ，代表一个移动的操作。 接下来一行一个整数，代表从初始状态到目标状态的最少步数。 数据范围： \(1 \le n \le 45\) ，$1 $...

洛谷P8217 [THUPC2022 初赛] 数正方体 题解 题目链接：P8217 [THUPC2022 初赛] 数正方体 题意： 小 E 有一块面积为 \(n\times m\) 的矩形区域，上面有 \(n\times m\) 个边长为 \(1\) 的格子，第 \(i\) 行 \(j\) 列的格子上堆了 $ A_{i,j}$ 个同样大小的正方体积木。小 E 做了某道题之后，突发奇想把这些正方体画成了字符画，然后让你帮他数一数他一共有多少个正方体。我们定义每个正方体为如下格式，并且不会做任何旋转，只会严格以这一种形式摆放： ..+---+ ./ /| 高 +---+ | | | + | |/.宽 +---+.. 长 每个顶点用 \(1\) 个 + 表示，长用 \(3\) 个 - 表示，宽用 \(1\) 个 / 表示，高用两个 | 表示。字符 . 作为背景。中间的空白是空格（ASCII 码为 \(32\) ）。 若两个正方体左右相邻，图示为 ..+---+---+ ./ / /| +---+---+ ...

OI模板-多项式 快速傅里叶变换 FFT 传送门：快速傅里叶变换 FFT #include <bits/stdc++.h> using namespace std; // #define int long long // #define INF 0x3f3f3f3f3f3f3f3f typedef complex<double> Complex; void up(int &x,int y) { x < y ? x = y : 0; } void down(int &x,int y) { x > y ? x = y : 0; } #define N ((int)(1e7 + 15)) const double pi = acos(-1.0); Complex a[N], b[N]; int l, r[N], limit = 1; void FFT(Complex *A, int type) { for(int i = 0; i < limit; i++) if(i < r[i]...