·

「UR #15」奥林匹克环城马拉松

给定一张 $n$ 个点的树或基环树,树上的每条边 $(u_i, v_i, w_i)$ 代表 $(u_i, v_i)$ 间有 $w_i$ 道路相连。 你需要统计有多少种从任意点出发的本质不同路径,使得经过所有道路恰好一次。 路径可以认为是一个从某个...

·

「UR #15」奥林匹克环城马拉松

给定一张 $n$ 个点的树或基环树,树上的每条边 $(u_i, v_i, w_i)$ 代表 $(u_i, v_i)$ 间有 $w_i$ 道路相连。 你需要统计有多少种从任意点出发的本质不同路径,使得经过所有道路恰好一次。 路径可以认为是一个从某个...

·

「集训队互测2018」完美的队列

你有 $n$ 个队列,每个队列有 $a_i$ 的容量。 $Q$ 次操作,每次给定队列的区间 $[l,r]$,push 一个 $x$。如果第 $i$ 个队列的元素个数 $>a_i$,会自动 pop。 要求每次操作后求出所有序列中本质不同的元素个数。 ...

·

「XX Open Cup. GP of Korea」Container

给定两个长度 $n$ 的序列 $s,t$,每一位是 $1$ 或者 $2$。每一次你可以翻转长度 $\leq 3$ 的区间,代价为区间和加上常数 $c$。问从 $s$ 变换到 $t$ 的最小代价。 $n \leq 500$。

·

「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$ 。

·

「HDU6810」Imperative Meeting

给定 $n$ 个点的树,定义 $m$ 个人的约会点 $x$ 为使得 $m$ 个人所在的点到 $x$ 的距离之和最小的点。 $m$ 个人所在位置在 $n$ 个点中随机选择(即总方案数 $\binom nm$),问所有方案到约会点距离之和的和。 $n \leq 10^6$,答案对 ...

·

「ZJOI2020」抽卡

有 $m$ 张带编号卡牌,每次你可以随机抽取一张。抽中每张的概率均为 $\frac 1 m$。当编号连续的 $k$ 张牌都被抽取过时,游戏结束。 问游戏结束的期望步数。 $1 \leq k \leq m \leq 2 \times 10^5$。

·

「Ynoi2019」美好的每一天~ 不连续的存在

给数组 $A$ 和 $n$ 个节点的树,每个点有一个 $1$ 到 $x$ 颜色。 $m$ 次查询,每次查询树上只保留 $[l,r]$ 内的所有节点,设一个极大连通块中出现奇数次数的颜色个数为 $t$,则其对答案的贡献为 $A_t$ ,即答案是所有连通...

·

「是男人就过8题——Pony.ai」IntervalTree

定义区间树为线段树的拓展,即每次断开的位置可以不是线段的中心。 给定一个 $[1, n]$ 的区间树和 $q$ 次询问,每次询问包含一个正整数 $k$, 你需要求出有多少区间的时间复杂度恰好等于 $k$。 $n, q\le 10^5,\ k\le 10^9$。...

·

「CometOJ Round #2 F」真实无妄她们的人生之路

有 $n$ 种操作,第 $i$ 种操作使用后有 $p_i$ 的概率升级,$(1-p_i)$ 的概率不升级。 进行若干次操作后,如果主人公的等级为 $i$,就能产生 $a_i$ 的贡献。 对于每个 $i \in [1;n]$ 求出,使用 $j \neq i$ 的所有操作 $j$,主人...

·

「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]$...

加载更多