前言 整体评价 很典的一场比赛， T3是俄罗斯套娃模型(如果n>=1e5), dp解(n<=1000)， T4是最小生成树，这边用kruskal(并查集)来构建. A. 小美的升序数组 模拟题，按题意要求就行 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStream(...

F. 是牛牛还是狗勾 一眼0-1背包 但是时间复杂度为 O(N*V) 但是这边N=10^6, V=10^3, 最大复杂度 10^9 显然直接做，是不行的 但是这题有个特例，如果N>=1001, 根据鹊巢原理，根据前缀和，必然存在2个同余(1000)相等。 也就是N>=1001必然有解 所以如果依旧使用 0-1背包算法 只要找到任意解就行，(最多1001项) 和 长途大佬 的解法，区别在于 不用分类讨论(n<=1000, n>1000) 当然这里还有一个难点，就是, 回溯构造 注意java要用快读 import java.io.*; import java.util....

E. 重生之我是QQ邮箱 因为只算最末尾的7个字符串，且只有6个按钮 第一按对的概率为1/6 总概率为 p = (1/6)^7 那期望为 E = n / p = n * 6^7 这题 长途大佬 出的很贼， 引入了很多干扰项 包括且不限于 小数四舍五入取整 如果无穷大，则返回 -1 根据题意，最终的结尾为 E^(2^m) 因为只取个位数，而个位数不受其他位数影响, 因此可以期望E提前 mod 10 ((E % 10) ^ (2^m)) % 10 这个形态就是 欧拉降幂 根据扩展欧拉定律 这边的p=10，其欧拉函数值10*(5-1)/5*(2-1)/2=4 而 b = 2^m 然...

G 魔法树 这题第一感觉就是树形DP 但是这里面的状态蛮多的，不太好下手。 其实可以分情况讨论 全是奇数 全是偶数 这样的话，dfs中需要维护的状态反而少了。 还有一点就是，这题的核心是边 也就是边的选择/不选决定了方案数 只有理解这点，才能理解下面的转移方程 全是奇数连通分量 每个节点，定义如下两个状态(s1, s2) s1表示包含该节点的连通图 累加和为 奇数 s2表示包含该节点的连通图 累加和为 偶数 那状态转移为 s1' = s1 * t1 + s1 * t2 + s2 * t1; s2' = s1 * t1 + s2 * t1 + s2 * t2; 全...

详细的解题报告https://blog.nowcoder.net/n/331464bebcdb4fe29af232c84b1c2919---A. 枚举签到题， 只要枚举前后两段的分界点，然后判定末尾的奇偶是否一致B. 枚举最终的字母，然后评估代价，这边单字母的转移代价 > cost = min(abs(i - j), 26 - abs(i - j)) 这符合环状结构C. 有3种解法3维DP，正向递推，从而求解最终的结果脑筋急转弯，分类讨论字符串长度n = 1，任意字符即可n = 2，前后两字符不相等就行n = 3，只有 101， 121， 202， 020这几个字符串满足需求n = 4，...

前言 整体评价 这场T3挺有意思的，只会3维状态DP进行构造。不过这题其实是脑筋急转弯，有规律可循。 T4是经典的树形DP，从比赛来看，T3难于T4. A. 游游的整数切割 枚举遍历就行，需要满足前后两段其末尾的元素奇偶一致 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStream(System.in)); ...

详细的解题报告在https://blog.nowcoder.net/n/60037c343b38459baf270a873285cc89------------------------------------这场没有水题，也没难题，很适合节日后A. 模拟引入双端队列，先按栈处理（很像括号匹配），最后再处理环状两侧B. 数学从5,6的因子切入， x和y在去除5,6因子后，需要相等才有解，同时5是乘积，6是整除，因此xy的5,6个数也有大小制约关系C. 两种思路，这一种是传统的滑窗解法，一种是前缀和&二分 D. 组合数学最后的解为 676 * (n-2) * 26^(n-3)

前言 整体评价 这场牛客周赛很特别，没有一题是水题（签到），也没真正意义上的压轴题。 牛客周赛还是注重数学，B，D是数学题，A是模拟题，C的解法偏多，滑窗/26组前缀和&二分皆可。 A. 小红的环形字符串 如果没有环形，那这题单纯使用一个 stack 就可以解决，就是括号匹配问题一样 那如果是环形结构呢？ 其实这题有一个性质 x...AAA...y 中间的3个A，如果第一个和第二个匹配，还是第二个和第三个匹配，都不会影响结果 同理在环形链接处，也满足相似的结论。 核心结论: 根据等价原理，合并操作的顺序，并不影响最终结果 可以引入双端队列 先把双端队列当栈使用 最后比较双端...

E. 小红打boss 思路 这题挺难贪心的，为啥这么说，因为有多种思路贪心，但是结果并非最优。 但是无论如何贪心 两种不同属性依次实施 尽量让大的技能伤害double 所以这个贪心，也就变成 最优配对，整体最大化的问题。 来引入一个众数思路 假设 不同属性技能的次数，分别为 a, b, c, 其中c为众数 如果 a + b <= c 分类讨论 如果最大数都在集合c中，那一定可以实现a+b=n-c次 如果最大数也分布于集合a，b中，那a和b直接选取c的最小元素即可, 等价于交换，也一定能实现a+b=n-c次 如果 a + b > c 由众数定理， 一定可以构建 全是不同属性...

D. 小红的转账设置方式 这题分两部 最短路计算 计算总方案数 求最小总代价，这个BFS最短路就可以出来 难点在于: 总方案数 这个方案总数和边的方向有关 在保证最小代价不变的情况下，也就是保证每个点的最小路径不变(有向图） 可以观察到 图存在两种类型的边 参与最短路的边 没有参与最短路的边 如何处理参与最短路的边 参与最短路的边，实际上 仅 属于一个集合，由集合贡献 如何处理非参与最短路的边 这类边，正反都可以，不影响结果，贡献2 分析到这里，这题的解题思路就很容易了。 先BFS预处理所有的点(最短路） 从点出发，找到上游的点集(边集), 贡献 找到剩下...

前言 整体评价 终于回归了周赛的5题制，还是喜欢这种。题目有难度，才会有进度。 D是道很特别的题，感觉很典，它是基于BFS基础上的乘法组合, E也是道好题，模拟贪心好像是错的，得从众数的角度去剖析。 A. 矩阵转置置 模拟即可 import java.io.*; import java.util.*; import java.util.stream.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new Buffe...

前言 整体评价 感觉前三题还是太简单，但第四题不错，不知道称呼为加权前缀和，还是前缀和的前缀和合适，真的太经典了。 比赛中，唯一的遗憾就是1000000007少写了一个0，哀叹一声。 A. 小美种果树 贪心，即第一天就施肥， 然后3天形成一个循环节, y + 3 * x 然后需要处理下尾巴 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = n...

前言 整体评价 数学场，牛客无论周赛，小白，练习赛，都喜欢出数论题。C题钻牛角尖了，二分+容斥一条路走到黑了，太惨了。D题是找规律题，找到了就容易了。E题是板子题，思路很容易想到，但是求解要么有板子，要么得有技巧。 A. B. C. 第K小表示数 这种类型的题，有两种思路 多路归并 二分 + 容斥 前者适合k值较小，后者是通解，大小通吃。 不过这题，按容斥来解，感觉毫无头绪，T_T 所以只能回到多路归并的思路去解 借助优先队列，每次扩展+a/+b，去重模拟即可。 当然这题，如果a=b, 直接返回k*a即可 import java.io.*; import java.util.*;...

前言 整体评价 T3和round 9的T3重复了，好意外。T4有点意思，比赛中一度不敢下手，然后试试骗分，发现过了。后来才知道，原来元素两两不等，那基本就退化为了。 A. 小美的外卖订单编号 index 1 / index 0的问题 先减1，再加1 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new Buffer...