月度归档: 2021年7月

18 篇文章

义乌中学暑假集训 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 这题有多种做法,这里提供一种比较简洁小清…
CF GYM102759 I. Query On A Tree 17
Description 题目链接:GYM102759 I 给定一棵以 $1$​ 为根节点的拥有 $N$​ 个节点的带点权树,初始时每个点的点权均为 $0$​,有 $Q$​ 次操作,每次操作有两种类型: 1 u,以 $u$ 为根节点的子树内每个点点权均加 $1$。2 u v,将节点 $u$ 到节点 $v$ 的简单路径上的点的点权均加 $1$。 每次操…
CF679E Bear and Bad Powers of 42
Description 题目链接:CF679E 定义一个正整数是坏的,当且仅当它是 $42$ 的次幂,否则它是好的。 给定一个长度为 $n$ 的序列 $a_i$,保证初始时所有数都是好的。 有 $q$ 次操作,每次操作有三种可能: 1 i 查询 $a_i$。2 l r x 将 $a_{l\dots r}$ 赋值为一个好的数 $x$。3 l r x …
CF453E Little Pony and Lord Tirek
Description 你有 $n$ 只小马(编号从 $1$ 到 $n$)。每只小马有三种属性。 $s_i$:时间为 $0$ 时这只小马拥有的法力值。 $m_i$:这只小马可以拥有的最大法力值。 $r_i$:这只小马单位时间内回复的法力值。 提雷克会给出 $m$​ 条指令,每一条都可以被描述为 $3$ 个整数:$t_i, l_i, r_i$。表示在…
义乌中学暑假集训 2021.07.12 C
Description 有一个 $2\cdot 10^9\times 2\cdot 10^9$ 的网格图,现要从 $(x_1,y_1)$ 走到 $(x_2,y_2)$,每次只能走上下左右四个方向且不能走到网格图外面。 假设当前位置为 $(x,y)$, 向南走一步($x$ 加一)的代价为 $2xy^2+2y^2+x^2$;向北走一步($x$ 减一)的…
义乌中学暑假集训 2021.07.11 D
Description 给定三个长度为 $n$ 的正整数序列 $A,B,C$。 定义 $f(X,l,r)$ 表示在序列 $X$ 中,$\max X_i-\min X_i$。 定义一个区间 $[l,r]$ 的权值为 $f(A,l,r)\times f(B,l,r)\times f(C,l,r)$。 求对于所有 $1\leq l\leq r\leq n…
义乌中学暑假集训 2021.07.10 D
Description 给定一棵 $n$ 个节点的树,有 $m$ 个询问,每次给定 $l,r$,查询若只保留点编号在 $[l,r]$ 的点,边编号在 $[l,r]$ 的边,有多少个连通块。 此时点 $a$ 与点 $b$ 连通当且仅当 $l\leq a,b\leq r$,且 $a,b$ 在树上的简单路径中所有的点与边的编号都在 $[l,r]$ 之间。…
义乌中学暑假集训 2021.07.09 D
Description 给定一棵 $n$​ 个节点的树 $T$​,有 $m$​ 个询问,每次询问给定 $l,r$​,问存在多少个 $k\in Z$​,使从树上编号为 $l$​ 的点沿着 $l\rightarrow r$​ 的简单路径走 $k$​ 步恰好到达 $k$​。 $1\leq n\leq 3\times 10^5,1\leq m\leq 3\…
CF765F Souvenirs
Description 题目链接:CF765F 给定一个长度为 $n$ 的序列 $a_i$,有 $m$ 个询问,每次询问给定 $l,r$,求对于 $i,j\in[l,r]$,且满足 $i\not = j$,$|a_i - a_j|$ 的最小值。 $1\leq n\leq 10^5,1\leq m\leq 3\times 10^5,0\leq a_i…
义乌中学暑假集训 2021.7.8 D
Preface 见到 lxl 小姐姐真的好好好兴奋!!! 果然好可爱 Description 给定一个序列 $A$,求所有 $1\leq l \leq r \leq n$ 的区间 $[l,r]$ 的最大子段和的和,答案对 $2^{64}$ 取模。 $1\leq n\leq 10^5,-10^9\leq A_i\leq 10^9$ Solution …
升学e网通 倍速播放
准备 请使用电脑网页端以进行。(手机其实也可以,不过本文不着重提) 安装 安装 Tampermonkey 可以在浏览器的**插件商店**中下载,也可以从其他渠道获取Tampermonkey的crx文件,然后解压提取出来。 然后进入浏览器设置→扩展程序,进入后再打开右上角的开发者模式并保持该窗口的开启。之后找到被解压后的tampermonkey.cr…