做法：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...

做法：二分 思路：  1.先找出二分所需要的边界 2.每次判断这个点是否成立，可以用upper_bound模拟。如果能模拟完所有点则成立，否则不成立。  代码 #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++) #define per(i,b,a)...

做法：线段树优化dp 思路： dp[i]表示覆盖[1,i]需要的最少区间数。然后用线段树更新取最小值。dp[t]=min(dp[t],min(dp[s]~dp[t])+1) 代码 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int N=5e4+10,INF=0x3f3f3f3f; int n,m; int dp[N<<2]; i...

做法：二分 思路： 考虑每次充最小使用时间的电脑（即)判断是否符合作为二分条件 代码 #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++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define...