题意  走迷宫，迷宫中有传送门，使用传送门需要花费三秒，求解从起点到终点的最短时间  思路  相较于传统搜索，出现的问题是对于一个点可能有多个到达时间，我们希望记录这多个时间中最短的时间 对于传送门，由于同一个点可能有多个传送门，所以不能使用点对点的映射，使用点对数组的映射，map<int,vector> 换言之，对于一个点的多个时间，我们处理完最短的就可以了，同时对于所有路径，我们总希望先处理当前时间最短的时间，故从维护队列变为维护优先队列，维护一个大顶堆，存储坐标和时间的pair 同时对于传统的vis数组，不再是只要走到就更新，而是时间最早的被处理后，更新vis 由于上一条，所...

题意  给定n根短棍，将其拼成若干等长的长棍，求能拼成的长棍的最短长度是多少  思路  枚举长棍的长度，深搜判断能否拼成（将每一个棍尝试摆上去，如果摆上去不大于枚举长度就深搜下一层，超过的就跳过，最终判断所有棍用完的时候，最后一根长棍是否刚好拼完） 优化一：对于枚举，枚举区间为最长的棍的长度到所有棍的长度和，且不能被总和整除的直接跳过 深搜优化一：对于所有短棍，先放短的再放长的，剪掉短的用完后长的无法拼成的情况 深搜优化二：对于一根短棍，如果回溯回到它（它放的有问题），说明则跳过所有和它等长的短棍 深搜优化三：如果回溯到的短棍是一根长棍的结尾，则换成比他短的一定不会更优，所以说明换成短的没有意...

题意  给定两个字符串a，b，不超过6条变换规则，,如果能在十步以内使用变换规则将a变换为b，输出步数，否则输出NO ANSWER!  思路  对于最优极限情况，每一步内a可用6次变换规则，总复杂度为6^10 只要超过两种规则出现重复使用，单项搜索就会TLE 所以使用双向搜索，维护两个队列，一个从a用变换，一个从b用变换，维护两个映射，建立变换后的结果和步数的映射关系 对于bfs，最初需要判断如果a==b则无需进行后面的变换，直接返回0； 如果不返回零，就永远优先处理更小的那个队列 对于当前队列，取出队首串，对于每一个位置遍历每一个规则 如果匹配上了，产生一个新串tp 如果tp和另一个队列已产...

题意 给定一个九宫格数字状态，询问能否恢复成 | 1 | 2 | 3 | | 4 | 5 | 6 | | 7 | 8 | x | 如果可以输出还原步骤，否则输出unsolvable 思路  对状态进行广搜，每次记录当前状态是由什么情况经过什么步骤改变而得到的，最终如果能搜到目标状态，说明可行，反之则不可以 将3x3表格映射为一个字符串，开一个map映射字符串和序号，开一个string数组映射序号和串，开一个last记录上一步状态  注意  每次生成新状态后要检查该状态是否之前已经出现过，如果是则无意义，直接跳过 不注意到这一点的话，会一直往队列里塞重复元素，最终mle  #include&lt...

题意  有一块奶酪，高度为h，内部有n个球洞，半径均为r,问这些球洞能否贯穿奶酪  思路  使用并查集，合并到顶和底两个大集合中，最后检查顶和底是否在同一个集合 注意，和顶部连通的球洞可能同时和底部连通，注意处理方式 另一种思路为使用深度优先搜索，看全部搜完后最大深度能否超过h  AC代码(并查集) #include<bits/stdc++.h> using namespace std; typedef struct{ long long x,y,z; }C; C a[1010]; int fa[1010]; long long n,h,r; bool cmp(C x,C y){ ...

题意  给定一个区间，将区间中每一个数放大为大于等于它的第一个全部由4，7，组成的数字，然后再求和  思路  dfs打表把所有4和7组成的数组打印出来，然后检查区间，输出即可 特别的，注意加入0和4444444444，否则lower_bound和upper_bound会出错  AC代码 #include<bits/stdc++.h> using namespace std; long long a[1024]={0,4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747,4774,4...

Dfs  依赖于栈实现 深度优先搜索，回溯，搜不到就回头 放置试探性问题需要回溯 迷宫类问题不需要回溯  Bfs  依赖于队列实现，预处理完后只要队列不空，就一直循环 对每一个路径标注第几步走到

A  给定一个串，sum初始为1，遇到-，sum-1，遇到*，sum*2，求给定串能否使得sum>=2025  思路  直接模拟即可  AC代码 #include<bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int sum=1; for(int i=0;i<s.size();i++){ if(s[i]=='-'){ sum-=1; }else{ sum*=2; } if(sum>=2025){ printf("YES\n"); return 0; } } print...

PS  此题是并查集的一种抽象运用，通过开大空间，将一条逻辑链存到一个合并集合里 开眼看世界  题意  三种动物：a吃b，b吃a，c吃a n只动物，m条信息，信息就两类——ab是同类\a吃b 若一条信息和之前矛盾，则认为新出现的是假信息，求一共有多少条假信息  思路  最终维护三个集合，每个集合代表一种逻辑关系：1号是A，1号是B，1号是C 同时1-n代表是A，n+1-2n代表是B，2n+1-3n代表是C 对于每一次信息，通过find判断是否成立，如a吃b，就判断a和b+n是否有同一个根结点 对于a是b的同类，如果ab之间没有吃和被吃的关系，就可以建立  AC代码 #include<bi...

题意  n个人，m次操作 每次操作要么在a,b之间建立亲戚关系，要么查询a，b之间是否为亲戚  思路  并查集典例，最开始每个结点的父亲是自己，建立，就合并两个，查询就查询  AC代码 #include<bits/stdc++.h> using namespace std; int fa[20202]; int find(int q){ return fa[q]==q?q:fa[q]=find(fa[q]); } void merge(int a,int b){ fa[find(a)]=find(b); } int main(){ ios::sync_with_stdio(fals...

题意  给定长为n的01串，给出m次描述，找出第一次矛盾的描述序号  思路  将区间值转化为端点值 eg:[5,10]中有奇数个1，说明前4个数中1的个数和前10个数中1的奇偶性不同，也就是前4个数中有奇数个一的时候前10个数有偶数个1 维护一个大小为2n的father数组，当属于1-n表明为奇数，属于n+1-2n表明为偶数，区间奇偶性不同就建边，奇偶性相同就在同区间建边 直到出现矛盾或者全部通过  注意  由于区间范围很大，不能开数组来存，需要使用map进行离散化 由于使用map，需要用count方法来判断是否已经存在，如果不存在就赋初值使得父节点是自己 如果存在就不用管  AC代码 #in...

介绍  实现集合的合并和查找 用树来存储一个集合 如果两个点有共同根，就在一个集合里 合并只需要把一个点的根放到另一个点的根的下面就行  两种优化 按秩合并  把矮的集合的根放到高的集合的根的下面 总能保证深度不超过logn  路径压缩（简单常用）  操作复杂度O(logn) 忽视两个点的父子关系，只关心在哪个集合里 在对一个点找根的时候同时将他的父亲变为根  int father[202020];//存储每个节点的父节点编号 int find(int x){ return father[x]==x?x:father[x]=find(father[x])； } void merge(int x...

题意  有n支军队，m支敌人，每支军队攻击力比对方高就可以消灭对方，同时减少对方攻击力的防御力，每只军队只能进攻一个敌人，能否消灭所有敌人，消灭敌人后最多剩多少军队  思路  贪心的思考，在已知敌人防御力的情况下，我们希望存活，所以使用刚刚好大一点的军队，去消灭他，如果最大都不够消灭，就选择防御力最低的去同归于尽。 军队按照攻击力降序排，敌人按照防御力降序排，对于每一个敌人，挑出所有可以消灭他的军队，如果同归于尽，就给损耗加一。最终答案是n-损耗。特别地，如果对于任意一个敌人，没有攻击力比他更大的军队，就说明无法消灭。 对于存放比敌人防御力高的军队，需要能够查找，排序，存重复，故选用multi...

题意  给定n个点对(x,y)，如果不存在一个点对(a,b),使得(a<=x&&b<y)||(a<x&&b<=y),则称(x,y)是有优势的点对 每次加入点对后，输出当前有优势的点对个数  思路  点对问题转换成二维坐标系中问题 画图发现，有优势的点对应的几何意义是，和坐标轴围成的范围(除自身以外的闭集)不含有其他点 用一个容器实现，使该容器对下标进行排序 注意：用map和set都会寄，因为无法处理重复点，本题中，两个重复点会都被记录为有优势点、  代码 #include<bits/stdc++.h> using namesp...