八月 31, 2020 · OI 题解
「UR #15」奥林匹克环城马拉松
给定一张 $n$ 个点的树或基环树，树上的每条边 $(u_i, v_i, w_i)$ 代表 $(u_i, v_i)$ 间有 $w_i$ 道路相连。 你需要统计有多少种从任意点出发的本质不同路径，使得经过所有道路恰好一次。 路径可以认为是一个从某个点出发，由经过道路编号和方向组成的序列。两条路线被认为是相同的当且仅当两序列相同...
八月 08, 2020 · OI 题解
「集训队互测2018」完美的队列
你有 $n$ 个队列，每个队列有 $a_i$ 的容量。 $Q$ 次操作，每次给定队列的区间 $[l,r]$，push 一个 $x$。如果第 $i$ 个队列的元素个数 $>a_i$，会自动 pop。 要求每次操作后求出所有序列中本质不同的元素个数。 $n,m,a_i,x \leq 10^5$。
八月 02, 2020 · OI 题解
「XX Open Cup. GP of Korea」Container
给定两个长度 $n$ 的序列 $s,t$，每一位是 $1$ 或者 $2$。每一次你可以翻转长度 $\leq 3$ 的区间，代价为区间和加上常数 $c$。问从 $s$ 变换到 $t$ 的最小代价。 $n \leq 500$。
七月 31, 2020 · OI 题解
「XX Open Cup. GP of Gomel」Hit
给出 $n$ 个区间 $[l_i, r_i]$ ，你需要放下至多 $n$ 个点，使得每个区间里至少包含一个点。并且区间里点个数的最大值要尽可能小。 $1 \le n \le 10^5, 10^9 \le l_i < r_i \le 10^9$ 。
七月 30, 2020 · OI 题解
「HDU6810」Imperative Meeting
给定 $n$ 个点的树，定义 $m$ 个人的约会点 $x$ 为使得 $m$ 个人所在的点到 $x$ 的距离之和最小的点。 $m$ 个人所在位置在 $n$ 个点中随机选择（即总方案数 $\binom nm$），问所有方案到约会点距离之和的和。 $n \leq 10^6$，答案对 $10^9 + 7$ 取模。
六月 28, 2020 · OI 题解
「ZJOI2020」抽卡
有 $m$ 张带编号卡牌，每次你可以随机抽取一张。抽中每张的概率均为 $\frac 1 m$。当编号连续的 $k$ 张牌都被抽取过时，游戏结束。 问游戏结束的期望步数。 $1 \leq k \leq m \leq 2 \times 10^5$。
六月 26, 2020 · OI 题解
「Ynoi2019」美好的每一天~ 不连续的存在
给数组 $A$ 和 $n$ 个节点的树，每个点有一个 $1$ 到 $x$ 颜色。 $m$ 次查询，每次查询树上只保留 $[l,r]$ 内的所有节点，设一个极大连通块中出现奇数次数的颜色个数为 $t$，则其对答案的贡献为 $A_t$ ，即答案是所有连通块贡献的和，询问相互独立。 $1\leq n,m\leq 10^5$，$1\leq x,A_i \leq 10^4$。
六月 02, 2020 · OI 题解
「是男人就过8题——Pony.ai」IntervalTree
定义区间树为线段树的拓展，即每次断开的位置可以不是线段的中心。 给定一个 $[1, n]$ 的区间树和 $q$ 次询问，每次询问包含一个正整数 $k$, 你需要求出有多少区间的时间复杂度恰好等于 $k$。 $n, q\le 10^5,\ k\le 10^9$。
五月 20, 2020 · OI 题解
「CometOJ Round #2 F」真实无妄她们的人生之路
有 $n$ 种操作，第 $i$ 种操作使用后有 $p_i$ 的概率升级，$(1-p_i)$ 的概率不升级。 进行若干次操作后，如果主人公的等级为 $i$，就能产生 $a_i$ 的贡献。 对于每个 $i \in [1;n]$ 求出，使用 $j \neq i$ 的所有操作 $j$，主人公产生等级贡献的期望。 $n \leq 10^5$。
五月 14, 2020 · OI 题解
「CF1349F2」Slime and Sequences (Hard Version)
定义一个排列 $p$ 是好的当且仅当对于每个 $k < \max\{p\}$，存在 $1 \leq i < j \leq n$ 使得 $a_i = k-1$ 且 $a_j = k$。 定义 $f_a(k)$ 为序列 $a$ 中数值 $k$ 的出现次数，假设所有合法序列集合为 $S$，对于每个 $k \in [1;n]$，求 $\displaystyle{ \left( \sum_{a \in S} f_a(k) \right) \bmod 998244353 }$ $n \leq 10^5$。