• .Title|raw

    SWERC 2019-20 Problem G. Swapping Places 拓扑排序


    题目大意有s种动物排成一个长度为n的队伍,有l种朋友关系a b,动物a和动物b为朋友可以互相交换位置,但是当且仅当这两种动物在相邻位置时。 问在所有的可能交换位置的方案后,序列最小的字典序排列是什么。 题解挺难想的一个题,看题解只有一句话,看代码看了好久才想明白。 通过动物之间的朋友关系,我们可以确定可以互相交换的有哪些位置,也可以确定哪些动物的相对位置是不能发生改变的。 于是我们可以利用不是朋友的动物之间的相对位置不能发生改变这一点,来进行拓扑排序(当然是字典序更小的动物为更优先序的) 首先给所有物种的名字排序保证是字典序,然后用二维数组E:0 表示两个物种可以交换(是朋友),1表示不能交换

  • .Title|raw

    SWERC 2019-2020 Problem A Environment-Friendly Travel DP+bfs


      题目大意给定起点和终点以及一些中继点的坐标,距离如题目描述中所示,有0-T这些道路,每种道路上每公里排放CO2数量不同,为ci L / km。 你的车最多能跑B(B≤100)公里,每个中继点连接着另外一些中继点,且连通的道路种类有规定。起点和终点到其它中继点的道路全为种类0. 问能不能从起点到达终点,如果不能输出-1,否则输出最少排放的CO2数。 题解首先不管别的,先把道路建起来,所有中继点的关系已经给出,而起点和终点需要额外建立两个点,并且设定连向所有的点。 本来看起来是像是个最短路,但是因为有规定最大的里程数,所以普通的最短路算法并不能适用。 但是注意到最大里程数B较小,所以

  • .Title|raw

    CodeForces 1303G. Sum of Prefix Sums 点分治+李超线段树


    题目大意定义一种叫做前缀数组和的东西sum_i为某个数组的前缀和数组的前i项之和。 现在给定一个树,树上每个节点有权值,树上一条有向路径的权值定义为从起点u到终点v上的所有数字组成的前缀数组和。 求问这种路径权值的最大值是多少。 题解此题解为搬运CodeForces官方题解,为其中文翻译版本。(严正声明,可能中间会加一些个人的理解,代码的话个人的代码感觉还不如官方的好看所以就放官方的题解代码了) 首先确认这是一个树上路径问题,针对树上路径问题,一般可用的方法就是树分治和树链剖分。 考虑到这道题的路径权值的定义,我们并不能用树链剖分的传统的LCA和线段树的方法来进行计算,我们大概需要用搜索算法才

  • .Title|raw

    CodeForces 1313.C2 Skyscrapers(hard version) nlogn线段树做法


     题目大意给定一个序列a,要求你每个元素都选出不超过ai的值,使得选出的元素序列满足不严格上凸(上凸、非严格单调皆可),且总和最大,求问每个位置上选出的元素是多少。 题解此题有一个暴力的easy version版本,只需要枚举每个位置为最大值点位置pos(也就是该点处选择的元素大小为apos)暴力计算即可。 但是当数据量变大到5*105数量级时,我们没有办法枚举位置暴力计算。 但是可以注意到,枚举每个位置为最大值点位置pos这一步仍然是不可避免地,这是解题的核心,于是很容易想到,我们需要在较短时间内算出当每个位置为最大值点位置时,所选出的最优序列的元素大小总和。我们不能用暴力的版本每

  • .Title|raw

    CodeForces 1303F. Number of Components 并查集


    题目大意一开始有一个所有数全都为0的n*m的矩阵。 一共有q次操作,每次操作读入x,y,c,将坐标为(x,y)处的值改为c。 问每一次操作后连通块的个数是多少。 如果两个相邻的格子数字相同,我们认为这两个格子属于同一个连通块。 询问中的c的值保证单调不减。 题解询问连通块个数的题目一般来说肯定需要用并查集。 但是有一个问题是普通的并查集并不支持删除操作。 因为改变值,实际上相当于是先删除一个值再添加另一个值。所以必定会涉及到删除操作。 此题也不能用可持久化并查集,因为操作并不是“回溯”,而是单纯的删除。 并查集询问连通块个数的时候一般都是静态询问,但是这个题明显是一个动态维护,难度更高。 首先

icontofig | 发布于 2020-03-08 21:56:31 | 阅读量 592 | topsort
发布于 2020-03-08 21:56:31 | topsort

题目大意

有s种动物排成一个长度为n的队伍,有l种朋友关系a b,动物a和动物b为朋友可以互相交换位置,但是当且仅当这两种动物在相邻位置时。

问在所有的可能交换位置的方案后,序列最小的字典序排列是什么。

题解

挺难想的一个题,看题解只有一句话,看代码看了好久才想明白。

通过动物之间的朋友关系,我们可以确定可以互相交换的有哪些位置,也可以确定哪些动物的相对位置是不能发生改变的。

于是我们可以利用不是朋友的动物之间的相对位置不能发生改变这一点,来进行拓扑排序(当然是字典序更小的动物为更优先序的)

首先给所有物种的名字排序保证是字典序,然后用二维数组E:0 表示两个物种可以交换(是朋友),1表示不能交换(不是朋友)、二维数组Fij:0表示物种i的当前最前位置的一个在物种j当前最前位置的前面,1则相反。

然后枚举每个位置放哪个物种,如果当前物种i满足有一个j使得Eij & Fij = 1,那么就说明这个物种当前最前面的个体之前有不能与其交换的个体,就不能在当前这个位置放这个物种的这个个体,就需要放其它物种。如果满足没有这样的j,那么这个位置就放物种i了(这时字典序一定最小),然后更新一下Fij(因为是Fij表示的是两物种当前未被放入序列种的最靠前的个题之间的位置关系),继续枚举下一位置放什么就可以了。

E和F由于只需要&操作,所以可以用bitset来进行加速。

代码

#include <bits/stdc++.h>
using namespace std;
int s,l,n;
const int maxn = 205;
vector<int>pos[maxn];
string a,b;
vector<string>name;
int id(string str){
   return lower_bound(name.begin(),name.end(),str) - name.begin(); 
}
bitset<maxn>e[maxn],f[maxn];
vector<int>ans;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s >> l >> n;
    name.reserve(s);
    for(int i = 0;i < s;++i){
        cin >> a;
继续阅读
icontofig | 发布于 2020-03-08 16:52:08 | 阅读量 540 | DP
发布于 2020-03-08 16:52:08 | DP

 

题目大意

给定起点和终点以及一些中继点的坐标,距离如题目描述中所示,有0-T这些道路,每种道路上每公里排放CO2数量不同,为ci L / km。

你的车最多能跑B(B≤100)公里,每个中继点连接着另外一些中继点,且连通的道路种类有规定。起点和终点到其它中继点的道路全为种类0.

问能不能从起点到达终点,如果不能输出-1,否则输出最少排放的CO2数。

题解

首先不管别的,先把道路建起来,所有中继点的关系已经给出,而起点和终点需要额外建立两个点,并且设定连向所有的点。

本来看起来是像是个最短路,但是因为有规定最大的里程数,所以普通的最短路算法并不能适用。

但是注意到最大里程数B较小,所以我们可以考虑到某个点在跑了x公里的情况下最小的排放CO2的量是多少,然后通过类似于最短路的BFS对这个维护量进行转移。

即,假设dp[i][j]表示跑到节点i,且已经跑了j公里,所排放的最小CO2的量。

剩下的就是通过类似spfa的bfs进行转移,注意判断边界即可。

 代码

#include <bits/stdc++.h>
using namespace std;
int xs,ys,xt,yt;
const int maxn = 1005;
int T,B,n;
const int INF = 1e9+7;
const int maxe = 1e6+5;
int dp[maxn][105];
int c[105];
struct point{
    int x,y;
}p[maxn];
typedef pair<int,int>PI;
vector<PI>g[maxn];
int dis(int a,int b){
    double x = sqrt(double((p[a].x - p[b].x)*(p[a].x - p[b].x) + (p[a].y - p[b].y) * (p[a].y - p[b].y)));
    return (int)ceil(x);
}
struct node{
    int id,dis,cos,pre;
};
struct edge{
    int to,next,dis,cos;
}e[maxe<<1];
int h[maxn];
int cnt = 0;
void add(int u,int v,int d,int c){
    e[cnt].to 
继续阅读
icontofig | 发布于 2020-03-04 13:04:20 | 阅读量 456 | 点分治 线段树
发布于 2020-03-04 13:04:20 | 点分治 线段树

题目大意

定义一种叫做前缀数组和的东西sum_i为某个数组的前缀和数组的前i项之和。

现在给定一个树,树上每个节点有权值,树上一条有向路径的权值定义为从起点u到终点v上的所有数字组成的前缀数组和。

求问这种路径权值的最大值是多少。

题解

此题解为搬运CodeForces官方题解,为其中文翻译版本。(严正声明,可能中间会加一些个人的理解,代码的话个人的代码感觉还不如官方的好看所以就放官方的题解代码了)

首先确认这是一个树上路径问题,针对树上路径问题,一般可用的方法就是树分治和树链剖分。

考虑到这道题的路径权值的定义,我们并不能用树链剖分的传统的LCA和线段树的方法来进行计算,我们大概需要用搜索算法才能确定一个路径的权值和长度。

但是问题是,路径总数实在太多了,我们是不可能把所有路径都找出来算一遍的。所以我们考虑采用点分治,看看如何去减少对路径的统计。

考虑使用树分治,这里使用点分治更为方便(当然我也不会边分治),因为下面的思路是依靠点分治经过树的重心的路径这一思路展开的。

我们考虑一个树,经过重心的一个路径u->rt->v,我们分成u->rt和rt前往v的路径的下面一个点x->v两条路径来看。

假设路径u->rt的路径权值为为presum、路径上所有点的值的和为precnt,路径x->v的路径的路径权值为precalc、长度为prelen。

那么u->v的路径的路径权值为:

sum = precnt*prelen + presum + precalc

这是一个一次函数的形式,可以看作是一个直线在某点处的取值问题。

具体而言可以看作一条斜率为prelen,参数为precalc的直线在x = precnt处的取值(最后再加上一个presum)

那么对于前半部分路径对后半部分路径进行组合结果计算的问题就转化成了求后半部分的路径代表的多个直线在某点处的取值的最大值问题(最高点)。

但是用什么来计算呢?暴力肯定行不通的。

这里介绍李超线段树。李超线段树的用途是,维护区间内最高的线段。其思想是线段树的每个节点保存在当前区间中心点mid处最高的线段。每当加入一条线段时,先检测当前区间中心点mid处这条线段的高度与原来的线段相比,然后更低的线段向其左/右孩子更新。李超线段树可以查询在某点处最高的高度为多少。具体实现可以看代码。

于是我们通过点分治和李超线段树可以成功地把此题的复杂度降低到O(nlog2n),并且成功计算出

继续阅读
icontofig | 发布于 2020-02-24 15:52:01 | 阅读量 421 | 线段树
发布于 2020-02-24 15:52:01 | 线段树

 题目大意

给定一个序列a,要求你每个元素都选出不超过ai的值,使得选出的元素序列满足不严格上凸(上凸、非严格单调皆可),且总和最大,求问每个位置上选出的元素是多少。

题解

此题有一个暴力的easy version版本,只需要枚举每个位置为最大值点位置pos(也就是该点处选择的元素大小为apos)暴力计算即可。

但是当数据量变大到5*105数量级时,我们没有办法枚举位置暴力计算。

但是可以注意到,枚举每个位置为最大值点位置pos这一步仍然是不可避免地,这是解题的核心,于是很容易想到,我们需要在较短时间内算出当每个位置为最大值点位置时,所选出的最优序列的元素大小总和。我们不能用暴力的版本每一次枚举都用O(n)的时间复杂度来算。

我们考虑用一种类似于前缀和和后缀和的形式来计算上述提到的我们需要计算的。前缀和和后缀和相加减去此位置本身所得的值,即在当前位置为最大值点位置时,所选出的最优序列的元素总和的大小。最优前缀和与最优后缀和的计算模式大致相同,直接来看最优前缀和pre的计算方法吧。

假设当前枚举到的位置为pos(pos>1),考虑两种情况:

1.apos>=apos-1,这时选取当前位置为最大值点时,不会对pos-1为最大值点时的最优前缀和的值产生影响,直接转移:pre[pos] = pre[pos-1];

2.apos<apos-1,这时选取当前位置为最大值点时,就不能用pos-1为最大值点时的最优前缀和的值来进行转移,因为这时pos-1位置不能选取其最大值了。这时候需要考虑我们不会对哪个位置之前的选值有影响,很明显是pos位置前第一个小于等于apos的元素所在的位置。

最优后缀和也类似考虑。

在第一种情况下,我们无需考虑什么东西,可以直接转移。重点在第二种情况,如何寻找pos之前第一个小于等于apos的元素所在的位置,这个操作的复杂度会影响到我们整体的算法复杂度。

据说有可以把这个操作整体复杂度做到O(1)的做法,但是这里并没有想到,于是选择nlogn的线段树做法。

首先对数组离散化,对离散化后的权值建一棵线段树,线段树节点上的值为其子树中元素的最大值,元素表示的是当前节点代表的区间的各个离散化后的值中出现的最晚的位置(最大)是哪个位置。

从开始向后逐个计算。

如果在第一种情况,直接转移,并将当前的位置pos更新到到线段树对应着当前位置元素的离散化后的值的权值叶节点。

如果在第二种情况,假设当前

继续阅读
icontofig | 发布于 2020-02-22 21:22:30 | 阅读量 436 | 并查集
发布于 2020-02-22 21:22:30 | 并查集

题目大意

一开始有一个所有数全都为0的n*m的矩阵。

一共有q次操作,每次操作读入x,y,c,将坐标为(x,y)处的值改为c。

问每一次操作后连通块的个数是多少。

如果两个相邻的格子数字相同,我们认为这两个格子属于同一个连通块。

询问中的c的值保证单调不减。

题解

询问连通块个数的题目一般来说肯定需要用并查集。

但是有一个问题是普通的并查集并不支持删除操作。

因为改变值,实际上相当于是先删除一个值再添加另一个值。所以必定会涉及到删除操作。

此题也不能用可持久化并查集,因为操作并不是“回溯”,而是单纯的删除。

并查集询问连通块个数的时候一般都是静态询问,但是这个题明显是一个动态维护,难度更高。

首先解决动态维护的问题吧。

我们可以去整一个add数组,里面记录当前操作后连通块个数相较于之前发生了什么样的变化。

后面就是如何计算这个add数组的问题了,先考虑删除问题。

删除是并查集无法完成的操作,但是添加可以,我们可以把删除看作是反向添加,用一个反向添加的并查集来表示删除的元素构成的连通块个数,用对应时间点的添加的连通块个数减去删除的连通块个数即为这个时间点操作后的答案。

具体在实施的时候,不能单纯对矩阵的方格建立并查集。我们需要对于不同的数字情况下分别对方格建立并查集,这样来操作,否则删除的时候会出现问题。

当添加一个元素的时候,扫描其周围四个点与其颜色相同的点的个数num,并查集个数改变量为1-num。

此题思路看代码可能会更加清晰,因为确实跟平常的并查集题目并不相像。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
const int maxc = 2e6+5;
int n,m,q;
int f[maxn*maxn];
int find(int x){
    if(f[x] != x)f[x] = find(f[x]);
    return f[x];
}
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
typedef pair<int,int> PI;
vector<PI>add[maxc],del[maxc];
int a[maxn][maxn],dif[maxc];
void calc(const vector<PI> &p,int flag){
    
继续阅读
icontofig | 发布于 2020-02-19 22:10:38 | 阅读量 504 | 字符串 可持久化线段树 可持久化数据结构 Trie

Input

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5

Output

7
5
6
3
6

题目大意

给出n个字符串,q次询问,每次询问l,r,k,求问

字符串l——r中,包含字符串k(字符串k作为子串)的字符串个数是多少。

题解

多模式串匹配肯定是AC自动机

但是这个问题是多个串中有多少能匹配到当前询问的这一个字串的问题,而不是经典的某个串能匹配多少个已经给出的串的问题。

AC自动机的Trie树中,某个节点的所有祖先节点表示一个或几个字符串在当前这个位置之前的字符串前缀。所以对于某个结束节点来说,他的所有祖先节点加上他本身构成了一个字符串。

而对于AC自动机建立的fail树来说,一个节点的fail指针指向的节点以及其trie树上的祖先一定构成了当前节点到trie树的根节点所表示的字符串的一个后缀。如果其fail指针指向的是一个结束节点,那么这个串就一定能匹配它的fail指针指向节点在trie树所代表的一个字符串,也就是完成了一个子串匹配。

于是我们可以借助这一点性质,来求解能匹配ac自动机中第k个字符串的字符串个数,方法是:

沿着当指向当前节点的fail路径的反方向走,每走到一个节点ans+1,最终无路可走时,得到的就是答案。(包括这个字符串本身)。、

但是这个题还有在区间[l,r]的字符串的限制。

考虑到普通的线段树没法做到这种询问,所以我们应该想到这个题可以用可持久化线段树来做。

可持久化线段树最大的特点就是每棵线段树的根节点都代表着一次更新的时间戳,我们可以利用这个时间戳去求区间的一个值。

但是这是一个AC自动机上的问题,准确的来说是fail树上的问题,如何建线段树?

对于树上问题,可以先想树链剖分,其本质就是求DFS序,所以我们也可以对fail树构建DFS序,然后在此基础依次添加每个串,构建可持久化线段树。

根据上面的fail树上的性质来说,通过fail路径的反方向路径构成的fail树,某个节点的子节点都是原先的fail指针指向当前节点的节点,也是我们要统计路径时走向的节点。

某个节点的子树,代表了能匹配到以此节点到trie树根节点构成的字符串的后缀的所有字符串所在的fail树的位置。

我们根据fail路径来构建DFS序,在此基础上建立可持久化线段树。在建立可持久化线段树的过程中,每添加一个字符串,都要对这个字符串在AC自动机Trie树上

继续阅读
icontofig | 发布于 2020-02-12 22:36:15 | 阅读量 289 | 字符串
发布于 2020-02-12 22:36:15 | 字符串

题目大意

维护一个集合支持:

1.1. 添加一个模式串。

2.2. 删除一个串。

3.3. 给出一个串,询问有多少个子串在集合中出现过,多次出现多次计算。

题目要求使用fflush(stdout)方法强制在线。

题解

更新了AC自动机内存池回收写法的模板。

多模式串匹配算法,明显的AC自动机的题目。

但是众所周知,AC自动机不支持动态的插入操作以及删除操作(Trie树是支持动态插入的,但是AC自动机里面的fail指针是不支持的,插入字符串只能重新暴力重构fail指针)。

于是考虑建立多个AC自动机,但是很遗憾的是,如果每一次添加or删除操作我们都去建立一个AC自动机,那么查询的时候时间复杂度会炸掉,但是多个AC自动机的做法又不可避免。

所以我们就要想如何优化。

首先将插入和删除分开建AC自动机组是没有任何异议的。最终答案就是在插入的AC自动机组中的答案减去在删除的AC自动机组中的答案。

根据二进制加法(二进制堆的启发式合并)的启发,我们对属于同一种操作的AC自动机进行二进制分组。

我们在动态维护该种操作的时候,将新来的模式串新建一个AC自动机,并设置其数量为1,表示该AC自动机中带有的模式串的数量。

当当前的AC自动机中的模式串数量和前一个AC自动机中模式串数量相等的时候,我们就将两个AC自动机暴力合并。

能证明这样每个字符串最多被加入AC自动机并重构fail的次数在log2n次。

每次查询的时候,只需要将某种操作的AC自动机组中的全体AC自动机全部扫一遍就行了。

注意合并的时候回收空间。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
typedef long long ll;
int st[maxn<<1];
int cnt;
struct trie_node{
    int next[26],fail,end,sum,ac[26];
}tr[maxn<<1];
struct AC_auto{
    int root;
    inline int newnode(){
        int p = st[cnt];
        for(in
继续阅读
icontofig | 发布于 2020-02-11 17:05:57 | 阅读量 318 | Trie
发布于 2020-02-11 17:05:57 | Trie

题目大意

有n个节点的有根树,根为1,每条边有权值,点对(u,v)的路径长度为从u到v路径上所有权值的异或值,认为点对(u,v)与(v,u)表示两个路径,总共有n2个点对路径(自己到自己也算一个),求问其中路径长度第k小的路径长为多少。

题解

n的范围是很大的,不可能通过枚举计算。

两点(u,v)之间的路径长度,可以通过lca转化为:

(u,lca) xor (v,lca) = (u,lca) xor (lca,root) xor(lca,root) xor (v,lca) = (u,root) xor (v,root);

所以可以将每个点到根节点的路径异或长度预处理出来,之后再进行下面的操作。

建立一个01Trie,我们可以有办法求得路径异或长度不超过某个值val的路径数目。

对于当前位bit,我们去检查小于之前已经决定的答案ans加1<<bit的值的个数。也即当前的二进制位上的数为0的个数。

如果这个个数size小于k,说明答案应该是大于等于ans + (1<<bit)的,于是就决定当前的二进制位为1,k -= size,进入当前层表示为1的子树内再向下搜寻。

否则就直接进入当前层表示为0的子树内再向下搜寻。

整个搜寻答案的过程是O(62·n)的。加二分实际上是没意义的。

最后的一个问题就是,空间明显不允许我们开这样一个完整的Trie,所以需要动态建立每一层的Trie节点,用到什么建什么,不用的不管,搜寻下一层的时候要将上一层的节点表示清空。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll k;
int id;
const int maxn = 1e6+5;
ll v[maxn];
int pre[maxn];
int tot = 0;
ll siz[maxn];
int son[maxn][2];
int a[maxn],b[maxn];
void init(){
    for(int i = 1;i <= n;++i)
        son[i][0] = son[i][1] = 0,siz[i] = 0;
    tot = 0;
}
int new_tag(int now,int ch){
    if(!son[now][ch])
        son[now]
继续阅读
icontofig | 发布于 2020-02-10 23:17:59 | 阅读量 224 | 二分 可持久化线段树 可持久化数据结构
发布于 2020-02-10 23:17:59 | 二分 可持久化线段树 可持久化数据结构

Input

5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5

Output

2
3
1

题目大意

给出一个序列,有m组询问。

每一组询问有三个参数l,r,w,问区间[l,r]中所有由连续w个元素组成的子序列中的最小值中的最大值是多少。

题解

看到题目里面的最小值最大,肯定能意识到应该是用二分+check去验证元素的(因为其他能想到的方法基本都是暴力,复杂度太高,这题数据范围在105级别没法用的)。

然后问题就在于这个check如何去操作。

如果我们当前二分一个值mid,怎么检查区间l-r中是否所有的连续的w个元素中的最小值中的最大值是mid呢?

这个没法做到,我们只能去确定,是否存在连续w的区间的数全部大于等于mid。

我们假设当前二分到的值为mid,大于等于mid的数都设为1,小于mid的数都设为0,那么问题就变成了询问区间内[l,r]上最长的连续为1的子序列长度len是否大于w的问题。

但是我们注意到一些问题,序列中的数比较大,直接二分的话常数会大些,而且也没有办法对每次二分的mid建一棵线段树去check,时间上会炸掉。

这种情况下我们可以考虑将序列中的值从大到小排序,保留其原先所在的位置下标,对排完序之后的值,我们可以直接用序列进行二分。

而在排完序的情况下,可以注意到,以当前位置的值为check的值时,其构建的线段树就是上一个位置对应的check所用的线段树上在当前位置的值在原序列中的下标对应的位置插入1。

这个修改只有一次,因此可以建立可持久化线段树进行check。

当前二分的位置为mid时,对root[mid]对应的线段树进行check,检索是否可行就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n,q;
struct height{
    int h;
    int id;
}a[maxn];
int rt[maxn];
int u,v;
const int INF = 1e9+7;
struct tree{
    int l,r;
    int lc,rc;
    int suml,sumr,sum,len;
}tr[maxn*25];
int cnt = 0;
void push_up(int now){
    tr[now].len = t
继续阅读
icontofig | 发布于 2020-02-06 20:52:24 | 阅读量 311 | 最小生成树 Trie
发布于 2020-02-06 20:52:24 | 最小生成树 Trie

题解

每条边的权值都是根据每个点的定值通过二进制异或得出的。

如果有两个点的数二进制高k位相等,那么我们如果要想要把这两个点的边加入最小生成树,那么花费的代价是与高k位无关的。

假设在第k+1位发生分歧,则这条边的最小权值即为这一位对应的二进制值。然后要做的就是继续向更低位检查。

这明显是个递归过程,而且很容易能想到这个过程是与01Trie的节点访问实际上是一样的。

于是所有的答案统计全部都在01trie上。

接下来看kruskal算法的核心:每一次将最小边权的边试图加入最小生成森林。

所以我们必然优先去找01Trie中同一个叶子节点上的点对的边。

假如一个叶节点上有k个点(k > 2),那么对应的建边方案就是kk-2种。

当从叶节点向上走的时候,假设某节点的父亲节点的两个子树上都有点存在(即两个子树都非空),那么我们肯定要用边把这两个子树连起来,连起来的时候就需要顺着trie往下找异或值最小的边的权值是多少。

细节不是很好解释,不过这种思路是二进制异或时一种常见的贪心思路,可以看代码理解一下。

这个题不需要并查集,因为当刚向上走到某个点时,如果其两个子树都非空,那么这两个子树代表的两个已经构建好的生成树必然属于两个不同的连通块。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PI;
const int maxn = 1e5+5;
const int INF = 2e9;
const ll MOD = 1e9+7;
int n, sz, fac[35], rt;
ll ans,sum;
struct tree{
    int l, r, cnt;
} tr[maxn*30];
ll quick_pow(ll x, ll y){
    ll ans = 1;
    while (y){
        if (y & 1)
            ans = ans * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ans;
}
void insert(int &d, int dep, int v){
    if (!d)
        d = ++sz;
继续阅读