- 博客(57)
- 资源 (3)
- 收藏
- 关注
RSS订阅
原创 树状数组入门及例题题解（一）——区间求和及单点修改
树状数组是什么树状数组是一种非常适合于求前缀和的工具（或者是其他的一些有关前缀的东西，例如区间最大值等等） 尤其是涉及到单点修改的操作的时候 如果是用普通的线性数组 和 线性的求和数组的话 复杂度会达到O(n)而使用树状数组 则可以将这个复杂度 降低至O(logn)怎么使用树状数组假设用一个a数组来储存这个区间中的元素（索引从1开始）树状数组的最基本的使用 主要有四个部分组成int ...
2020-01-16 15:57:09
404
原创 【题解】PAT 1018 Public Bike Management
读题：最短路径问题的变化，需要从一个节点走最短路径到另一个节点（最短路径可能不止一条），每个节点都会有一些点数，然后要求输出满足点数大于等于某一个值，且点数尽可能小的最短路径...
2022-07-26 18:42:19
146
1
原创 【题解】PAT 1014 Waiting in Line
然后利用优先队列，根据题目意思，离队时间小且所在队伍编号较小的排在前面，首先对于N个窗口中的第。，其中记录三个信息客户编号（用于输出），客户离队时间（从0开始计时），客户所在队伍编号。个窗口，可往队列中加入M个客户编号为0，离队时间为0，所在队伍编号为i的元素。前开始进行服务，则一直到其完成业务之后才关门）然后按照优先队列入队出队的规则安排客户即可。分钟（注意，如果客户在。那么可以构建一个结构体。......
2022-07-25 18:23:10
281
原创 【题解】PAT 1007 Maximum Subsequence Sum
注意还有特殊情况Incasethatthemaximumsubsequenceisnotunique,outputtheonewiththesmallestindicesiandj(asshownbythesamplecase).【如果有多个最大值序列，则输出i和j最小的】建立动态规划数组dp，其中dp[i]表示以元素N[i]结尾的子序列的最大和，则。读题，给出一个数组N，求这个数组的一个子序列，使得这个子序列的和最大。——很明显的动态规划问题。...
2022-07-16 08:58:10
80
原创 【题解】PAT 1006 Sign In and Sign Out
本题大意为，给出进出教室的同学的出入时间，求出最早来到教室和最晚离开教室的同学的ID。那么这个题很明显的是考察字符串操作，至于对于时间的比较，直接将时间字符串比较即可。
2022-07-15 17:32:58
87
原创 【题解】PAT 1005 Spell It Right
原题链接：1005 Spell It Right首先读题，给出一个非零整数，要求求出其各位数字之和，并要求以英文的方式输出这个很简单，只需要注意题目输入的N≤10100N\le 10^{100}N≤10100，说明此时肯定需要使用字符串类型来接收这个变量（还需要注意输入：0）...
2022-07-14 18:15:49
276
原创 【题解】PAT 1004 Counting Leaves
原题链接：1004 Counting Leaves首先读题，本题需要我们统计一棵树中叶子节点的个数，按照题目中的要求，需要逐层统计，即：那么很简单，我们只需要使用BFS逐层统计叶子节点个数即可，为了方便，我们可以使用父亲-兄弟的方式来建树，如图所示：这样更加方便使用BFS进行逐层遍历...
2022-07-14 17:59:58
99
原创 【题解】PAT 1003 Emergency
原题链接：1003 Emergency首先读题，这是一个图论的问题，需要从一个城市走最短路径到另一个城市（最短路径可能不止一条），每个城市都会有一些人手，同时要求求出走这些最短路径最多召集多少人手。要求输出最短路径的条数和最多召集多少人手。首先解决要求出最短路径的条数，这个只需要在Dijkstra算法上做一些简单的改动即可，回顾一下最经典的Dijkstra算法：要求出最短路径的条数，只需稍微修改一下即可：同时还可以求出最多召集的人手数：综上，对于目标城市，只需要输出...
2022-07-14 10:44:27
87
原创 【题解】PAT 1002 A+B for Polynomials
原题链接：1002 A+B for Polynomials首先读题，题目的是要求两个多项式的和，输入有两行，分别用来表示这两个多项式，每一行的第一项K为该多项式的项数，每一项用两个值NiN_iNi和aNia_{N_i}aNi来表示，即多项式可表示为f(X)=∑i=1KaNiXNif(X)=\sum\limits_{i=1}^K a_{N_i}X^{N_i}f(X)=i=1∑KaNiXNi，最后输出也使用同样的方法输出。那么理解题意之后，解答题目就很简单了，同时注意到0≤Nk＜⋯＜N1≤10
2022-07-13 21:49:09
85
原创 【题解】剑指 Offer 12. 矩阵中的路径
原题链接：剑指 Offer 12. 矩阵中的路径给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。限制其实就是很简单的深搜+回溯，每一次记录访问过的方格坐标，如果一直到单词的最后
2022-07-09 22:00:08
57
原创 【题解】剑指 Offer 11. 旋转数组的最小数字
原题链接：剑指 Offer 11. 旋转数组的最小数字把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …,
2022-07-08 18:00:15
70
原创 【题解】剑指 Offer 10- I. 斐波那契数列
原题链接：剑指 Offer 10- I. 斐波那契数列写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。约束利用斐波那契数列的递推关系式进行计算首先对于斐波那契数列的递推关系式可以将其扩展为一个矩阵：F(n)=F(n−1)+F(n−2)⇒[1110][F(n)
2022-07-08 16:48:36
1315
原创 【题解】剑指 Offer 09. 用两个栈实现队列
原题链接：剑指 Offer 09. 用两个栈实现队列用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )限制...
2022-07-04 21:35:57
54
原创 【题解】剑指 Offer 07. 重建二叉树
原题链接：剑指 Offer 07. 重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。示例输入2约束首先是二叉树遍历的思路前序遍历中序遍历利用中序遍历的特点遍历前序遍历查找根节点的同时进行递归建树即可，思路如图所示...
2022-07-02 11:06:40
56
原创 【题解】剑指 Offer 06. 从尾到头打印链表
原题链接：剑指 Offer 06. 从尾到头打印链表输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。约束利用栈后入先出的性质首先遍历整个链表，获得其中元素个数，然后开一个数组从后往前将这些元素填进去即可...
2022-07-02 09:27:46
50
原创 【题解】剑指 Offer 05. 替换空格
原题链接：剑指 Offer 05. 替换空格请实现一个函数，把字符串 s 中的每个空格替换成"%20"。限制
2022-07-01 14:49:57
106
原创 【题解】剑指 Offer 04. 二维数组中的查找
原题链接：剑指 Offer 04. 二维数组中的查找在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。限制首先可以确定思路使用二分解决转换一下，利用好从左到右，从上到下递增的特点，那么就可以将其转为一个搜索二叉树...
2022-07-01 14:35:20
105
原创 【题解】剑指 Offer 03. 数组中重复的数字
原题链接：剑指 Offer 03. 数组中重复的数字找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。限制暴力分析，直接建立一个长度为n的bool数组，然后遍历整个nums数组判断重复注意到数组长度为n，且所有数字都在0~n-1范围内，所以可以采用下标与值对号入座的方法判断重复对于nums进行遍历：...
2022-07-01 13:30:52
53
原创 大型数据库复习笔记——PL/SQL
PL/SQL介绍【优点】PL/SQL是ORACLE在标准SQL语言上的过程性扩张，允许嵌入SQL语句，允许定义常量和变量，允许过程语言结果，允许使用异常处理ORACLE错误。PL/SQL能提高程序的运行性能，将PL/SQL块内嵌到应用程序中，最大优点可以降低网络开销，提高应用程序的性能。PL/SQL提供模块化的程序设计功能，简化应用程序的开发和维护工作，可以将企业规则和商业逻辑集成到PL/SQL程序中,包括存储过程，函数，包中，然后在应用程序中调用相应的功能。具有过程语言控制机构，PL/SQL允
2021-12-25 11:29:07
794
原创 大型数据库复习笔记——Oracle数据库
描述Oracle服务器的体系结构及其主要构件列举用户连接到Oracle实例所涉及的结构双机模式：RAC/HOT STANDBYOracle服务器主要组件【用户进程无法直接与服务器进行交互，必须通过服务器进程与数据库交互】注意：实例不是数据库，数据库主要是指用于存储数据的物理结构，总是实际存在的实例是由操作系统的内存结构和一系列进程组成的，可以对实例进行启动和关闭一台计算机上可以创建多个Oracle数据库——要同时使用这些数据库就需要创建多个实例因此Oracle系统要求..
2021-12-25 11:26:21
966
原创 图论（十一）——多源最短路径之Floyd算法
算法思想如下：首先使用邻接矩阵建图，构建邻接矩阵DDD（邻接表反而会使得时间复杂度和空间复杂度变大，链式向前星反而无法处理这类问题，因为需要经常访问矩阵元素并更新）此外，还可以加上一个路径回溯矩阵RRR，RijR_{ij}Rij表示要从节点iii到节点jjj的路径为：从节点iii通过最短路径到达节点RijR_{ij}Rij再通过最短路径到达节点jjj然后“插入”节点，每“插入”一个节点，则更新矩阵DDD的值（min），若进行了更新，则修改路径回溯矩阵RRRint dir[node_num][
2021-08-02 10:34:52
156
原创 《数据库》笔记整理
数据库 学习笔记CH01概念数据库（DB）的概念文件系统管理数据存在的局限：数据冗余与非一致性文件格式不相容，数据冗余程序依赖于数据新任务要写新程序数据孤立文件格式不相容完整性问题完整性约束 隐于 程序难修改更新的原子性保证问题并发访问未加控制的并发访问会导致不一致性安全性问题数据库是长期存储在计算机内有组织的、大量的、相关的、可共享的数据集合数据库管理系统（DBMS）的概念一个数据库管理系统是管理数据库的一些程序的集合
2021-03-16 10:11:49
2221
原创 《编译原理》笔记整理
编译原理 笔记整理1.1 《编译原理》引论基本概念——发展机器语言汇编语言高级语言工具语言基本概念——翻译程序把某一种语言程序（称为源语言程序）等价的转换成另一种语言程序（称为目标语言程序）的程序如：中英互译系统、DBMS语言（DDL、DCL）基本概念——编译程序把某一种高级语言程序等价的转换成另一种低级语言程序（如：汇编语言或机器语言程序）的程序编译程序分类：诊断编译程序&优化编译程序交叉编译程序&可变目标编译程序运行基本概念——解释程序
2021-03-16 10:02:46
8554
原创 Qt——当父窗口关闭时同时关闭子窗口
例如以下这种情况：Dialog窗口是在MainWindow窗口中创建的子窗口那么要做到在关闭MainWindow时自动关闭Dialog，只需要在代码中修改：MainWindow::MainWindow(){ Dialog *dialog = new Dialog(this);}那么如果想要在MainWindow关闭时保持Dialog不关闭，则修改代码：MainWindow::MainWindow(){ Dialog *dialog = new Dialog(0); //Dialog *d
2020-07-16 21:58:37
3590
1
原创 【Codeforces 1352C】K-th Not Divisible by n（暴力）
原题链接：K-th Not Divisible by n原题截图：题目大意：输入n和k，求第k个不能被n整除的正整数解题思路：直接暴力就好了计算从1到k的所有可以被n整除的正整数个数temp用cnt记录在前面的过程中已经生效了的被n整除的正整数个数，k=k+temp-cnt，cnt=cnt+temp重复操作1和操作2，知道temp-cnt=0AC代码：#include<cstdio>using namespace std;int main(){ int t,n,
2020-05-15 12:04:47
324
原创 【Codeforces 1349A】Orac and LCM（数论⭐）
原题链接：A. Orac and LCM原题截图：题目大意：输入一个数组a，由a中的任意两个元素s[i]和s[j]的最小公倍数构成另一个数组t，求t中所有元素的最大公约数题目中算是有一个小提示吧 t = { lcm(aia_iai,aja_jaj) | i<j }，让人容易想到固定i，aia_iai与ai+1a_{i+1}ai+1到ana_nan的所有元素的最小公倍数构成一个子集m，这样所有子集m的最大公约数构成一个新的集合q，那么集合q的所有元素的最大公约数就等于集合t的所有
2020-05-14 17:35:01
358
原创 【Codeforces 1348D】Phoenix and Science（思维）
原题链接：D. Phoenix and Science原题截图：题目大意：某人一开始有1个混乱度（mess）为1的细菌，在白天时，每个细菌都可以将其分裂为两个混乱度相同的细菌，并将其混乱度均分给这两个细菌【例如：一个混乱度为1的细菌可以变成两个混乱度为0.5的细菌】在晚上时，每个细菌的混乱度均会增加1假设这个人可以控制每天会有几个细菌将会分裂问：最少经过d个夜晚，使得所有细...
2020-05-06 18:40:41
249
1
原创 【Codeforces 1348B】Phoenix and Beauty（思维）
原题链接：B. Phoenix and Beauty原题截图：题目大意：大概就是给出一个长度为n数组a，需要在其中加入一些元素，使得这个数组的任意一段长度为k的子数组（subarray）的元素之和都相等输出加入这些元素后，数组的长度并输出数组解题思路：既然在题目中说，不存在方案的情况输出-1，那么就想一想需要怎么判断是否存在解决方案：假设数组处理完之后的结果为数组b，那么来看看这...
2020-05-05 09:10:53
255
原创 图论（五）——最小生成树之Prim算法
最小生成树对于一张边带权的连通图 G = (V , E)，由numNode-1条边和numNode个节点连通子图，且这个子图的边权值之和最小，则称这个子图为图G的最小生成树Prim算法该算法的思想简述如下：在图中取一点x，将其看作一个集合M，将其他的所有节点看作一个集合N遍历x的所有边，找到终点位于集合N中且权值最小的边，将这个终点y加入到集合M中遍历y的所有边，找到终点位于集合N...
2020-04-30 16:01:47
179
原创 【Codeforces 1340A】Nastya and Strange Generator（思维）
原题链接：A. Nastya and Strange Generator原题截图：题目大意：有一个长度为n的数组s，然后要把1~n这n个整数从小到大、按照“规则”填入数组中，然后判断能否得到input中的目标数组“规则”：r数组：r[i]代表此时数组s中从下标r[i]到n的第一个未填入的位置（若没有未填入的位置，则r[i]为undefined，用*表示）count数组：count[...
2020-04-30 10:46:32
385
原创 【Codeforces 1342D】Multiple Testcases（思维+暴力）
原题链接：D. Multiple Testcases原题截图：题目大意：有一个有n的元素的数组m，要将其分成若干组，其中每一组中大于等于i的元素不超过c[i]个，问：最少划分为几个组并输出分组的方案解题思路：首先找出最少分成几组，因为在每一组中大于等于i的元素最多为c[i]个，所以不妨统计数组m中[i,k]的元素为p个，那么最少分组的个数就是ans=max(ans, ⌈p/c[i...
2020-04-29 15:07:53
263
原创 【Codeforces 1343E】Weights Distributing（最短路）
原题链接：E. Weights Distributing原题截图：题目大意：给出一张有n个节点和m条边的无向连通图，再给定m的权值，要求将这m个权值分配到m条边上，使得从a到b再从b到c的距离最短，输出最短距离解题思路：这个问题的难点有两个：路径要求从a到b再从b到c要自己分配边权值那么首先简化问题：如果是从x到y，得出一个分配的方案使得路径距离最小那么自然想到的...
2020-04-27 11:12:09
138
原创 【Codeforces 1343D】Constant Palindrome Sum（打标记）
原题链接：D. Constant Palindrome Sum原题截图：题目大意：对于一串长度为n的数组a（n为偶数），要求修改其中的若干元素，使得对于任意i，有a[i]+a[n-i+1]=x，问：最少修改多少个元素解题思路：因为x不是一个确定的值，那么对于任意一对a[i]+a[[n-i+1]，通过改变这两个的值，都可以变成从2到2*k的任意一个值，只是改变的次数有区别，假设两个数中...
2020-04-24 16:08:26
179
1
原创 图论（十）——网络流的最大最小费用最大流问题
费用流在求网络的最大流的同时加上一个条件：每条边的流过流的单位费用，由此得出费用流的问题【其实费用流就可以算是最大流和最短路最长路的综合】费用流问题分为两类：最小费用最大流（最大流+最短路）最大费用最大流（最大流+最长路）最小费用最大流为什么说最小费用最大流就是最大流+最短路呢，可以这样想：有一条流量为f的增广路，对于其中的每一条边都有一个单位费用cost[i]，每条边的流量都...
2020-04-08 16:34:49
1689
原创 图论（九）——网络流的最大流问题之Dinic算法
最大流图论（五）——网络流的最大流问题引入Dinic算法回顾EK算法【图论（六）——网络流的最大流问题之Edmonds-Karp算法】，发现EK算法在每次BFS搜索全图的过程中，只会得出一条增广路，这样的效率比较低，所以需要优化，优化之后的算法就叫做Dinic算法节点的层次：从起点S到节点i所需要经过的最少的边的数目如果用BFS在网络中得到节点层次的分层图，再用DFS搜索这个分层图（...
2020-04-07 21:54:16
216
原创 图论（六）——最小生成树之Kruskal算法
最小生成树对于一张边带权的无向连通图 G = (V , E)，由numEdge-1条边和numNode个节点无向连通子图，且这个子图的边权值之和最小，则称这个子图为图G的最小生成树Kruskal算法该算法的思想简述如下：建立并查集，每个点自己为一个集合将所有边（from , to , weight），按权值weight从小到大排序，依次扫描对于边（from , to , weigh...
2020-03-30 22:46:51
221
原创 图论（七）——网络流的最大流问题引入
网络流一个网络 G= (V , E) 是一张有向图，图中的每一条边 (x , y) ∈ E，其权值w的意义为 最多可以将w个物品从节点x运输到节点y，所以这个权值又称为边的 容量，记为c(x , y)；此外，在图中没有标出的边，即 (x , y) ∉ E，则c(x , y) = 0然后还有两个指定的特殊的节点 S ∈ V，T ∈ V（S != T）分别...
2020-03-30 22:06:00
468
原创 图论（八）——网络流的最大流问题之Edmonds-Karp算法
增广路为了解决最大流问题，再引入一个概念：剩余容量【c(x , y)-f(x , y)】如果可以找到一条从源点出发，经过中间节点，流向汇点，且其中每一条边的剩余容量均大于0的路，就称这条路为一条增广路，假设可以知道这一条增广路中所有的边的最小剩余容量为p，那么对于整个网络系统而言，就可以增加一个流量为w的流从源点通过这一条路流向汇点，那么这个网络的流量就增加了w。如果找到了所有的增广路，已...
2020-03-30 22:04:37
1300
1
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人