镜子的知识栈 Tsuki's stack

模运算与基本四则运算有些相似，但是除法例外。其规则如下： $ (a + b) \mod p = (a \mod p + b \mod p) \mod p $ （1）$ (a - b) \mod p = (a \mod p - b \mod p) \mod p $ （2）$ (a * b) \mod p = (a \mod p * b \mod p) \mod p $ （3）$ a ^ b \mod p = ((a \mod p)^b) \mod p $ （4） 结合律： $((a+b) \mod p + c) \mod p = (a + (b+c) \mod p) \mod p $ （5）$ ((ab) \mod p * c)\mod p = (a * (bc) \mod p) \mod p $ （6） 交换律： $(a + b) \mod p = (b+a) \mod p $ （7）$ (a * b) \mod p = (b * a) \mod p $ （8） 分配律：$ ((a +b)\mod p * ...

欧拉函数 欧拉函数表示为 从1 ~ n 内所有互质的数 的个数 公式法法求欧拉函数12345678910111213141516int phi(int x){ int res = x; // 我们只取较小质因子 for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { res = res / i * (i - 1); while (x % i == 0) x /= i; } // 检查是否包含大于根号x的质因子并带入公式 if (x > 1) res = res / x * (x - 1); return res;} 筛法求欧拉函数123456789101112131415161718192021222324252627282930313233const int N = 1e6 + 10;int prime[N];int st[N];int eul[N];in ...

2023 February 20 ~ 26周计划补充说明: 周任务规划与复盘规则说明@ver1.0 考研还剩 43 周蓝桥杯还剩 5 周 Base 每日复习200个单词打卡 蓝桥杯集训前缀和每日一题和总结 力扣每日一题 数据结构, 二分, 算法每日题库 周六acwing周赛, 周日力扣周赛 acwing算法基础课数学知识后三节 Advance 刷蓝桥杯提高课 力扣100热题 Product acwing第92场周赛 Base Review下周归纳整理做过的题, 回头看看以前写过的题有没有新的思路或者是优化. 温故知新 力扣每日一题打卡即可 力扣100热题有点没时间做, 基本没有做过 周赛惯例准时参加 Summary周赛总结acwing周赛 T1 输出输出不够细心, 输出大小写错了不应该扣分 T2 二叉树前序遍历题, 没有一眼看出来是前序遍历, 对遍历不敏感, 而且不能处理连续输入的数据, 对输出输出函数不是特别熟悉. T3 并查集, 能看出来是一道并查集的题目, 带有集合信息的并查集, 第二题浪费时间有点多, 第三题都没能写出来. 总的来说这次acwing周赛难度不是很大, 第三 ...

T3 AcWing 4863. 构造新矩阵二分 + 抽屉原理 整理体面要求 思路二分 首先我们找到每一列最大值的集合 的最小值 且选取的列数不能超过行数, 即不是一个方矩阵 最大值的最小值,我们首先想到用二分去做. 在一个数轴上分为两个区间, 成立和不成立的区间, 如果mid小于我们要求的答案, 那么永远成立,否则不成立 抽屉原理 在check函数中,我们要验证给定的mid是否符合要求 如果行列都等于n 那么我们只需要求一行中至少有一个数大于mid即可, 但是题目要求的是列数小于行数- 1 所以有某一列,一定有两个数成立 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<iostream>#include<cstring>#include<algorithm>#include<vector>using namespace std;int n,m; ...

T1 合并两个二维数组 - 求和法思路1哈希表 使用哈希表合并两个数组 1234567891011121314class Solution {public: vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) { map<int,int> m; for(auto &p:nums1) m[p[0]]+=p[1]; for(auto &p:nums2) m[p[0]]+=p[1]; vector<vector<int> > ret; for(auto &p:m) ret.push_back({p.first,p.second}); return ret; ...

数论质数 Primes质数的性质 数学符号“∣”的意义,如a∣b： ‘|’为整除符号，对于整数a,b(a≠0),若存在整数k,使b=ka,则称a整除b,或b能被a整除,记为a∣b。 d | n => n / d | n 也就是说 a * b = c, c能整除a, 也能整除b. 我们找质数只要遍历一遍较小的a即可 质数定理 在 1~n中有n / lnn个质数 试除法判定质数123456789101112131415161718192021222324252627282930#include<iostream>using namespace std;const int N = 110;bool is_Prime(int x){ // 从质数的性质出发判断质数; if(x < 2) return false; // 等价于 i * i <= x或者i <= sqrt(x) for(int i = 2; i <= x / i; i++) if(!(x % ...

Find 2 elements swapped in a sorted array99. 恢复二叉搜索树无论在升序数组还是降序数组中, 如果两个数被交换那么一定符合一个规律 在一个升序数组中, 所有的数一定都符合 a[i] < a[i + 1]; 如果某两个数被交换, 那么一定符合 a[i] > a[i + 1] 当表达式第一次匹配时, 第一个要找的数是 i ; 表达式第二次被匹配时, 第二个要找的数就是 i + 1 至此匹配结束 1234567891011121314151617181920212223242526272829void findTwoSwapped(int *arr, int size){ int x = - 1; int y = -1; int i; for(i = 0; i < size -1; ++i) { if( arr[i+1] < arr[i]) { // 每次匹配时都分别将i + 1作为第二个被交换的元素 y = i + 1; // 第一次被匹配时, ...

DFSDFS本质是使用栈进行搜索 123456789101112131415161718192021222324void dfs(int x, int n) { // 递归结束条件 if(x == n) { g.push_back(temp); return; } for(int i = 0; i < n; i++) { if(col[i] == 0 && dg[x + i] == 0 && udg[n - x + i] == 0) { // 向下搜索 col[i] = dg[x + i] = udg[n - x + i] = 1; temp[x][i] = 'Q'; dfs(x + 1, n) ...

并查集模板12345int find(int x){ if(q[x] != x) q[x] = find(q[x]); return q[x];} 路径压缩思想, 每次执行一次find x直接连接到x的祖宗; 附带额外信息的并查集应用240. 食物链 题目要求我们分为三类 ABC循环吃. 我们可以用一个路径距离来表示ABC之间的关系, 若A的路径大于B则表示 A 能够吃 B 分别用不同的路径对3求余来表示表示每个点是什么种类 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 500010;// p表示节点的父节点. d表示到根节点的 ...

刷题归纳数据结构 101. 对称二叉树 19. 删除链表的倒数第 N 个结点 136. 只出现一次的数字 (原地算法需要使用二进制运算) 二进制 136. 只出现一次的数字 前缀和 AcWing 3956. 截断数组 1124. 表现良好的最长时间段 ( 前缀和 + 单调栈) 1230. K倍区间 双指针 11. 盛最多水的容器 15. 三数之和 滑动窗口 1234. 替换子串得到平衡字符串 单调栈 962. 最大宽度坡 直方图中最大的矩形 二分 AcWing 1460. 我在哪？ 数学 1250. 检查「好数组」 (裴蜀定理) 搜索 124. 二叉树中的最大路径和 (dfs) 动态规划 337. 打家劫舍 III (不明白记忆化搜索优化)