前置芝士：  欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次  思路：  因为求欧拉路的最短长度，且可以把任意边复制任意多次（其实就是每一条边可以走多次） 由贪心的思想就是尽可能重复走短边，长边只走一次 可以任意造几个数据可得重复走的边最多走两次 所以可以得出每条边的长度*2-树得直径就是所求答案 树的直径我用的是二次dfs的思想（树形dp也可，还有二次bfs）（二次bfs不知道这题能不能过）  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #defi...

做法：可持久化01tire 思路： 令s[i] = a[1] ^ a[2] ^ … a[i-1] ^ a[i]则a[p] xor a[p+1] xor … xor a[N] xor x 相当于 s[N] ^ x ^ s[p-1]s[N] ^ x 每次可以看成一个固定值 v提前算出来, 则相当于 求 l-1 <= p-1 <= r-1 使得 v 与 s[p-1]异或最大 s[p-1]的二进制最高位开始到最低位的每一个数字尽量与v的二进制对应位相反就可以保证异或出来最大。s的每个版本可以看成是持久化的trie记录下来。对持久化trie的每个节点额外维护一个信息max_id，表示其所属的...

做法：Borůvka+01字典树  关于MST中的Borůvka算法详见https://www.luogu.com.cn/blog/Tweetuzki/solution-p3366  思路：  dfs走法：有左儿子就走左儿子，有右儿子就走右儿子，同时存在则合并取min后加上深度的值  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) ...

做法：01字典树+贪心 题意： 有长度为n的两个a,b数组，改变b中元素的顺序,使数组c (c[i]=a[i]^b[i])的字典序最小，并输出数组c 思路：  这题思路和前两题很相似，唯一不同点是求最小而已 每次a[i]上异或上一个b数组中任意元素（不能重复使用），使得c[i]最小即可 记录每个节点经过多少次，每一次插入的时候将出现次数的标记加1，每一次查询的时候将经过的点的标记减1，如果这点标志为0，那么这条路就不能走。  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define m...

做法：01字典树 题意： mex 是一个序列中没有出现过的最小非负整数。 给出你一个长度为 的非负整数序列以及 个询问，每次询问先给你一个整数 ，然后：  把序列中所有数异或上 输出序列的 mex  注意，在每个询问过后序列是发生变化的。 思路：  1.先插入原数组中每一个数（重复的不需要再插入） 2.每次更新数组比较麻烦，所以可以等价与把每次异或的值异或起来，查找异或起来的值 3.对于异或出来的值，在01trie上贪心的找，如果能找到和他当前位相等的值时，判断一下他的子树中的数字是否满足前面所有的数都在  代码 #include <bits/stdc++.h> using nam...

做法：01字典树 思路：  这一题和The XOR Largest Pair思路很像，唯一不同的是这题求的是一段连续区间的最大值，并且还要维护区间的左端点和右端点.所以我们只需存每个连续区间的右端点.并且上个区间的右端点+1即为所求区间的左端点.  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b)...

前言：暑假集训时学的字典树orz 太弱了www模板用的是wiki上用一个结构体封装的模板（当时就是看wiki学的字典树链接：https://oi-wiki.org/string/trie/  做法：01字典树 思路：  一个整数,是可以转化成为一个32位的二进制数,而也就可以变成长度为32位的二进制字符串. 每一次检索的时候,我们都走与当前这一位相反的位置走,也就是让异或值最大,如果说没有路可以走的话,那么就走相同的路.  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp...

做法：位运算 思路： 确定攻击的每一位填1还是填0填1必须满足：该位为1了以后总和不能大于最大的攻击力填1了之后运算过后答案的二进制位上还是1 其余情况填1也会变成0，否则就大于了m，还不如填0有效 代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);...

思路  1.把鬼的位置存起来，双向边建树 2.进行一遍dfs找到离树根最远的鬼 3.对该点进行一遍dfs找到离该鬼点最远的鬼点 4.再对鬼点进行一遍dfs，即找出两个相邻最远的鬼点 5.此时如果有点满足到这两个鬼点小于等于d，则成立  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(in...

做法：dp 思路：  1.先用结构体把每个横坐标的情况记录下来 2.dp[i][j]表示到坐标(i,j)最少需要跳的次数 3.考虑上升转移和下降转移，其中上升转移要考虑到顶这种特殊情况  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #...

思路  1.先用结构体存树 2.对树进行dfs遍历，记录子树的大小 3.写一个check函数判断是否是对称二叉树  代码： #include<bits/stdc++.h> using namespace std; const int N=1e6+10,INF=0x3f3f3f3f; typedef long long ll; struct node{ int v; int l,r; int size; }tree[N]; int n,ans; void dfs(int u){ tree[u].size=1; if(tree[u].l!=-1){ dfs(tree[u].l); tr...

做法：构造 思路：  由样例+对数字的敏感可以得到最大拆分数是出现最大的数字。然后将数按条件拆分。 为了方便，先把数字转成字符串 当每位数为0时，输出0；大于0时，输出1并减去1. 注意删去前导零  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);...

做法：spfa+dp 思路：  1.用邻接表连双向边 2.st[i][j]存i码头第j天不工作 3.cost[i][j]表示第i天到第j天的花费，spfa来求值 4.dp求最小的总成本  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #...

做法  1.删除掉两条边所以会分成相同的三部分 ---> 先判断树上的值是否能被3整除 2.求出三部分的值是什么 3.对树跑一边dfs，记录能分成这个值的边 4.如果由三部分则输出答案，否则输出  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b...