牛客33187K多校 - Link with Bracket Sequence I 链接： 知识点：DP、组合数学 难度：紫 UPD 后续 杭电多校对本题出了续集。“Link with Bracket Sequence II” https://blog.nowcoder.net/n/3d5af4fe3b58455a976ee3e312279d19 UPD 类似题 https://blog.nowcoder.net/n/cca78595e55d4783ad5f78f9e058d20c 题意 给出一个长度为 nnn 的括号序列（也能不合法）SSS，需要构造出一个长度为 mmm 的新的合法的...

HDU7154多校 - Slayers Come 链接：https://acm.hdu.edu.cn/showproblem.php?pid=7154 知识点：DP、线段树、组合数学 难度：紫 题意 给出 nnn 个怪物的战力值 aia_iai​，抵御值 did_idi​。 有 mmm 种技能，每种有属性 xix_ixi​，LiL_iLi​，RiR_iRi​，代表下标为 xix_ixi​ 的怪物立即死亡。该怪物死亡时会对左边相邻的怪物造成 axi−Lia_{xi}-L_iaxi​−Li​ 的伤害，对右边相邻的怪物造成 axi−Ria_{xi}-Riaxi​−Ri 的伤害。会产生连锁反...

牛客34442J - 收集者 链接：https://ac.nowcoder.com/acm/contest/34442/J 知识点：计数DP,组合数学 难度：紫 题意 给出一个长度为 nnn 的 01串，你需要从中选出一个开头为 111 的子序列 能选出多少种长得不一样的子序列。 （题目额外要求：如果给出的01串中有0，最后的答案额外加1。） 思路 错误思路：利用组合数公式 错误原因：去重太麻烦。 正确思路：DP dp[i]dp[i]dp[i] 代表截止到第 iii 位（第 iii 位可选可不选），有多少种子序列。 对于每一位，有选和不选两种选择。 如何去重？ 以下面的01串...

牛客7329D - 火柴排队 链接：https://ac.nowcoder.com/acm/contest/7329/D 知识点：概率、古典概型、组合计数、分组背包DP 难度：紫 题意 给出一个长度为 nnn 的序列，序列中的数字两两不同。 现在随机从中选择 kkk 个元素，将它们的数值 +d+d+d。 设原序列为 aia_iai​，新序列为 ai′a_i'ai′​，求 ai<aja_i<a_jai​<aj​ 并且 ai′<aj′a_i'<a_j'ai′​<aj′​ 的概率。 需要对于每个 k∈[1,n]k\in [1,n]k∈[1,n] 求出它对...

牛客14599 - 子序列 链接：https://ac.nowcoder.com/acm/problem/14599 知识点：组合数学 难度：蓝 题意 给出一个小写字母字符串 T，长度为 nnn。 求有多少长度为 m(m≤105)m (m\leq10^5)m(m≤105) 的小写字母字符串 S，满足 T 是 S 的一个子序列。 思路 错误思路 利用排列组合公式，先确定原字符串 T 中每个字母的位置，再确定剩下的空位放什么。但是去重麻烦。 初步思路 我们从合法的新串下手，考虑制定出一种方法来从中找出原串。 对这种方法的要求是：按照这种方法 找出的新串 的下标 必须唯一。 ...

牛客5633D - 宝石装箱 链接：https://ac.nowcoder.com/acm/contest/5633/D 知识点：线性容斥、背包DP 难度：蓝 题意 将 nnn 个物品装进 nnn 个箱子，每个箱子恰好装一个物品。 要求第 iii 个物品不能装入第 aia_iai​ 个箱子中。 问有多少种合法的方案。 思路 错误思路 线性容斥。计算不合法的总方案数。ans=n!−不合法的总方案数ans=n!-不合法的总方案数ans=n!−不合法的总方案数 不合法的总方案数=∑i=1n前i个箱子合法且第i个箱子不合法的方案数不合法的总方案数=\sum_{i=1}^{n}前i个箱子合...

牛客2927E - 树 链接：https://ac.nowcoder.com/acm/contest/2927/E 知识点：树形DP、组合数学、数学演算 难度：紫 题意 有一棵 nnn 个节点的树，每条边长度为 111，设 dis(u,v)dis(u,v)dis(u,v) 为 uuu 到 vvv 的距离。 求 ∑i=1n∑j=1ndis2(i,j)\sum_{i=1}^{n}\sum_{j=1}^{n}dis^2(i,j)∑i=1n​∑j=1n​dis2(i,j) 答案对 998244353998244353998244353 取模。 思路 如果将此题改为：求 ∑i=1n∑j=1n...

牛客33634E - 野兽追猎者塔维什plus 链接：https://ac.nowcoder.com/acm/contest/33634/E 知识点：概率期望、二项分布 难度：蓝 题意 动物伙伴总共有三种： 米莎：4点攻击力，2点血量。 雷欧克：2点攻击力，4点血量。 霍弗：4点攻击力，4点血量。 每种动物伙伴出现的概率均为 13\frac{1}{3}31​。 其中每只 雷欧克 有一个效果：除了该 雷欧克 以外的其他随从获得 f(x)f(x)f(x) 的攻击力，xxx 为雷欧克的总数。 f(x)=∑i=110aixif(x)=\sum_{i=1}^{10}a_ix^...

牛客11251D - 小红的构造题 链接：https://ac.nowcoder.com/acm/contest/11251/D 知识点：构造、组合计数、贡献 难度：蓝 题意 构造一个长度不超过 2×1052\times10^52×105 的字符串，其中包含 K(K≤1014)K(K \leq 10^{14})K(K≤1014) 个“red”的子序列。 思路 “red”的长度仅为3，可以只分析“e”。 某个“e”对子序列数量的贡献为 这个e前面的r的数量×这个e后面的d的数量这个e前面的r的数量 \times 这个e后面的d的数量这个e前面的r的数量×这个e后面的d的数量 如果我...

牛客4784F - 美丽的序列I 链接：https://ac.nowcoder.com/acm/contest/4784/F 知识点：组合计数、贡献 难度：蓝 题意 给出一个长度为 nnn 的序列。再给出 nnn 个lil_ili​，rir_iri​。意思是aia_iai​是[li,ri][l_i ,r_i][li​,ri​]中的随机一个，并且出现的概率一致。 如果一个序列出现 ai>ai+1a_i>a_{i+1}ai​>ai+1​，那么就在i和i+1之间将序列断开。定义一个序列的美丽值为该序列最终的段数（如果一次也没有从中间分断过，那么美丽值为1）。 求出所有可能...

GYM102798C - Rencontre 来源：CCPC2020 · 威海 链接：https://codeforces.com/gym/102798/problem/C 知识点：树形DP、组合数学、古典概型、贡献 难度：紫、银牌 题意 给出一棵 n 个节点的树， 再给出三个点集，点集中的点表示树上的点，这三个点集中的点互不相同。 现在从这三个点集中各随机选出一个点。有三个人分别从这三个点出发，前往同一个会合点，求这三个人走过距离总和的期望。 思路 考虑古典概型 ans=所有情况对答案的贡献的加和情况总数ans=\frac{所有情况对答案的贡献的加和}{情况总数}ans=情况总...

牛客11187D - 月之暗面 链接：https://ac.nowcoder.com/acm/contest/11187/D 知识点：树形DP、组合计数 难度：绿 题意 给出一棵 n 个点的树， 有 X 种普通颜色，Y 种特殊颜色 现在要给树上的每个节点染色，普通颜色染色没有限制， 但两个相邻的节点不能染相同颜色的特殊颜色 这些颜色不要求全部使用 求染色方案数， 答案对 998244353 取模。 思路 考虑树形DP 错误思路 用 dp[cur][0/1]dp[cur][0/1]dp[cur][0/1] 表示 curcurcur 节点染普通颜色和特殊颜色的方案数。 假设该父节点...

牛客32282C-Little Pony and Expected Maximum 链接：https://ac.nowcoder.com/acm/contest/32282/C 知识点：概率期望、容斥 难度：绿 题意 一个骰子有 mmm 面，第 iii 个面有 iii 个点，每一面等概率出现，每次投掷的结果独立。 计算投掷 nnn 次骰子所能获得最大值的期望。 思路 一个骰子有 m 面，投掷 n 次，仅前 i 面出现的概率为 (im)n(\frac{i}{m})^n(mi​)n 所以答案 ans=1×(1m)n+2×(2m)n+...+n×(nm)nans=1\times(\f...

牛客9510D - 数列 链接：https://ac.nowcoder.com/acm/contest/9510/D 知识点：取模的性质、哈希 难度：蓝 题意 给出一个数列，求有多少个区间里每个数都出现了 KKK 的倍数次。 n,K<=106n,K<=10^6n,K<=106 思路 往 %K\% K%K 的方向考虑 原因：涉及到倍数次都往这方面想。 如果你对这个性质不熟，推荐你用这些题练手：牛客91L、牛客14694、洛谷2634 接着，按照感觉，考虑 DP。 我们马上发现，DP很难，因为他要求“每个数都出现了 K 的倍数次”。 我们发现，他要求的是连续的区间...