D， Miku and Generals 缩点+背包 1、如果第一个人确定选择一个点，那么跟第一点有关系（有冲突）的所有的点都可以确定是第一个人还是第二个人的。 2、所以可以将每个联通块缩成一个点，这个点用两个值来表示，表示第一个人如果选了这个点，他将会得到，并且另一个人会得到。反之，第一个人得到，另一个人得到。 （在这里记录一下最小获得的 val  3、假设第一个人取了某个点最大的，那么他在这个点获得的“净val”就是他们的差值。 4、但是我们想让两个人的差值尽量小，所以我们对第一个人能得到的“净val”做一下01背包，就得到了第一个人可能得到的“净val”。 5、两个人差值尽...

补题记录 A. Remainder #include <bits/stdc++.h> using namespace std; int n, m, k; char s[200005]; int main() { scanf("%d%d%d", &n, &m, &k); scanf("%s", s); int ans = 0; for (int i = 0; i < m; i++) { if (i == k) { if (s[n - 1 - i] == '0') ans++; ...

E、希望 线段树维护区间最小值，计算出数组中小于0的元素删除所需要的代价和删除后对答案的贡献，然后做一次01背包， 就是最后可以获得的值。 #include <bits/stdc++.h> #define ll long long #define lson left,mid,k<<1 #define rson mid+1,right,k<<1|1 #define imid int mid=(left+right)/2; using namespace std; const int MAXN = 1e5 + 5; const int inf = 1e7;...

http://poj.org/problem?id=1556 几何+最短路 先算出所有的n*4+2个点和3*n个边界，然后每次从n*4+2个点中取两个点，判断一下这两个点构成的线段是否与3*n个边界相交，如果不相交，那么表示“这条路”是可以走的，就加边，否则不加边，然后跑一遍最短路。 poj输出要%f，%lf 会错。 #include <iostream> #include <stdio.h> #include <math.h> #include <vector> #include <algorithm> #includ...

求树的重心 树的重心也叫树的质心。对于一棵树n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小。换句话说，删除这个点后最大连通块（一定是树）的结点数最小。 我们假设以 1 为根节点，那么我们只能求到任意一个点的子树的大小，并不知道这个点的父节点方向的联通分量的节点个数，但我们已知这个节点的子树大小，并且所有节点数目为 n ，那么我们可以知道这个点的父节点方向的联通分量的节点个数，然后每个点的子树的最大节点数就算出来了，然后遍历一次，就得到了树的重心。 #include <iostream> #include <stdio.h> ...

D、数列求和(嘤雄难度) 1、  2、 3、考虑先求出  的所有质因数，然后通过容斥来求所有与  不互质的  的和。 4、假设当前容斥算的质数是  ，那么就有  个该质数的倍数，即要求  ，式子化简得，求和公式再化简即可在时间内算出结果。 Code： #include <bits/stdc++.h> #define ll long long using namespace std; const ll mod = 1e9 + 7; vector<ll>v; ll power(ll a, ll b) { ll res = 1; while (b) { ...

H、小阳的贝克 区间增加，区间求差的绝对值的最大值，区间gcd 1、，同理 ，所以维护一个差分数组，求区间和、最大值、最小值、gcd就可以A掉这题。 Code: #include <bits/stdc++.h> #define ll long long #define lson left,mid,k<<1 #define rson mid+1,right,k<<1|1 #define imid int mid=(left+right)/2; using namespace std; const int MAXN = 1e5 + 5; struct ...

使用k次半价，求最小花费 #include <bits/stdc++.h> #define ll long long using namespace std; const int MAXN = 10005; const ll inf = 1e18 + 7; struct edge { int to; ll w; int nex; }e[50000 * 2]; int head[MAXN], tot; int n, m, k; void add(int a, int b, ll c) { e[tot] = edge{ b,c,head[a] }; head[a] = t...

线段树区间翻转，区间找最长连续数字的长度。 1、题目要求，区间反转，区间找最长连续1长度。 2、首先想到维护以区间左端点开始的最长连续0/1长度，和从区间右端点开始的最长连续1长度，和这个区间的最长连续1长度。 3、反转操作的话，似乎需要重新来算每一个点，对于线段树来说，显然是不可以接受的，所以我们在维护1的时候，顺带维护一下0，当这个区间需要反转的话，实际上就是0变成1，1变成0，那么我们只需要将这个区间的0和1的三个值交换一下就完成了反转操作。 4、所以现在我们的线段树维护以区间左端点开始的最长连续0/1长度，和从区间右端点开始的最长连续0/1长度，和这个区间的最长连续0/1长度。...

笛卡尔树 题意，如果两个序列中所有子区间的最小值的下标都相等的话，我们就认为他们是这两个序列是相等的。 给你两个长度为  的序列，找到最大下标  使得两个序列的  区间相等。 1、首先考虑二分，那么我们如何判断这个区间是否相等？ 2、线段树 or RMQ 找区间最小值，判断一下下标是否相等，如果不相等，直接return false; 3、如果相等呢？我们考虑在一个区间中取数。     a、两个数字都在最小值的左边/右边，那么我们只需要对左区间/右区间递归。     b、两个数字一个不大于最小值，一个不小于最小值，因为最小值一定是我们之前找到的最小值，所以这种取法显然成立。 4、...

已知  ，求   在模1e9+7意义下的值。 保证  都是正整数，并且  各不相同。 ----------------------------------------- 先解里面的式子，裂项相消。  ------------------------------------ 所以原式等于 --------------------------------------- Code: #include <bits/stdc++.h> #define ll long long using namespace std; ...

求01矩阵中次大全1矩阵的面积 （） -------------------------------- 1、首先我们知道用栈可以解决直方图中的矩形最大面积问题 2、在这个题目中，如果我们将每一行看作直方图的底，自底向上的连续 1 看成高的话，整个题目就变成了 “求 n 个直方图内所有面积的次大值”。 假设原数组是 所以预处理后原数组变成了 然后遍历行，将这一行的值看成每个位置的高，然后就变成了直方图中矩形最大面积问题了。 3、但我们这里求的是次大面积，并不是最大面积，如果直接将每次的最大面积保存下来取第二大值的话似乎不太行，比如下面这组案例。 我们将这一行看成直方...

已知  ，， ，，求 的最小值 ------------------------------------------------ 1、首先将常数m从式子中提出来 2、 同时乘上一个 m  ， 3、我们知道对于平方和来说，为了使和更小，我们尽量将最大的数字最小化，才能使和最小 比如说 ，我们将3减少一，等到的平方和是 ，将6减少一，得到的平方和是 ，显然将最大数字最小化是最好的选择。 4、但由于 ，所以上一步我们只能优化 为正的项，使他们的最大值尽量小，考虑一种情况，所有大于0的  都已经减少到0了，但此时，就是说还有一部分  没有放入式子中，由于此时所有的  都是非正的了，所...

平面上给  个点的横坐标，纵坐标，a 值，b 值，要求将所有点划分为两个集合，如果在集合A中，那么这个点的值就是a，否则，这个点的值就是b，求将所有点划分之后的所有点值的和的最大值。 对于所有  和 ，都不存在。 ------------------------------------------------------- 1、首先分析限制条件，如果对于所有A中的元素，都不在B中所有元素的右下方。 2、那么平面上必然存在一条不减折线，将集合A、B分开，并且集合A中所有点在折线的左上方，集合B所有点在折线的右下方。 3、考虑对于点  来说，假设以 ，为顶点的矩形（不包括点 ）的所有点划...