D 预知 本题使用到了鸽巢原理（抽屉原理）的思想。 首先考虑 的情况，由于总卡牌数 ，故这是必败的。 当 时，看样例也能发现分为几种情况： 全是 时，说明随便翻两张都必胜，所以 只有一个 时，例如 这种情况，很多同学以为要预知 张，其实只要 张就够了，因为预知出来的两张都一样的话，说明剩下的四张就成了全 的情况，所以 其他情况， ，因为我们预知 张相同的卡牌后，就知道了剩下的所有卡牌和已经知道的卡牌都是不一样的，从这两堆里各选一张即可。 #include <bits/stdc++.h> using namespace std; const int N =...

C 小数字 当 足够大的时候， 。 当 小到一定程度时，以上大小关系才会发生一定变化。 并且当 时，我们发现只有 的操作可以让 减少。 所以我们定一个界限（比如10），然后大范围开根号，小范围判断，小于0的时候直接计算即可。 #include <bits/stdc++.h> using namespace std; void solve() { int n, m; cin >> n >> m; while(m -- ) { if (n >= 10) { n = ceil(sqr...

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

D 小红的01子序列构造（easy） 两种写法，这里都介绍一下： 方法1:双指针 先考虑一个区间内的 子序列如何统计，我们只需要对于每个 ，看它之前有几个 ，就是它的贡献。 例如对于序列 ， 都是 ，他们的贡献依次为 ，所以最后的 子序列数为 。 用双指针枚举区间的左右端点，假设当前区间是 ，区间内的 子序列为 个。 如果 则直接输出当前区间。 如果 k&preview=true"> 说明当前 子序列过多，需要把左端点往右靠。 如果把 给排出序列，说明后面的所有 的贡献都减少了 ，所以总共减少了 个（ 表示当前区间内 的个数） 如果把 给排出序列，...

E 小红的二分图构造 先思考如何把 判掉。 由于一条边贡献 的度，所以所有点的度数和必须为偶数。 接下来考虑如何构造。我们可以直接按照二分图的定义来，把原来的所有点分成两个集合，保证两个集合的度数和相等即可。 那么现在问题就变成了如何分集合，注意到这是一个经典01背包，但是需要知道具体的方案，所以需要进行转移的记录。 时间复杂度 #include <bits/stdc++.h> using namespace std; const int N = 110; const int INF = 0x3f3f3f3f; int d[N]; int dp[N][N * N]; /...

F 小红的01串（六） 碎碎念：第一眼看题意，这不是非常经典的线段树么。然后开始写，都把 push_down 写完了，结果发现 是 的，要加个离散化才行。 建议正在学线段树的同学都可以做做这题，如果能独立把代码调出来的话相信你的收获一定会很大。 我们先思考 左右的情况。我们可以开一个线段树，维护以下信息： 将当前区间修改为 开头的好串和 开头的好串的最小修改次数（分别记作 和 ） 首先考虑合并操作，我们在 push_up 的时候，当前节点的 就是左子树的 加上右子树的 或者 ，取决于左子树维护的区间长度。如果是奇数，说明 开头的好串一定是 结尾，那么右子树需要从 ...

C 小红的01串（三） 首先考虑 的情况。 如果 ，那么 中也得有一个为 ，否则就输出 如果 ，那么需要对 分类讨论 若 ，那么 的理论最大值是 ，如果超出这个范围就是 若 ，那么 的理论最大值是 ，如果超出这个范围就是 接下来考虑构造。通过刚刚判断 的过程中可以看出，我们可以先通过 这样的方式凑出 来，多出来的 或者 找某个地方一起***去即可。 如果直接写就会有一些问题：我们不知道是 开始构造还是 开始，需要写多个if，感觉很麻烦。 所以我们可以把这种操作封装成一个函数，具体看代码。 #include <bits/stdc++.h...

牛客周赛 Round 72 题解 不知道为啥牛客的博客会吞掉一些latex表达式，更好的阅读体验可以点击这里 A 小红的01串（一） 直接遍历即可 #include <bits/stdc++.h> using namespace std; void solve() { string s; cin >> s; int n = s.size(); int cnt = 0; for (int i = 1; i < n; i ++ ) { if (s[i] != s[i - 1]) cnt ++; } cout ...

D 气球谜题 官方题解是DP做法，我们这里使用前缀和来做。 由于最后的颜色排列是 的全排列之一，所以我们也是枚举全排列，然后对于每一种排列进行枚举，具体方式如下： 设当前的排列的颜色为 。 定义前缀和数组 表示将前 个气球全部变成 颜色所需的时间，这个递推就可以解决，具体看代码。 可以将最后的气球分成三块区域，其中 是颜色 ， 是颜色 ， 是颜色 。那么当前的消耗就是 看出我们需要枚举两个端点 来实现这个，但是这样的话就是 的算法。 我们考虑优化，可以只枚举其中一个端点，例如我们从右往左枚举 ，那么我们只需要在 之前找到一个位置 ，使得 最小即可。这个可以另外开一...

牛客周赛 Round 71 题解 有些东西不知道为啥牛客渲染不出来，更好的观感看这里 A 构造A+B 容易想出最多有 种构造方法，所以只要判断 和 的关系即可。 #include <bits/stdc++.h> using namespace std; int main() { int n, k; cin >> n >> k; if (k <= n - 1) { cout << "YES\n"; } else { cout << "NO\n"; } return ...

G 小苯的树上操作 容易看出是换根dp，我们可以这样定义： 表示以 为根的子树， 不去掉的最大点权和 和 分别表示在以 为根的子树中，只保留一颗子树的最大权值和次大权值(不包括 的权值) 表示以 为根， 不去掉的最大点权和 和 分别表示在以 为根时，只保留一条相连的边的最大权值和次大权值(不包括 的权值) 接下来考虑转移 我们设当前树的根是 ，遍历到 时，设 有 个孩子，其中 的第 个孩子为 在求 时，考虑从某个孩子 转移过来，可以考虑保留 节点，从 转移过来；也可以不保留 节点，直接去掉整个子树，也就是 ；还可以从 的最大子树转移过来（...

F 小苯的优雅好序列 题目需要让 数组中的每个连续子数组都是优雅的，容易看出其实我们只需要让所有长度为 的连续子数组优雅就可以了。 那么接下来思考如何根据给定的 和 求出 。 我们不妨设 ，题目需要求出满足要求的 ，即存在一个正整数 满足 即 也就是 所以我们只要枚举 的因子即可。最后的 其实就是用所有相邻两数之差 的因子求出的 的交集，所以我们先随便求一组差的解集，然后枚举所有的 ，验证即可。 由于一个数 的因子数大概是 级别的，所以最后的时间复杂度为 #include <bits/stdc++.h> using namespace std;...

牛客周赛 Round 70题解 A 小苯晨跑 #include <bits/stdc++.h> using namespace std; void solve() { int a[4]; for (int i = 0; i < 4; i ++ ) cin >> a[i]; sort(a, a + 4); if (a[0] == a[3]) { cout << "NO\n"; } else { cout << "YES\n"; } } int main() {...

满意的数字 解法：暴力即可 #include <bits/stdc++.h> #define endl '\n' #define ls u << 1 #define rs u << 1 | 1 using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL,LL> PLL; const int INF = 0x3f3f3f3f, N = 1e5 + 10; const int MOD = 1e9 + 7; const doub...