分类: oi

201 篇文章

义乌中学暑假集训 2021.07.16 D
有一天 Mifafa 回到家,发现有 $n$ 只老鼠在她公寓的走廊上,她大声呼叫,所以老鼠们都跑进了走廊的洞中。 这个走廊可以用一个数轴来表示,上面有 $n$ 只老鼠和 $m$ 个老鼠洞。第 $i$ 只老鼠有一个坐标 $x_i$,第 $j$ 个洞有一个坐标 $p_j$ 和容量 $c_j$。容量表示最多能容纳的老鼠数量。 找到让老鼠们全部都进洞的方式…
义乌中学暑假集训 2021.07.15 D
白云在白兔的城市,打算在这里住 $n$ 天,这 $n$ 天,白云计划找白兔订购水。 白云给出了接下来的 $n$​ 天,每天的需水量,第 $i$​ 天为 $D_i$ 升。 白兔给出了接下来的 $n$ 天,每天水的价格,第 $i$ 天为 $P_i$ 元每升。 白云的小区有一个共用水壶,最大容量为 $V$ 升,初始为空。 接下来每天,白云可以进行如下操作…
义乌中学暑假集训 2021.07.15 C
白云有一颗 $n$ 个节点的树,每个点有一个点权 白兔需要找到两条点不相交的路径,要求最大化这两条路径覆盖点的点权和 $n\leq 10^5$。 Sol 换根 DP。 考虑两条路径的形态。 从两个子树中各抽出一条链。在一棵子树中抽一条经过根的链,再在剩余的儿子的子树中抽一条链。在一棵子树中抽一条子树内的链,再在经过这个子树的父亲抽一条链。 然后维护…
义乌中学暑假集训 2021.07.15 B
白云建立了 $n$ 个商店,白兔打算按照编号 $1\sim n$ 的顺序访问这些商店。商店 $i$ 有一个价格 $ai$ 表示交易商品所需的代价。 白兔在按顺序走时,每到达一个商店,可以花费代价购买一件商品,并放入自己手中。也可以出售手上的商品,并获得利润。 白兔的力量有限,同一时刻只能携带一个商品。问它遍历完所有商店后能够获得的利润最大是多少? …
义乌中学暑假集训 2021.07.14 D
给定一个 $n$​ 个节点,$m$ 条边无向图,初始边权均为 $1$。有 $k$ 次操作,每次操作可以选取一条边,使其边权加一。 设一条边的边权为 $v$​​,定义经过该边的时间为 $\frac{1}{v}$​​。 现有两个人,其中一个从 $s_1$ 走到 $t_1$,一个从 $s_2$ 走到 $t_2$,问如何操作使得两人花费总时间最少? $n,…
义乌中学暑假集训 2021.07.13 D
给定 $n$ 个数的序列 ${a_i}$,有 $m$ 组询问,每次询问给定区间 $[l,r]$,问有多少个子区间 $[i,j]$ 满足 $a_i,\dots,a_j$ 中不同的整数的数目是奇数。 $n,m\leq 5\times 10^5,1\leq a_i\leq n$。 Sol 首先肯定是考虑将询问离线。 然后考虑如何维护这个答案。 不难发现,…
义乌中学暑假集训 2021.07.13 C
给定一棵 $n$ 个节点的带权有根树,保证每个节点权值均为非负整数。 定义 $f(x)$​,表示对于节点 $x$​,包含 $x$​ 的节点的平均值最大的连通块内平均值。 求 $\min_{i=1}^n f(i)$。 $n\leq 10^5$。 Sol 既有最小也有最大,想到二分。 可以二分答案,每次 check 的时候数字权值减去 mid,跑一次换…
义乌中学暑假集训 2021.07.13 B
给定串 $s$,问其中有多少 namomo 子序列。定义一个子序列 $t$​ 是 namomo 子序列,当且仅当: $t_3=t_5$$t_4=t_6$$t_1,t_2,t_3,t_4$​ 两两不同。 输出答案 $\bmod 998244353$ 的结果。 $6\leq |s|\leq 10^6$。 Sol 这题有多种做法,这里提供一种比较简洁小清…