- 博客(275)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 2021南京理工大学计算机考研初试复试经验帖
写下这篇帖子是之前考研也借鉴了前人的经验，现在自己上岸了，一方面给后面的学子作参考，另一方面算是给整个考研历程画一个句号。个人情况本科普通双非，绩点中上，参加了ACM工作室，大学四年基本上在搞竞赛，水平在区域赛铜左右，无项目。报考的是南京理工大学计算机专硕（计算机技术），初试【政治 + 数二 + 英二 + 877专业课】，复试【上机 120 + 笔试 100 + 面试 80】，其中：专业课【数据结构 50 + 计算机组成原理 50 + 操作系统 50】，笔试【计算机网络 50 + 数据库系统 50】，
2021-09-20 21:54:13
9747
9
原创 Leetcode 3. 无重复字符的最长子串（双指针）
Leetcode 3. 无重复字符的最长子串题目给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。分析思路找符合特定条件的子串，首先暴力就是枚举。为了方便枚举可以将其分类为以 s[i] 结尾的字符串集合，这样就变为找所有集合中最大值。进一步，对于每一个结尾为 s[i] 的字符串，要找到最左边的 j ,那么 s[j -> i]即为当前集合的目标字串，i - j + 1 即为当前集合的答案。如何找 j，可以从 i 往前扫，直到 s[j-1 -> i] 中有重复元素。
2021-01-13 12:19:27
311
原创 Leetcode 2. 两数相加（模拟）
题目给两个非空链表，每个链表代表一个数，返回两个链表之和分析思路：直接模拟即可实现：维护一个进位 t????：Leetcode 链表题可以设置一个虚拟头节点 dummy，使头节点一般化，便于操作。代码/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} *
2021-01-12 22:21:51
266
原创 Leetcode 1. 两数之和（哈希）
题目给一个数组，和一个目标值 target，要找到数组中两个数加起来等于 target，并返回两个数下标，注意两个数不能是相同的数。只有一种答案。分析当然可以暴力，O(n^2)枚举所有两个数的可能。O(n) 做法是，利用两个数之间的联系，固定一个数 a，另外一个数也随之固定：target - a。可以用哈希预处理数组，将第二个循环优化掉。代码思路就是，因为一定存在一对数符合，可以固定第二个数，在当前位置前面找第一个数。注意 map 底层红黑树，平均 O(logn)；unordered_map
2021-01-12 20:38:37
233
原创 《暗时间》思考总结
《暗时间》《暗时间》是一本关于思维，高效学习，心理学方面的书籍，作者是计算机专业的，因此视角对于程序员比较亲切。下面是一些摘抄句子，加上自己的思考。（黑体原文）第一篇：暗时间1. 暗时间思考与效率实际投入的是时间和效率的乘积。开篇就强调了学习效率的重要性。因为看书并记住书中的东西只是记忆，并没有涉及推理，只有靠推理才能深入理解一个事物，看到别人看不到的地方，这部分推理的过程就是你的思维时间，也是人一生中占据一个显著比例的 ”暗时间”我所理解的暗时间就是使自己难受的思考时间，好多人不推荐考
2021-01-12 17:35:29
269
2
原创 【CCF-CSP】201403-2 窗口（模拟）
【CCF-CSP】201403-2 窗口题目先给出 n 个窗口（窗口的左边范围），之后有 m 次点击（即一个坐标），每次点击输出当前坐标最顶层的窗口序号，同时将当前窗口移动到最顶层。分析用链表存窗口的优先级，每次点击按照优先级遍历所有窗口，看自己在哪个窗口的范围，并将找到的窗口移动到链表的前端。#include <bits/stdc++.h>using namespace ...
2020-04-17 21:15:21
258
原创 【CCF-CSP】201403-1 相反数（模拟）
#include <bits/stdc++.h>using namespace std;#define d(x) cout<<x<<endltypedef long long ll;const int INF = 0x3f3f3f3f;const int N = 2e3 + 10;int n, ans, num;int a[N], b[N];...
2020-04-17 21:11:16
202
原创 【CCF-CSP】201312-5 I’m stuck!（暴力bfs）
【CCF-CSP】201312-5 I’m stuck!题目给一个迷宫，50 * 50，S起点 T终点，每种符号代表下一步能走的方向，问满足以下条件的格子数：能从S出发到达从当前格子出发到达不了 T。分析迷宫很小，从一个点开始 BFS 最多 50 * 50，直接按照题目意思暴力 BFS 即可。先找从 S 出发能够到达的点，再 BFS 检验这个点是否满足第二个条件。O（50 * 5...
2020-04-02 11:48:07
295
原创 超好用网站收藏
文件格式加加PDF：https://www.addpdf.cnSmallPDF：https://smallpdf.com/cnPDF. io：https://pdf.io/tw/iLovePDF：https://www.ilovepdf.com/zh-cnPDF派：https://www.pdfpai.comLightPDF：https://lightpdf.com/zh/Cleve...
2020-03-23 11:27:49
7608
原创 【CCF-CSP】201312-4 有趣的数 (划分状态dp）
【CCF-CSP】201312-4 有趣的数题目给一个数 n，求长度为 n 且满足一下条件的数字串的个数，结果取模。只包含 0, 1, 2, 3，且必须包含0 不作为开头所有 0 在 所有 1 前面，所有 2 在所有 3 前面分析遇到这样的题，肯定要先写几项，观察规律。可以看出 2 一定开头，因为数字 1、3都有限制，而 0 又不能作为开头。不过好像没什么用。在写规律的时候发现...
2020-02-22 23:14:27
337
1
原创 【CCF-CSP】201312-3 最大的矩形（单调栈）
【CCF-CSP】201312-3 最大的矩形题目给 n 个数，代表 n 个矩形的高度，将 n 个矩形平放，求能剪出的最大矩形的面积。n < 1e3。分析这题跟 POJ-2559 一样，不过数据很水，暴力也行。用单调栈可以达到 O(n) 的做法。对于每个数，找到向左向右第一个比当前数小的数的位置，就可以确定包含当前数的矩形的最大宽度，而高度即是当前数的值。#include &...
2020-02-21 18:37:46
345
1
原创 【CCF-CSP】201312-2 ISBN号码（模拟）
【CCF-CSP】201312-2 ISBN号码题目给出一个字符串代表 ISBN 号，按题目给出公式检查最后一个校验位是否正确，正确输出 “Right”， 反之输出正确 ISBN 号。分析#include <bits/stdc++.h>using namespace std;#define d(x) cout<<x<<endltypedef lo...
2020-02-21 17:33:25
264
原创 【CCF-CSP】201312-1 出现次数最多的数（模拟）
【CCF-CSP】201312-1 出现次数最多的数题目给 n 个数，求出现次数最多且值最小的数字。分析#include <bits/stdc++.h>using namespace std;#define d(x) cout<<x<<endltypedef long long ll;const int INF = 0x3f3f3f3f;co...
2020-02-21 17:08:20
175
原创 【PAT 甲级】1011 World Cup Betting (20分)（模拟）
1011 World Cup Betting (20分)题目有三场比赛，每场比赛都有三种结果 W-win，T-tie，L-lose，每种结果有一定的赔率，分别输出每场比赛赔率最大的结果，并输出按照题中公式输出最大利润。分析甲级题目不难，都是些模拟题，就是英语看的太捉急了【看不懂。。】#include <bits/stdc++.h>using namespace std;#...
2020-02-17 23:17:34
251
原创 【PAT 甲级】1010 Radix (25分)（二分）
1010 Radix (25分)题目字符串形式给出两个数 n1, n2，告诉其中一个数的进制 radix，要使两个数相等，求另外一个数的进制的最小取值，如果无法满足输出 “Impossible”。分析进制越大，数值越大，对于另外一个数二分找进制即可。上界，给出进制数 n1 的数值；下界，n2 中出现的最大的数 + 1。特殊情况，两个数为 0 0，输出 1。注意二分时 long long...
2020-02-17 14:31:50
192
原创 【PAT 甲级】1009 Product of Polynomials (25分)（模拟）
1009 Product of Polynomials (25分)题目多项式相乘，输入有两行，分别代表两个多项式的指数 exponent，和系数 coefficient。分析按题目模拟，两个循环。注意系数不为零的部分。#include <bits/stdc++.h>using namespace std;#define db(x) cout<<x<<...
2020-01-31 15:01:38
183
原创 【PAT 甲级】1008 Elevator (20分)（模拟）
1008 Elevator (20分)题目电梯开始在 0 层，给出一个序列，代表电梯要到达的顺序，上一层花费 6，下一层花费 4，每层停 5，计算总时间。分析直接模拟即可，#include <bits/stdc++.h>using namespace std;#define db(x) cout<<x<<endltypedef long lon...
2020-01-30 17:52:02
198
原创 【PAT 甲级】1007 Maximum Subsequence Sum (25分) (线性DP）
1007 Maximum Subsequence Sum (25分)题目求序列的最大连续子序列和。序列长度不超过 1e4。分析经典 DP 问题，
2020-01-29 21:22:30
184
原创 【PAT 甲级】1006 Sign In and Sign Out (25分) (模拟）
1006 Sign In and Sign Out (25分)题目给出每个人来和走的时间（时：分：秒），输出最早来和最晚走的人的名字。分析直接根据题意模拟即可。写两个比较函数分别以来和走的时间排个序。#include <bits/stdc++.h>using namespace std;#define db(x) cout<<x<<endlty...
2020-01-29 20:29:37
187
原创 【PAT 甲级】1005 Spell It Right (20分)（水）
1005 Spell It Right (20分)题目给一个 100 位以内的数，计算所有数字之和，并将结果的每一位用英文表示。分析直接模拟即可，注意特判 0。#include <bits/stdc++.h>using namespace std;#define db(x) cout<<x<<endltypedef long long ll;...
2020-01-28 20:36:50
216
原创 【PAT 甲级】1004 Counting Leaves (30分)（dfs水）
1004 Counting Leaves (30分)题目给一颗节点数不超过 100 的树，求每一层的叶子节点的个数。分析建树之后记录每个节点有无孩子，之后 dfs 一下记录每个节点在第几层。将信息归总统计一下即可得出每层叶子节点数。#include <bits/stdc++.h>using namespace std;#define db(x) cout<<x...
2020-01-28 20:13:42
134
原创 【PAT 甲级】1003 Emergency (25分)（dfs + STL）
1003 Emergency (25分)题目给一个顶点数不超过 500 的图，每个顶点有权值，边也有权值。给定起点和终点，求边权值最短的路径集合（也就是说最短的路径不止一条，而且每条最短路径对应一个顶点权值和），输出这个集合的路径个数，以及集合中顶点和的最大值。分析题目在求最短路径的基础上，还增加了每条路径对应的顶点权值和。所以可以用 dfs 求出所有最短路径，并将对应的权值和放入到 m...
2020-01-27 18:01:20
228
原创 【PAT 甲级】1002 A+B for Polynomials (25分)（map）
1002 A+B for Polynomials (25分)题目给出两个多项式的系数和指数，求相加后的多项式系数和指数。分析用 map 存系数和指数的对应关系，将系数加到相同的指数里面即可。注意只需要输出不为零的项。#include <bits/stdc++.h>using namespace std;#define db(x) cout<<x<<...
2020-01-15 19:59:26
269
原创 【PAT 甲级】 1001 A+B Format (20分)（水）
1001 A+B Format题目给两个数 a, b，输出 a + b 的和，但是输出格式有要求，每三个一组用逗号分开。分析先判断正负，模拟即可。#include <bits/stdc++.h>using namespace std;#define db(x) cout<<x<<endltypedef long long ll;const i...
2020-01-15 19:12:19
157
原创 AcWing 278. 数字组合（简单背包问题）
AcWing 278. 数字组合题目给你 n 个数，让你从中选出一些数，使其和为 m，问一共有多少方案？n <= 100, m <= 10000分析简单的背包问题。看成背包容量为 m，n 个物品。①：状态表示集合：dp[i][j]dp[i][j]dp[i][j] 表示用前 i 个数，和为 j 的所有方案的集合属性：方案的数量②：状态转移根据最后一位来划分集合，选...
2020-01-10 08:50:49
391
原创 操作系统期末复习
《现代操作系统》期末复习第一章 引论① 内容② 习题1、 操作系统的两大主要作用是什么？：1. 作为扩展机，为上层提供抽象。2. 作为资源管理器9、在建立一个操作系统时有几个设计目的，例如资源利用、及时性、健壮性等，请列举两个可能相互矛盾的设计目的。：考虑公平性和实时性。 公平性要求每个进程都以公平的方式分配其资源，没有任何进程获得超过公平份额。 另一方面，实时性需要根据不同进程必...
2019-12-17 15:55:34
2700
原创 JSP 复习总结
JSP 复习第二章 基本语法在 " <%! " 和 “%>” 之间声明变量和方法。声明的变量在整个 JSP 页面都有效，同时多个用户访问时会互相影响，用 synchronized 修饰的成员变量同一时间只能被一个线程访问。在" <%!" 和 “%>” 之间插入 Java 程序片，并且按顺序执行。程序片里面的变量都是局部变量，不互相影响。可以在程序片中插入 HTML...
2019-12-11 22:39:52
2222
1
原创 AcWing 277. 饼干 (特殊的集合划分方式）
AcWing 277. 饼干题目有 m 块饼干分给 n 个人，要求每人至少分一块。同时每一个人有一个怨气值 a[i]，假设有 g[i] 个人比他分到的饼干多，那么这个人产生的怨气就是 a[i] * g[i]。问最后怎么分配饼干使得怨气值总和最小，输出任意具体方案？分析所有分配方案的集合太大了。考虑缩小最优解集合。首先肯定要分配的尽可能一样，这样就不会产生怨气。如果不可避免的产生怨气，那么...
2019-11-26 20:32:00
329
原创 AcWing 276. I-区域（状态机 dp + Hard）
AcWing 276. I-区域题目给出 n 行 m 列矩阵，和一个参数 k，求 k 个格子组成的凸联通块最大权值和。（凸连通块就是形状是凸性的）。n < 30, m <分析此处凸包定义不严谨，可以直接理解成连续的若干行，每行的左端点列号先递减、后递增，右端点列号先递增、后递减。（这里的递增递减都是不严格的）那么这样就可以从每一行入手，考虑每行选取的起点和终点。①： 状态...
2019-11-14 22:39:50
210
2
原创 AcWing 275. 传纸条 (dp 状态优化）
AcWing 275. 传纸条题目给一个 m 行 n 列矩阵，当前位置在（1，1），需要走到（m，n）然后再走回来，走到一个点可以拿走当前的值，但是每个点只能走一次，求最后能得到的最大值。分析如果只有一条路线就很简单了。现在要回去，可以看成同时从（1，1）走两条不相交的路线，状态表示可以用 dp[x1][y1][x2][y2]dp[x1][y1][x2][y2]dp[x1][y1][x2]...
2019-11-14 19:31:04
208
原创 AcWing 274. 移动服务 (递推三种出边dp）
AcWing 274. 移动服务题目在平面上有 L 个点，有三个服务员在初始给出的三个点上，并且题目给出平面上点两两之间的距离。随后有 n 个请求，每发出一个请求，需要派一个服务员去（只能去一个），花费就是距离。问满足所有请求的最小花费。L < 200， n < 1000分析首先爆搜肯定能出结果，对于每个请求枚举三个服务员。思考如何用动态规划做：①： 状态表示（经验）集...
2019-11-13 22:12:16
167
原创 AcWing 273. 分级 （序列型DP + 前缀最值优化）
AcWing 273. 分级题目给一个序列 A，长度 n < 3e3。你需要构造出序列 B，且序列 B只能不增或者不降。求 S 的最小值。S=∑i=1N∣Ai−Bi∣S=\sum_{i=1}^{N}\left|A_{i}-B_{i}\right|S=i=1∑N∣Ai−Bi∣分析题目关键（性质）：一定存在一组最优解 B，B 序列的每一个元素都在 A 序列中出现过。其实自己画几个...
2019-11-12 21:06:45
305
原创 AcWing 272. 最长公共上升子序列 (线性DP + 前缀最值优化）
AcWing 272. 最长公共上升子序列题目名字就是题目，给出两个序列A，B，求最长公共上升子序列。(n < 3e3)分析线性dp。①： 状态表示（经验）集合：dp[i][j]dp[i][j]dp[i][j] 表示所有在 A[1..i]A[1..i]A[1..i] 和 b[1..j]b[1..j]b[1..j] 中出现过，且最后以 b[j]b[j]b[j] 结尾的最长公共上升...
2019-11-12 19:44:01
191
原创 Acwing 271. 杨老师的照相排列（线性dp求方案数）
Acwing 271. 杨老师的照相排列题目分析https://www.bilibili.com/video/av69678938根据闫氏 dp 分析法，
2019-11-11 16:41:37
348
原创 51nod 1880 单词究错（模拟）
51nod 1880 单词究错题目：给你 n 个字符串当词典， 还有 m 个字符串当作查询，每次查询输出字典中与当前询问字符串差一个字符不一样的字符串（增加，减少，修改）。分析：模拟水题，直接暴力枚举即可。只不过做这个题时 oj 一直报错，最后才发现有个返回值为 int 的函数没有写返回语句导致 wa。记录一下。#include <bits/stdc++.h>using n...
2019-11-07 21:55:35
197
原创 《算法竞赛进阶指南》动态规划习题与总结
《算法竞赛进阶指南》0x50 动态规划算法网站 acwing.com，提供了《算法竞赛进阶指南》0x50 动态规划节的所有习题。同时组织了打卡活动，而且有大佬解题视频。平时没事准备刷完这一章。地址：0x50 动态规划一、线性DP...
2019-11-06 21:54:50
299
原创 LeetCode #12 双周赛题解（水 + 水 + 树形DP + 区间dp）
LeetCode #12 双周赛5097. 力扣排行榜题目：设计一个排行榜，满足插入、前缀和、排序。分析：数据范围很小，用不到 logn 的数据结构，直接暴力即可。用 mapmapmap 存编号对应成绩，每次查询暴力排序找前 k 和。class Leaderboard {public: map<int, int> mp; Leaderboard() {} ...
2019-11-03 21:44:17
262
原创 LeetCode #161 场周赛题解（思维 + 水 + 模拟 + 裴蜀定理）
LeetCode #161 场周赛（感觉 LeetCode 上的题不需要考虑复杂度，能想出来做法就能过5247. 交换字符使得字符串相同题目：给你两个只包含 ‘x’, ‘y’ 的字符串 s1,s2s1, s2s1,s2 ，每次操作可以交换两个分别位于两个字符串中的字符，问最少交换几次可以使字符串变为完全相同。分析：首先两个字符串 ‘x’,‘y’ 总数不是偶数，都是不行的。只关心字符串不...
2019-11-03 16:30:47
217
原创 51nod 1091 线段的重叠 （贪心）
51nod 1091 线段的重叠题目给出 nnn 条线段，问任意两条线段最大重叠区间长度。n<5e4n < 5e4n<5e4分析贪心，先按起点升序，终点降序排序，之后扫一遍所有区间。由于按起点升序，所以后面的区间起点一定小于前面的，因此对于当前区间，维护出现过的最远右端点 pospospos，考虑吧 pospospos 与当前区间的相对位置跟新答案即可。#include...
2019-11-01 18:45:56
172
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人