题解

对于一次询问，相当于在考虑整数 \(\frac{n}{x}\) 变为 \(1\) 的方案数。进一步的，这相当于给定一个数列 \(c_0\cdots c_k\)，每一次可以减小任意位的任意值，但不能空选，问方案数，这里“空选”指的是不选任何一个数。 先考虑允许空选的时候应该怎么做，令 \(f(x)\) ......

首先我们考察 LIS 长度为 \(n-1\) 的数列的性质。可以发现，这必定是 \(1,2,3,\cdots,n\) 中拎出一个不听话的元素甩到其他地方去，剩下的元素依次补齐所构成的。这意味着，最多只有一个元素满足 \(a_i-i\ge2\)，更具体的，不考虑只对邻项交换的排列（即形如 \(1,2, ......

这篇题解并不做任何形式上的理论推导，而是在于引导像我一样的蒟蒻，如何在遇到这样的题时，不会陷入数据结构暴力分别求三种形态的深渊里无法自拔。 看到这道题我们的第一想法应该是把三种形态的数量都求出来，如果可以的话，这题马上就秒掉了。那么我们尝试着去求—— 比较简单的可能是高山形态的个数。你可能会想到把这 ......

U288469 Piggy 算路程 显然是简单贪心。黄。 U306825 Piggy 数编号 先推式子。 令 \(L(n,k)\) 为最长区块长度为 \(k\) 的方案数，则 \(Ans=\sum_{i=0}^n\limits{L(n,i)}\times k\)。下面转为求 \(L(n,k)\)。 ......

如果能想到这道题用随机化，想来这道题的解法就显然了。但是为什么这道题一定要随机呢？ 我们考虑一棵完美二叉树，编号随机。这棵树的熵毛估估一下应该是 \(O(\log^n n)\) 的，但是一次询问的话，考虑每次只能得到三个点的偏序关系为某几种情况的一种，这个熵是很小的，只有 \(O(\log n)\) ......

原问题可转化为：在一个长为 \(10^9\) 的环上，每次走 \(1\sim6\) 步，指定起点，问到原点的期望步数。 考虑走到 \(-1\sim-6\) 的期望步数。我们发现，对于 \(X-R\equiv -i\pmod {10^9},i\in[1,6]\)，\(C\) 的期望应该存在线性关系，因 ......

实际上，这是两个向量的叉积已经是其他题解说烂了的。这里只是给出一个容易记忆 \(dim\le 3\) 的行列式的值的办法。 我们以 \(3\) 维行列式为例子，假设为 \[\begin{vmatrix} a & b & c\\ i & j & k\\ o & p & q \end{vmatrix} ......

我认为，这道题是我学 OI 历史以来做过的最难写，最难受，最变态，最不可做，最怀疑人生的题。 然后还莫名其妙遇见了！ 给出一种时间复杂度略劣于 ix35 的做法。因为本人码力不是很好，因此认为这道题讲讲代码写法也很必要。 题意就是给一些线段上戳洞，使得对于给定的一个区间 \([l,r]\)，从无穷远 ......

FWT 入门题，很适合我这样的蒟蒻。 首先我们可以轻松的根据转移条件写出来一个优美的函数 \(T(i)=1+\sum_{j\oplus k=i}a_kT(j)\)，边界为 \(T(0)=0\)。 这个方程属于转移带环的 DP，处理方法一般是高斯消元，在这道题里会 T 飞。 但是我们又注意到后边是一个 ......

因为懒得用 bitset MLE 了。所以各位想 A 这题的别偷懒用布尔数组！ 本题解意在解释如何做类似的 dp 题，而不在于解释本道题做法的具体推导，只是给出一个思路。 我们观察发现，题目想让我们最小化一个最大值。我们并不能枚举每种方案去找最大值再取 \(\min\)，这样复杂度爆炸而且没有前途真 ......

在 HL 群里吃瓜，顺手写一篇题解。 第一眼必定是数位 dp，可是这会使原题难度反而升高了。相对而言，我们要是枚举前缀 \(1\) 的长度，然后寻找对答案有贡献的区间，此问题是很容易的。同时我们不难发现，前缀 \(1\) 长度为 \(l\) 的所有有贡献的数字即为 \(\forall i\in[l, ......

P7400，一个有趣的博弈论。 下面称 Paula 和 Marin 都执行一轮操作的“一整轮”为一个周期。 Sub 1：\(n\le 100\) 我们采用 \(O(n^2\times n)=O(n^3)\) 的 DP 即可。这里略去具体实现。 Sub 2：边的颜色均为洋红 这意味着两人都可以走过任意 ......

显然这道题的解法与 \(8\) 强相关。从这一点下手，我们不难想到先对每一种奶牛做前缀和，这样我们可以做到 \(O(8)\) 查询每个区间是否可行，从而有了一个 \(O(4n^2)\) 的纯暴力做法。不知道多少 pts，反正不是正解。 下一步我们考虑优化。如果我们能快速地找到哪些区间是合法的，那么时 ......

远古模拟赛里的一道题，前来写篇题解记录一下。 我们考虑一个显然的转化。将每条边染色，那么原问题等价于求下面的染色的方案数： 对于每个点对 \(a,b\)，我们记 \(\operatorname{lca}(a,b)=c\) 有 \(a\sim c\) 上的所有边同色。 \(b\sim c\) 上的所有 ......

因为本题的代码难度远大于解法的思考，因此这里提供一种好写的写法。 做法不再赘述，就是转化为 \(depth\) 差以后上线段树分别维护两个信息以后求和。题解中大多数使用同一个线段树维护两个信息，可读性并不高，且比较难写。 事实上我们注意到两棵线段树仅有初始的信息不一样，剩下需要支持的操作完全一样，这 ......

不妨先考虑一个弱化版的问题，这个问题和原来的问题仅有一个区别：\(k\) 是给定整数。 称最后 \(n-k\) 个数是“特殊的”。那么我们可以注意到，每个特殊的数字的极大段必然递增放置或者递减放置。例如我们有排列 \([7,5,8,1,4,2,6,3]\) 而且 \(k=2\)，那么极大段的下标应该 ......

省流：离线以后，每个字符做前缀和然后直接水过去 首先离线所有询问。对于每个英文字母，我们把查询这个字母的询问都一起处理。 对于每个字母 \(c\)，我们跑一遍前缀和，令 \(p_i\) 表示 \(\mathit{s}_{1,i}\) 中字符 \(c\) 出现的次数。接下来我们定义 \(\operat ......

前置知识：简要了解 CRT 和高斯消元 题意简述：给定一些系数，求 \(n\) 元线性同余方程组 \(A_i+\sum^{M}_{j=1}a_{i,j}x_j\equiv B_i(\mod 365)\) 的解。 注意到 \(365=5\times73\)，而且他们都是质数，这引导着我们思考先分别求出 ......

此题问 \(\operatorname{lcm}(a\sim b)\) 的后导 \(0\) 个数。 考虑 \(\operatorname{lcm}\) 相当于对唯一分解中的素数的指数取 \(\max\)，此题等价于： 定义 \(\operatorname{g}(x,y,z)\) 在 \([a,b]\ ......

Meaning 在二维平面内，有位置不同且不存在三点共线的 \(R\) 个红点和 \(B\) 个黑点，判断是否能用一些互不相交的线段连接每一个点，使得每条线段的两端都分别是黑点和白点。 Solution 当 \(R\ne{B}\) 时，显然无法实现红点与黑点的两两组合，故题干所述的情况一定不存在。 ......

P5765 [CQOI2005] 珠宝 题解 思路 好题，注意到有性质：颜色数最多为 \(\lfloor\log_2 n\rfloor + 1\)，有了这个性质之后直接树形 DP 糊上去就过了。 简要的证明： 考虑一个点，显然一种颜色即可。 对于一个颜色为 \(c\) 的点，其儿子至少有 \(c - ......

题目传送门 前置知识 二分答案 | 并查集 解法 对条件的合法性判断其他题解已经讲得很明白了，这里不再赘述。这里主要讲一下用并查集实现黑白染色问题。 以下内容称被覆盖为黑色，不被覆盖为白色。 本题因为是单向染色，即从白到黑，故可类似 luogu P1840 Color the Axis 和 D 的并 ......

CF1916B 分析 题目给出的是 \(x\) 的两个小于 \(x\) 的最大因子，首先考虑 \(a\) 不整除 \(b\) 的情况。既然 \(a\) 不整除 \(b\)，那么 \(a\times b\) 必定是 \(x\) 的倍数，但是此时 \(a,b\) 就不一定是最大的，所以需要除以一些东西， ......

Question 杭州电子科技大学2023新生赛 G 逃离节奏面 题太长自己看吧 Solution 考虑到如果走了几步后走到了相同节奏面的相同点是没有意义的，所以直接 BFS ，对于走过的节奏面的哪个点不需要走就能刷出最短路了 实际上实现的时候细节很多，要注意一下 Code #include<bit ......

Question 杭州电子科技大学2023新生赛 E 树 给定一颗包含 \(n\) 个节点的带边权的树，定义 \(xordist(u,v)\) 为节点 \(u\) 到 \(v\) 的简单路径上所有边权值的异或和 有 \(q\) 次询问，每次给出 l r x 求 \(\sum_{i=l}^r xord ......

省选题解第一发～ 【省选联考2020】树 我和这道题还挺有缘分的。 有一次看大佬的省选游记（不知道是哪一年），然后提到有一道是01trie整体加一，当时我就印象深刻，然后在 oiwiki 上看了一下，心想这整体加一也只能从低位到高位维护 01trie 啊，又不能查询最大值，有什么卵用（划掉）。 这是 ......

可以看出来出题人很想出一道把李超和别的什么东西凑起来的题目，于是给了这么一个缝合怪。 https://www.luogu.com.cn/problem/P4069 符号有点混乱。比如箭头又可以表示路径又可以表示赋值，代入语境应该还是好理解的。 看到 \(a\times dis + b\) 就应激反应 ......

Problem - D - Codeforces Counting Rhyme - 洛谷 法1： 我们之前肯定看过这样一道非常经典的题： 求 \(a_i\) 中有多少对 \((i,j)\)，满足 \(\gcd(a_i,a_j)=1\) \(n \leq 10^6\) 这题是莫反板子题，但显然可以不用 ......

题目传送门 一道贪心题。 数量为 \(2\) 的袜子不用考虑，因为最好的情况就是相同颜色的配一对。 我们只需要考虑那 \(k\) 种只有 \(1\) 个的袜子，如果 \(k\) 为偶数，答案为相邻两数之差之和；如果 \(k\) 为奇数，就枚举删掉一个数，让剩下的数按照 \(k\) 为偶数的情况做，最 ......

题目传送门 一道 dfs 题。 先统计出绿连通块数量，然后对于每个红色方块统计涂成绿色方块后会变成多少个连通块。正常涂成绿色后应该会增加一个大小为 \(1\) 的绿连通块，但若是有不同的绿连通块与其相邻，答案又会减少 \(1\)。 Code #include <bits/stdc++.h> cons ......