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个，这个数是因为一种特殊情况，当场上…

url: https://www.luogu.com.cn/problem/P1108tag:动态规划思路：问题1就是求最长下降子序列。问题2可以用c[i] 来表示以i为结尾长度为f[i] 的所有下降子序列，然后属性是数量。他可以由倒数第二个数的情况来转移，初始化是当长度为1时数量为1，之后遍历j从1到i，如果满足长度比f[j]大1，然后d[j] …

url: https://www.luogu.com.cn/problem/P7469tag:NOI Online 2021 提高组，字符串，哈希思路：用双重循环枚举每一个b中的字串，对于每一个枚举的字串，扫描一遍a，找出a中相同的子序，然后计算哈希值并存储，最后遍历结束，对哈希数组去重得出答案。代码：#include <iostream&g…

url: https://www.luogu.com.cn/problem/P3135tag:枚举，构造，动态规划思路：看了题解好像是可以用动态规划中的求最大子矩阵来做，但是这里用了很暴力的写法，加上前缀和优化也能过。这个做法本质上就是不断地枚举每一个矩形然后判断四条边是不是满足条件，然后再更新最大值就好了。代码：#include <iost…

url: https://www.luogu.com.cn/problem/P1080tag:NOIP2012 提高组，贪心，高精度思路：用贪心的策略，将大臣按照左右手金币数量的乘积从小到大排序，贪心证明: https://www.luogu.com.cn/article/2xwnkq6p . 然后因为数据范围比较大又用到了乘除所以需要使用高精度，…

url: https://www.luogu.com.cn/problem/P4552tag:差分思路：说是一道差分的题，但觉得更像是脑筋急转弯的那种感觉。为了求出最少的操作次数，可以依次求a(i) - a(i-1)，表示相邻两个数的差，然后将正的差和负的差分别求和，之后取这两个和的最大值就是最少的操作次数，因为对于差分来说，如果要对原数组的某一个…

url: https://www.luogu.com.cn/problem/P2009tag:图论，最短路思路：这道题因为读入的时候，会有不同权值的相同的边，要求是如果有重复的就保留最长的那个，这种情况下用邻接链表不是很好做，所以可以用邻接矩阵来存比较方便。然后就是数据范围比较小，k是小于等于100，刚好floyd算法可以过，所以就用floyd来求…

url: https://www.luogu.com.cn/problem/P1111tag:kruskal算法, 并查集思路：先按照边权排序，然后依次取出每条边，判断两个点是否联通（是否在一个集合）如果不连通就加一条边，然后更新下res = max(res, w) 然后边数++，最后判断边数是否为点个数-1，表示所有点都连上，如果没有则输出-1，…

url: https://www.luogu.com.cn/problem/P1083tag:差分，前缀和，二分思路：因为要求第一个不满足要求的订单，所以可以想到用二分。二分查找的是不满足要求的情况。通过订单的编号来查找，因为题目中写道有一个不满足要求的订单，后面就会停止分配，这可以抽象成假如有一个订单不满足，后面的订单一定也不满足，而前面的订单或…