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(sqrt(n)); } else if (n >= 0) { in...

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 (k < max(n, m...

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 << cnt << endl; } ...

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 0; }  B 宝石手串 遇到这种问题，我们先思考什么情况下...

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() { int T; cin >> T; while (T -- ) solv...

满意的数字 解法：暴力即可 #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...