keduoli

分类

未归档(1) 题解(86)

/ 注册

TA的专栏 55篇文章 3人订阅

牛客周赛解题报告系列

37篇文章 1279人学习

牛客小白月赛解题报告系列

16篇文章 1342人学习

牛客练习赛解题报告

2篇文章 730人学习

全部文章（共88篇）

题解 | #只出现一次的牛II#

思路经典题异或有如下特性 a ^ a = 0,a != b 必然 a ^ b != 0根据该特性，把整个数组进行异或和s，必然为非0，而这个非0，必然是由两个孤立的值提供然后根据s，其中的某一个幂次不为0，进行分组然后在进行分组求异或和为啥要这么做呢？如果一组只有一个孤立值，那异或和必然为孤立值本身...

2023-11-21

2 271

牛客小白月赛81 解题报告 | 珂学家 | 期望 + 二分验证 + 变动点压缩来自专栏

前言整体评价 D题感觉像博弈论书的经常提到的一个场景题。 E题题意有点晦涩，赛后才看明白啥意思，F题是道经典题吧，但是感觉太追求最优解了。 ST预处理，查询为分治二分，时间复杂度为 + 。正解预处理，维护每个右端点的左侧变动列表，而下一个右端点基于相邻点构建，所以为 + 。 A. 小辰打比...

Java 贪心二分查找模拟数学

2023-11-21

3 536

牛客周赛 Round 20 解题报告 | 珂学家 | 状压DP/矩阵幂优化 + 前缀和的前缀和

前言整体评价这场比赛很特别，是牛客周赛的第20场，后两题难度直线飙升了。前四题相对简单，E题是道状压题，历来状压题都难，F题压轴难题了，感觉学到了不少。 A. 赝品先求的最大值然后统计非最大值的个数，即可。 import java.io.*; import java.util.*; ...

Java 数学数组动态规划计数树状数组枚举

2023-11-20

4 645

题解 | #F. 小红的零#

欢迎关注珂朵莉牛客周赛专栏珂朵莉牛客小白月赛专栏 F. 小红的零整数末尾0的个数，取决于2和5的因子个数的最小值. 难点就在于：最小值先来看2道基础题对于一个数组arr，给予一个x，求这题的思路，就是对arr进行排序，然后绝对值去掉，这样就划分为2个部分，一部分小于x，另...

Java 数组前缀和计数树状数组

2023-11-20

5 462

题解 | #E. 小红的漂亮串#

欢迎关注珂朵莉牛客周赛专栏珂朵莉牛客小白月赛专栏 E. 小红的漂亮串一眼状压DP 这题有'red', 'der'限制，所以直接想O(1)求容斥解，行不通. 如何n很大的话，需要矩阵幂优化。回到状压的思路引入5种状态 0, any是1,2,3,4以外的所有状态 1, 以r字母结尾 2...

Java 数组动态规划

2023-11-20

6 814

题解 | #小辰打比赛#

欢迎关注珂朵莉牛客周赛专栏珂朵莉牛客小白月赛专栏 F. 小辰刚学 gcd 我多么想，出题人，你可以亚撒西一点。关于大量区间查询问题，还有gcd,最值，位运算这类，往往可以借助ST来加速。这题比较特殊，可以分治二分（不知道这样说法对不对）来快速计算整个区间的不同gcd数。可惜这个思...

Java 数学贪心数组

2023-11-17

5 404

题解 | #D. 小红的扫雷游戏#

欢迎关注珂朵莉牛客周赛专栏珂朵莉牛客小白月赛专栏 D. 小红的扫雷游戏一开始想着，是否可以搞一个方程组如果确定为雷和非雷，这些是可解的，还有一些不能明确解的。然后想想，这我也不会呀，重新审视了下数据范围，4*4，还有雷/非雷, 这个0-1特性，所以想到了全枚举状态，然后进行验证。如...

Java 数组数学模拟枚举

2023-11-12

7 356

牛客周赛 Round 18 解题报告 | 珂学家 | 分类讨论计数 + 状态DP

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

Java 动态规划数学计数字符串数组贪心脑筋急转弯

2023-11-06

2 382

题解 | #D. 游游买商品#

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

Java 数组动态规划

2023-11-05

3 386

题解 | #C. Kevin的抱团游戏#

欢迎关注珂朵莉牛客周赛专栏珂朵莉牛客小白月赛专栏 C. Kevin的抱团游戏很有意思的一道题男生贡献1，女生贡献2，团为k大小，求落单的最少个数思路分析对于a，b两个变量，求最优组合解？这题的指导思路是：反悔堆至少我是这么去组织思路的。优先安排女生，尽量让所有的女生组...

Java 贪心

2023-11-04

3 902