# P12544 \[UOI 2025\] Boys and Girls ## 思路 将问题转化为图论模型。 把每个女孩看成一个点，每种男孩看成一条边： - 男孩类型 $i$ 对应边 $(a_i,b_i)$； - 边权为 $c_i$。 题目要求选择最大的男孩集合，使得任意两个被选择的男孩至少喜欢同一个女孩。 等价于： >...

# GESP C++ 一级大纲 - 1. 知识范围 计算机基础常识 计算机基本组成、输入输出设备、操作系统基本概念、文件、文件夹、常见编码常识。 C++ 基础入门 认识 C++ 程序结构：#include、using namespace std;、main 函数 标准输出语句：cout换行、空格输出 常量、标识符命名规则，关键字 基础数据类型：int...

原题链接：https://loj.ac/p/6913 ~~变态扫描线~~。 ## 形式化题意 给出 $k$ 行 $n$ 列的矩阵 $(a_{i,j})_{1\leq i\leq k,1\leq j\leq n}$，对 $q$ 个询问，每次询问给出 $l,r$，求： $$ \sum_{l\leq x\leq y\leq r}F\bigg(\max_{1\leq...

# 【排序 + 状态压缩背包】掷出重围 ## 关键性质 对于已经选定的一组球，投掷顺序不会改变最终被占据的位置集合。 考虑交换两个相邻且落点逆序的球，它们的初始落点分别为 $a>b$。设从 $b$ 开始的第一个空位置为 $u$。 - 若 $u\0$：上一个球的最终位置为 $ w\_i+k-1. $...

# 【独立计数，快速幂】P6075 子集选取 ## 题意概括 在一个边长为 $ k $ 的三角形中放置若干个集合 $ A\_{i,j} $。 每个集合都必须是 $ S={1,2,\ldots,n} $ 的子集，并满足向左和向上包含： $ A\_{i,j}\subseteq A\_{i,j-1}, \qquad A\_{i,j}\subseteq...

# ABC468F Chmax 核心结论是： > 删除所有“前缀最大值”，剩余序列记为 $Q$。\ > 答案等于“前缀最大值个数”加上 $Q$ 的最长上升子序列长度。 官方题目给出的范围是 $N\le 5\times 10^5$，因此需要使用 $O(N\log N)$...

```cpp /* 题意：求所有线段子集的并集连通块数量之和。 思路：每个连通块由左端点最小的线段唯一代表。扫描端点，当遇到第 k 个左端点时， 已有 c 条线段完全结束。让当前线段成为新连通块起点的方案数为 2^(c+n-k)。 */ #include using namespace std; using ll=long long; const int...

# [P16995 【MX-S15-T1】「DLESS-5」Another OR Problem](https://www.luogu.com.cn/problem/P16995) 好题！ 看到这个按位或求 $\max$ 很难不想到按位枚举，但是这个 $\sum{b} = k$ 的限制很烦人，可以考虑能不能知道当 $a$ 固定时，随着 $k$...

神题，写篇题解学习一下。 学习 [大犇的题解](https://www.luogu.com.cn/article/f8ob8nzl)。 显然 $c_i$ 一定能写成 $a_ix+b_iy$ 的形式，考虑操作会对两部分有什么影响： * 如果 $r_i=0$，那么 $a_i=a_{i-1}+1$。 * 如果 $r_i=1$，那么...

# Miller-Rabin 与 Pollard-Rho 这两个算法通常配合使用，用来处理较大的整数： - **Miller-Rabin**：快速判断一个数是不是质数。 - **Pollard-Rho**：快速找到一个合数的非平凡因子。 - 找到因子后递归分解，就能求出一个大整数的全部质因数。 它们适合处理 $10^{18}$ 范围内的整数。 --- ##...

# 【最大笛卡尔树，倍增 LCA】传送 ## 题意概括 有 $n$ 个星球按照编号排成一行。每个星球 $i$ 有两个传送门： - 一个传送到左侧第一个满足 $p\_j>p\_i$ 的星球。 - 一个传送到右侧第一个满足 $p\_j>p\_i$ 的星球。 - 如果对应方向不存在更大的星球，这个传送门会传回星球 $i$ 自身。 每次任务会在 $k$...

# P1850 [NOIP 2016 提高组] 换教室 ## 知识点 Floyd 最短路 + 概率期望 + 动态规划 ## 题意概括 牛牛每节课原本在教室 $c_i$，可以申请换到教室 $d_i$。第 $i$ 节课申请成功的概率为 $k_i$，最多申请 $m$ 节课。 需要选择申请哪些课程，使相邻课程教室之间最短路长度总和的期望最小。 ## 解题思路...

题目保证存在一种合法方案，我们可以考虑由一个合法方案怎么调整出不同的合法方案。 为了方便理解，我们钦定优先向左遍历，把换向操作转换成翻转子树的操作。 容易发现，翻转一棵子树时已经合法匹配的点不受影响，那么只有那些当前未配对的点需要考虑。跟虚树的角度差不多，我们把这些子树内已经匹配上的点踢掉分析。 分析问题的重要方法：从小入手。 ### 两种颜色...

 ~~我应该不会被TA们砍成臊子吧~~ ~~骗你的其实还有很多，不过被系统吃了而已~~ --- # 展示极致赚损比😎  我的赚损比≈1:3.7...

# 前言 本文去掉代码全文共 4800 字。 这篇博客并非完全意义上的题解，主要是对我学习这道题的思路回顾与总结，基于以下两篇题解融合和补充（所以记号不是我原创的，我觉得尤其是第二篇题解定义的名词非常形象易懂直接抄了），以及一些碎碎念。 写了很多细节问题，都是我在学习这个题时思考过的，所以这篇文章非常长。 两篇神犇的题解： 1....