牛客43084A - Monster Killer https://ac.nowcoder.com/acm/contest/43084/A 难度：绿～蓝 题意 有 n(n≤103)n(n\leq 10^3)n(n≤103) 个怪物，每种怪物的抵御力为 aia_iai​ 初始时，主人公的战斗力为 000，主人公需要按顺序击败这些怪物 在某次战斗中，假设主人公的战斗力为 mmm，那么有如下情况： m=aim=a_im=ai​，他击败了当前怪物 m>aim>a_im>ai​，他击败了当前怪物，并且有 pip_ipi​ 的概率他的战斗力变为 m−1m-1m−1 m<aim...

牛客46811D - 宿命之间的对决 https://ac.nowcoder.com/acm/contest/46811/D 题意 给出一个正整数 x(1≤x≤1018)x(1\leq x\leq 10^{18})x(1≤x≤1018)，Alice 和 Bob 轮流进行如下操作： 选取原数的一个因子 ppp 令 x:=x−px:=x-px:=x−p 谁先将 xxx 减到 ≤0\leq0≤0，谁输。Alice 先手 问谁赢 思路 不难发现，如果双方足够聪明，选择的因子 ppp 一定 ≤\leq≤ 当前数，最终数字会被正好减到 000 前置知识： 奇数的所有因子都是奇数，偶数至少有一个因子是偶...

牛客7606D - 变换 https://ac.nowcoder.com/acm/contest/7606/D 题意 给出一个长度为 n(n≤106)n(n\leq 10^6)n(n≤106) 的序列 ai(1≤ai≤106)a_i(1\leq a_i\leq 10^6)ai​(1≤ai​≤106)，你每次操作可以选择一个数字不变，其他数字乘以任意一个质数 求出：为使序列中所有数字两两相同，至少需要的操作次数 思路 最终序列中所有数字两两相同，那么这个数字是什么？ 假设这个数字是 AAA，那么 AAA 可以写成 p1x1×p2x2×⋯×pkxkp_1^{x_1}\times p_2...

牛客32708G - ICPC2021 · 昆明 - Glass Bead Game https://ac.nowcoder.com/acm/contest/32708/G 来源：ICPC2021 · 昆明 知识点：条件概率 难度：蓝、铜牌题 题意 给出一个长度为 n(n≤100)n(n\leq 100)n(n≤100) 的排列，数字 kkk 被选中的概率是 pkp_kpk​ 刚开始序列是 1,2,3,…n1,2,3,\dots n1,2,3,…n 有序的。 现在随机选择一个元素（注意数字 kkk 被选中的概率是 pkp_kpk​），将它移动到序列最前。假如选择的元素是从前往后第 iii...

牛客41614I - It Takes Two of Two https://ac.nowcoder.com/acm/contest/41614/I https://codeforces.com/gym/103931/problem/I 来源：2022 · 上海市赛 难度：金牌题、紫 题意 有一个随机数生成器，每次独立、均匀、随机地生成两个在 [1,n][1,n][1,n] 的随机数 u,vu,vu,v 有一张图初始时图为空。 流程如下： （1）运行一次随机数生成器，得到 u,vu,vu,v （2）将双向边 u↔vu\leftrightarrow vu↔v 添加到图中后，图满足如下条件...

概率期望 洛谷1850 - 换教室 https://www.luogu.com.cn/problem/P1850 难度：蓝 题意 有 nnn 节课。学生需要按顺序依次完成所有的 nnn 节课。 若不提交申请，时刻 iii 学生需要在 cic_ici​ 的教室上课。 学生可以申请将教室更改为 did_idi​，对于时刻 iii 的申请，有 pip_ipi​ 的概率申请通过。 只能申请更换至多 mmm 个时刻的教室。申请是一次性提交的，即无法根据之前的申请通过情况决定接下来申请哪个。 教室和教室之间的距离已知。学生一开始在第一节课的教室。课间学生需要走到下一次课的教室。 原题面： 有 ...

牛客24346M - String Problem https://ac.nowcoder.com/acm/contest/24346/M 来源：ICPC2021 · 沈阳 题意 给出一个长度为 nnn 的字符串，对于每个前缀，求最长的、字典序最大的子串，对于每个 i∈[1,n]i\in [1,n]i∈[1,n] 输出所求的子串的开始和结束位置。 样例： pbpbppb 1 1 1 2 1 3 1 4 1 5 5 6 5 7 对于每个 i∈[1,n]i\in [1,n]i∈[1,n]，结束位置一定是 iii。 考虑用 SAM 处理结束位置的左端点的位置。 先思考几个前置知识： ...

牛客7502I - Subsequence Pair 链接：https://ac.nowcoder.com/acm/contest/7502/I 来源：ICPC2020 · 小米 知识点：DP、字典序的性质 难度：紫 题意 给出两个字符串 SSS 和 TTT（∣S∣≤2000|S|\leq2000∣S∣≤2000，∣T∣≤2000|T|\leq2000∣T∣≤2000）。 需要从 SSS 和 TTT 中分别选出一个子序列 xxx 和 yyy。 要求：xxx 的字典序 <<< yyy 的字典序，（ 以下记为 lex(x)<lex(y)\text{lex}(x)&...

牛客331194I多校 - The Great Wall II https://ac.nowcoder.com/acm/contest/33194/I 题意 给出一个长度为 n(n≤8000)n(n\leq 8000)n(n≤8000) 的序列，你需要将序列切割成 kkk 段，每段对答案的贡献为这一段的最大值。 需要最小化答案。 你需要对于所有的 k∈[1,n]k \in [1,n]k∈[1,n]，回答每个询问。 思路 初步思路 考虑 DP。 令 dp[i][j]dp[i][j]dp[i][j] 为前 iii 个物品，分成 jjj 段，的最小值。 转移：dp[i][j]←min⁡(d...

牛客8409H - Equivalent Prefixes https://ac.nowcoder.com/acm/contest/8409/H ICPC2020 · 小米 题意 给出两个长为 nnn 的数组 aia_iai​，bib_ibi​，求最大的前缀 q(1≤q≤n)q(1\leq q \leq n)q(1≤q≤n) 满足其任意子区间的 RMQa(l,r)=RMQb(l,r)\text{RMQ}_a(l,r)=\text{RMQ}_b(l,r)RMQa​(l,r)=RMQb​(l,r)，其中 l≤r≤ql\leq r \leq ql≤r≤q。 RMQw(l,r)\text{RMQ...

牛客33194G多校 - Magic Spells 链接：https://ac.nowcoder.com/acm/contest/33194/G 知识点：Manacher、哈希 难度：蓝 题意 给出 KKK 个字符串，求所有字符串的公共回文子串的个数。 K≤5K \leq 5K≤5，∑n≤3×105\sum n \leq 3\times 10^5∑n≤3×105 思路 错误思路 先用 Manacher 处理出第一个字符串的回文串，从左到右分别计算以每个位置为中心的每个回文串的哈希，放入 set 中。 错误原因：复杂度太大。 正确思路 先用 Manacher 处理出第一个字符串...

HDU7215多校 - Weighted Beautiful Tree 链接：http://acm.hdu.edu.cn/showproblem.php?pid=7215 知识点：树形DP、贪心 难度：紫 题意 给出一棵 nnn 个节点的树，每个点有点权 wiw_iwi​，每条边有边权。 现在需要修改一些点的点权，使得 wu≤wedge≤wvw_u \leq w_{edge} \leq w_vwu​≤wedge​≤wv​，即任意两点之间的边权的数值要在这两个点的点权之间。 修改 iii 节点点权的代价是：d×cid\times c_id×ci​，其中 ddd 是修改后点权的变化量。 ...

HDU7190多校 - BBQ 链接：http://acm.hdu.edu.cn/showproblem.php?pid=7190 知识点：DP、哈希 难度：紫 题意 给出一个字符串 SSS，你可以进行如下 333 种操作。 在任意位置添加字符；删除、修改任意字符。 你需要让 SSS 满足以下要求： ∣S∣mod  4=0|S| \mod 4=0∣S∣mod4=0 si=si+3s_i=s_{i+3}si​=si+3​，si+1=si+2s_{i+1}=s_{i+2}si+1​=si+2​ (imod  4=1)(i \mod 4=1)(imod4=1)，iii 从 111 开始。...

后缀自动机 SAM 重要性质 后缀自动机的节点数不超过 2n−12n-12n−1。 以下是字符串 aababaaababaaababa 形成的图 模版讲解 fail[i]fail[i]fail[i] 指向的节点可以这么描述： 是当前节点表示不了的、是当前节点能表示的子串集合的后缀。 若当前节点能表示的最短子串为 c+Sc+Sc+S，那么指向的节点能表示的最长子串一定为 SSS。 以下是上图中的 fail\rm failfail 树，括号代表 当前节点表示的子串集合的长度范围 特征 父节点能表示的最短子串的长度 === 儿子节点能表示的最长子串的长度 +1+1+1 每个...