这题太变态了吧。 分析 我们预处理出每个帮派的lca节点，当帮派合并的时候，我们就可以求各个帮派的lca的节点。 假设首都节点是u,各个帮派的lca是pos，分两种情况 当lca(u,pos) ！= pos的时候，说明u不在pos的子树下，答案就是dis(u,pos)。 当lca(u,pos) == pos的时候，说明u在pos的子树下，首先我们明确一点，对于帮派控制的节点，它与u的lca一定是pos的子节点，我们对每个联盟的帮派求离u最近的dfs序的节点，答案就是dis(u,lca(u,v))。 求最近的dfs序可以利用二分。 #include <bits/stdc++.h&g...

A题不会 Circle 显然按排列是最大的，答案就是。 Tree 换根。 一个节点的联通点集的数量可以通过子树和非子树求出来。 被逆元虐了，是没有逆元的，因为除以是不合法的。 PUBG 求两个值的，注意爆 「水」悠悠碧波 联想到的，以结尾的子串可以匹配到的最长前缀的长度。 我们直接求就行了，并且要小于等于max(1~n-1)的。 暴力可过

题意 一个的矩阵，每次每行取一个数，取次。 每行取数的得分 被取走的元素值 。 求得分的最大值。 分析 显然每行怎么取值都是相互独立的，不会影响其他行，所以我们只需要考虑如何取值才可以让一行的得分最大化。 很明显，我们最先只可以取第一个或者最后一个数，第二次取剩下的第一个或者最后一个数。 我们可以利用区间dp记忆化来做这题。 注意会爆 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define...

题意 给一个连通图，每次询问两点间最短路。 分析 首先我们取联通的条边，利用，处理出询问的答案。 然后我们最多还剩下条边，我们对这些边的点跑，处理出所有点到该点的距离，然后遍历所有的询问，更新答案。 时间有点紧 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> const int inf = 0x3f3f3f3f; const int maxn = 201110; const int M = 1e9+...

题意 给定和，要求一个二叉树，使得任意节点左右子树深度之差不超过，求左右子树节点差值的最大值。 分析 我们可以使左子树节点个数最多，右子树节点个数最少。 左子树显然是一颗满二叉树。 考虑如何求右子树：首先深度尽量小，为。 我们定义表示深度为的子树最少总节点个数。 则转移方程， 可以理解为左边放了一颗深度的子树，右边就得放深度的子树。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define i...

题意 有一个长度为的数组，每次询问一个区间，找一个，使得最大。 分析 我们考虑每一位，假设我们区间的长度为，有个数在这位上是，三个数是，那么的这一位选的贡献会更大，因为异或之后这一位就会有个，个。 所以我们可以根据区间的每一位的的个数来决定的这一位的取值。 具体一点就是： 多放，多放，一样多放。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long const ...

题意 珂朵莉给了你一个长度为的序列，有个子区间，求所有区间逆序对的个数和。 分析 比如说我们选择有一对逆序对，，那么以为结尾的逆序对，所产生的贡献是， 区间左边有个选择，区间右边也有个选择。 现在我们统计假设区间是，那么以为结尾的逆序对，所产生的贡献是。 所以我们可以发现就是统计前面比它大的数的下标和乘以自己后面的下标个数。 然后我们可以离散化，然后统计比我大的数不好统计，我们可以反过来，把当成，把当成 ，去统计比我小的数。 最后注意精度问题就好了，int__128_t真香。 #include <bits/stdc++.h> using namespace std; #define...

题意 有一个长度为的区间，有次操作，每次使得区间的值减去。 分析 我们每次只需要做两种操作： 询问区间最小值。 使得区间减去。 线段树模板。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long const int inf = 0x3f3f3f3f; const int maxn = 1001110; const int M = 1e9+7; int n,m...

这应该是最简单的一场周周练了吧。 最小生成树 每个点都连节点值最小的那个点，类似于的思想。 病毒感染 题目说图的类型保证没有大小大于等于3的环，那不就是告诉你是一颗树了吗。 树的重心。 Shopping 贪心，假设凳子一共有个，那么一共有个东西可以半价，一下求和。 铺地毯 题目只有一个询问，倒过来模拟一遍就好了。 金币馅饼 ，枚举列，再枚举行，只能从上中下三个方向转移。 A https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44098798 B https://ac.nowcoder.com/acm/contest...

题意 有两个属性和，每一天他可以通过努力，让涨点或涨点。 有种奖励，当大于等于，大于等于时，每天可以获得的奖励。 问天可以获得的最大奖励是多少？ 分析 首先我们将和分别离散化。 然后我们可以定义表示第天可以获得的总奖励。 表示第天当天可以获得的总奖励。 转移方程 可以通过二维前缀和求解出来。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long const ...

题意 给定一颗树，分成个点对，使得他们的距离和最小。 分析 显然不同点对之间不共用边的情况是最优的，如果有共用边，明显可以重新分配，使得距离和更小。 接下来考虑，显然如果子树大小是偶数的话，可以子树内部消化，如果是奇数，就要加上边权。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long const int inf = 0x3f3f3f3f; const int...

题意 有一个字符串，有一些匹配串，问匹配串是否是字符串的子序列。（子串是连续的，子序列是递增非连续的） 分析 显然我们可以贪心的去匹配，尽量匹配前面出现的字符。 然后我们可以定义一个数组，代表下一个字母出现的位置。 然后我们不停的跳就可以了。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> const int inf = 0x3f3f3f3f; const int maxn = 1001110; c...

题意 有一颗树，可以删去一些边，代价是边权。 现在要使得叶子节点和根节点不连通，求删边的最小代价。 分析 M=N−1，这也太坑了吧。 举个栗子 我们可以选择删去这条边，或者删去和这条边，显然选代价小的。 我们可以通过求出所需的代价。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long const int inf = 0x3f3f3f3f; const int...

题意 在一颗树上面，求节点到节点的最大值的变化次数。 分析 先看一波题解 首先我们发现一定是节点的祖先，所以我们可以利用倍增的思想（类似于求）， 首先我们先定义一个节点的父亲是在该路径上第一个大于当前节点的值的节点。 然后我们可以利用倍增的思想，求出第个购入节点。 然后就像求一样去往根节点跳就好了。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long cons...