- 博客(35)
- 收藏
- 关注
RSS订阅原创 编译原理基本定义(LR(0)与SLR(1))
LR(0)第一步：改写为扩广文法，一般只是新加一个起始非终结符，并且将所有的产生式拆开即可，然后在所有文法的前面加从0开始的编号，以便构建LR(0)分析表的时候有用。第二步：列出所有项目。这个比较简单，将所有的产生式插空加点即可。第三步：写出所有项目集规范族。即写出所有项目的转移，并且标号。第四步：画出状态转移。即根据第三步构造的项目写出DFA。第五步：作出LR(0)分析表。一般题目都只会问到LR(0)的分析表，有些第三小问会问对一些指定的输入串进行分析，这时候也比较简单，下面先给个例子。例子
2021-12-27 18:47:00
6652
1
原创 编译原理基本定义（文法、算符文法、算符优先文法、算符优先关系表、算符优先分析过程）
文法文法和语言分为4类。0型文法：最大类，包含1、2、3型文法。1型文法：对0型文法来说，所有的产生式的右边的字符长度都要大于左边的字符长度。2型文法：所有的产生式左边都只有一个字符。3型文法：在满足2型文法的基础上，每个产生式具有以下形式：A–>a（终结符）、A–>a（终结符）B(非终结符)，或者具有以下形式：A–>a（终结符）、A–>B（非终结符）a（终结符）。例：S–>aSS–>aAA–>bAA–>bBB–>cBB–>
2021-12-27 12:35:21
5002
原创 编译原理基本定义（短语、直接短语、句柄、素短语、最左素短语）
一般先根据句型写出语法树，然后再根据语法树进行求解。举个例子：先画出语法树（最左推导）：短语：在语法树中，先找出所有的非终结符，然后用叶子节点去替换他们，最后得到的集合就是短语的集合。这里的非终结符从上到下为：E、E、T、E、T、F、T、T、F。我们用叶子节点全部替换这些非终结符。所以短语有：T、F、TF、i、T+TF、T+T*F+i。（重复的去掉了）直接短语:在语法树中，一步就能够用叶子节点替换掉非终结符的短语。在这个例子，我们可以用叶子节点T一步替换掉E，那么T就是一个直接短语，然后我们
2021-12-26 17:04:28
9700
4
原创 2021-07-05
C. Strange FunctionLet f(i) denote the minimum positive integer x such that x is not a divisor of i.Compute ∑i=1nf(i)\sum_{i=1}^{n} f(i)∑i=1nf(i) modulo 10910^9109+7. In other words, compute f(1)+f(2)+⋯+f(n) modulo 10910^9109+7.InputThe first line con
2021-07-05 18:13:16
198
原创 Codeforce round #729 B题
B. Plus and Multiply1 is in this set.If x is in this set, x⋅a and x+b both are in this set.For example, when a=3 and b=6, the five smallest elements of the set are:1,3 (1 is in this set, so 1⋅a=3 is in this set),7 (1 is in this set, so 1+b=7 is in th
2021-07-05 17:11:18
109
1
原创 算法基础之数学知识——公平组合游戏ICG
概念：公平组合游戏ICG若一个游戏满足：1.由两名玩家交替行动；2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；3.不能行动的玩家判负；则称该游戏为一个公平组合游戏。NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。介绍：1.Mex运算设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：mex(S) = min{x}, x属于自然数
2021-05-11 09:51:53
719
原创 算法基础之数学知识——NIM游戏
概念：给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只
2021-05-11 09:03:41
445
原创 算法基础之数学知识——组合数问题之卡特兰数
题目：给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。输出的答案对 10^9+7 取模。输入格式共一行，包含整数 n。输出格式共一行，包含一个整数，表示答案。数据范围1≤n≤10^5输入样例：3输出样例：5思想：题目中给定的0和1的个数一样，排列的序列前缀中的0不小于1的个数，所以我们应该想到可以用DFS来做，但是发现数据范围有10^5那么大，用DFS绝
2021-05-05 11:36:40
305
原创 算法基础之数学知识——求组合数III（样例n = 20，a，b ＜= 10^18）lukas（卢卡斯定理） + 快速幂+ 逆元，时间复杂度O(plogn)
题目：给定 n 组询问，每组询问给定三个整数 a,b,p，其中 p 是质数，请你输出 Cab modp 的值。输入格式第一行包含整数 n。接下来 n 行，每行包含一组 a,b,p。输出格式共 n 行，每行输出一个询问的解。数据范围1≤n≤20,1≤b≤a≤10^18,1≤p≤10^5,输入样例：35 3 73 1 56 4 13输出样例：332思想：题目的核心原理是用到了一个卢卡斯定理：Cab = Ca%p b%p * Ca/p b/p 通过这个定理可以将a和b减小
2021-05-04 16:10:54
226
原创 算法基础之数学知识——求组合数II（样例n = 10000，a, b ＜= 10^5）预处理+快速幂+逆元，时间复杂度O(aloga)
题目：给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cab mod(10^9+7) 的值。输入格式第一行包含整数 n。接下来 n 行，每行包含一组 a 和 b。输出格式共 n 行，每行输出一个询问的解。数据范围1≤n≤10000,1≤b≤a≤10^5输入样例：33 15 32 2输出样例：3101思想：因为a，b太大，如果还是采用递推公式去推的话，时间复杂度为10^5 * 10 ^ 5 = 10 ^ 10，这绝对会TLE。我们通过Cab = a! /
2021-05-04 15:22:52
192
原创 算法基础之数学知识——求组合数（样例n = 10000， a, b ＜= 2000）预处理+递推式，时间复杂度O(ab)
题目：给定 n 组询问，每组询问给定两个整数 a，b，请你输出 组合数Cab mod(10^9+7) 的值。输入格式第一行包含整数 n。接下来 n 行，每行包含一组 a 和 b。输出格式共 n 行，每行输出一个询问的解。数据范围1≤n≤10000,1≤b≤a≤2000输入样例：33 15 32 2输出样例：3101思想：没有用到什么思想，主要是用到了一个递推式：Cab = C(a - 1)b + C(a - 1)(b - 1)代码如下：#include<i
2021-05-04 14:41:05
162
1
原创 算法基础之搜索与图论——染色法判定二分图（查询一个图是否为二分图）时间复杂度O(n + m)
题目：给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。请你判断这个图是否是二分图。输入格式第一行包含两个整数 n 和 m。接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。输出格式如果给定图是二分图，则输出 Yes，否则输出 No。数据范围1≤n,m≤10^5输入样例：4 41 31 42 32 4输出样例：Yes思想：对一个图进行染色，一个点染成一个颜色，那么与之相邻的点就得染成另一个颜色，染到最后如果发现有矛盾那么此图
2021-05-03 21:13:35
528
原创 算法基础之搜索与图论——kruskal算法（求最小生成树，存在负权边，适用于稀疏图）时间复杂度O(mlogm)
题目：给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。输入格式第一行包含两个整数 n 和 m。接下来 m 行，每行包含三
2021-05-03 16:33:00
731
原创 算法基础之搜索与图论——prim算法（求最小生成树，存在负权边，适用于稠密图）时间复杂度O(n^2)
题目：给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。输入格式第一行包含两个整数 n 和 m。接下来 m 行，每行包含三
2021-05-03 11:08:13
1631
1
原创 算法基础之搜索与图论——Floyed算法（多源最短路， 存在负权边， 使用于求多源最短路问题）时间复杂度O(n^3)
题目：给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。数据保证图中不存在负权回路。输入格式第一行包含三个整数 n,m,k。接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。输出格式共 k 行，每
2021-05-03 09:15:53
178
原创 算法基础之搜索与图论——SPFA算法( 队列优化过的bellman-ford算法 ) ( 单源最短路，存在负权边，适用于各种图 ) 时间复杂度O(m)，最坏O(nm)（网格图）
题目：SPFA求最短路给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。数据保证不存在负权回路。输入格式第一行包含整数 n 和 m。接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。输出格式输出一个整数，表示 1 号点到 n 号点的最短距离。如果路径不存在，则输出 impossible。数据范围1≤n,
2021-04-05 15:52:40
179
原创 算法基础之搜索与图论——bellman-ford算法( 单源最短路，存在负权边，适用于求有边数限制的最短路) 时间复杂度O(nm)
题目：有边数限制的最短路给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。注意：图中可能 存在负权回路 。输入格式第一行包含三个整数 n,m,k。接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。输出格式输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。如果不存
2021-04-05 15:09:34
157
原创 算法基础之搜索与图论——堆优化版Dijkstra（单源最短路，不存在负权边，适用于稀疏图）时间复杂度O(mlogn)
题目：Dijkstra算法求最短路II给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。输入格式第一行包含整数 n 和 m。接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。输出格式输出一个整数，表示 1 号点到 n 号点的最短距离。如果路径不存在，则输出 −1。数据范围1≤n,m≤1.5×10^5,图中涉及边长均不
2021-04-05 11:51:32
196
原创 算法基础之搜索与图论——朴素Dijkstra（单源最短路，不存在负权边，适用于稠密图）时间复杂度O(n^2)
题目：Dijkstra算法求最短路1（适用于稠密图）给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。输入格式第一行包含整数 n 和 m。接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。输出格式输出一个整数，表示 1 号点到 n 号点的最短距离。如果路径不存在，则输出 −1。数据范围1≤n≤500,1≤m≤10^5,
2021-04-05 10:43:17
151
原创 算法基础之搜索与图论——拓扑排序
题目：有向图的拓扑排序给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。输入格式第一行包含两个整数 n 和 m。接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。输出格式共一行，如果存在拓扑序列，则输出任意
2021-04-05 09:57:23
442
原创 每日一题
今天做了一道题目，感觉可以记录一下。身为菜鸟的我，在一些边界问题上吃了亏，想了一阵子才处理得较好。题目：反转链表定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。请同时实现迭代版本和递归版本。样例：输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL思想：(1)可以从头遍历到尾，用数组存起来，然后再从头到尾用数组倒序更新链表，这样比较简单，但需要付出一些空间的代价，并且我们并
2021-03-31 20:14:43
52
原创 每日一题
今天看到一道很好的题目，很菜的我并没有想到这种解法。题目：二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。样例：输入数组：[[1,2,8,9]，[2,4,9,12]，[4,7,10,13]，[6,8,11,15]]如果输入查找数值为7，则返回true，如果输入查找数值为5，则返回false。自己的思想：开始我只想到对每一行二分查找，然后找到目标值
2021-03-30 22:02:59
52
原创 算法基础之搜索与图论——树与图的广度优先遍历
题目：图中点的层次给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。所有边的长度都是 1，点的编号为 1∼n。请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。输入格式第一行包含两个整数 n 和 m。接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。输出格式输出一个整数，表示 1 号点到 n 号点的最短距离。数据范围1≤n,m≤10^5输入样例：4 51 22 33 41 31
2021-03-28 21:06:18
196
转载 C++中unordered_map 与map的区别
https://blog.csdn.net/batuwuhanpei/article/details/50727227
2021-03-28 16:02:29
88
原创 算法基础之搜索与图论——BFS走迷宫问题
题目：走迷宫给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。输入格式第一行包含两个整数 n 和 m。接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组
2021-03-28 15:00:07
301
转载 C++STL库——队列
https://blog.csdn.net/Allenlzcoder/article/details/79755427?utm_source=blogxgwz1
2021-03-28 14:25:59
142
原创 算法基础之搜索与图论——n皇后问题
题目：n皇后问题n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数 n，请你输出所有的满足条件的棋子摆法。输入格式共一行，包含整数 n。输出格式每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。每个方案输出完成后，输出一个空行。注意：行末不能有多余空格。输出方案的顺序任意，只要不重
2021-03-26 16:35:11
503
原创 算法基础之搜索与图论——DFS排列数字
题目：排列数字给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。输入格式共一行，包含一个整数 n。输出格式按字典序输出所有排列方案，每个方案占一行。数据范围1≤n≤7输入样例：3输出样例：1 2 31 3 22 1 32 3 13 1 23 2 1思想：如果纯粹用暴力去做，那么并不是题目想让我们的做法，这里题目想让我们用DFS深度优先搜索算法去做。我们开始寻找第一个数，如例子来说，我们第一次可以选择1，2，3，
2021-03-26 15:28:56
184
原创 算法基础之数据结构——哈希表
题目：模拟散列表维护一个集合，支持如下几种操作：I x，插入一个数 x；Q x，询问数 x 是否在集合中出现过；现在要进行 N 次操作，对于每个询问操作输出对应的结果。输入格式第一行包含整数 N，表示操作数量。接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。输出格式对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。每个结果占一行。数据范围1≤N≤1e5−1e9≤x≤1e9输入样例：5I 1I 2
2021-03-22 22:40:36
56
原创 算法基础之数据结构——并查集2
题目：连通块的数量给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。现在要进行 m 个操作，操作共有三种：C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；Q2 a，询问点 a 所在连通块中点的数量；输入格式第一行输入整数 n 和 m。接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。输出格式对于每个询问指令 Q1 a b，如果
2021-03-20 12:59:36
372
原创 算法基础之数据结构——并查集
题目：合并计算一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。现在要进行 m 个操作，操作共有两种：M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；输入格式第一行输入整数 n 和 m。接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。输出格式对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则
2021-03-20 11:55:11
118
原创 算法基础之数据结构——Trie最大异或对
题目：在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？输入格式第一行输入一个整数 N。第二行输入 N 个整数 A1～AN。输出格式输出一个整数表示答案。数据范围1≤N≤10^50≤Ai<2^31输入样例：31 2 3输出样例：3主要思想：因为要求两个数异或的最大值，在输入这些数后，我们通常会想到用暴力的做法去解决这个问题，复杂度为O(n^2)，这样肯定是过不了的。我们想到将这些数字分解成二进制表示，然后将这些二进制组
2021-03-20 11:01:47
80
原创 算法基础之数据结构——Trie字符串统计
题目：维护一个字符串集合，支持两种操作：“I x”向集合中插入一个字符串x；“Q x”询问一个字符串在集合中出现了多少次。共有N个操作，输入的字符串总长度不超过 1e5，字符串仅包含小写英文字母。输入格式第一行包含整数N，表示操作数。接下来N行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。输出格式对于每个询问指令”Q x”，都要输出一个整数作为结果，表示x在集合中出现的次数。每个结果占一行。数据范围1≤N≤2∗1e4输入样例：5I abcQ abcQ ab
2021-03-17 20:39:13
116
原创 算法基础之数据结构——单调栈
如题给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。输入格式第一行包含整数N，表示数列长度。第二行包含N个整数，表示整数数列。输出格式共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。数据范围1 ≤ N ≤ 1051 ≤ 数列中元素 ≤ 10e9输入样例：53 4 2 7 5输出样例：-1 3 -1 2 2主要思想：此道题目用到了单调栈。从数组第一位开始进行，第一位肯定是输出-1的，因为前面根本没有
2021-03-14 10:36:22
204
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人