笑看世事似水变迁
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
斜率优化，为什么维护队尾和维护队头的顺序颠倒一下，连样例都过不去。 AC 的代码长这样： ```cpp h=1;t=0;q[h]=0; for(int i=1;i =Slope(q[t],i)) t--; q[++t]=i; while (h =Slope(q[t],i)) t--; q[++t]=i; } ``` 就…
$\color{blue}{\texttt{[Problem Discription]}}$ 给定一张图，$1$ 表示可以到达，$0$ 表示障碍。你一次移动可以向相邻八个方向运动，但不能碰到障碍物。单位时间内你可以且进行 $[l,r]$ 次移动（在区间内即可，具体多少次可以选择）。 求从 $(1,1)$ 到 $(n,m…
$\color{blue}{\texttt{[Analysis]}}$ 贪心。优先运送**楼层高**的货物，在能装下的情况下尽量多装。 > 因为运送货物的代价仅和最高楼层的货物有关，假设一次运送货物时的最高楼层为 $h$，那么无论你剩下的货物楼层高还是低，代价都是 $h$ 是固定的。 > > 既然这样，我们应该优先把尽…
$\color{blue}{\texttt{[Analysis]}}$ **思路参考了官方题解。** 赋值操作的特点是最终的结果只和最后一次赋值操作有关。 构造这么一张有向图 $G$：边 $i \to j$ 存在当且仅当 $i 定理：如果存在合法的方案，则一定存在一种方案，它只交换了相邻的两个操作。 > > - 证明：…
> 这是一道好题。 $\color{blue}{\texttt{[Problem Discription]}}$ $n$ 个人依次来队伍里排队，其中第 $i$ 个人来后会排在当前队伍中第 $\text{pos}_{i}$ 个人的后面。若 $\text{pos}_{i}=0$，则代表插队到队首。求最终队伍的顺序。 $1\…
$\color{blue}{\texttt{[Problem Discription]}}$ **不提供题目翻译，仅提供简要题面。** 给定两个数组 $a_{1 \dots n},b_{1 \dots m}$ 和 $q$ 次询问。每次询问给定三个参数 $x,y,z$，你需要求出在 $\{ a_{i} \}$ 中选出**…
在讨论《40分求调！必关！》回复：
@[Codyma881024](luogu://user/1633754) 小孩儿，要习惯，C/C++ 标准库函数都是从下标 $0$ 开始编号的。
在讨论《dijsktra算法不会优化 全M了 求救》回复：
？你不是 dijkstra 不会优化的问题，是不会邻接表。用二维数组存图是 $O(n^{2})$ 的。
$\color{blue}{\texttt{[Translation]}}$ 你有一个初始硬币价值 $k$ 和 $n$ 个操作，每个操作形如 $[l_{i},r_{i},\text{real}_{i}]$。对于每个操作，如果你当前的硬币价值满足 $l_{i} \leq \text{cur} \leq r_{i}$，则你…
> 牛客暑期多校连续两场都考了 Min_25 筛，看来不得不学了。 ### 前言 Min_25 筛是一种计算**积性函数**前缀和的高效算法。 时间复杂度好像是 $O\left ( \frac{n^{\frac{3}{4}}}{\log n} \right )$ 的。 ### 模板题（洛谷 P5325） $\color…
在讨论《对于复杂一些的推式子题有什么好的调试方法吗？》回复：
首先检查式子推错没有，然后对着式子检查程序？感觉没有太好的方法。
$\color{blue}{\texttt{[Analysis]}}$ 如果可以知道一个点的点权的话，那么 $O(n)$ 的时间内我们可以把所有点的点权均求出来。 我们先考虑随机给点 $1$ 赋上一个权值，那么可以把所有的 $b_{u}^{1}$ 求出来。当然这未必是一个合法的方案。 显然，可能会存在某个或某些点 $v…
$\color{blue}{\texttt{[Problem Discription]}}$ 给定一个 $n \times m$ 的表格 $a_{i,j}$，你可以**恰好**进行一次如下操作： 1. 选择一个格点 $(r,c)$。 2. 对于所有满足 $i=r$ 或者 $j=c$ 的格点 $(i,j)$，使 $a_{…
$\color{blue}{\texttt{[Problem Discription]}}$ 给定一个长度为 $n$ 的序列 $a_{1 \dots n}$，求满足以下三个条件的区间 $[l,r]$ 的数量： 1. $\sum\limits_{i=l}^{r} a_{i} =s$。 2. $\max\limits_{i…
$\color{blue}{\texttt{[Analysis]}}$ 显然，一般的位运算的题目都是需要拆位考虑的。 > 位运算最大的特点就是按位运算，没有进位和退位，所以按位考虑是很常见的思路。 > > 而按位考虑最大的优势就是每一位数只有 $0$ 和 $1$，情况最多 $4$ 种组合，考虑起来方便很多。 考虑修改操…
在文章《P12500 XOR and OR》发表评论：
博主是不是特意在 merge 的倒数第二行挖了个坑啊/xyx
$\color{blue}{\texttt{[Problem]}}$ 给定一个长度为 $n$ 的数组 $a_{1\dots n}$，进行 $m$ 次一下操作： 1. 给定 $l,r$，求出 $\sum\limits_{l \leq i n=n; for(int i=1;i 2) return -1; --num; re…
$\color{blue}{\texttt{[Analysis]}}$ 话说这题和贪心、图论有什么关系。 ~~不过这种题目是我的死穴。~~ 我们首先证明如下结论：**如果目标状态和初始状态有 $x$ 个人位置失配，则一定可以通过 $x$ 的代价调整回来。** > 我们考察其中一个失配的同学 $\alpha_{1}$，假…
在讨论《60分求调》回复：
请求给代码加点注释，不然真的看不懂
在讨论《关于题解规范的补充规定》回复：
@[return_second](luogu://user/1047309) 《原则上已经提交并通过审核的视频题解不会被撤下》
在讨论《想问一下这个思路对不对（悬关》回复：
什么叫把上个限速存下？和什么求最小值？
这题可不入门。 $\color{blue}{\texttt{[Analysis]}}$ ~~作为一个经历了高考摧残的人，最会干的事情就是化简冗长的式子。~~ 干瞪眼看不出这两个式子有什么规律，变量太多了，因此考虑先消元。 由 $x-\dfrac{y}{z}=n!$ 得 $x=\dfrac{y}{z}+n!$，把它带入第…
在讨论《为什么我刚输入2个数就崩坏了！！！！！！！！！！！》回复：
在给 vector 赋值的时候只能用 `push_back()` 函数，`push_back()` 函数会为你的值申请储存的空间，你连储存的空间都没申请就直接访问，不崩溃就奇怪了
在讨论《为什么我刚输入2个数就崩坏了！！！！！！！！！！！》回复：
您要这么使用 vector，那当然会崩坏啦
$\color{blue}{\texttt{[Analysis]}}$ 既然都是字符串前缀的问题了，那当然首先就应该想到 Trie 树。 我们可以发现这么一个性质，如果选从根到 Trie 树上某一点形成给定字符串作为前缀，那么子树内所有的字符串都会被归为这个类，子树外的其它字符串都不会被归为这个类。 于是可以想到在 T…
> 我敢赌，就算你知道怎么做，也必然得调试半天才能 AC。 $\color{blue}{\texttt{[Analysis]}}$ 显然不可能正面计算。所以被迫正难则反。 把所有三元组分成四类：不考虑有没有边相连；有且只有一条边连接；有且只有两条边连接；三个点形成三元环。 每种情况分别考虑。 1. 不考虑有没有边相连。…
$\color{blue}{\texttt{[Problem Discription]}}$ 给定一个 $n$ 个点，$(2n-2)$ 条边的**有向**图，每条边有边权。前 $(n-1)$ 条边构成一棵以 $1$ 为根的树，边的方向远离根；后 $(n-1)$ 条边为每个点到 $1$ 的边。每次操作修改其中一条边的边权…
$\texttt{\color{blue}{[Analysis]}}$ 很显然，对于单个点来说，它的第一项对答案的贡献就是往左最大连续子段和和往右最大连续子段和的较大值，第二项对答案的贡献就是往上的最大连续子段和和往下的最大连续子段和的较大值，第三项是本身。 于是把问题转化为求最大连续子段和。 当然这个问题可以用一个经…
$\color{blue}{\texttt{[Analysis]}}$ 首先，对数据结构比较熟悉的同学应该知道，静态数组求区间最大公约数可以用 ST 表来解决。 > 事实上，ST 表的本质就是倍增算法。因此，只要是静态数组的问题，基本都可以用 ST 表解决。 > > 只不过，对于求区间和、区间异或和之类的问题，每个数出…