- 博客(350)
- 收藏
- 关注
RSS订阅原创 2022年6月第十三届蓝桥杯大赛软件赛全国决赛C++A组题解
目录比赛成绩与复盘试题 A: 小蓝与钥匙试题 B: 排列距离试题 C: 内存空间试题 D: 最大公约数试题 E: owo试题 F: 环境治理试题 G: 选素数试题 H: 替换字符试题 I: 三角序列试题 J: 括号序列树
2022-06-18 13:25:19
9739
12
原创 编译原理学习笔记
目录引论什么是编译程序为什么要学习编译原理从计算机科学与技术中学什么？编译原理的应用编译过程编译程序的结构编译程序总框遍编译前后端高级程序设计语言概述常用的高级程序设计语言程序设计语言的定义高级程序设计语言的一般特性高级语言的分类数据类型与操作标识符与名字数据结构抽象数据类型高级程序设计语言的语法描述上下文无关文法文法与语言推导句型、句子和语言语法树与二义性最左推导和最右推导语法树形式语言鸟瞰词法分析词法分析的概述词法分析器的输出词法分析器的设计超前搜索状态转换图正规式和正规集正规式的等价性确定性有限状态自
2022-05-27 18:43:39
1129
1
原创 leetcode第294场周赛巫师的总力量和——维护前缀和的前缀和
主要记录一下On预处理，O1取任意区间前缀和的前缀和题目6077. 巫师的总力量和解题思路贪心从小到大考虑，每次计算以aia_iai为最小值时的贡献。下面来看具体例子：考虑a2a_2a2作为最小值时的贡献区间[1,2],[1,3],[1,4],[1,5],[2,2],[2,3],[2,4],[2,5][1,2],[1,3],[1,4],[1,5],[2,2],[2,3],[2,4],[2,5][1,2],[1,3],[1,4],[1,5],[2,2],[2,3],[2,4],[.
2022-05-22 17:29:54
259
原创 调试C/C++程序的常见方法
目录gdb调试安装gdb使用前的准备使用进入调试运行程序设置断点下一步继续执行设置主函数参数打印变量退出参考资料gdb调试安装gdb使用前需要安装gdb：yum install -y gdb使用前的准备在编译文件时，需要加入参数-g来确保编译后的文件可以被调试。g++ -g demo.cpp -o demo使用demo代码1#include <unistd.h>#include <bits/stdc++.h>using namespace std;in
2022-04-27 21:02:56
5671
1
原创 大/小根堆
大小根堆down 和 push 两种操作，维护出堆顶即可。值得一提的是，插入n个元素复杂度是O(nlogn)，但是将n个元素建成堆时间复杂度是O(n)的，建堆代码如下：for(int i = n/2;i >=1 ;i --) down(i);代码#include <bits/stdc++.h>using namespace std;class pile{private: int a[(int)1e6 + 5]; int size;public:
2022-04-19 21:09:15
246
原创 LRU 最近最久未使用算法 哈希表+双向链表实现
目录LRU 算法实现思路题目代码实现LRU 算法基于局部性原理，最近被访问到的内存将来很可能会被再次访问。因此我们淘汰数据时，优先选择淘汰最久未使用的数据。实现思路使用双向链表，将最近使用的数据挂载到链头，这样最久未使用的数据就在队尾，淘汰数据时删除队尾元素即可。要快速定位某个keykeykey在链表中的位置，可以使用一个哈希表记录key−Nodekey-Nodekey−Node映射。题目力扣 146. LRU 缓存代码实现class LRUCache{public: st
2022-04-11 12:12:57
807
原创 2022年4月第十三届蓝桥杯C/C++程序设计A组（省赛）试题及题解
试题A：裁纸刀试题B：灭鼠先锋试题C：求和试题 D: 选数异或试题 E: 爬树的甲壳虫试题 F: 青蛙过河试题 G: 最长不下降子序列试题 H: 扫描游戏试题 I: 数的拆分试题 J: 推导部分和
2022-04-09 13:00:16
23048
16
原创 C++的虚函数表
虚函数每个类有一张虚函数表，每个类对象有一个虚表指针。因为基类和子类都有虚表指针，所以当基类指针指向子类对象的时候，可以调用子类的虚函数，体现了多态性。动态绑定：虚函数静态绑定：非虚函数析构函数一般写成虚函数的原因，这样当基类指针指向子类对象的时候，可以正确的调用子类的析构函数，正确的释放子类对象的资源。构造函数一般不写成虚函数的原因，因为调用构造函数时对象还未被创建，也就没有虚表指针，更别提找到虚函数地址了。...
2022-04-07 12:47:01
1194
1
原创 进程间通信
有六种通信方式：管道、消息队列、信号、共享内存、信号量、socket管道半双工的通信方式，通信效率低，不适合进程间频繁的交换数据，如果管道中的数据未被取走，写者会被阻塞，要双向通信就需要创建两个管道。匿名管道和有名管道，匿名管道只能用于父子进程间的通信。消息队列类似于发邮件，进程A把消息挂载到另一进程B的消息缓冲队列尾，进程A可以立即返回，进程B需要的时候再从消息缓冲队列读取消息即可。缺点：通信不及时、消息有大小限制，不适合大数据的消息传输，存在用户态和内核态的数据拷贝开销。共享内存、信号量开
2022-04-07 12:45:15
398
原创 MYSQL的redolog 、binlog、undolog以及MVCC
目录前置知识BinlogRedologundologMVCC前置知识重要概念：逻辑日志：可以简单的理解为记录的是SQL语句物理日志：记录的是数据的实际变更Crash-safe：崩溃安全，数据库在遇到崩溃、断电等极端情况，可以恢复内存尚未刷新到磁盘的数据。WAL：write-ahead logging，先写日志，再写磁盘。Innodb要对数据的更新时，先将数据加载到内存的Buffer pool中，对Buffer pool中的数据进行更新，最后找合适的时间的刷新到磁盘。如果这时候遇到断电crash
2022-04-07 12:43:56
1574
原创 InnoDB的Buffer pool、free链表、flush链表
Buffer poolInnoDB的数据是存储在磁盘上的，但是磁盘读写很慢，因此当要访问某个记录时，会将整页（默认大小16KB）数据加载到内存中，也即Buffer pool（缓冲池）。默认大小为128MB。Free链表（空闲链表）把空闲的缓冲页的控制块用链表连接起来。每当从磁盘加载一个页到Buffer Pool中时，就从free链表中找一个控制块，将其移除。判断页面有没有在Buffer Pool是使用的哈希表技术。Flush链表如果我们修改了Buffer Pool中的某个数据，那么它与磁盘中的数据
2022-04-07 12:36:56
581
原创 leetcode剑指offer合集+题解
目录一、用两个栈实现队列题目解题思路AC代码二、包含min函数的栈题目解题思路AC代码三、从尾到头打印链表题目解题思路AC代码四、反转链表题目解题思路AC代码五、复杂链表的复制题目解题思路AC代码六、替换空格题目解题思路AC代码七、左旋转字符串题目解题思路AC代码八、数组中重复的数字题目解题思路AC代码九、I. 在排序数组中查找数字题目解题思路AC代码十、II. 0～n-1中缺失的数字题目解题思路AC代码十一、二维数组中的查找题目解题思路AC代码十二、旋转数组的最小数字题目解题思路AC代码十三、第一个只出现
2022-04-05 11:16:42
2985
原创 阿里巴巴3.25C++研发笔试编程题解
第一题、判断密码合法性长度要在6-12之间，要全为字母，之前不能已经存在有个小坑，有空格。AC代码#include <bits/stdc++.h>using namespace std;map<string, int> mp;bool check(char x){ if (x >= 'a' && x <= 'z') return 1; if (x >= 'A' && x <=
2022-03-25 10:34:18
6321
1
原创 力扣第284场周赛题解
A.6031. 找出数组中的所有 K 近邻下标找到每个nums[j]==keynums[j] == keynums[j]==key的jjj，将所有max(0,j−k),min(j+k,n−1)max(0,j-k),min(j+k,n-1)max(0,j−k),min(j+k,n−1)的下标都统计起来即可。1<=nums.length<=10001 <= nums.length <= 10001<=nums.length<=1000，不需要优化可以直接O(n2)O(n^2
2022-03-13 12:00:03
2088
原创 操作系统学习笔记
目录操作系统定义计算机系统的层次结构操作系统的四个特征发展与分类运行机制和体系结构中断和异常系统调用进程定义进程间的组织进程的特征进程的状态进程控制进程间的通信线程处理机调度调度算法的评价指标FCFS、SJF、HRRN调度算法时间片轮转、优先级、多级反馈队列调度算法进程的同步与互斥进程互斥的软件实现方法进程互斥的硬件实现方法信号量机制用信号量实现进程互斥、同步、前驱关系生产者消费者问题读者写者问题哲学家进餐问题管程死锁预防死锁银行家算法死锁的检测和接触内存内存管理覆盖技术与交换技术连续分配管理方式动态分区分
2022-02-22 10:05:26
3530
7
原创 Redis_NoSQL入门学习笔记
目录NoSQL简介NoSQL四种分类分布式基础之CAP和BASE理论集中式和分布式分布式系统设计理论CAPBASE理论Redis简介常见命令五大数据类型持久化之RDB持久化之AOF事务主从复制NoSQL简介NoSQL = Not Only SQL ，意即“不仅仅是SQL”。泛指非关系型的数据库。这些类型的数据存储不需要固定的模式，无序多余操作就可以横向扩展。特点：易扩展：NoSQL数据库种类繁多，但是一个共同的特点都是去掉关系数据库的关系型特性。数据之间无关系，这样就非常容易扩展。也无形之间，在
2022-02-07 10:44:08
669
1
原创 剑指Offer30包含min函数的栈
题目剑指 Offer 30. 包含min函数的栈为栈新增功能，O(1)O(1)O(1)得到栈中最小值。解题思路如果当前压入的元素不是最小值，那么它一定不会作为最小值。所以我们只需要开一个辅助栈维护好每个“在压入时是最小值”的元素。代码class MinStack{public: stack<int> st, st2; MinStack() { while (!st.empty()) st.pop();
2022-01-26 20:51:45
160
原创 剑指Offer09用两个栈实现队列
题目剑指 Offer 09. 用两个栈实现队列用两个栈实现队列。解题思路感觉有O(n)O(n)O(n)的解法，但是想了好一会还是没想到，看了数据范围1e4，交了一发O(n2)O(n^2)O(n2)的过了。原思路就是简单的来回倒。题解思路维护两个栈，一个维护插入，一个维护删除。需要删除的时候可以把插入栈里的元素全部倒进删除栈里，注意只有删除栈为空了，才会倒，否则会破坏元素的顺序。很巧妙。代码class CQueue{ stack<int> st1, st2;publ
2022-01-26 20:49:50
6192
原创 MySQL高级学习笔记
文章目录MySQL基础篇学习笔记SQL性能下降的原因SQL的执行顺序索引索引的优劣势索引的分类索引的创建索引结构判断是否需要创建索引EXPLAINEXPLAIN之idEXPLAIN之select_typeEXPLAIN之tableEXPLAIN之typeEXPLAIN之possible_keysEXPLAIN之keyEXPLAIN之key_lenMySQL基础篇学习笔记SQL性能下降的原因查询语句写的烂索引失败关联查询太多join（设计缺陷或不得已的需求）服务器调优及各个参数设置（缓冲、线
2022-01-21 22:59:23
1176
原创 牛客练习赛D数学家的谜题线段树+bitset优化
题目https://ac.nowcoder.com/acm/contest/11175/D单点修改和区间查询，询问区间乘能被多少个素数整除。解题思路显然是维护区间质因子的数量，可以用带修莫队。也可以用线段树+bitset优化。将质数映射到1-10000的位中。代码#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 5, M = 5e4 + 5;vector<int> fac[N];
2021-11-17 11:10:22
399
1
原创 牛客练习赛C魔法学院(hard version) 并查集加速
题目https://ac.nowcoder.com/acm/contest/11181/C给出一个小写字母字符串，现在有m种魔法，每种魔法可以将区间LR的字母变为新字母X，求最后字符串的最大字典序。题解思路两种比较容易想到的操作：将操作按照X的大小从小到大排序，每次暴力区间覆盖即可，可以使用客珂朵莉树。将操作按照X的大小从大到小排序，相同区间覆盖一次，之后不再覆盖，可以用并查集加速跳跃过程。并查集代码#include <bits/stdc++.h>using namespa
2021-11-16 16:14:38
577
原创 洛谷P1160 双向链表
题目洛谷P1160代码#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;struct node{ int L, R;} a[N];void insert_left(int x, int k) //将x插入到k的左边{ a[x].R = k; a[x].L = a[k].L; a[a[k].L].R = x; a[k].L = x;}void i
2021-11-16 16:07:41
551
原创 2018ICPC焦作F-Honeycomb 蜂巢BFS
题目https://codeforces.com/gym/102028/problem/F求S-T至少要经过几个蜂巢，例如下图为7。题解注意细节，按照题意模拟即可。代码#include <cmath>#include <cstdio>#include <algorithm>#include <cstring>#include <queue>#include <iostream>using namespace s
2021-11-16 11:09:08
371
原创 HDU - 4793 思维、计算几何、直线和圆交点
题目HDU 4793有一个圆（图中红色部分），其有一个初速度，撞到黑色部分会发生完全弹性碰撞，求红色圆在蓝色区域的时间。题解训练赛的题，队友给了一个关键转化，可以将蓝色、黑色圆的半径同时加上红色圆的半径，然后将红色圆缩成一个点。这样各种事件还是等价的。转化之后就很简单了：一、红色点不进入蓝色区域，答案为0二、红色点进入蓝色区域但不进入黑色区域，答案为与蓝色区域两个交点的距离/速度与蓝色区域两个交点的距离/速度与蓝色区域两个交点的距离/速度三、红色点进入黑色区域，可以证明的是，与黑色圆发生碰
2021-11-16 11:02:00
394
原创 HDU4801 转魔方、DFS模拟
题目HDU 4801题解由于是两阶魔方，左边UP等于右边DOWN，因此共有6种转动方式。直接模拟即可，时间复杂度O(67×12)O(6^7\times 12)O(67×12)代码#include <bits/stdc++.h>using namespace std;int mp[][6] = { {-1, -1, 0, 1, -1, -1}, {-1, -1, 2, 3, -1, -1}, {4, 5, 6, 7, 8, 9}, {10, 11,
2021-11-16 10:51:05
439
原创 HDU5572 2015ICPC上海A计算几何
题目HDU 5572无限大的平面上，有一个圆柱。圆柱外有两个点A、B，点A有个速度向量V，A撞到圆柱会发生完全弹性碰撞。问点A是否能经过点B。解题思路我们记A -> A+V的运动轨迹为直线 l1l1l1（射线在代码实现中并不好处理）。共分以下几种情况：一、 l1l1l1与圆不相交判断A是否能直接经过B，即判断向量V⃗、B−A⃗\vec{V}、\vec{B-A}V、B−A是否同向。二、 l1l1l1与圆相切情况同一。三、 l1l1l1与圆相交记l1l1l1与圆距离较近的点为X。
2021-11-16 10:45:54
263
原创 D. Treelabeling 思维，01染色
题目D. Treelabeling题解x ^ y <= min(x,y) 等价于x、y二进制最高位相同。只要树上每条边的邻点都满足该条件，那么先手无论将棋子放哪都必胜。考虑如何构造。可以将树01染色，相邻点颜色不同， 将所有点分为两类，不同类的最高位都不同即可。#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 5;vector<int> mp[N];vector<int&g
2021-11-13 21:22:11
433
原创 POJ1106极角排序
题目POJ Transmitters给出若干个点和一个半圆，半圆可以绕着圆心任意旋转，问最多能覆盖多少个点。解题思路距离圆心的距离大于半径的点可以直接先排除掉。将剩余的点进行极角排序，然后用一个双端队列维护能被半圆覆盖的点，当队首和当前处理点的角度大于π\piπ时，弹出队首元素。期间队列最大的size就是答案。需要注意的是，当前处理点极角接近π\piπ时，最开始邻近−π-\pi−π处的点也会有贡献，可以将所有点复制一份加到后面，并将复制的点极角加上2π2\pi2π。时间复杂度O(nlogn)O
2021-10-29 10:10:55
170
原创 极角排序
极角排序在平面内取一个定点O，叫极点，引一条射线Ox，叫做极轴，再选定一个长度单位和角度的正方向（通常取逆时针方向）。对于平面内任何一点M，用ρ表示线段OM的长度（有时也用r表示），θ表示从Ox到OM的角度，ρ叫做点M的极径，θ叫做点M的极角，有序数对 (ρ,θ)就叫点M的极坐标。那么给定平面上的一些点，把它们按照一个选定的极点排成顺（逆）时针。代码实现cmath库中有一个函数atan2(y,x)atan2(y,x)atan2(y,x)，返回的值域为(−π,π](-\pi,\pi](−π,π]。可
2021-10-28 10:33:00
297
原创 莫队
莫队莫队是一种解决区间查询等问题的离线算法，基于分块思想，时间复杂度为nnn\sqrt{n}nn。一般来说，如果在已知区间[L,R][L,R][L,R]的答案的情况下，可以快速的计算出[L−1,R][L-1,R][L−1,R]、 [L+1,R][L+1,R][L+1,R]、 [L,R−1][L,R-1][L,R−1]、 [L,R+1][L,R+1][L,R+1]这四个与之紧邻的区间的答案，则可以考虑使用莫队。模板一、维护区间数的种类数代码#include <bits/stdc++.h>
2021-10-27 11:02:37
133
原创 2021ICPC江西省赛G.Magic Number Group莫队
题目G.Magic Number Group给定一个正整数序列，每次询问区间[L,R][L,R][L,R]，任意选择一个大于1的正整数p，该区间内最多有多少数能被p整除。解题思路对于p，我们一定是选择一个质数，问题就转化成了区间[L,R][L,R][L,R]，要使尽可能多的数包含质因子p。考虑对于所有数都分解出所有质因子。每个数的质因子数量很少，最后就是莫队离线维护众数板子。代码#include <bits/stdc++.h>using namespace std;const
2021-10-27 11:02:04
680
1
原创 分块模板
模板#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;const int M = 350;long long sum[M], add[M], w[N];int len;int n, m;int get(int i){ return (i - 1) / len + 1;}void ADD(int l, int r, int val){ if (get(l) == ge
2021-10-20 14:35:10
120
原创 POJ2397DP搜索
题目Spiderman蜘蛛侠刚开始在高度为0的位置，每次可以向上或者向下aia_iai个距离，最后要回到高度为0的位置、中途高度不能低于0、最大高度最小。求跳跃的具体方式。解题思路先用DP求出最小最大高度，然后DFS求解路径。代码#include <set>#include <map>#include <list>#include <stack>#include <queue>#include <cmath>#
2021-10-19 10:57:23
86
原创 abcE-Xor Distance思维、拆位
题目E - Xor Distances给出一颗带边权的树。求所有简单路径异或和。解题思路找任一结点x为根结点。记F(u,v)为u到v简单路径的异或值。对于两个结点u，v，设w为uv的最近公共祖先，有F(u,v)= F(u,w) ^ F(w,v)= F(u,w) ^ F(w,v) ^ F(x,w) ^ F(x,w)= F(u,x) ^ F(x,v)由于异或值每一位互不影响，因此可以拆位考虑。设DP[i][j][k]DP[i][j][k]DP[i][j][k]为子树中所有结点 到结点iii、
2021-10-12 09:21:35
214
1
原创 数位DP、多少小于n的数包含k个非0位
题目到处都是0解题思路数位DP板子改改代码#include <bits/stdc++.h>using namespace std;const int N = 1e2 + 5;char s[N];long long dp[N][5];int n;long long dfs(int pos, int lim, int k){ if (k < 0) return 0; if (pos > n) return k
2021-10-08 21:20:17
81
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人