题解 | #F. 是牛牛还是狗勾#

F. 是牛牛还是狗勾一眼0-1背包但是时间复杂度为 O(N*V) 但是这边N=10^6, V=10^3, 最大复杂度 10^9 显然直接做，是不行的但是这题有个特例，如果N>=1001, 根据鹊巢原理，根据前缀和，必然存在2个同余(1000)相等。也就是N>=1001必然有解 ...

Java 数组动态规划前缀和

2023-10-22

3 422

牛客周赛 Round 15 解题报告 | 珂学家 | 状态DP构造 + 树形DP

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

Java 深度优先搜索字符串贪心字符串匹配枚举动态规划回溯

2023-10-16

2 851

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

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

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

2023-09-25

2 808

牛客周赛 Round 11 解题报告 | 珂学家 | 线性dp+大剪枝

前言整体评价 T3和round 9的T3重复了，好意外。T4有点意思，比赛中一度不敢下手，然后试试骗分，发现过了。后来才知道，原来元素两两不等，那基本就退化为了。 A. 小美的外卖订单编号 index 1 / index 0的问题先减1，再加1 import java.io.Buffere...

Java 数组动态规划数学图贪心

2023-09-10

3 790

牛客练习赛115 解题报告 | 珂学家 | 记忆化 + 斜率极值 + dfn序&树状数组来自专栏

前言整体评价比赛刚开始的时候，看到清一色的英语题目，就有种不祥的预感，果然...... 感觉这场练习赛好难，在知识范围内是前四题，但是实际能ac 4题的却很少，是真的难。 A. Mountain sequence 要求构建一个山峰数组，求累计的方案总数其实这题是构造题，按照要求确定山峰(...

Java 数学动态规划数组深度优先搜索贪心二叉搜索树模拟树状数组组合数学

2023-09-09

4 730

牛客周赛 Round 8 解题报告 | 珂学家 | 构造 + 树形DP

前言人工智能究竟能不能拥有和人一样的“爱”。看完这本书的我觉得，这种爱，人工智能不应该去渴求拥有。整体评价原题场吧，开赛前就直言不讳说是来自美团的笔试题。整体还是简单，D这个树形DP不错，可能有段时间没写树形DP题。 A. 小美的排列询问简单题，线性遍历即可。 import jav...

Java 动态规划数学贪心数组深度优先搜索二叉搜索树枚举

2023-08-20

7 1242

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

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

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

2023-08-13

6 993

牛客周赛 Round 2 解题报告 | 珂学家 | 字符串hash + 打家劫舍型DP + 离线双指针

前言在黎明到来之前，必须有人稍微照亮黑暗。整体评价比赛的时候，A题用了字符串Hash，哭了。B题是经典题，C是模拟题，很怕的. D也是经典题，离散双指针，套路满满。 A. 小红的环形字符串因为长度为1000，所以理论上能接受对于这种环形，最好的处理方式: 方法一: 暴力 impo...

Java 字符串动态规划数学模拟前缀和滑动窗口

2023-07-09

7 989

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

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

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

2023-07-03

7 988

牛客小白月赛70 解题报告 | 珂学家 | 博弈SG函数 + 树上背包来自专栏

前言我会永远呆在桐人身边所以请不要怕。整体评价前几题中规中矩，到是C题一度眼前一亮，如果C题按照现实游戏中的来，求全局最优解，那估计有非常的有意思了。E是一道经典的博弈SG函数，F题则是一道树形DP（背包形态）。 A. 小d和答案修改给你一个字符串，把小写改成大写，大写改成小写。签到...

Java 动态规划双指针脑筋急转弯博弈论博弈数学

2023-06-16

2 691