前言 整体评价 T3是一道0-1 BFS题, 这样时间复杂度可以控制在O(n*m), 也可以用优先队列。 T4这类题型，在牛客Round周赛系列出现好多次了，要么状态机DP，要么容斥，如果n很大，就用矩阵幂优化。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 小红的整数操作 思路：同余分组 对k进行取模分组，同余的任意两个数，一定可以构造成一样 from collections import Counter n, k = list(map(int, input().split())) arr = list(map(int, input().split())) cnt...

前言 整体评价 思维场吧，T3印象深刻，其实我不会做，我就是猜的，到现在都不知道怎么过的，惭愧。 T4是换根模板题，也就这样了。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 小红购物 思路: 模拟 java python import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new Buf...

前言 这场感觉偏简单，T1构造，T2是求因子的变体题, T3是贪心思维题, T4是很典的二分题。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 小红的矩阵构造 思路: 构造 按斜对角线切割，并进行构造 对于a(i, j)点，其斜率为i+j 令i+j为奇数，则赋予奇数，反之填冲偶数 java python import java.io.BufferedInputStream; import java.util.Arrays; import java.util.Scanner; import java.util.stream.Collectors; public...

前言 题解 前三题都是构造类型的题，倒是D题是很典的动态规划题。 牛客还是偏思维，偏构造，偏数学，T_T. 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 小红的整数转换 a次操作+b，且a，b都是正整数 等价于 a * b = y - x 分类讨论下 y - x > 0 a=1, b=y-x，是可行解 y - x <= 0 无解 java python import java.io.BufferedInputStream; import java.util.Scanner; public class Main { publ...

前言 周末参加了一场赛氪组织的比赛，从上午9点做到下午2点，实在饿坏了，就错过这场比赛。 因为自己思维题比较弱，就把这场心心念念的比赛补了下。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 跳棋Ⅰ 思路: 思维+数学 这个跳棋1比跳棋2难太多了, ^_^. 感觉这题，因为一枚子做炮架子，然后彼此互相做炮架子，这样应该是最快的。 形式地话，假设炮架距离为x, 类似这样的函数 f(x) = 2x + n / x + c, c为常数 如果求函数值最大，那x在[1, sqrt(n)]之间 可以三分求解，也可以枚举x在[1, sqrt(n)] 这题难在思维，还有尾巴的处理。 1...

前言 划水打了这场比赛，感觉签到题稍有点多，^_^，整体做起来挺舒服的。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 宇宙万法的那个源头 式子可以拆为 11145 * (10^5x + 10^(5x - 5) + ... + 10^5 + 1) 所以质数一定小于11145，然后巴拉巴拉一顿分析.... 回到正题，因为3是11145的因子，且这个数是奇数 所以3就是天选之子。 B. 小苯的台灯 如果模数较小，那么一定存在循环节（I题 带猫猫任务也涉及这块）。 所以模拟就行了，因为存在较小的循环节。 C. 小苯的排列构造 可以把 2 4 1 3 作为内核 然后n &g...

前言 整体评价 C题这个构造题挺好的，赛中把-1写成No, 直接整不会了，T_T. D题是一道很裸的最小生成树题，只需要一个小小的逆向思维，把删除操作转换为构建过程。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 小红的漂亮串 数据规模较小，直接暴力匹配即可，当然也可以使用API。 java python import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) ...

前言 整体评价 这场小白真心难，E题成为这场的意难平，最后时候才理清。不过我是动态开点的线段树做法，时间刚好卡过。 C是状压+容斥，也可以用矩阵幂加速， D是反悔堆贪心。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 谜题：质数 很有趣的一道题 两个质数(奇数）和一定是偶数， 所以需要特判质数2，可以配对7，使得2+7=9 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] arg...

前言 整体评价 从A题中的Baidu, 可以猜到这场有几道题来自于百度校招。 其实B题有点意思，如果把十字星的范围放大，那就可以成为一个hard题。 D题也挺意思的，大概有两种思路，一种是从左到右枚举右端点，增量累加，一种是贡献思路。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 小红的Baidu 字符串s，重排后，可以等价于“Baidu” 思路， 最小化表达式 import java.io.*; import java.util.*; import java.util.stream.Collectors; public class Main { // J...

欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 简要版 这场参与的人数不是很多，可能和8:30开始有点关系。跟着榜单打的，有几题的题面还是来不及看。 非出题人，单纯从 做题人 的视角，简单写下流水账题解。 A. 鸭鸭 目标值要么为全0，要么为全1，求最小操作数 这题的难点在于，负数的原码 其实就是 负数的绝对值，然后额外高位置1 令 f(x)为 x二进制表示下1的个数 非负数， min(f(x), 32 - f(x)) 负数， min(f(-x) + 1, 31 - f(-x)) B. 鸭鸭拆快递 完全背包板子题 C. 鸭鸭多分切片 这场唯一的意难平，看了题，但是不...

思路经典题异或有如下特性 a ^ a = 0,a != b 必然 a ^ b != 0根据该特性，把整个数组进行异或和s，必然为非0，而这个非0，必然是由两个孤立的值提供然后根据s，其中的某一个幂次不为0，进行分组然后在进行分组求异或和为啥要这么做呢？如果一组只有一个孤立值，那异或和必然为孤立值本身这边通过分组，巧妙地把两个孤立数，分在两个不同的组中。最后的结果，比对大小，那个小，放在前面。代码 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 ...

前言 整体评价 D题感觉像博弈论书的经常提到的一个场景题。 E题题意有点晦涩，赛后才看明白啥意思，F题是道经典题吧，但是感觉太追求最优解了。 ST预处理，查询为分治二分，时间复杂度为 + 。 正解预处理，维护每个右端点的左侧变动列表，而下一个右端点基于相邻点构建，所以为 + 。 A. 小辰打比赛 田忌赛马 优先选择比自己实力弱进行pk，这样成就感会到达某个高点。 这题其实可以不用排序 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) ...

具体的解题报告：https://blog.nowcoder.net/n/8ff38d04db1a44e2928bef59e08a8350这是第20场牛客周赛，官方出了一场特别场A. 求的最大值，然后过滤最大值后的个数，即为解B. 状态机DP，因为是线性的，可以简化为两个变量C. 构造题，观察发现：实际上相邻1的对数，从一个组到另一个组，不改变总对数，应该可以把所有相邻对数放在第一组，后续补充独立的1，以及padding的0。D. 二进制枚举/BFS 求解E. 状压DP题，可以正向状压求解，也可以容斥求解F. 前缀和的前缀和，基于四个树状数组求解[珂朵莉 牛客周赛专栏]https://www.n...

前言 整体评价 这场比赛很特别，是牛客周赛的第20场，后两题难度直线飙升了。 前四题相对简单，E题是道状压题，历来状压题都难，F题压轴难题了，感觉学到了不少。 A. 赝品 先求的最大值 然后统计非最大值的个数，即可。 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStream(System.in)); int ...