2024年中国传媒大学程序设计大赛（同步赛）解题报告(流水账版) | 珂学家

前言整体评价整场还是挺nice，不是特别难，除了I题。J题是运气好，刚研究过区间gcd的性质，F题是启发式合并，不知道是不是正解，D题是一道很好的构造题，很妙。B题用了调和级数。其他的题，没啥印象了。倒是G题，感觉太套路，但是过的人有点少。 A. 小苯的区间和疑惑思路: 前后缀拆解 n ...

pypy3 Java 数学贪心模拟滑动窗口计数枚举

2024-03-20

12 680

牛客小白月赛82 解题报告 | 珂学家 | 状压容斥 + 反悔堆 + 动态开点线段树来自专栏

前言整体评价这场小白真心难，E题成为这场的意难平，最后时候才理清。不过我是动态开点的线段树做法，时间刚好卡过。 C是状压+容斥，也可以用矩阵幂加速， D是反悔堆贪心。欢迎关注珂朵莉牛客周赛专栏珂朵莉牛客小白月赛专栏 A. 谜题：质数很有趣的一道题两个质数(奇数）和一定是偶数...

Java 数学动态规划贪心计数状态压缩前缀和

2023-12-02

10 641

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

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

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

2023-11-20

4 645

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

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

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

2023-11-06

2 382

牛客周赛 Round 14 题解报告 | 珂学家 | 环形模拟 + 滑窗&前缀和&二分 + 数学

前言整体评价这场牛客周赛很特别，没有一题是水题（签到），也没真正意义上的压轴题。牛客周赛还是注重数学，B，D是数学题，A是模拟题，C的解法偏多，滑窗/26组前缀和&二分皆可。 A. 小红的环形字符串如果没有环形，那这题单纯使用一个 stack 就可以解决，就是括号匹配问题一样 ...

Java 数学字符串二分查找双指针滑动窗口模拟栈计数组合数学

2023-10-08

5 992

牛客周赛 Round 13 解题报告 | 珂学家 | 乘法原理场 + BFS上组合 + 众数贪心

前言整体评价终于回归了周赛的5题制，还是喜欢这种。题目有难度，才会有进度。 D是道很特别的题，感觉很典，它是基于BFS基础上的乘法组合, E也是道好题，模拟贪心好像是错的，得从众数的角度去剖析。 A. 矩阵转置置模拟即可 import java.io.*; import java.uti...

Java 数学动态规划图组合数学计数广度优先搜索

2023-09-25

2 808

牛客小白月赛78 解题报告 | 珂学家 | 数学场 + 线性同余方程来自专栏

前言整体评价数学场，牛客无论周赛，小白，练习赛，都喜欢出数论题。C题钻牛角尖了，二分+容斥一条路走到黑了，太惨了。D题是找规律题，找到了就容易了。E题是板子题，思路很容易想到，但是求解要么有板子，要么得有技巧。 A. B. C. 第K小表示数这种类型的题，有两种思路多路归并二分...

Java 数学哈希表计数前缀和分治滚动哈希组合数学枚举

2023-09-16

4 669

牛客周赛 Round 9 解题报告 | 珂学家 | 平均数定律

前言整体评价 C题只能模拟，好像直接用贡献法不行，如果要搞个O(n)时间复杂度还是挺难的。D题挺有趣的，名义上的众数，本质还是平均数构造，这题不是n个众数，就是n-1个众数。而n-1个众数，如何最小化代价挺费思量。 A. 小美的外卖订单编号因为涉及取模，所以最好的方式，是index 0，而...

Java 二分查找数学字符串数组贪心计数

2023-08-27

3 903

牛客周赛 Round 7 解题报告 | 珂学家 | 状态机DP + 数学场

前言所有他努力长大成人的日子，不过是为了与她相遇。整体评价这场C有点考验智商，太难了，最后用了暴力解，挺虚了的，感觉数据弱了。D到是一眼题，套路满满，反而简单，应该是属于状态计数DP。 A. 游游的you矩阵就是把字符转换为的幂次，这样方便统计. y -> 1, o ->...

Java 数学字符串动态规划枚举计数贪心组合数学

2023-08-13

6 993

牛客周赛 Round 1 解题报告 | 珂学家 | 分类计数 + 同余DP

前言生于生时，亡于亡刻。遵从自心，尽人之事。整体评价终于等来了侧重面试的比赛，而且题量刚刚好，不超纲，不涉及算法竞赛。第一场的比赛，感觉题目出的比较典，A是简单模拟，B则是计数题，C则是贪心思路，D是经典的同余DP。唯一吐槽的是，牛客好像当前只JDK 11, 用不了var. A. ...

Java 动态规划数学字符串贪心前缀和计数

2023-07-03

7 988