Gooby114514

分类

未归档(12) 题解(25)

/ 注册

全部文章（共37篇）

题解 | #E 而后单调#

E 而后单调首先思考不可能的情况，分成两种：存在重复元素，那么最后就不可能是严格单调增或者严格单调减的情况，因此如果要满足题目要求，那么原数组必须要满足有至少长度为的区间能和最后排好的某一段是能匹配的，如果不能就是那么解法也很显然了，匹配的过程可以使用或者二分查找+双指针优化...

二分查找双指针

2024-12-30

2 43

题解 | #D 预知#

D 预知本题使用到了鸽巢原理（抽屉原理）的思想。首先考虑的情况，由于总卡牌数，故这是必败的。当时，看样例也能发现分为几种情况：全是时，说明随便翻两张都必胜，所以只有一个时，例如这种情况，很多同学以为要预知张，其实只要张就够了，因为预知出来的两张都一样的话...

2024-12-30

5 55

题解 | #C 小数字#

C 小数字当足够大的时候，。当小到一定程度时，以上大小关系才会发生一定变化。并且当时，我们发现只有的操作可以让减少。所以我们定一个界限（比如10），然后大范围开根号，小范围判断，小于0的时候直接计算即可。 #include <bits/stdc++.h> u...

2024-12-30

2 40

题解 | #B 球格模型（简单版）#

B 球格模型（简单版）我们容易想到一种构造，可以从开始往右下角斜着填写。剩下有不够的地方，我们就直接把那一行/列填满即可。根据以上可以得出，如果的话，说明是填不了的，直接输出 #include <bits/stdc++.h> using namespace std; in...

2024-12-30

4 54

题解 | #小红的01子序列构造（easy）#

D 小红的01子序列构造（easy）两种写法，这里都介绍一下：方法1:双指针先考虑一个区间内的子序列如何统计，我们只需要对于每个，看它之前有几个，就是它的贡献。例如对于序列，都是，他们的贡献依次为，所以最后的子序列数为。用双指针枚举区间的左右端点，假设当前区间...

双指针前缀和二分

2024-12-24

8 68

题解 | #小红的二分图构造#

E 小红的二分图构造先思考如何把判掉。由于一条边贡献的度，所以所有点的度数和必须为偶数。接下来考虑如何构造。我们可以直接按照二分图的定义来，把原来的所有点分成两个集合，保证两个集合的度数和相等即可。那么现在问题就变成了如何分集合，注意到这是一个经典01背包，但是需要知道具体的方案...

背包动态规划

2024-12-24

1 65

题解 | #小红的01串（六）#

F 小红的01串（六）碎碎念：第一眼看题意，这不是非常经典的线段树么。然后开始写，都把 push_down 写完了，结果发现是的，要加个离散化才行。建议正在学线段树的同学都可以做做这题，如果能独立把代码调出来的话相信你的收获一定会很大。我们先思考左右的情况。我们可以开一个线段树，维...

线段树离散化

2024-12-17

4 174

题解 | #小红的01串（三）#

C 小红的01串（三）首先考虑的情况。如果，那么中也得有一个为，否则就输出如果，那么需要对分类讨论若，那么的理论最大值是，如果超出这个范围就是若，那么的理论最大值是，如果超出这个范围就是接下来考虑构造。通过刚刚判断的过程...

贪心模拟

2024-12-17

3 105

题解 | #牛客周赛 Round 72 题解#

牛客周赛 Round 72 题解不知道为啥牛客的博客会吞掉一些latex表达式，更好的阅读体验可以点击这里 A 小红的01串（一）直接遍历即可 #include <bits/stdc++.h> using namespace std; void solve() { string ...

2024-12-17

0 72

题解 | #D 气球谜题#

D 气球谜题官方题解是DP做法，我们这里使用前缀和来做。由于最后的颜色排列是的全排列之一，所以我们也是枚举全排列，然后对于每一种排列进行枚举，具体方式如下：设当前的排列的颜色为。定义前缀和数组表示将前个气球全部变成颜色所需的时间，这个递推就可以解决，具体看代码。可以将最...

前缀和

2024-12-09

4 150