镜子的知识栈 Tsuki's stack

AcWing 3956. 截断数组（每日一题）思路1构建前缀和数组分别使用三个指针截三段, i < j <k 如果a[i] == a[j] - a[i] == a[k] - a[j] 并且k == n 则认为我们已经分为三段 1234567891011121314151617181920212223242526272829#include<iostream>using namespace std;const int N = 10e5 + 10;int n, ret;int a[N];int main(){ cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i<= n; i++) a[i] = a[i] + a[i - 1]; for(int i = 1; i <= n; i++) { int j = i + 1; ...

T1 6354. 找出数组的串联值求整数的位数 除以10的次数就是整数的位数 双指针 左右指针同时向中间移动 奇数特殊处理 题解代码 12345678910111213141516171819202122232425class Solution {public: long long findTheArrayConcVal(vector<int>& nums) { int i = 0; int j = nums.size() - 1; long long t = 0; while(i < j) { long long y = nums[j]; long long x = nums[i]; // 求y的位数 while(y) { x *= 10; y /= 10; ...

2023 February 13 ~ 19周计划补充说明: 周任务规划与复盘规则说明@ver1.0 考研还剩 44 周蓝桥杯还剩 6 周 Base 每日复习200个单词打卡 蓝桥杯集训前缀和每日一题和总结 力扣每日一题 周六acwing周赛, 周日力扣周赛 总结归纳算法不牢固知识点, 包括不限于 排序算法, 二分搜索(重点边界问题) KMP和Trim 单调栈, 单调队列, 并查集, 哈希表, 堆 DFS和BFS 动态规划类问题 Advance 补充数学知识 Product 二分搜索做题模板 蓝桥杯集训每日一题:截断数组 裴蜀定理 设 $ a,b $ 是不全为零的整数，则存在整数 $ x,y $, 使得 $ ax+by=\gcd(a,b) $. 1250. 检查「好数组」 求模运算法则 $ a % k = b % k $ => $ (b - a) % k = 0 $ 并查集附带额外信息 异或运算符法则 a ^ b ^ c ^ b ^ a = a ^ a ^ b ^ b ^ c = 0 ^ ...

2023 February 6 ~ 12周计划补充说明: 周任务规划与复盘规则说明@ver1.0 考研还剩 45 周蓝桥杯还剩 7 周 Base 每日复习200个单词打卡 力扣每日一题 周六acwing周赛, 周日力扣周赛 算法基础课贪心 Base Review每日一题三维动态规划没有写出来, 对动态规划不是很敏感, 需要多练习. Production 力扣332周赛 Summaryacw周赛总结第二题找数字 贪心问题 ​ 对于特殊情况1 0 没有考虑到, 思考不够全面 第三题构造字符串 KMP问题 ​ KMP算法模板掌握不熟练, 还需复习KMP算法 力扣周赛总结6355. 统计公平数对的数目 双指针 或者 二分搜索 ​ 二分搜索模板掌握不熟练, 代码调试时间太长, 需要复习二分 T3和T4做不出来 ​ 在缩短T2的基础上尽可能去做T3, T2主要考察对算法的熟练度, 提高自己对基础算法熟练度

前置文章 二分查找 注意!!!!!!!!以下模板是闭区间内代码, 搜索结果是下标模板1: 搜索左端点(小于等于x的值)123456while (l < r) { int mid = l + r >> 1; if (q[mid] >= x) r = mid; else l = mid + 1; } 模板2: 搜索右端点(大于等于x 的值)123456while (l < r) { int mid = l + r + 1 >> 1; if (q[mid] <= x) l = mid; else r = mid - 1; } 搜索右端点时, 重点要寻找靠右的中点一个mid = (l+r)>>1一个mid = (l+r+1)>>1加 ...

基础算法acwing算法基础课第一章 基础算法 排序: 总结十大排序 快速排序 归并排序 二分: 二分查找 高精度 前缀和差分: 前缀和 和差分 双指针(滑动窗口) 位运算 离散化 区间合并 第三章 搜索与图论 DFS BFS 最短路问题 图问题:最短路,最小生成树和二分图 Djikstra bellman-ford spfa Floyd 最小生成树 图问题:最短路,最小生成树和二分图 Prim Kruskal 二分图问题 图问题:最短路,最小生成树和二分图 染色法判定二分图 匈牙利算法 第四章 数学知识第五章 动态规划 背包问题 动态规划:背包问题和优化 01背包问题 完全背包问题 多重背包问题 分组背包问题 线性DP 线性DP问题 区间DP 计数DP 数位统计DP 状态压缩DP 树形DP 记忆化搜索 第六章 贪心 区间问题 哈夫曼树 排序不等式 绝对值不等式 推公式

为什么周复盘量化学习 首先我觉得对于学习的过程,不是觉得自己会了就是学会了. 必须有自己的产出, 学习输入必须有产出的价值. 就像算法, 每一个输出都与输入一一对应. 为了保证能够量化自己的学习进度, 必须保证自己的产出. 用公司的角度管理自己的大脑. 在过去20年对我自己的反思和总结过程中, 我发现自己的大脑思维过度发散, 容易分散掉自己的精力, 在研究某一领域的过程中, 很有可能被别的事物所吸引, 精力不断被分散, 为了保持对某一领域的专注, 必须遏制自己发散的思维. 这也是为什么我要量化自己的学习, 对于产出的笔记或者是文章, 都及时反馈给大脑, 不断产生正反馈. 属于良性发展的方向. **精力分配 在量化学习的基础上, 有效遏制思维发散之后, 合理分配自己的精力资源是非常有意义的. 更多希望使用在长期价值最大化的事情上, 例如深度的学习和长期健身. 这两点都是我非常向往的方向. 深度问题 对于困难复杂的问题, 和短时间内解决不了且意义重大的问题, 显然需要更多的精力去支持. 为此, 对于深度问题的解决, 更需要去量化我的学习过程. 周复盘, 对于日复盘, 频率太高的复 ...

典型的动态问题比如背包问题和线性DP问题, 我们之前都已经解决过了, 我们来看其他常见的DP问题 区间DP石子合并 设有 N 堆石子排成一排，其编号为 1,2,3,…,N1,2,3,…,。 每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。 例如有 44 堆石子分别为 1 3 5 2， 我们可以先合并 1、21、2 堆，代价为 44，得到 4 5 2， 又合并 1、21、2 堆，代价为 99，得到 9 2 ，再合并得到 1111，总代价为 4+9+11=244+9+11=24； 如果第二步是先合并 2、32、3 堆，则代价为 77，得到 4 7，最后一次合并代价为 1111，总代价为 4+7+11=224+7+11=22。 问题是：找出一种合理的方法，使总的代价最小，输出最小代价。 状态表示 : 集合: 这类问题我们状态表示的是一个区间 属性: 表示这个区间代价的最 ...

数字三角形 给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 12345 7 3 8 8 1 0 2 7 4 44 5 2 6 5 这是一道非常简单的DP问题 状态表示 可以用f[i][j] 来表示某个某一行某一列的最大值 **状态转移 ** 上一行的前两个之中的最大值 代码中有一些细节需要注意一下 1234567891011121314151617181920212223242526272829303132333435#include<iostream>using namespace std;const int N = 510, INF = 0x3f3f3f3f;int a[N][N], dp[N][N];int n;int main(){ cin >> n; for(int i = 1; i <= n ; i++) for(int ...

背包问题 01背包问题: 每件物品最多只用一次 完全背包问题: 每件物品有无限个 多重背包问题: 分组背包问题: 01背包问题01背包模型 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。 首先我们要解决一个问题, 状态表示 和 状态转移 状态表示我们可以用一个数组表示, f[n][m] n表示0 - n个物品选择 m表示当前容积 状态转移 第i个物品放入背包和不放入背包的最大值 简单版代码 12345678910111213141516171819202122232425262728#include<iostream>using namespace std;const int N = 1010;int v[N], w[N];int f[N][N];int n, m;int main(){ cin >> n >> m; for(int i = 1; i &l ...