POJ List
为了不再被虐,我力争学会… 助你早日成为信息学奥赛斗士  GitHubyzxoi/POJ  
二项式系数 Binomial Coefficients
1.1 基本恒等式 Basic Identities 1.1.1 定义 Definition $\binom nk$ 表示二项式系数,其中 $n$ 称作上指标 (upper index),而称 $k$ 为下指标 (lower index)。 $$\binom rk=\begin{cases}\frac{r^{\underline{k}}}{k!} …
CF377D Developing Game
题目链接 有 $n$ 个工人,第 $i$ 个工人的能力是 $v_i$,他只与能力在 $l_i$ ​到 $r_i$ 之间的人在一起工作,问最多能选出多少人一起工作并输出方案。 Sol 如果我们选了一个集合 $\mathcal{S}$ 合法,则必有: $$\max_{i\in \mathcal{S}}l_i\le \min_{i\in \mathcal…
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$。表示在…