最近更新
最新更新的文章（含置顶文章）
某帅气的哥群周刊第五刊
# 某帅气的哥群周刊第五刊
**[第一期 Link](https://www.luogu.com.cn/article/e7l583bi)**
**[第二期 Link](https://www.luogu.com.cn/article/jyivt87v)**
**
[置顶] Sleeping Cup's Introduction
**置顶公告：**
- Sleeping Cup #7 已经开赛，欢迎参加！
- Sleeping Cup #8 即将开赛，欢迎参加！
- 网址：http://8.136.99.126/
---
欢迎来到 Sleeping Cup！
这是一个以 Hydro 做框架搭建的网站，但又又不只是一个以 Hydro 做框架搭建的网站。在这里，我们将努力打破你对 OI 的传统认知：
- 与众不同的体
P3810 【模板】三维偏序（陌上花开）
考虑二维偏序。
我们将所有点按某一维排序，然后按照这一位扫描线。这样操作的目的是把这一维变成时间维。
然后维护一个树状数组，在扫描的过程中做在线的一维偏序。这是简单的。
这给了我们一个启示：离线的 $x$ 维偏序与在线的 $x - 1$ 维偏序的难度相同。做法就是将某一维转化成时间维。
同理对于三维偏序我们要做在线的二维偏序。考虑 cdq 分治。
首先按 $x$ 排序。
定义函数 $\
CF600E Lomsat gelral
线段树合并。
考虑合并两颗线段树，设它们分别以 $root_x$ 和 $root_y$ 为根。我们递归合并这两颗线段树上的每个节点：
```cpp
void merge(int &x, int y, int l, int r) {
if (!x) x = y;
else if (!y) return;
else if (l == r) {
tr[x].v.first +=
P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
路径加可以树上差分。即令 $res_{i, j}$ 表示答案中第 $i$ 个节点上 $j$ 种类的数量，$d_{i, j}$ 为其差分数组。每次操作 $(x, y, z)$ 等价于：
$$
d_{x,z} \gets d_{x, z} + 1 \\
d_{y,z} \gets d_{y, z} + 1 \\
d_{lca,z} \gets d_{lca, z} - 1 \\
d_{fa_{
题解：CF425E Sereja and Sets
MX-C day1 T1。
### 题意
数轴上有 $n$ 个点，构成了 $\frac{n(n+1)}2$ 个线段。令所有线段为全集。问有多少子集，满足这个子集内的线段，在两两不交的情况下能选出的最多线段数恰好为 $k$。$k \le n \le 500$。
### 做法
如果暴力 dfs，那么 check 的做法是经典贪心。即将所有线段按照**右端点**排序，然后顺次判断能不能选这条线段
题解：CF93E Lostborn
MX-C day1 T2。
### 题意
给定 $k$ 个两两互质的正整数，求 $1 \sim n$ 中有多少数不能被任意一个数整除。
### 做法
「多少数不能被任意一个数整除」= $n - $ 「多少数能被任意一个数整除」。
考虑 DP。设 $f(n, k)$ 表示有多少个 $1 \sim n$ 的数，能被 $a_1,a_2\dots a_k$ 中的任意一个数整除。
很妙的转移！
题解：CF1371F Raging Thunder
MX-C day1 T3。
### 题意
[太长了回去看吧](https://mna.wang/contest/1242/problem/3)。
### 做法
我们给每个空隙一个属性：
$$
a_i = \left\{ \begin{matrix} 1&, s_i = \texttt {//} \\
-1 &,s_i = \texttt{\\\\} \\
+\infty&,s_i = \
题解：P9731 [CEOI2023] Balance
MX-WF-C 8.14 最难题。
## 题意
给定一个 $n \times s$ 的矩阵。保证 $s$ 是 $2$ 的幂。你需要给出一种将矩阵的每一行重排的方案，使得对于每个矩阵中出现的数而言，在所有列中的出现次数的极差 $\le 1$。
## 做法
首先考虑 $s = 2$。不妨设这个矩阵形如 $[[u_1,v_1],[u_2,v_2]\dots[u_n,v_n]]$。
我们考虑将每
题解：P10207 [JOI 2024 Final] 马拉松比赛 2
MX-C 8.16 模拟赛 T4。
对楼上大佬的题解做的一些详细解释。
## 题意
一条数轴上放了 $n$ 个球，第 $i$ 个球放在了位置 $x_i$，一个位置可能有多个球。
你需要从起点 $s$ 出发，捡起所有 $n$ 个球（一个球捡起了就不能放下了），回到终点 $t$。如果你能在规定时间 $T$ 内完成，则算你成功。
已知：拿起 $1$ 个球需要 $1$ 单位时间；带着 $x$ 个
POJ.3041 Asteroids
> 给定一个网格，网格上有敌人，每次可以同时消灭某一行或某一列上的所有敌人。求消灭所有敌人需要的最小操作次数。
我们将每个敌人的所在行与所在边连边，问题转化成：
> 在图中选择最少的点，使得每条边的两个端点中至少有一个被选择。
这是最小点覆盖。而最小点覆盖等于最大匹配，所以直接 dinic 做完了。
题解：P9351 [JOI 2023 Final] Maze
太摆了丢个代码跑路：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 10;
vector<vector<bool>> g;
int n, m, k, sx, sy, tx, ty;
vector<vector<bool>> st;
vector
题解：P10206 [JOI 2024 Final] 建设工程 2
### 题意
给定一张无向图。求有多少 $u < v$ 满足在 $u, v$ 间连一条边权为 $l$ 的边后，$s \rightsquigarrow t$ 的最短路 $\le k$。
### 做法
首先判掉最开始 $s \rightsquigarrow t$ 的最短路已经 $\le k$ 的情况。答案是 $\binom n2$。
否则，若原来最短路 $> k$，但加上 $(u, v)$ 这
题解：P8178 「EZEC-11」Sequence
不难发现：
$$
f_i = A_if_0 + B_i
$$
其中 $A_i = \prod_{j = 1}^i a_j, B_i = \sum_{j=1}^i b_j \times \prod_{k=j+1}^i a_k$。是关于 $i$ 的常数。
那么条件就变成了：
$$
\left\{
\begin{matrix}
A_1f_0 + B_1 \equiv 0 \pmod {p_1}
椰子
本题解的复杂度分析中均视求 $\gcd$ 是 $\mathcal O(1)$ 的。
## 题意
给定 $n$ 的排列 $a$。对于每个数字 $i$，求将排列中值为 $i$ 的数修改为 $1$ 后，所有区间的 $\gcd$ 的种类数。$n \le 2 \times 10^5$。
## 做法
令 $p_i$ 表示值 $i$ 在 $a$ 中的出现位置。有 $p_{a_i} = a_{p_i}
vscode 高效配置和进阶（避坑指南）
# vscode 高效配置和进阶（避坑指南）
为了简单易懂，我直接写了很多快捷键，大家请放心按。
身为一个换了 4 台电脑都每次能用 vscode 的人，我觉得这个配置方法还是很使用的。
同时我也再开了一个虚拟机重测了一遍，保证无误。
因为老是用，所以写的很详细，绝对是针对 OIER 最详细的配置指南。
---
以上都是吹嘘，太绝对了，但虚拟机上实测的确无误。
先上效果图（其实效果不
T1
### 题意
令 $y^2$ 是距离 $x$ 最近的完全平方数，若有不止一个最近的直接输出 $\texttt{Game Over}$ 结束程序。定义 $f(x) = (-1)^{y+1}y$。
求 $\sum_{i=l}^r f(i)$。$l, r \le 10^{18}$。
### 做法
$\texttt{Game Over}$ 是不可能的。
显然第一步差分。问题变成求 $[1, r]
T4
# 题意
给定一张 $n$ 个节点 $m$ 条边的简单无向图，和一个整数 $k \in [1, 3]$。你需要将每个点黑白染色。令在一种方案中，有 $m$ 条边的两端点都是黑色。求所有方案的 $m^k$ 的和。
# 做法
$m^k$ 很难受。我们可以理解成有 $m$ 条边，你要从中**依次**选择 $k$ 条边的方案数。**选择的边可能相同**。
例如，$(3,3,2)$ 和 $(2, 3
题解：AT_abc369_f [ABC369F] Gather Coins
求二维 LIS。
首先将所有值按一维排序，在另一维上求解朴素的 LIS 即可。
<https://atcoder.jp/contests/abc369/submissions/57332899>
题解：P9755 [CSP-S 2023] 种树
二分答案 $m$。
我们需要判断是否存在一个序列 $\{d_n\}$ 表示对于每个 $i$，第 $i$ 棵树如果在第 $d_i$ 天种下，都要达到 $a_i$ 的高度。
显然一棵树种的越早越好。我们可以求解一个 $f(i)$ 表示第 $i$ 棵树最晚在第几天种可以满足要求。
假设我们已经求好了。不难发现一个必要条件是：
> 对于所有 $1 \le i \le n$，满足 $f(u) \le