A.Maximize The Beautiful Value（贪心，前缀和） 题目： 一个单调不减的序列，进行一次操作后使值最大。操作：选一个往前挪至少位。 做法： 不难发现每个有合法操作，而且多往前挪几位不会使答案更优。所以贪心枚举计算往前挪位的值，取即可。算用前缀和优化。具体看代码。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl u...

题目： 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。 做法： 可以拆分成2个区间处理。。问题变成了：统计区间中每个数的因子的最高位数码的出现次数。例如：区间。1的因子：12的因子：1、23的因子：1、34的因子：1、2、45的因子：1、56的因子：1、2、3、61作为因子出现了6次，2、3作为因子出现了2次，4、5、6作为因子出现了1次。1-9数码出现次数：6、2、2、1、1、1、0、0、0。（7-9没出现过）我们发现：我们不关注每个数有什么因...

题目： 一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。 做法： 这题处理起来比较神奇。结点要么自己染色，要么被子树内的结点染色。所以如果所有都染不到，则必选。是不是只要有能对染色，就不用考虑了？不是这样的。按题目描述，不可以先对染色再考虑，因为先对染色，再对染色可能更优！！那么对...

题目： 一棵偶数结点的树，边带权。请将结点分成n/2对点，使每对点路径求和最小。 做法： 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << using namespace std; typedef long long ll; const int N = 1e4 + 7; vector<pair<int,int> > g[N...

题目： 月月和华华一起去吃饭了。期间华华有事出去了一会儿，没有带手机。月月出于人类最单纯的好奇心，打开了华华的手机。哇，她看到了一片的QQ推荐好友，似乎华华还没有浏览过。月月顿时醋意大发，出于对好朋友的关心，为了避免华华浪费太多时间和其他网友聊天，她要删掉一些推荐好友。但是为了不让华华发现，产生猜疑，破坏了他们的友情，月月决定只删华华有可能搭讪的推荐好友。月月熟知华华搭讪的规则。华华想与某个小姐姐搭讪，当且仅当小姐姐的昵称是他的昵称的子序列。为了方便，华华和小姐姐的昵称只由小写字母构成。为了更加方便，保证小姐姐的昵称长度不会比华华的长。现在月月要快速的判断出哪些推荐好友要删掉，因为华华快回来了...

题目 Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 w_i 现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。定义删除一条边的代价为这条边的边权，现在 Rinne 想知道完成这个游戏的最小的代价，这样她就能轻松到达 rk1 了！作为回报，她会让你的排名上升一定的数量。2≤S≤N≤10^5,M=N−1，保证答案在 C++ long long 范围内。 做法 代码 #include <bits/...

题目： 有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。 在每次行程开始时，你手上有价值为 c 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 u 和 v ），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。现在你想要对每一次行程，求出会进行多少次购买事件。 做法： 下手慢了，数据更新了，暴力跑不动了。/(ㄒoㄒ)/~~...

题目： 给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位。你的任务是找出窗体在各个位置时的最大值和最小值。 做法： 单调队列的经典例题。最大值最小值分开处理。处理最大值时，从左到右遍历维护一个数值从大到小的单调队列。具体操作就是每加入一个数从队尾扫到队头发现有比它小的数则覆盖掉（相当于剪掉尾巴）。队头先pop掉不在窗口中的数值，然后在队头查询以该位置为窗口右端点的答案。复杂度O(n)最小值同理。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(...

题目 题意：在长为n的序列a[]中选2段不连续长度为k的区间使区间和最大。n ≤ 2e5 做法 代码 #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl using namespace std; typedef long long ll; const int N = 2e5 + 7; const ll INF = 1e18; int n, k, m,...

题目： 输入两个字符串A和B，合并成一个串C。问C的最长回文子串长度。合并规则：属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被合并成"axbycz"或"abxcyz"等。|A|、|B| ≤ 50 做法： 代码 #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl using namespace std; typedef long ...