思路 考虑最简单的情况，的情况。每条边就一定是经过两次——去和回。那么遍历完，每条边就需要复制一次，所以。由于不是回路所以可以减去从起点到终点的路径。所以我们要使起点到终点的路径最长。所以问题就是找到树的直径。答案就是。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e5+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; int n,cnt,maxx=0,ans; int head[N],dis[N]; struct node { int n...

写在前面的 确实，题如其名，是一道实实在在的。在隔壁JK_Lover的指导下找到了一篇非常优秀的题解，并悟了一会儿。 思路 连边和连通性——可以通过并查集维护点的查询和加权——用vector存储每一个连通块的点连通块加权——打标记合并——启发式合并，同时要更新标记全局加——开个变量记录一下（这个操作真的拉胯，感觉一只哈士奇混入狼群）局部以及全局的最大值——开个堆记录一下，需要支持可删除存在的元素，而且还需要支持可合并 这样就可以了呢。真的是一道呢（u1s1,这个思路相对于线段树，左偏树的写法又好理解代码量又少很多只是复杂度有一点点的高）。 代码 #include<bits/stdc++....

咕了好久终于来写了 题意 给你个点的无向完全图，每个点有点权，每两个点之间的边权是点权的值。问最小生成树边权和。 思路 从别人那里学来的巧妙思路，我们考虑树，首先，我们先把样例从高位到低位插入线性基。容易发现，对于每个叶子节点，既每个点值之间，是需要互相连边，那么求他们以后的边的异或值即可。由此可得，若是的深度越深，便越优。因为我们是从高位到低位插入的，所以浅的点权值较大，要尽量避免选择浅的点。我们把可能是的点找出来，可以发现如果均不相等那么这样的点就恰好有个。如果有,我们建一条边连接，，权值为，对答案完全没有影响。我们每找到这样的点，就暴力贪心下去：每次尽量同时走左儿子或右儿子；如果两个都有...

题意 给你两个序列 ，让你求的一种排列，使得得到的序列字典序最小 思路 贪心的选择与匹配，使得最优。我们将,拆分后 , 贪心就可以方便地进行。枚举两串上,每一位上的数尽量使各位相异或后为即可选择出最合适的 。 实现 还是要用到我们的树来实现。先建立一棵基于 的二进制数的字典树,并记录各节点代表的元素出现的个数。然后传入每一个进行查找，从字典树的根部向下查找每一位，尽可能使得异或和为。若最优值在此位置个数为,选择另一值,使此位置选择的值数量,并进入下一层 , 继续进行查找。 代码 #include<bits/stdc++.h> #define ll long long const i...

题意 给你一个序列，有次操作，每次询问给你一个数，将序列所有数异或上。每次求序列中没有出现过的最小非负整数。 分析 在别人的博客里学到，如果没有异或操作。那么求题目中的只需要用权值线段树上二分就好了。每次走到线段树的某个节点时，看一下左儿子存在的数是不是等于左儿子对应的值域大小，就是看一下左儿子是不是满的。然而加上了异或就明显不能维护了。所以这个时候就又到了我们树表演了，上二分查，并且走到上某个点时，如果异或的数这一位为，意义就是交换的左右儿子，然后就可以用和线段树一样的方法做了。 代码 #include<bits/stdc++.h> #define ll long long c...

题意 给你一个序列,让你进行次操作。操作有如下两种：1.在序列末尾添加一个数。2.求以到内的任意位置为起始，以为结尾，是的这个子序列异或和最大。 分析 可以看出这是一个可持久化Tire树，首先利用前缀和转化问题，将查询操作转化为求。如果查询没有区间限制，那么就是一个Tire树就可以。但有了区间限制就无法直接用Tire树求解。考虑用可持久化，每次询问区间时即为相当于用第个版本的树-第个版本的树得到区间的树。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e8+5,INF=0x3f3f3f3f,mod=9982...

题意 给你一个序列，让你找出一个连续子序列使得其异或和最大。若方案不唯一，输出右端点最左的方案，若还不唯一，输出最短的方案。 思路 同一个值异或两遍就是，所以用前缀记录从到的异或和，到异或和就是。所以答案就转化成了，求和的异或和最大。 做法 用字典树来实现记录和查找就好了。记得以此按照题目要求比较。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e7+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; int n; int ans=-1<<...

题意 你有个数，要求你选择其中的两个数使得他们的异或值最大。 分析 由于位运算都是按位进行，也就是说在二进制下的位运算每一位之间是独立的。我们还知道二进制下位数越高，对应的值也就越高。（也就是）。也就是我们就是要让两个数在二进制下从高位到低位尽可能的不同。那我们考虑建一棵字典树，对每一个数字进行一次插入和查询的操作，尽可能的使得每一次查询的时候,我们都选择与当前位相反的走,也就是让异或值最大,如果说没有路可以走的话,那么就走相同的路。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e7+5,INF=0x3f...

题意 你有次机会，可以选择是否对原数与进行与、或、异或三种操作之一（已指定），求最后的最大值是多少？ 分析 因为位运算每一位之间是独立的，所以我们可以贪心的选择。我们知道在二进制下数位越高代表的值越大，所以我们只需要从高位到低位贪心的是其尽可能的为。 做法 我用和两个变量表示二进制每一位全为和全为经过门之后的结果。贪心时，就能用换就一定换，能用换也换。对于，如果第位变成了，那么就得看原数的第位，如果是且它还在范围内，对最后的答案贡献为。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e5+5,INF=0x3...

题意 你有一棵有个节点树，其中有个已告知的标记点，求个点中，有多少个点到这个标记点的最大距离不大于。 分析 。所以我们可以处理一下，跑两次，分别把子树内和子树外两种情况处理出来，最后统计答案时，两者同时满足就可以纳入。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e5+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; int n,m,d,cnt,py,ans,u,v; int head[N],dis[N][2],gw[N]; struct node...

题意 今天的题意很难简化诶，就提醒一下吧，就算没有管道（障碍物），也是有上下界的哦。 分析 我们令表示为在第列，第行所需要的最小点击次数。那如果是上升，状态转移方程就类似完全背包转移方式；如果是下降状态转移方程就类似背包转移方式。飞行过程中如果高度超过了那就需要特判来降为。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e3+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; int n,m,k; int f[N][N]; bool e[N]; str...

题意 给你一棵树，你需要找到它的一颗子树满足以下条件1.是一棵二叉树2.这棵树的所有节点的左右儿子交换位置，交换后新树和原树的结构及每个位置的点权没变。 分析 先预处理出每棵子树的大小，然后枚举以任意节点为子树的根。递归处理这棵树的正确性。当这个节点没有儿子直接返回。当有两个儿子且两个儿子的权相同时，递归这两个儿子的儿子就可以了。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e6+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; int n; in...

题意 给你一个数，要求你将这个数拆成个每一位为或的数，如等。求的最小值，以及任意一种方案 分析 首先对于第一问，对于每个数位分析，你每次最多每个数位只能加，所以我们只需要找到数位里最大的那个数，那就是的最小值。对于任意一种方案，我们只需要每次求数位时，就需要当前位置数字个，用数组记录一下就好。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e5+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; int n,res,ans; int num[N]; ...

做法 SPFA+DP 思路 贪心显然不可取，考虑用动归。令表示第天的最小花费，最后输出的答案显然就是。DP方程的转移显然：哦，对了数组存的是第天到第天都走同一条最短路的花费。对于数组的初始化，很简单，对于每一个，先把到天之间封闭的码头全部设为不可走，跑一遍最短路即可，初值为无穷。 代码 #include<bits/stdc++.h> #define ll long long const ll N=1e2+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; ll n,m,k,ee,cnt,d; ll head[N],dis[N]...