keduoli

题解

未归档(1)

/ 注册

全部文章 / 题解（共70篇）

题解 | #E. 重生之我是QQ邮箱#

E. 重生之我是QQ邮箱因为只算最末尾的7个字符串，且只有6个按钮第一按对的概率为1/6 总概率为 p = (1/6)^7 那期望为 E = n / p = n * 6^7 这题长途大佬出的很贼，引入了很多干扰项包括且不限于小数四舍五入取整如果无穷大，则返回 -1 根据题意，...

Java 数学

2023-10-21

6 562

题解 | #G 魔法树#

G 魔法树这题第一感觉就是树形DP 但是这里面的状态蛮多的，不太好下手。其实可以分情况讨论全是奇数全是偶数这样的话，dfs中需要维护的状态反而少了。还有一点就是，这题的核心是边也就是边的选择/不选决定了方案数只有理解这点，才能理解下面的转移方程全是奇数连通分量每个...

Java 二叉树深度优先搜索数学递归

2023-10-21

3 305

牛客周赛 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 14 题解报告 | 珂学家 | 环形模拟 + 滑窗&前缀和&二分 + 数学

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

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

2023-10-08

5 992

题解 | #E. 小红打boss#

E. 小红打boss 思路这题挺难贪心的，为啥这么说，因为有多种思路贪心，但是结果并非最优。但是无论如何贪心两种不同属性依次实施尽量让大的技能伤害double 所以这个贪心，也就变成最优配对，整体最大化的问题。来引入一个众数思路假设不同属性技能的次数，分别为 a, b, c, ...

Java 数学贪心

2023-09-25

4 341

题解 | #小红的转账设置方式#

D. 小红的转账设置方式这题分两部最短路计算计算总方案数求最小总代价，这个BFS最短路就可以出来难点在于: 总方案数这个方案总数和边的方向有关在保证最小代价不变的情况下，也就是保证每个点的最小路径不变(有向图）可以观察到图存在两种类型的边参与最短路的边没有参与...

Java 数学广度优先搜索组合数学

2023-09-25

7 399

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

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

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

2023-09-25

2 808

牛客周赛 Round 12 解题报告 | 珂学家 | 异或拆位技巧+加权前缀和

前言整体评价感觉前三题还是太简单，但第四题不错，不知道称呼为加权前缀和，还是前缀和的前缀和合适，真的太经典了。比赛中，唯一的遗憾就是1000000007少写了一个0，哀叹一声。 A. 小美种果树贪心，即第一天就施肥，然后3天形成一个循环节, y + 3 * x 然后需要处理下尾巴 i...

Java 数学哈希表字符串贪心哈希函数脑筋急转弯前缀和

2023-09-18

6 1032

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

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

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

2023-09-16

4 669

牛客周赛 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