欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 E. 小红的漂亮串 一眼状压DP 这题有'red', 'der'限制，所以直接想O(1)求容斥解，行不通. 如何n很大的话，需要矩阵幂优化。 回到状压的思路 引入5种状态 0, any是1,2,3,4以外的所有状态 1, 以r字母结尾 2，以d字母结尾 3，以re字母结尾 4，以de字母结尾 先聊下如何解决 Q: 子串不包含‘der’ 只要在递推过程中, 对der的状态构造忽略即可 Q: 需要包含至少一个‘red’ 额外引入一维的状态0/1, 表示当前字符串以包含red, 和暂时不包含red 设计好了状态, 以及解决思路...

欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 F. 小辰刚学 gcd 我多么想，出题人，你可以亚撒西一点。 关于大量区间查询问题，还有gcd,最值，位运算这类，往往可以借助ST来加速。 这题比较特殊，可以分治二分（不知道这样说法对不对）来快速计算整个区间的不同gcd数。 可惜这个思路TLE了，感觉被严格卡复杂度了，多一个log也不行。 Java卡在56%， 等价C++（常数优化后）卡90%。 其实正解的思路，在数组 按与/或操作，区间查询最值等等问题，经常有出现。 就是维护变动的点列表 位运算的话，最多32位，所以最多32个点 而gcd的话，其实也是一样，因为最小的质因...

欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 D. 小红的扫雷游戏 一开始想着，是否可以搞一个方程组 如果确定为雷和非雷，这些是可解的，还有一些不能明确解的。 然后想想，这我也不会呀，重新审视了下数据范围，4*4，还有雷/非雷, 这个0-1特性，所以想到了全枚举状态，然后进行验证。 如果一个合法的状态，可以对相应的格子进行打标签。 如果一个格子，即被标签为雷，又被打标签为非雷，那就是不确定，反之就是确定态。 在来分析下时间复杂度为, O(2^16 * 16 * 8), 这是理论上复杂度，实际上因为游戏本身的限制，并没有这个高。 写出来，还是挺有意思的，这个题目。 import j...

前言整体评价这场挺有意思的，尤其是T4， 其实很早之前也想过这个问题？如何智能的扫雷，感觉有点难。这题被逼得主动去求解这个扫雷问题，幸好只有4*4，可以暴力枚举。喜欢这种比赛。A.  小红的字符串大小写变换Q: API题，把前k个字符大写，后n-k个字符小写可以切分为2段，然后分别大写，小写化，然后拼接即可 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner ...

前言 整体评价 前三题蛮简单的，T4是一个带状态的DP，这题如果用背包思路去解，不知道如何搞，感觉有点头痛。所以最后还是选择状态DP来求解。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 游游的整数翻转 这题最好是用API来处理，这样更简洁且准确率高 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner...

欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 D. 游游买商品 状态DP 令 dp[i][j][s], i为前i个项，j表示使用了多少钱，s为0,1表示状态 0表示 第i项不购买，或者半价购买 1表示 第i项全价购买 那状态转移为 dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1], dp[i - 1][j - cost[i] / 2][1] + happy[i]); dp[i][j][1] = max(dp[i - 1][j - cost[i]][0], dp[i - 1][j - cost[i]][1]) + ...

欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 C. Kevin的抱团游戏 很有意思的一道题 男生贡献1， 女生贡献2， 团为k大小，求落单的最少个数 思路分析 对于a，b两个变量，求最优组合解？ 这题的指导思路是：反悔堆 至少我是这么去组织思路的。 优先安排女生，尽量让所有的女生组团 男生去填补女生留下的空，完成团 多余的男生去开拓新的团 剩下的男生2:1 去替换女生 为啥说这是反悔堆思路呢？ 优先耗尽a，然后逐个增加b，记录此过程中的最大值。 这题的组团，是有点麻烦, 而且要考虑k的奇偶。 思路题： 假如这题男生贡献为x，女生贡献为y，那又如何解呢？ 代码 imp...

欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 D. Kevin翻硬币 比赛的时候，一直在猜结论，一共wa了17次，泪目。 但有一个想法，慢慢浮现出现来，比较硬核。 硬核解法 模拟 + 环形差分 先来说下模拟，实际上从原点出发，每次走k步，在环形的n中，一定可以回到原点的。最简单的验证，就是做n次的k步，必然回到原点。 更通俗的数学证明 kx = 0 mod n gcd(k, n) | 0 必然成立，也就说 x 有解. 根据鹊巢原理，最多走n次，就能回到原点. 为了方便处理，我们把 1-index 转换为 0-index 那剩下的核心问题是： 如何判定是否能够翻转呢？ 这...

欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 C. 数组平均 这题很有意思，先来看一个显而易见的结论 k == 1, 则结果为 最大值 - 最小值 k == n, 则结果必然为 0 如果核心的焦点在于， k在两者之间时，如何求解 一开始猜了一个，从收益最大(差值减少梯度)的角度去贪心，结果WA，而且得分不高 一度没辙，后面仔细分析了下，感觉可以枚举最大的没有被选中的项 如果选中某一个项为最大值，那比它小，而离的越近必然被保留，所以k的选择一定分布在前后缀. 所以思路是 排序 枚举未被选中的最大值 利用前后缀优化加速 import java.io.*; import jav...

前言 整体评价 其实T3最有意思， T4很典，是一道二分+最短路径经典套路。 T3 如果尝试 增量差值最小 的最大梯度去贪心的话，会失败，需要切换思路。 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 游游的正方形披萨 如果横竖差值最小的话 两者要么相等，要么差一 令 e1 = n / ((k + 1)/2+1), e2 = n / (k/2 + 1) 则 s = e1 * e2 这样很好的兼顾了k为奇偶的情况 import java.io.*; import java.util.*; public class Main { public static void mai...

详细的解题报告见https://blog.nowcoder.net/n/46ca5c404fa84dafb0af8aa382469d81--------A. 手玩能发现规律， a(n) = n + 1, 当然矩阵幂也可以B. 贪心即可，找到最大的组，分类讨论即可C. 姊妹题，比D范围小一点D. 前缀和优化的 二分, 在线解法是 n*logn，也可以尝试离线解法E. 二分图最大匹配的板子题F. 手玩找规律，就是分类讨论，以及找到关键点，被制约数的总数，以及制约数的种类数--------欢迎关注专栏珂朵莉 牛客周赛专栏https://www.nowcoder.com/issue/tutorial...

前言 整体评价 这场好像比前几场小白月整体要简单。《放学后》系列贯穿3题，突然想起来东野圭吾的《放学后》，现在的故事情节，还历历在目。 E，F挺有意思的，只是仅仅看着像博弈。 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 矩阵快速幂签到 非常优秀的一道题，明示矩阵幂 但是手玩一下，可以发现规律 a(n) = n + 1 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { ...

F. 一种异或游戏 这题卡常，真的没想到, 慎用map，不过可以使用数组hash来代替 这题虽然是披着博弈的皮，但感觉和常规的博弈差别蛮大的. 作为压轴题，带了一点思维，但又不是特别难. 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 n为Alice的牌数，m为Bob的牌数 先引入几个概念 被限定的数，特指 Alice牌中的数，且能在 Bob牌中找到 异或K 限定的数，特指 Bob牌中的数，能挤兑Alice牌，构建异或K 我们需要的是 被限定的数的总个数，注意是总个数 Hits 限定的数的各种种类，注意是种类数 Category 举例： Alice: 2 2 2...

前言 整体评价 很侧重思维的一场小白月赛，后几题都出的特别用心，特别巧妙。 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 数位dp？ 贪心， 就是逆序寻找到第一个非奇数，这一段就是最小操作数 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStream(System.in))...