分析 出现了最大值最小这类关键字，一般要考虑二分答案。但首先我们必须考虑答案是否具有单调性。先钦定一个答案 。那么 。如果我们把绝对值符号拆开，这是由两个一次函数构成的，那么对于 。仍满足上式。所以这个是满足单调性的。考虑二分答案，只有两个限制需要考虑。 和 。当没法同时满足两个条件时，返回 。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 5000010; LL n,Sa,Sb,Sc,Sd,mod; LL A[N],B[N],F[N]; LL f(L...

分析 对于 我们非常不好处理，可以考虑 分治。先按 由小到大排序。那么所有右侧的 一定大于左侧。在处理某一层时，再按 排序。这样处理答案就非常方便了。维护一个前缀和和一个后缀和。两个指针移一下。使用快排的时间复杂度为 ，可以在分治过程中归并排序从此复杂度为 。 代码 #include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define LL long long const int inf = 0x3f3f3f3f; int read(){ ...

分析 如果枚举左右端点复杂度的下界为 。那么只能枚举一个端点，那么对于另一个端点，我们只关心这两个端点中间有没有最低消费不大于 的。如果我们从左向右扫描，我们一定希望这个点越靠右越好，因为这可以影响更多的点对。对于每一个颜色记录上一个同颜色在哪里。那么只需要最小值点出现在 的右边，那么就可以更新答案，否则只能继承上一个节点的答案。时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 2e5+100; int c[N],val[N],cnt[N],...

题意 有一个 个结点的树，每条边有边权，结点度数就是与之相连的边数量。对于 ，删掉一些边使每个结点的度数不大于 ，求出删掉的边的权值和最小值。 分析 简化问题 求解 时的问题。考虑 ，定义 为，结点 为根子树满足 ，且与父亲的边是否断掉的最小代价。那么对于一个度数大于 的节点，如果不断父亲的边，我们就要选择 个儿子断掉，如果断父亲的边则选择 个儿子。那么贪心的考虑哪些儿子是最优的。我们 的儿子的值放在一个平衡树中，对于小于 的，直接加 。然后贪心选取前几个就好了。时间复杂度为 。 原问题 考虑由小到大枚举 。如果一个节点的度数已经小于或者等于 ，那么这个节点...

题意 给你一个字符串的生成方式，求问 和 的最长公共子序列。 第一步时字符串仅包含单个字符 在第 步中，我们将第 步中得到的字符串复制两次，并在这两个串中间插入字母表中的第 个字符。分析 无论任何时候这个串都是一个回文串，且第 步时，回文中心是 。那么可以递归构造这两个字符串。那么讨论这个串左右端点和回文中心的位置关系递归下去。注意边界问题。时间复杂度为 。代码 #include<bits/stdc++.h> using namespace std; int solve(int l1,int r1,int l2,int r2,int S){ if(r1 ...