Logo

Menu

十七

Archives

2021 / 03

PAT1035. 插⼊与归并(25)

2021-03-17

#PAT乙级
根据维基百科的定义：插⼊排序是迭代算法，逐⼀获得输⼊数据，逐步产⽣有序的输出序列。每步迭代中，算法从输⼊序列中取出⼀元素，将之插⼊有序序列中正确的位置。如此迭代直到全部元素有序。归并排序进⾏如下迭代操作：⾸先将原始序列看成N个只包含1个元素的有序⼦序列，然后每次迭代归并两个相邻的有序⼦序列，直到最后
acwing846. 树的重心

2021-03-16

acwing #dfs
给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。输入第一行包含整数n，表示树的结点数。接下来n-1行，每
搜索与图论

2021-03-16

算法模板 #图论
树与图的存储树是一种特殊的图，与图的存储方式相同。对于无向图中的边ab，存储两条有向边a->b, b->a。因此我们可以只考虑有向图的存储。(1) 邻接矩阵：g[a][b] 存储边a->b(2) 邻接表：可以用数组来存储邻接表，h[n]表示第n个顶点的头节点，e[n]表示第n条边的
acwing 836. 合并集合

2021-03-12

acwing #并查集
1. 朴素并查集：int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点int find(int x){ if (p[x] != x) p[x] = find(p[x]); return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i &lt
acwing835.Trie字符串统计

2021-03-12

acwing #字符串#Trie
维护一个字符串集合，支持两种操作：“I x”向集合中插入一个字符串x；“Q x”询问一个字符串在集合中出现了多少次。共有N个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。输入第一行包含整数N，表示操作数。接下来N行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。5I
KMP字符串

2021-03-11

算法模板 #KMP
给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。模板串P在模式串S中多次作为子串出现。求出模板串P在模式串S中所有出现的位置的起始下标。输入格式第一行输入整数N，表示字符串P的长度。第二行输入字符串P。第三行输入整数M，表示字符串S的长度。第四行输入字符串S。输出
算法笔记

2021-03-11

单链表 —— 模板题 AcWing 826. 单链表// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点int head, e[N], ne[N], idx;// 初始化void init()// 在链表头插入一个数avoid insert(in

2021 / 02

PAT1033. 旧键盘打字

2021-02-24

PAT #PAT乙级#字符串
旧键盘上坏了⼏个键，于是在敲⼀段⽂字的时候，对应的字符就不会出现。现在给出应该输⼊的⼀段⽂字、以及坏掉的那些键，打出的结果⽂字会是怎样？输入输⼊在2⾏中分别给出坏掉的那些键、以及应该输⼊的⽂字。其中对应英⽂字⺟的坏键以⼤写给出；每段⽂字是不超过105个字符的串。可⽤的字符包括字⺟[a-z, A-Z]
PAT1032 挖掘机技术哪家强

2021-02-24

PAT #PAT乙级
为了用事实说明挖掘机技术到底哪家强，PAT组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。输入输入在第1行给出不超过10^5的正整数N，即参赛人数。随后N行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从1开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。6
PAT1031. 查验身份证

2021-02-24

PAT #PAT乙级
Previous 40 / 43 Next