题解
最大流基础栈
Projectors
题面
$n$ 个讲课， $m$ 个研讨会， $x$ 个高清投影仪和 $y$ 个普通投影仪。
每堂讲课必须使用一个高清投影仪，而研讨会可以使用普通或高清投影仪。
给定讲课和研讨会的时间区间，构造一个投影仪的分配方案。
$n,m,x,y \leq 300, a_i,b_i,p_i,q_i \leq 10^6$ 。
题解
厉害的建模题。
分配普通投影仪的分配时不需要考 …
Jayun 发布于 2024-02-19 20:59:03
00
基础线段树
题目
你有一个由大写字母 $A$ 和 $B$ 构成的长度为 $n$ 的基因序列 $s$ 。每一次操作把所有子串 $BA$ 替换为 $AB$ ，若干次后基因序列可以有序，即如同 $AAA\dots BBB$ 的形式，你想要知道这个最小次数。
但是这个问题太简单了，你决定加入修改。你现在有 $q$ 次修改，每一次（永久地）把基因序列 $s$ 的一个区间 $[l,r …
Jayun 发布于 2024-02-17 07:54:27
00
高斯消元
题目大意
给定一个二分图，已知这个二分图的完备匹配个数是奇数，询问删除每条边后完备匹配个数的奇偶。
$n\leq2000,m\leq5\times10^5$ 。
题解
线性代数苦手者。
令二分图的邻接矩阵为 $A$ ，二分图的完备匹配个数可以列式 $\sum_p\prod_{i=1}^nA_{i,p_i}$ 。由于题目只考虑奇偶，所以可以看作是在模 2 的背景下，此时邻接矩阵的行列式 $| …
Jayun 发布于 2024-02-15 21:20:02
00
指数生成函数
题面
你有 $n$ 个数 $a_1,a_2,\dots,a_n$ 要进行 $k$ 次操作，每次随机选择一个数 $x \in [1,n]$ ，把 $a_x$ 减一，并将答案增加除 $a_x$ 外所有数的乘积。
求最终答案的期望，答案对 $10^9 + 7$ 取模。
题解
设最终 $a_i$ 的减少量为 $b_i$ ，可以把答案转化为 $\prod_{i=1}^na_ …
Jayun 发布于 2024-02-12 12:17:05
00
普通生成函数
题意
$n$ 种糖，每种糖有 $m_i$ 个，求选出 $a$ 到 $b$ 颗糖的方案数。
$n\leq10,0\leq a\leq b\leq10^7,m_i\leq10^6$ 。
题解
在第 $i$ 堆糖吃糖果的方案数的生成函数
$$F_i(x)=\sum_{j=0}^{m_i}x^j=\frac{1-x^{m_i+1}}{1-x}
$$
把这些组合起来，其生成函数相乘
$ …
Jayun 发布于 2024-02-10 18:22:32
00
李超线段树线性动态规划（线性 DP）
题意
$n$ 天开始时有 $S$ 元钱，每天 $A$ 种股票价格为 $a_i$ ， $B$ 种价格为 $b_i$ 。然后出售必须 $A$ 和 $B$ 出售相同比例，买入时 $A$ 和 $B$ 必须按照 $r_i$ 的比例买入。
求最后的钱最多是多少。
$n\leq10^5$ 。
题解
可以证明要买全买要卖全卖。
设 $f_i$ 为第 $i$ 天最多拥 …
Jayun 发布于 2023-11-17 14:58:10
00
双指针二叉堆贪心
题意
数轴上有 $k$ 个点是草地，每个草地有不同收益， $m$ 个点是地方的点，现在你要放置 $n$ 个我方的点，不能和敌方的点重合。
如果一个草地离最近的我方的点距离严格小于最近的敌方点距离，那么这个草地被占领。
给出敌方点和草地坐标（保证两两不同），求占领草地的最大收益和 。
$1\leq n,m,k\leq 2\times10^5,1\leq x\leq 10^9$ 。
题解
…
Jayun 发布于 2023-11-17 10:36:43
00
线段树分治基础栈并查集
Pastoral Oddities
题面
给定一张 $n$ 个点的无向图，初始没有边。
依次加入 $m$ 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。
若存在，则还需要最小化边集中的最大边权。
$n \le 10^5$ ， $m \le 3 \times 10^5$ 。
题解
线段树分治好题。
每条边要么选不了，要么选完后被取代再也回不来。这就是在时间的一个区间 …
Jayun 发布于 2023-11-17 09:11:52
00
极角排序凸包计数容斥原理双指针
题目大意
二维平面上有一些点，保证不存在重合的点和三点共线。求每一个点集的凸包在平面上包含的点数的和。
$n\leq1000$ 。
题解
有趣的。
假如所有点都在所有凸包内，答案 $n2^n$ 。
考虑斥掉不合法的。对于一个点对，它们直线分割的半平面，两个平面内的点不能同时取。那么枚举一个点，把所有点挪到以它为原点的坐标系，然后极角排序，双指针维护半平面的区间即可。
本题的启发：如果有“不存在 …
Jayun 发布于 2023-11-16 16:43:52
00
组合意义线性动态规划（线性 DP）排列组合
[AGC001E] BBQ Hard
题面
有 $n$ 个数对 $(a_i, b_i)$ ，求出
$$\sum_{i=1}^{n}\sum_{j=i + 1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j}
$$
答案对 $10 ^ 9 + 7$ 取模。
$n\leq10^5,a_i,b_i\leq2000$ 。
题解
考虑组合意义，相当于横着走 $a_i+ …
Jayun 发布于 2023-11-16 07:39:36
00