镜子的知识栈 Tsuki's stack

DFS写法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include<iostream>#include<cstring>using namespace std;const int N = 100000 + 10;int h[N], e[2 * N], idx, ne[2 * N];int n, m;int st[N];void add(int a, int b){ e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;}bool dfs(int x, int c){ // c表示的是当前的颜色 st[x] = c; for(int i = h[x]; i != -1; i = ne[i]) { int d = e[i]; i ...

AcWing 903. 昂贵的聘礼思路建立虚拟源点 每一个物品都有一个初始价格, 初始价格我们定义为虚拟源点到当前点的权值. 每次从虚拟源点出发遍历图, 寻找1点的最短路 本题有等级限制, 等级限制其实就是决定了 图遍历的范围, 不同范围得出的结果不同,所以每一个限制我们都要遍历一遍 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 110;int level[N];int st[N];int dist[N];int w[N][N];int n, l;int dijistra(int down, int up){ // 初始化 memse ...

341. 最优贸易思路我们需要找到一个路径上的最大解 我们可以分为n个分界点, 在k之前的最小价格和在k之后的最大价格 再用k之后的最大价格减去k之前的最小价格就是我们要求的的最终解 正向遍历一遍,再反向遍历一遍. 所以我们需要两个相反的领接表来存储边的信息 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 100010;const int M = 2000010;// 使用两个不同的领接表来存储信息int ht[N], ...

2023 March 6 ~ 12周计划补充说明: 周任务规划与复盘规则说明@ver1.0 考研还剩 41 周蓝桥杯还剩 3 周Base 每日复习300个单词打卡 蓝桥杯集训每日一题和 总结 力扣每日一题 周六acwing周赛, 周日力扣周赛 英语阅读理解, 积累语法 Advance 补充英语语法 准备开始高数复习 Production Dijkstra算法使用虚拟源点 spfa -> DP思想, Dijkstra 贪心思想 Kruskal -> sort + findx Prim -> 魔改Dijkstra LCA算法 周末休息

T2 AcWing 4868. 数字替换思路:DFS剪枝 搜索顺序优化 最优性优化 预测最优性优化 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;LL num, n;int ans = 1000;void dfs(int u, LL num){ // 记录当前位数和记录出现的数字 int cnt = 0; int st[10] = {0}; for(LL i = num; i; i /= 10) { st[i % 10] = 1; cnt++; } // 最优性剪枝, 如果当前步数 + 剩余位数 大于最优解停止 ...

最常见的几种类型 搜索一个固定的数值 类两数之和做法 猜答案

Tire树我们一般实现字典树的两个功能, 插入操作和查询操作. AcWing 835. Trie字符串统计字典树模板题 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 200100;int idx, a[N][30], st[N];// 插入操作void insert(string s){ int n = s.size(); int j = 0; for(int i = 0; i < n; i++) { int u = s[i] - 'a'; if(a[j][u] == -1) a[j][u] ...

2023 February 27 ~ March 5周计划补充说明: 周任务规划与复盘规则说明@ver1.0 考研还剩 42 周蓝桥杯还剩 4 周Base 每日复习200个单词打卡 蓝桥杯集训每日一题和 总结 力扣每日一题 周六acwing周赛, 周日力扣周赛 英语阅读理解, 积累语法 Advance 蓝桥杯算法集训课 数学考研课基础两节 Production 循环中 i >= 0 等价于 ~i s=a^b a=s^b Int 有31位,从第0~第30位 pq互质且不能凑出来的最大数为 (q - 1)(p - 1) - 1 上取整 默认double ceil( ) Trie树 BFS 记录每次遍历时的个数, 确定确定当前层数 拓扑序遍历所有入度为0 的点, 放入队列, 然后BFS 费马平方和 奇质数能表示为两个平方数之和的充分必要条件是该质数被4除余1 Base Review蓝桥杯集训每日一题比较重要, 单词每天花费一个小时左右 力扣周赛T3 Summary周赛总结Acwing T1 公式题, 不能直接暴力推 T2 DFS剪枝, 思路对了但是优化的过 ...

6369. 左右元素和的差值思路前缀和后缀和相减的绝对值 注意后缀和下标问题 1234567891011121314151617181920class Solution {public: vector<int> leftRigthDifference(vector<int>& nums) { int n = nums.size(); vector<int> left(n + 10); vector<int> right(n + 5); for(int i = 0; i < n; i++) left[i + 1] = left[i] + nums[i]; for(int i = n; i; i--) right[i - 1] = right[i] + nums[i - 1]; vector<int> ret; for(int i = ...

第92场周赛T2 AcWing 4865. 有效类型思路本题的输入是一个数的前序遍历, 只要通过前序遍历构造一棵树即可. pair有两个孩子, 左孩子和右孩子分别合法即pair合法. 分解成子问题递归解决 这道题没写出来的原因主要就是对于没有确定的连续输入不太熟悉 AC代码123456789101112131415161718192021222324252627282930313233343536373839#include<iostream>#include<cstring>#include<algorithm>using namespace std;string ans;string s;int flag = 0;void dfs(){ if(cin >> s) { ans += s; if(s == "pair") { ans += '<'; dfs(); ...