- 博客(88)
- 问答 (1)
- 收藏
- 关注
RSS订阅原创 红黑树实现（代码：插入、删除、检测、打印树的结构、随机生成数据测试）
插入结点使用维基百科红黑树的插入实现多种情况分类讨论，log级别代码如下 /* 先找到合适位置插入，之后再根据父节点颜色判断是否进行调整 */ void insert(int key, T value) { Node *insertNode = new Node(key, value); Node *traver = root; while (traver) {
2022-05-10 18:37:26
646
原创 第十五章-进程地址空间-linux内核设计与实现
地址空间把有相同地址空间的进程称为线程一个进程访问了不在有效范围中的内存区域，或者以不正确的方式访问了有效地址，那么内核就会终止进程内存区域包含的内存对象代码段：可执行文件代码的内存映射数据段：可执行文件已经初始化的全局变量内存映射未初始化的全局变量进程的用户空间栈（注意进程的内核栈独立存在，由内核维护）C库或者动态连接程序等共享库的代码段内存映射文件共享内存段匿名的内存映射内存描述符内存描述符mm_struct结构体表示进程地址空间mm_strcutmm_use
2022-04-29 18:34:25
418
原创 第十三章-虚拟文件系统-linux内核设计与实现
文件系统抽象层内核在底层文件系统接口上建立了一个抽象层，这个抽象层可以让linux支持各种文件系统VFS定义了所有文件系统都支持的基本，概念上的接口和数据结构，实际文件系统在统一的接口和数据结构下隐藏了细节用户空间：write() – 》VFS:sys_write() --》文件系统：文件系统的写方法 --》物理介质UNIX文件系统VFS把目录当做文件看待文件本身：文件相关信息：inod（索引结点）：关于文件的访问控制权限，大小，拥有者，创建时间。存储在单独的块中文件控制信息：存储在超
2022-04-28 13:20:43
443
原创 外部排序~
被面试官问了个对数组求交集，但是内存只能装载一个数组。然后想到数据结构的外部排序，但是当时没去看，现在补一下对于这个面试问题的个人解法，可能不对，欢迎交流先对两个数组用外部排序.使得有序然后分别对两个有序数组掉一部分到内存，然后进行求交集，对两个有序数组求交集用双指针即可，具体执行搜索了解朋友的解法 感觉很妙！！！将数组记录各自哈希到文件，用各自数组同哈希值的文件进行求交集，如果文件过大进行rehash外部排序基本方法1.将外存n个记录分成若干长度为l的子文件或段，依次读入内存.
2022-03-16 17:55:35
534
1
原创 Binary Search Tree代码实现
插入查找都很简单，主要是删除删除思路：从要删除的结点左子树中找到最右边的结点（要删除结点的前驱），替代要删除的结点特殊情况：①要删除的点是根节点的情况，记得更新根结点② 要删除的结点没有左子树，那么直接用右子树代替要删除的结点的位置，（右子树也为空，说明要删除结点是叶子节点，也可以用空右子树（nullptr)代替）代码入下/*删除①找到目标结点 否则报错②如果有左儿子，找左子树最右边的点替代当前结点,如果没有左儿子，把这棵树的右儿子顶替它的位置④注意如果删除结点是root记得修改r
2022-02-17 13:10:33
432
原创 类成员函数做友元报错问题解决。类外实现函数的作用体现
1.先看代码分为Buliding类和GoodGay两个类要把GoodGay类的成员函数visit()声明为Buliding类的友元，使得可以访问Building类的私有成员变量BedRoom;#include<bits/stdc++.h>using namespace std;class GoodGay; //类声明class Building;//类声明class GoodGay{ public: GoodGay();//构造函数声
2022-01-14 13:43:58
1341
10
原创 1044. 最长重复子串
字符串哈希学习h[i] = h[i-1] * p + s[i];p[i] = p[i - 1] * p;hashNum = h[i + len] - h[i] * p[len];可以用字符串哈希来写且仅当两个哈希值溢出程度与 Integer.MAX_VALUE 呈不同的倍数关系时，会产生错误结果（哈希冲突），此时考虑修改 或者采用表示范围更大的 long 来代替 int。int做乘法发生溢出警告，可以 * 1ll 转换成 足够大的long long 来完成乘法操作，然后强行向下转换in
2021-12-23 18:06:58
335
原创 2019CCPC秦皇岛 A. Angle Beats
#include<bits/stdc++.h>#define IOS std::ios_base::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);// 快读using namespace std;typedef long long ll;const ll inf = 4e9 + 1;const int N = 2E3 + 10;struct ty{ ll x,y;// x = (xa - x2) y =
2021-11-19 10:46:13
286
原创 2019 ICPC 南昌 Regional K. Tree（树上启发式合并 + 动态开点线段树）
#include<bits/stdc++.h>using namespace std;#define IOS std::ios_base::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);// 快读const int N = 1e5 + 10;const int MAX = 2e7;int h[N],to[N << 1],ne[N << 1];int son[N],sz[N];int c
2021-11-12 22:06:46
689
原创 dsu on tree
要点把问题转化成求解任意结点子树一整个层上的所有结点某些性质的特点。注意预处理要求的答案，或者优化求解答案的时间复杂度，dsu on tree 时间复杂是 n logn ，一定要防止求解答案过程中的复杂度退化注意数组越界，有时候要求的答案是不合法的，比如让你求一个在第5层的结点的它第3层儿子的数量，或者给你的层数大于树的有效层数当有多棵树时，因为要遍历多棵树，防止遍历上一颗树信息对下一棵树的影响，所以遍历每一棵树都要把根节点设置为轻链，遍历整棵树的最后要消除掉这棵树的信息。消除子树信息的方法，
2021-10-30 17:59:10
206
原创 奇奇怪怪的魔法阵 状压dp
传送门思路对每个T集合，求独立子集合把一个集合对应成二进制数按以下方式划分，没有最低位 : 只有高位，直接加上高位表达的集合有最低位①只有最低位这个位：加上这个低位表达的集合②除了最低位还有其它高位：加上与低位无边的高位集合#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N = 26;const ll mod = 1e9 + 7;int dp[1 <<
2021-10-20 17:51:29
98
原创 Starship Troopers 树上分组背包
传送门Problem DescriptionYou, the leader of Starship Troopers, are sent to destroy a base of the bugs. The base is built underground. It is actually a huge cavern, which consists of many rooms connected with tunnels. Each room is occupied by some bugs, and
2021-10-17 09:52:01
176
原创 E. Gardener and Tree 树形DP
传送门题目描述思路求一下每个结点的所有分支路径中第二长的那条路径的长度，如果长度大于K，那么k次操作后这个结点就会被保留。做两次dfs第一次，沿着这个固定结点往下搜索，求得最长路径长度，并且记录当前结点的最长路径是来自哪个结点的（第二次搜索会用到）。第一次搜索后除了第一个结点，其它结点的最长路径都没有考虑到其经过父节点的那条路径，所以要再用第一次的根节点搜索一次，对每个结点，考虑父节点路径对它的第二长路径答案的影响，要特判父节点的最长路是不是就是自己的路径对其的贡献。具体实现看代码#incl
2021-10-16 15:09:36
183
原创 线段树维护dp状态转移
传送门题目描述给长度为 n 的序列 a[]，一个区间的得分为这个区间内有多少种元素恰出现一次。输出得分最大的区间，得分为多少。分析如果暴力枚举所有区间那么是N^2,需要考虑如何优化，可以根据区间得分的特点去思考。设dp[l][r-1]为区间l~r-1的得分，那么dp[l][r]的得分有3种情况dp[l][r]=dp[l][r−1]+1，第r个数没有在l∼r−1出现过 dp[l][r] = dp[l][r-1] + 1，第 r 个数没有在l \sim r - 1出现过 dp[l][r
2021-10-13 19:22:16
236
原创 2021ccpc网络赛 Monopoly 不处理负模数做法
传送门Problem DescriptionLittle Rabbit loves playing a tabletop game called Monopoly. In the game, players roll the dice to move around the game board, buying and trading properties, and developing them with houses and hotels. Players collect rent from thei
2021-10-12 16:36:57
298
原创 2021ccpc网络赛 Nun Heh Heh Aaaaaaaaaaa
Problem DescriptionVasily Tadokorov is a stringologist. He thinks a string is fragrant if it can be divided into two parts — nunhehheh as the prefix and a number of (excluding 0) a as the suffix. For example, nunhehhehaaaaaa is fragrant, but nunhehheh and
2021-10-10 20:53:44
316
原创 HDU - 5884
一年前入门的题目了，当时没写出来，现在填坑题目Recently, Bob has just learnt a naive sorting algorithm: merge sort. Now, Bob receives a task from Alice.Alice will give Bob N sorted sequences, and the i-th sequence includes ai elements. Bob need to merge all of these sequences.
2021-10-07 13:37:11
123
原创 牛牛种小——超级详细的N^2和N^3做法
题意①题意中的度指的是对于数中每个结点的边数和，实际上就是图中无向图结点的度②根据树的特点，每个结点度至少为1，且n个结点的有n-1条边，每条边连接两个点，对这两个点都有一个度的贡献，所以树的度的和为 2*(n-1)③问题转化为 对 n 个结点选择 1 ~ (n - 1) 的度数，在度数和为 2 * （ n - 1 ）的前提下，求最大价值其实我很好奇这样构造在结点个数和度数满足树的条件时，到底真的实际上能不能构造出这棵树，不知道有无证明？很明显但会T的O(n^3)的做法n^3的背包dp做法很
2021-09-26 16:02:08
161
原创 D2. Seating Arrangements (hard version)
传送门题意对于有先后顺序到来的n * m 个人你要给他们安排座位，对于任意两个人如果 ai<aj ai < aj ai<aj 必须有 si<sj si < sj si<sj这里的si 和 sj 其实就是图片中的编号大小。对于任何来寻找座位的人，都要先找到他自己的那一排，然后从那一排的第一列开始，从左到右开始走，知道找到自己的座位，过程中每路过一个人，那么 * * inconvenience ** 就 + 1。要求你在满足1.的条件下，安排座
2021-09-13 12:34:55
488
4
原创 D. Expression Evaluation Error
D. Expression Evaluation Error题目题意给你一个十进制数s,n,要求你把s拆成用n个10进制数的和，再把这n个十进制数看成11进制，让这n个11进制数的和的11进制尽管可能大。分析首先n个数按11进制求和一定小于等于按10进制求和，因为11进制是逢11进1，10进制逢10进1，所以11进制相比10进制每次进位都要亏损1个1。所以为了让答案尽可能的大，我们可以尽量在做加法的时候不让它进位，即使需要进位也要让它在低位进位，这样损耗更小。所以我没可以从左到右考虑s的每一位
2021-09-07 12:24:50
312
原创 P1174打砖块
题目描述小红很喜欢玩一个叫打砖块的游戏，这个游戏的规则如下：在刚开始的时候，有 nn 行 mm 列的砖块，小红有 kk 发子弹。小红每次可以用一发子弹，打碎某一列当前处于这一列最下面的那块砖，并且得到相应的得分。（如图所示）某些砖块在打碎以后，还可能将得到一发子弹的奖励。最后当所有的砖块都打碎了，或者小红没有子弹了，游戏结束。小红在游戏开始之前，就已经知道每一块砖在打碎以后的得分，并且知道能不能得到一发奖励的子弹。小红想知道在这次游戏中她可能的最大得分，可是这个问题对于她来说太难了，你能帮帮她吗？
2021-08-31 23:52:58
1046
原创 打砖块(brike)
链接：https://ac.nowcoder.com/acm/problem/210249来源：牛客网题目在一个凹槽中放置了\ n n 层砖块，最上面的一层有\ n n 块砖，第二层有\ n-1 n−1块，……最下面一层仅有一块砖。第 \ i i 层的砖块从左至右编号为1，2,\dots i1，2,…i，第i层的第j块砖有一个价值a[i,j]（a[i,j]\leq 50）a[i,j]（a[i,j]≤50）。下面是一个有5层砖块的例子：如果你要敲掉第 \ i i层的第 \ j j 块砖的话，若
2021-08-31 11:52:39
483
原创 HDU2059
超级详细题目据说在很久很久以前，可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后，心中郁闷，发誓要报仇雪恨，于是躲进了杭州下沙某农业园卧薪尝胆潜心修炼，终于练成了绝技，能够毫不休息得以恒定的速度(VR m/s)一直跑。兔子一直想找机会好好得教训一下乌龟，以雪前耻。最近正值HDU举办50周年校庆，社会各大名流齐聚下沙，兔子也趁此机会向乌龟发起挑战。虽然乌龟深知获胜希望不大，不过迫于舆论压力，只能接受挑战。比赛是设在一条笔直的道路上，长度为L米，规则很简单，谁先到达终点谁就算获胜。无奈乌龟自从上次
2021-08-30 22:01:12
100
原创 D2. Two Hundred Twenty One (hard version)
题目思路预处理前缀和数组pre[N]，然后l ~ r 的和就是pre[r] - pre[l - 1]（当然可能和实际的l ~ r 的和是相反数，受到l的位置影响，不过不影响你让l ~ r 的和变为 0）令 x = pre[r] - pre[l-1];①x是奇数那么你只要把 前缀和为 pre[l-1] + x/2 + 1,并且位置在 l ~ r 的那个位置的移除就行。假设这个位置是p ，l ~ p - 1的贡献是 x/2,因为移除了p,所以p + 1 ~ r 的贡献就会取反也就是 -x/
2021-08-29 10:34:36
336
原创 [NOIP2018]道路铺设
解析一下： 给你一个数组，每个数都 > 0,你每次可以选一个区间对着个区间里的每个数 - 1，让你求最少的操作次数，从而使得数组里的每个数都为0。对区间里的每个数减同一个数，很容易想到，用对差分数组的操作替代原数组的操作。这里我们考虑起始状态的差分数组和最终状态的差分数组。可以得到起始状态的差分数组，一定不全为0,但和为0，最终状态的差分数组一定全为0，考虑每次对区间的操作转换为对差分数组d[l] - 1, d[r + 1] + 1,然后我们要做的就是通过这样若干次后d[i]数组变为全0 的最.
2021-08-22 16:23:58
226
原创 智乃酱的静态数组维护问题多项式
定理：最高次项为ｎ次的多项式做ｎ＋１次差分的余项为常数题目最多为5次，所以做6次差分就够了。如果次数小于6次，每多做一次差分增加一项余项，余项还是不超过。根据定理，做完6次差分后的余项一定在前6项内.所以可以把对修改区间 l∼r l \sim r l∼r的操作 ，转换为修改6次差分后的区间l∼l+6 l\sim l + 6 l∼l+6然后若干次修改后，再做6次前缀和把原数组还原回去。因为差分，所以要考虑对r+1∼nr + 1 \sim nr+1∼n 的影响，所以要做一个抵消操作。如何..
2021-08-22 00:49:33
416
原创 1590：恨 7 不成妻(数位DP）
这题有一个难点一个坑点,and 你要细点难点你要用DP维护出区间内所有和7无关的数的平方和。这个需要你做一个数学转换。因为你用DP预处理一个区间的所有与7无关的数，就是通过固定最高位，枚举次高位来递推。所以这个时候我们可以试着把一个数拆成最高位和剩余位的和，看看它有没有什么特点，从而得到DP的状态转移方程。所以一个数可以拆成 t∗10k+xi t*10^{k} + x_{i} t∗10k+xi则有固定最高位，低位,每个数的平方和如下(x1+t∗10k)2+(x2+t∗10k)2+⋯⋯(
2021-08-18 13:12:14
390
原创 D2. Mocha and Diana (Hard Version)
首先你可以尽可能的去连边，并且保证森林1和森林2中的所有树还是树。你可以试着对每一个结点x建立一个（1，x)的边，在保证还是棵树的前提下。假设这是原图进行上述操作后就是这样了之后再定义2个集合分别为s1,s2分别表示森林1和森林2中除结点编号1所在的树的其它树的根结点编号。如上图，对应的s1,s2分别为下图所示那么它有如下两个性质①这两个集合内不存在相同结点。反证: 如果有，根据s1,s2集合的定义,这两个相同结点的树一定可以各自连接到1号结点所对应的树，那么通过
2021-08-16 20:38:26
703
2
原创 nowcode 逆序对
题目链接：https://ac.nowcoder.com/acm/problem/14731来源：牛客网求所有长度为n的01串中满足如下条件的二元组个数：设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。答案对1e9+7取模。输入描述:输入一个n。输出描述:输出答案对1e9+7取模示例1输入3输出6说明备注:n <= 10^18思路n数据可以很大，应该考虑推出公式直接求出答案根据题意，首先假设出一个长度适当的01串，试着
2021-08-11 10:57:35
130
原创 斐波那契博弈证明
前提：任意数都能由若干斐波那契数列的不同项组成，而且任意两项都不是相邻的斐波那契数，因为相邻两项可以合并：a_(n) = a_(n-1) + a_(n - 2)对于斐波那契数列a_(1) = 1 , a_(2) = 1, a_(3) = 2, a_(4) = 3, a_(5) = 5，……,a_(n) = a_(n-1) + a_(n-2);可以发现 石子数为 a_(3),a_(4) 先手必败，也就是最后取光石子的是后手。分类讨论①当石子数为 一项斐波那契数，因为前5项结果已知
2021-08-08 21:50:29
231
原创 树的中心(模板)~
思路见代码#include<bits/stdc++.h> //树的中心 using namespace std; //对于一棵树的每一个结点，该结点与离该最远的结点的路径const int N = 1e4 + 10; // 要么过这该点的子结点，要么过该点的父节点const int M = N << 1;typedef long long ll;const ll inf = 0x3f3f3f3f3f3f;int h[N];int cnt = 0;ll
2021-08-08 17:25:58
144
原创 数字交换 求树的直径
题目链接题目描述如果一个数 x 的约数和 y （不包括他本身）比他本身小，那么 x 可以变成 y，y 也可以变成 x。例如 4 可以变为 3，1 可以变为 7。限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。题意题目描述有点绕,就是如果x > x的不包括x本身的约数和,那么 x 和 y 就可以相互转换思路把图画出来,你会发现这是一棵树,要你求出树的直径,把每个点的约数和预处理一下就行代码#include<bits/
2021-08-08 17:23:43
163
1
原创 VIM常用快捷键
光标移动n + < space> 向这一行后面移动n个字符H,M,L光标分别移动到屏幕的最上方、中央、最下方的那一行n + ENTER 向下移动 n 行n + G 光标移动到 第 n 行gg 移动到第一行G移动到整个文档的最后一行。搜索/word 向下寻找第 1 个 word的位置 按enter 进行光标移动?word 向上寻找，功能相同n 在上一次搜索的基础上向下进行光标移动N 在上一次搜索的基础上向上进行光标移动搜索替换: n1,n2s/word1/w
2021-07-29 14:33:12
275
原创 [ZJOI2007]棋盘制作
[ZJOI2007]棋盘制作1. 题目链接2.问题描述链接：https://ac.nowcoder.com/acm/problem/20471来源：牛客网国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源 于易经的思想，棋盘是一个88大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主人公小Q， 正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。小Q
2021-07-21 17:57:00
229
原创 2021暑期牛客多校训练营第二场 K-Stack
K-Stack题目链接##### 题目描述思路题意：让数组a的元素按顺序，进入单调栈。给出数组a中部分 第 pi 个数进入栈后的栈的大小，让你求出满足以上关系的数组 a 的排列组合，如果不存在输出 - 1分析：题目中所给代码维护了一个单调栈。所以我们也可以根据单调栈的特点，和给出的pi、xi、 和p(i - 1) 、x（i - 1) 的关系来构造出a[i] (i : 1-n) 这些数，这些数没必要一定 要 1-n，重要的是他们之间的大小关系，只要把他们的大小关系转换为排列组合即
2021-07-20 20:08:33
154
2
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人