Solutions

Exponential Generating Function (EGF)
题面 你有 $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
Ordinary Generating Function (OGF)
题意 $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
Li Chao Segment TreeLinear Dynamic Programming (Linear 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
Two PointerBinary HeapGreedy
题意 数轴上有 $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
Segment Tree DCSimple StackDisjoint Set
Pastoral Oddities 题面 给定一张 $n$ 个点的无向图,初始没有边。 依次加入 $m$ 条带权的边,每次加入后询问是否存在一个边集,满足每个点的度数均为奇数。 若存在,则还需要最小化边集中的最大边权。 $n \le 10^5$ , $m \le 3 \times 10^5$ 。 题解 线段树分治好题。 每条边要么选不了,要么选完后被取代再也回不来。这就是在时间的一个区间 …
Jayun 发布于 2023-11-17 09:11:52
00
Polar SortConvex HullCountPrinciple of Inclusion-ExclusionTwo Pointer
题目大意 二维平面上有一些点,保证不存在重合的点和三点共线。求每一个点集的凸包在平面上包含的点数的和。 $n\leq1000$ 。 题解 有趣的。 假如所有点都在所有凸包内,答案 $n2^n$ 。 考虑斥掉不合法的。对于一个点对,它们直线分割的半平面,两个平面内的点不能同时取。那么枚举一个点,把所有点挪到以它为原点的坐标系,然后极角排序,双指针维护半平面的区间即可。 本题的启发:如果有“不存在 …
Jayun 发布于 2023-11-16 16:43:52
00
Combinatorial SignificanceLinear Dynamic Programming (Linear DP)Permutation and Combination
[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
Dynamic Programming on Trees (Tree DP)Second Scanning
题意 在一棵树上,边有边权,给定 $k$ 个特殊点,对于每个点 $i$ 求,从 $i$ 出发必须经过所有特殊点的最短路径长度(可重复)。 $n,k\leq10^5$ 。 题解 不能直接对 dfn 排序然后线性做因为不对。 考虑树形 DP,答案就是从 $i$ 出发到每个有点的儿子一来一回,最终减去最长链,也可以跑到父亲那里,换根即可。对于最长链,有时需要次长链更新。 const i …
Jayun 发布于 2023-11-15 20:21:26
00
Simulated Annealing
退火。 const int N = 1e3 + 5; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); whil …
Jayun 发布于 2023-11-15 16:39:38
00
Dynamic Programming on Trees (Tree DP)Second ScanningCount
题意 给出一棵大小为 $n$ 的树,和两个值 $p,q$ ,求有多少个四元组 $(a,b,c,d)$ 满足路径 $a\rightarrow b$ 的长度是 $p$ ,路径 $c\rightarrow d$ 的长度是 $q$ ,且两路径不交。 $n,p,q\leq3000$ 。 口胡 考虑容斥转化问题为求交的。交有两种情况,两条路径的 LCA 都是同一个点;一条路径穿过另一条 …
Jayun 发布于 2023-11-15 08:10:28
00