分类: oi

207 篇文章

CF878E Numbers on the blackboard
题目链接:CF878E 给出 $n$ 个数字,每次询问一个区间 $[l,r]$,对这个区间内部的点进行操作。 每次操作可以合并相邻两个数 $x,y$ 其中 $x$ before $y$,将它们变成 $x+2y$ 对于每次询问输出当最后只剩下一个数字时,这个数字的最大值。 询问互相独立,答案对 $10^9+7$ 取模。 $1\leq n,q\leq …
CF1179D Fedor Runs for President
题目链接:CF1179D 给一棵 $n$ 个点的树,求加入一条边后,最多有多少条无向简单路径。 简单路径定义为任意一个点最多经过一次的路径。 $n\leq 5\times 10^5$。 Sol 考虑原来的树显然任意两点之间都能抵达,答案为 $\frac{n(n-1)}2$。 然后加入一条边 $(x,y)$ 就可以把 $x$ 到 $y$ 之间的路径拉…
P6072 『MdOI R1』Path
题目链接:P6072 给定一棵 $n$ 个节点的无根树,从中选择两个不交路径,求边权异或和之和最大值。 $n\leq 3\times 10^4$。 Sol 这里具体讲讲一只 $\log$ 的做法(在此感谢 神仙lwy)。 考虑这种题首先套路地枚举分界点 $x$,使两条路径一条在节点 $x$ 的子树内,另一条在子树外。 然后就很自然地想到了 $\ma…
「NOIP2021模拟赛8.19 C」玩家(gamer)
给定一个序列 ${a_i}$,统计有多少个排列 $p_1,\dots,p_n$ 对于任意 $i$ 满足 $p_i=a_i$ 或 $p_{p_i}=a_i$。 $1\leq n\leq 10^5,1\leq a_i\leq n$ $\texttt{2s/512MB}$ Sol 首先考虑一个满足条件的排列 $p$,一定会构成若干个环,使得每个点必然走一…
P3349 [ZJOI2016]小星星
题目链接:P3349 给定一棵 $n$ 个节点的树和一个 $n$ 个节点的图,要求为树上的每个节点映射到一个图上的节点(双射),且要求树上边对应图上也必须有相应的边,求方案数。 $n\leq 17$。 Sol 考虑朴素 DP,设 $F[i][j][k]$​ 表示将 $i$ 映射到 $j$,且 $i$ 的子树内的映射集合为 $k$ 的方案数。 瓶颈在…
浅谈容斥原理
容斥原理 定理: 设有 $n$ 个集合,第 $i$ 个集合为 $A_i$,则所有集合的并集可以表示成如下形式:$$|A_1\cup A_2\cup \cdots\cup A_n|=\sum_{i=1}^n (-1)^{i-1}\sum|A_1\cap A_2\cap\cdots\cap A_i|$$ 证明: 假设元素 $a$​ 被 $x$​ 个集合…
义乌中学暑假集训 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]$ 之间。…