AGC038 部分题解
E题意有一个随机数生成器，生成 $[0,n-1]$ 之内的数，生成第 $i$ 个数的概率为 $\frac{A_i}{S}$，其中 $S=\sum_{i=1}^n A_i$。当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成，求期望生成次数，对大质数取模。题解设第 $i$ 个数最后一次被随机到的时间为 $t_i$，答案就是 $\max t_i$ 的...
E题意有一个随机数生成器，生成 $[0,n-1]$ 之内的数，生成第 $i$ 个数的概率为 $\frac{A_i}{S}$，其中 $S=\sum_{i=1}^n A_i$。当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成，求期望生成次数，对大质数取模。题解设第 $i$ 个数最后一次被随机到的时间为 $t_i$，答案就是 $\max t_i$ 的...
题意给出一个 $n$ 个点的数，边有边权，支持翻转一条边的边权，以及求最长的满足路径上边权异或和是 $0$ 的路径。题解相当于子树翻转，求相同颜色的直径。赛时被卡常做法：直接动态维护直径端点，合并的时候暴力枚举合并。一个比较优秀的做法：转括号序后两个点的距离就是括号匹配后失配的括号数量。先考虑如何快速求区间内失配的括号数量：考虑维护失配的右括号和左括号数量，记为 $a,b$。合并的时候设左儿...
题意要求构造大小为 $n$ 的排列，要求至少 $\lceil \frac{m}{2} \rceil$ 条限制：第 $i$ 条限制 $(a_i,b_i,c_i)$ 形如排列中 $b_i$ 的位置要在 $a_i$ 和 $c_i$ 之间。题解神仙题。这个题一般确定排列的方法都不能用了，我们考虑这个在两个数中间的限制：考虑用按照顺序每次将一个数放到前面或者后面的方式。因为保证有解，所以肯定能搞出来一...
A. 气球设 $f_i$ 表示最后一次选择的是 $i$ 的答案，暴力转移是枚举一个 $j$，判断 $c_i,c_j$ 是否相同对应乘上系数转移就行了。我们记 $mx_i$ 表示当前考虑完的所有 $f$ 的时候 $c_k = i$ 的 $f_k$ 的最大值，那么我们转移只需要知道 $mx_{c_i}$ 和剩下的数的最大值就行了，分别记录最大值和次大值是什么即可。#include <bit...
B 被降智了，所以掉分了。A考虑将这个串拆成三部分考虑：114，5，14。设 $f_{i,j}$ 表示 114 的 $4$ 的位置是 $i$，1 代表 $j$ 的方案数，$g_{i,j}$ 表示 14 中 1 的位置是 $i$，4 代表 $j$ 的方案数，另外记录一个 $s_{i,j}$ 表示前 $i$ 个字符中 $j$ 的数量，字符串是 $a$，那么答案是：我们枚举 $i$ 和 $a_j$...