url: https://www.luogu.com.cn/problem/P4667tag:BalticOI 2011，最短路，双端队列，bfs思路：用双端队列的bfs，每次走到下一步的时候判断方向是否相同，相同且更新之后路径变小就插到队列前面，不同且更新之后路径变小就插到队列后面。判断是否无解就判断一下终点横纵坐标和是否为奇数，为奇数就无解，因…

url: https://www.luogu.com.cn/problem/P1119tag:图论，枚举，最短路思路：这道题可以用floyd算法来做，每次询问，都将当前这个时间可以重建完的村庄用floyd算法更新一下所有点的最短路。最后判断一下这个询问的两个村庄是否重建完以及是否可以联通，如果重建完并且联通就输出最短路，否则输出-1代码：#incl…

url: https://www.luogu.com.cn/problem/P2195tag:树的直径，树形DP，dfs，搜索，并查集，图论思路：先用树形DP求出每棵树的直径，并用并查集维护联通情况。用数组c来维护树的直径。对于询问1，直接输出直径，对于询问2，如果不在一个集合中，直径可能是原来两棵树的直径和 + 1，和原来两棵树的直径取一个最大值…

url: https://www.luogu.com.cn/problem/P1731tag:NOI1999，dfs，剪枝，搜索思路：使用dfs和剪枝。dfs有四个参数，分别表示第几层，剩余体积，当前的面积，剩余层数。剪枝是有两个，第一个，如果当前的表面积加上之后最小的面积大于当前的面积，就return，第二个，之后最大的体积小于剩余的体积就ret…

url: https://www.luogu.com.cn/problem/P5194tag:USACO05DEC，dfs，剪枝，搜索思路：先按照从大到小排序，然后计算前缀和。之后每次dfs，先判断上一个累加的结果有没有超过w，如果有就return，否则就更新res，然后判断是不是所有点都判断完了，如果是，则return。之后计算一下剩余的值之和，…

url: https://www.luogu.com.cn/problem/P1433tag: 动态规划，状压DP，dfs，记忆化搜索思路：可以是状态压缩dp，也可以是用dfs加上记忆化搜索。这里就用dfs加上记忆化搜索。用二进制来存储每一种状态，每次访问一个点就将那个点异或一下。最后每次都是返回一个答案。dp中存的是从x点开始走走到最后一个点的最…

url: https://www.luogu.com.cn/problem/P1032tag:NOIP2002 提高组，字符串，bfs思路：因为是求最少的变换次数，所以可以用bfs。每次搜索都遍历字符串的每一个位置，将可以替换的地方都替换，然后判断是否出现过，没有出现过就加入队列。最后第一次出现字符串b的时候步数就是答案。代码：#include &…

url: https://www.luogu.com.cn/problem/P2672tag:NOIP2015 普及组，贪心，线段树，树状数组，前缀和，动态规划。思路：思路都是用贪心的策略，有两种情况，一种是取前x个a最大的客户，第二种是取前x - 1个a最大的客户，然后再从第i到n个中选择距离最远的一个去替换第x个a最大的客户，两种情况取最大值输…

url: https://www.luogu.com.cn/problem/P2568tag:数论，欧拉函数，筛法，前缀和思路：假设又两个互质的整数a, b，则gcd(a, b) = 1，那么对于任意的自然数p有gcd(a p, b p) = p。利用这个结论，对于这道题我们可以先求欧拉函数，然后求一遍gcd(a, b) = 1 的前缀和，这里求前…

url: https://www.luogu.com.cn/problem/P1488tag:博弈论，模拟思路：我觉得比起博弈论，更像是模拟题。这道题先是判断黑色三角形的位置，通过判断是不是有两条边为多边形的边界，如果是，说明先手可以直接切。如果不是，就继续判断n-5的奇偶性，n-5是三角形的个数，表示切了n-5个，这个数是因为一种特殊情况，当场上…