Polycarp 有两个最喜欢的整数 xx 和 yy（它们可以相等），他找到了一个长度为 nn 的数组 aa 。Polycarp 认为一对索引 ⟨i，j⟩⟨i，j⟩ （ 1≤i<j≤n1≤i<j≤n ） 很漂亮，如果：ai aja i a j 能被 xx 整除;ai−aja i −a j 可被 yy 整除。例如，如果 x=5x=5 ， y=2y=2 ， n=6n=6 ， a=a= [ 1,2,7,4,9,61,2,7,4,9,6 ]，那么唯一漂亮的对是：⟨1,5⟩⟨1,5⟩ ： a1 a5=1 9=10a 1 a 5 =1 9=10 （ 1010 可被 55 整除 ） 和 a1−a5=1−9=−8a 1 −a 5 =1−9=−8 （ −8−8 可被 22 整除）;⟨4,6⟩⟨4,6⟩ ： a4 a6=4 6=10a 4 a 6 =4 6=10 （ 1010 可被 55 整除 ） 和 a4−a6=4−6=−2a 4 −a 6 =4−6=−2 （ −2−2 可被 22 整除 ）。求数组中漂亮对的数量 aa 。 输入的第一行包含单个整数 t t ( 1 ≤ t ≤ 1 0 4 1≤吨≤10 4 ） — 测试用例的数量。然后是测试用例的描述。 每个测试用例的第一行包含三个整数 n n , x x 和 y y ( 2 ≤ n ≤ 2 ⋅ 1 0 5 2≤n≤2⋅10 5 , 1 ≤ x , y ≤ 1 0 9 1≤x，y≤10 9 ） — 数组的大小和 Polycarp 最喜欢的整数。 每个测试用例的第二行包含 n n 整数 一个 1 , 一个 2 , … , 一个 n 一个 1 一个 2 。。。一个 n ( 1 ≤ 一个 我 ≤ 1 0 9 1≤a 我 ≤10 9 ） — 数组的元素。 保证 n n 不超过 2 ⋅ 1 0 5 2⋅10 5 .

今日主要学习树论。 一.最近公共祖先（LCA） 最近公共祖先的求解主要分为几个部分： 1.初始化：加边，初始化每个节点的祖先节点，初始化每个节点的深度。 加边：使用vector存储，注意一共输入n−1n-1n−1跳条双向边。 初始化每个祖先节点： f[x][0]表示节点xxx的父亲。 f[x][1]表示节点xxx的祖父（父亲的父亲）。 f[x][2]表示节点xxx的超级祖父（祖父的祖父）。 由此可知：f[x][i]=f[f[x][i−1]][i−1]f[x][i]=f[f[x][i-1]][i-1]f[x][i]=f[f[x][i−1]][i−1] 初始化每个节点的深度：每个节点的深度=每个节点的父节点深度+1 2.求最近公共最先：将两个点提升至同一高度，找寻它们的公共祖先。 将两个点提升至同一高度：一层一层的提升会超时间复杂度，选择倍增的思想。 寻找它们的公共祖先：从后往前找，使用排除的思想。 模版：链接描述 代码： 二.树上路径最小值 其实和上一题差不多。 但是需要求最小点权，所以需要多加一个mi[][]mi[][]mi[][]数组。 mi[][]mi[][]mi[][]和上一道题目中的f[][]f[][]f[][]差不多。 它表示的是节点xxx到xxx的父/祖父/超级祖父节点的最小点权。 这是mi[][]mi[][]mi[][]的计算公式：mi[i][j]=min(mi[i][j−1],mi[f[i][j−1]][j−1]);mi[i][j]=min(mi[i][j-1],mi[f[i][j-1]][j-1]);mi[i][j]=min(mi[i][j−1],mi[f[i][j−1]][j−1]); 代码： 三.树上差分 这是一个比较古怪的题目，要考虑如何在树上做差分的同时，也代表要在树上做前缀和。 题目：链接描述 大概是这样子的： （两个）

LCA,树上差分，树的直径，数论，最小生成树，并查集，逆元，Floyd，树的重心（换根） 15 5 15 kuai 5 10 10 5 15 LCA复习已完成。 树上差分复习已完成，但需要重做。 树的直径已完成，有时间可考虑重做。 快速幂已完成。 逆元已完成。 并查集已完成。 最小生成树已完成。

诶？不好意思，14行多写了个换行，删了就行

在键盘上同时按fn和字母e，就能随时打开表情包窗口啦！大家可以尝试一下哟！

二分答案 1、确定单调性/二段性 二段性题目：找分界点 2、二分模板 int l=答案可能的最小值, r=答案可能的最大值; int ans=0; while(l<=r){ int mid=(l+r)/2; if(check(mid)){ ans=mid; // 求最大值 l=mid+1; // 求最小值 r=mid-1; } else{ // 求最大值 r=mid-1; // 求最小值 l=mid+1; } } 3、check 函数 具体问题具体分析 需要检查当前二分的答案是否符合题目要求 明确所有变量代表的意义 最后和什么比? 题目中的某一个定值 4、如何提升自己二分答案的能力

动态规划（DP） 解决 最值问题、方案数问题、可行性问题 第一步：设动态规划数组（确定状态表示） dp[i]: 第 i 步的方案数是多少 / 走到第 i 步的最大 / 小花费是多少 dp[i][j]: 走到第 i 行第 j 列的方案数 / 最大值 / 最小值 第二步：写出状态转移方程（递推式） 方案数 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + ... + dp[i-k]; 最大值 dp[i] = max(dp[i-1], dp[i-2]+a[i]); 最小值 dp[i] = min(dp[i-1], dp[i-2]+a[i]); 第三步：初始化 dp[1] dp[2] dp[3] 最小值 for(int i=1;i<=n;i++) dp[i]=1e9; memset(dp,0x3f,sizeof(dp)) // 把数组中所有的值赋值成某一个数字 dp[1]=0; 第四步：求出答案 dp[n] dp[n][m]

WA\color{red}WAWA ononon222 MLE\color{blue}MLEMLE ononon444

AC代码你提交都提交不上去，包爆内存的，还有字数限制

#include<algorithm> #include<sstream> #include<bitset> #include<conio.h> #include<fstream> #include<iterator> #include<complex> #include<deque> #include<exception> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #if __cplusplus >= 201103L #include<array> #include<atomic> #include<chrono> #include<condition_variable> #include<forward_list> #include<future> #include<initializer_list> #include<scoped_allocator> #include<mutex> #include<ratio> #include<random> #include<regex> #include<system_error> #include<tuple> #include<typeindex> #include<type_traits> #include<unordered_set> #include<unordered_map> #include<windows.h> #include<thread> #endif 注： ”#include<bits/stdc++.h>“ “#include<windows.h>” #include<conio.h>//万能头不能导入这两个头文件

自己看

最短路，负环，最小生成树，FLOYD，并查集，树状数组，逆序对，单调栈，扩展欧几里得算法，单调队列，树状数组1,树状数组2. 树状数组1已完成。 树状数组2已完成。 并查集已完成。 负环已完成。 扩展欧几里得算法已完成，但并不熟练。 最小生成树已完成。 最短路已完成。 FLOYD已完成。 逆序对已完成。 单调栈已完成。 单调队列已完成。

今天主要学习了提高组复赛知识点：并查集和相关的最小生成树。复习了最短路的一些相关算法。 一.并查集和最小生成树 并查集，最喜欢找爹的一集。 也就是查找最近公共祖先的算法。 也就是在图论中找父亲节点。 但是仔细想想，一个一个节点的遍历过去时间复杂度太高了，所以就有了所谓“路径压缩”。 听起来很诡异，但其实做法非常简单。 看图：链接描述 所谓路径压缩，就是在查找祖先节点的过程中，将自己的父节点转换为父节点的父节点的父节点的..... 这个查找的过程是递归，递归要有截止条件，其截止条件就是当前的节点，它没有父节点/父节点就是自己（根据初始化不同而不同）。 模版代码： 与其相关的还有最小生成树，那个在此不进行解释（没时间了，还要默模版） 最小生成树模版：链接描述 二.最短路问题 DIJKSTRA 对于这个算法不多进行解释，详情请见坐着的其他文章。 模版：链接描述 SPFA 模版：链接描述 FLOYD(阴间版） 模版：链接描述

这题数据有问题，10个有9个“NO”，只有一个“YES”还和样例一样； 所以我们可以这么过

DIJ 01DFS

加油！！！！！！

eeeeee-------

第一题： <连通块问题> 时间限制：1.00s 内存限制：128MB 题目描述 输入一个n个点m条边的图。然后输入两个整数x,y，判断结点x与结点y是否在同一个连通块中。 如果节点x与节点y在一个连通块中，输出该连通块内节点的数量，否则输出0。 输入格式 第一行输入两个整数 n,m (1≤n≤10^5, 1≤m≤2∗10^5) 接下来m行，每行输入两个整数 u,v(1≤u,v≤n) u,v(1≤u,v≤n) 表示点u与v之间有一条无向边。 最后一行输入两个整数x,y(1≤x,y≤n) 输出格式 输出一个整数。如果节点x与节点y在一个连通块中，输出该连通块内节点的数量，否则输出0。 输入输出样例 输入#1 输出#1 5 3 .......... 3 1 2 1 3 4 5 2 3 输入#2 输出#2 5 3 ........... 0 1 2 1 3 4 5 2 4 先是深搜（dfs）： 再展示广搜做法（bfs）： 第二题： <充满希望的课程安排> 时间限制：1.00 内存限制：128MB 题目描述 : 盖亚正在军事学院进修，他需要上完所有的课程，才能获得战争学博士学位。 但是军事学院的课程之间有一定的依赖关系。比如你需要学习了离心机使用课程，才能学习核燃料制备课程。但是有传言说军事学院已经被间谍渗透，所有人都无法学完所有的课程。 现在盖亚已经拿到了所有的课程依赖关系，想知道他是否能学完所有的课程。 输入格式 第一行输入一个整数 n(1≤n≤100000,1≤m≤200000)，n为课程总数， m为依赖关系数量。 第 2 行到第 m+1行,每行输入2个整数 x,y。表示需要先上课程 x 才能上课程 y。 输出格式 如果可以上完所有课程，输出“YES”，否则输出"NO"。 输入输出样例 输入#1 输出#1 5 5 ......... YES 1 2 1 3 2 3 3 5 4 5 输入#2 输出#2 5 4 ............ NO 1 2 2 3 3 1 4 5 先判断题目为搜索类题型，即可用深搜或广搜，这里用深搜举例： 第三题： <拼接质数1> 时间限制：1.00 内存限制：128MB 题目描述： 盖亚为了抵御邪恶敌人的进攻，必须建立一个防护罩。 防护罩可以由若干个魔力水晶组成，每个魔力水晶有一定的魔力值， 而防护罩的总魔力值为所有魔力水晶魔力值之和。 盖亚发现只有当防护罩的总魔力为质数时，才可以保证防护罩的正常运转。 现在盖亚有 n 个魔力水晶，并且知道每个魔力水晶的魔力值 Ai。。他想知道他有多少种构建防护罩的方案。 假设所有魔力水晶都是不同的。只要在一种方案中选择了第 i 个魔力水晶， 在另一种方案中没有选择第 i 个魔力水晶 （1≤i≤n），那么我们就认为这两种方案不同。 输入格式： 输入两行，第一行包含一个整数n（1≤n≤12），表示魔力水晶的数量。 第二行包含n个整数，表示每一个魔力水晶的魔力值Ai（1≤Ai≤1000）。 输出格式： 输出一个整数，表示可以组成质数的方案数量。 输入输出样例： 输入#1 输出#1 4 ................. 8 1 2 2 4 依旧用深搜： 第四题： <充满希望的拼接质数2> 时间限制：1.00s 内存限制：128MB 题目描述： 盖亚为了抵御邪恶敌人的进攻，必须建立一个防护罩。 防护罩可以由若干个魔力水晶组成，每个魔力水晶有一定的魔力值，而防护罩的总魔力值为所有魔力水晶魔力值之和。 盖亚发现只有当防护罩的总魔力为质数时，才可以保证防护罩的正常运转。 现在盖亚有 n 个魔力水晶，并且知道每个魔力水晶的魔力值 Ai。他想知道他有多少种构建防护罩的方案。 假设所有魔力水晶除魔力值以外全部相同。 也就是说只有如果两个方案不同，当且仅当每个方案的水晶的魔力值从小到大排序后的序列不同。 输入格式： 输入两行，第一行包含一个整数 n（1≤n≤12），表示魔力水晶的数量。 第二行包含 n 个整数，表示每一个魔力水晶的魔力值 Ai（1≤Ai≤1000）。 输出格式： 输出一个整数，表示可以组成质数的方案数量。 输入输出样例： 输入#1 输出#1 4 ............... 5 1 2 2 4 看似与上题一样，实际用另一种方法能够更便捷， 用冷门的set。 如果不会用set，即可用搜索解决： 题毕。 2.补充笔记： ① set的使用方法： ② 文件判题： 举个例子： 用文件判题实现A+B：