墨染枫-CSDN博客

新浪微博可以在发言中嵌入“话题”，即将发言中的话题文字写在一对“#”之间，就可以生成话题链接，点击链接可以看到有多少人在跟自己讨论相同或者相似的话题。新浪微博还会随时更新热门话题列表，并将最热门的话题放在醒目的位置推荐大家关注。本题目要求实现一个简化的热门话题推荐功能，从大量英文（因为中文分词处理比较麻烦）微博中解析出话题，找出被最多条微博提到的话题。输入格式:输入说明：输入首先给出一个正整数N（≤105），随后N行，每行给出一条英文微博，其长度不超过140个字符。任何包含在一对最近的#中的内容均被认

2022-06-04 15:04:34 146

原创 pta7-6悄悄关注

新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。输入格式：输入首先在第一行给出某用户的关注列表，格式如下：人数N 用户1 用户2 …… 用户N其中N是不超过5000的正整数，每个用户i（i=1, …, N）是被其关注的用户的ID，是长度为4位的由数字和英文字母组成的字符串，各项间以空格分隔。之后给出该用户点赞的信息：首先给出一个不

2022-06-04 12:30:35 283

原创 pta7-4 插入排序还是归并排序

根据维基百科的定义：插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？输入格式：输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最

2022-05-27 21:23:30 902

原创 pta7-2 插入排序还是堆排序

根据维基百科的定义：插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。堆排序也是将输入分为有序和无序两部分，迭代地从无序部分找出最大元素放入有序部分。它利用了大根堆的堆顶元素最大这一特征，使得在当前无序区中选取最大元素变得简单。现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？输入格式：输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；

2022-05-27 21:18:54 996

原创数据结构二叉树的删除（带图详解

第二个例子没选好…将就用5.5凑合一下把#include<iostream>using namespace std;typedef struct ElemType { int key;}ElemType;typedef struct BSTNode { ElemType data; BSTNode* lchild, * rchild;}BSTNode, * BSTree;void DeleteBST(BSTree& T, char key) { BSTree.

2022-04-24 21:11:42 1025

原创单链表的创建和删除（带头节点

#include<iostream>using namespace std;int a;typedef struct Node { int data;//数据域 Node* next;//指针域}Node;typedef Node* List;//定义线性表void tailinsert(List& h) { //尾插法建立线性表 List tail;//建立一个尾指针 h = new Node;//给链表创建一个空的头 h->next = NULL;/

2022-04-23 15:06:57 1385

原创 pta7-2 根据后序和中序遍历输出先序遍历

题目：本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。输入格式:第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。输出格式:在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。输入样例:72 3 1 5 7 6 41 2 3 4 5 6 7输出样例:Preorder: 4 1 3 2 6 5 7#inclu

2022-04-05 16:08:14 318

原创 pta7-4 出栈序列的合法性

题目：给定一个最大容量为 M 的堆栈，将 N 个数字按 1, 2, 3, …, N 的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 M=5、N=7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。输入格式：输入第一行给出 3 个不超过 1000 的正整数：M（堆栈最大容量）、N（入栈元素个数）、K（待检查的出栈序列个数）。最后 K 行，每行给出 N 个数字的出栈序列。所有同行数字以空格间隔。输出格式：

2022-03-24 22:19:08 356

原创后缀表达式求值 stod函数的使用

题目来自pta代码来自看到的某个佬的解法发现stod这个神奇的东西找不到原链接就贴一下代码好了侵删题目：我们人类习惯于书写“中缀式”，如 3 + 5 * 2 ，其值为13。 (p.s. 为什么人类习惯中缀式呢？是因为中缀式比后缀式好用么？）而计算机更加习惯“后缀式”（也叫“逆波兰式”，Reverse Polish Notation）。上述中缀式对应的后缀式是： 3 5 2 * +现在，请对输入的后缀式进行求值。输入格式:在一行中输入一个后缀式，运算数和运算符之间用空格分隔，运算数长度不超

2022-03-16 23:13:53 698

原创 pta7-3表达式转换

题目：算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入格式:输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。输出格式:在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。输入样例:2+3*(7-4)+8/4输出样例:2 3 7 4 - * + 8 4 / +#inclu

2022-03-15 21:47:31 873

原创 pta7-10 求连续maxsum并返回起始结束的下标

初学数据结构、、书上的在线算法感觉有点像dp、、当然简单求lis的话dp能过不过没试过这个用dp怎么样、、有机会补上#include<iostream>#include<stdio.h>using namespace std;#pragma warning(disable:4996)const int N = 1e5 + 10;int a[N];int k;int main() { scanf("%d", &k); for (int i = ..

2022-02-22 22:19:48 103

原创 AcWing282 石子合并区间dp

区间dp常见套路：枚举区间长度枚举左端点（同时得到右端点枚举分割点构造状态转移方程注意和贪心的合并果子区别这个每次只能合并相邻的两堆贪心可以任意题目设有 N 堆石子排成一排，其编号为 1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。例如有 4 堆石子分别

2022-02-06 14:37:33 90

原创 AcWing902 最短编辑距离

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：删除–将字符串 A 中的某个字符删除。插入–在字符串 A 的某个位置插入某个字符。替换–将字符串 A 中的某个字符替换为另一个字符。现在请你求出，将 A 变为 B 至少需要进行多少次操作。输入格式第一行包含整数 n，表示字符串 A 的长度。第二行包含一个长度为 n 的字符串 A。第三行包含整数 m，表示字符串 B 的长度。第四行包含一个长度为 m 的字符串 B。字符串中均只包含大写字母。输出格式输出一个整

2022-02-05 23:41:56 503

原创 AcWing09 分组背包问题

分组背包实际上可以看作是限制了的多重背包每组只能取一个那就枚举所有的策略#include<iostream>#include<algorithm>using namespace std;const int N = 110;int s[N], v[N], w[N];int n, m;int dp[N];int main() { cin >> n >> m; int s; for (int i = 0; i < n; i++) {

2022-02-05 15:24:46 413

原创多重背包问题二进制优化版

转化成01背包问题s件物品总能用二进制数想办法±得到#include<iostream>#include<cstring>#include<algorithm>#include<vector>using namespace std;const int N = 2010;int n, m;int dp[N];struct Good { int v, w;};int main() { cin >> n >>

2022-02-05 14:20:59 525

原创完全背包问题的一点相关问题及解答

先放01背包和完全背包的状态转移方程：Q:为什么完全背包的表达式第二个是f[i][j-v]+w ?从这也可以看出和01背包的代码差别Q: 为什么是01从大到小枚举？A: 因为01背包每次用到的是i-1层的f值如果从小到大枚举 j-v<j 那么此时的j-v在第i轮会被计算出不满足用的i-1层但如果从大到小那么第i轮中j-v并没有被计算得出会在i-1中才被计算因此要从大到小枚举对于完全背包问题从小到大枚举同样分析可得...

2022-02-04 16:35:30 271

原创博弈论 Nim游戏-台阶-集合-拆分

acwing891 nim游戏#include<iostream>using namespace std;const int N = 100010;int main() { int n; cin >> n; int res = 0; for (int i = 0; i < n; i++) { int x; cin >> x; res ^= x; } if (res)puts("Yes"); else puts("No");

2022-02-04 14:39:01 418

原创 AcWing890 能被整除的数容斥原理

题解建议看这个：https://www.acwing.com/solution/content/29702/#include<iostream>using namespace std;typedef long long LL;const int N = 20;int p[N];int main() { int n, m; cin >> n >> m; int res = 0; for (int i = 0; i < m; i++)cin &gt

2022-02-03 15:57:04 69

原创 AcWing889 满足条件的01序列卡特兰数

给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。输出的答案对 1e9+7 取模。输入格式共一行，包含整数 n。输出格式共一行，包含一个整数，表示答案。数据范围1≤n≤1e5输入样例：3输出样例：5由于直接求排列比较困难因此转化为求路径假设0是向右走一格 1是向上走一格则问题转化为卡特兰数问题卡特兰数如下：#include<iostr

2022-02-03 14:08:11 235

原创高精度的加减乘除法汇总

高精度加法#include<iostream>#include<stdio.h>#include<vector>using namespace std;vector<int>C;vector<int>add(vector<int>& A, vector<int>& B) { int t = 0; int i = 0; while (i < A.size() || i < B.s

2022-02-03 00:06:01 61

原创关于组合数的不同数据规模情况/问题的不同解法--4种

情况1 询问组数比较多但是b<=a<=2000 比较小递推公式法#include<iostream>#include<algorithm>using namespace std;const int N = 2010, mod = 1e9 + 7;int c[N][N];//从i里面取出j个的方案数void init() { for (int i = 0; i < N; i++) for (int j = 0; j <= i; j++)

2022-02-03 00:02:06 235

原创 AcWing883 高斯消元解线性方程组

#include<iostream>#include<algorithm>#include<cmath>#include<cstring>using namespace std;#pragma warning(disable:4996)const int N = 110;const double eps = 1e-8;double a[N][N];int n;int gauss() { int r , c ; for (r = 0,

2022-02-02 14:20:38 461

原创 AcWing148 合并果子哈夫曼树

哈夫曼树每次让在最底下的达到最小那么总和一定最小#include<iostream>#include<queue>#include<stdio.h>using namespace std;int main() { int n; cin >> n; priority_queue<int, vector<int>, greater<int>>heap; for (int i = 0; i < n;

2022-02-01 16:25:40 601

原创 AcWing907 区间覆盖

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。输出最少区间数，如果无法完全覆盖则输出 −1。输入格式第一行包含两个整数 s 和 t，表示给定线段区间的两个端点。第二行包含整数 N，表示给定区间数。接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。输出格式输出一个整数，表示所需最少区间数。如果无解，则输出 −1。数据范围1≤N≤1e5,−1e9≤ai≤bi≤1e9,−1e9≤s≤t≤1e9输入样例：

2022-02-01 15:25:20 94

原创 AcWing906 区间分组贪心运算符重载

实在受不了数论的折磨于是感觉贪心友好多了but不严谨证明多少带点运气成分（（题目：给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。输出最小组数。输入格式第一行包含整数 N，表示区间数。接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。输出格式输出一个整数，表示最小组数。数据范围1≤N≤1e5,−1e9≤ai≤bi≤1e9输入样例：3-1 12 43 5输出样例：2#i

2022-02-01 13:41:26 112

原创 AcWing204 表达整数的奇怪方式中国剩余定理

题解建议看这个：https://www.acwing.com/solution/content/3539/#include<iostream>#include<stdio.h>#include<math.h>using namespace std;typedef long long LL;LL exgcd(LL a, LL b, LL & x, LL & y) { if (!b) { x = 1, y = 0; return a;

2022-01-31 16:37:45 68

原创 AcWing861 二分图的最大匹配匈牙利算法

就是说是怎么才能让尽可能多的人找到对象法（（给定一个二分图，其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。数据保证任意一条边的两个端点都不可能在同一部分中。请你求出二分图的最大匹配数。二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。输入格式第一

2022-01-30 22:08:40 73

原创 AcWing860 染色法判定二分图

#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N = 100010, M = 200010;int h[N], e[M], ne[M], idx;int color[N];int n, m;void add(int a,int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++;}

2022-01-30 15:57:58 386

原创 AcWing859 kruskal算法求最短路

#include<iostream>#include<algorithm>using namespace std;const int N = 2e5 + 10;int n, m;int p[N];struct edge { int a, b, w; bool operator< (const edge& W)const { return w < W.w; }};edge edges[N];int find(int x) { if

2022-01-30 12:56:08 858

原创 AcWing798 差分矩阵

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 c。请你将进行完所有操作后的矩阵输出。输入格式第一行包含整数 n,m,q。接下来 n 行，每行包含 m 个整数，表示整数矩阵。接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。输出格式共 n 行，每行 m 个整数，表示所有操作

2022-01-29 20:47:03 687

原创 AcWing858 prim算法求最小生成树

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。输入格式第一行包含两个整数 n 和 m。接下来 m 行，每行包含三个整数

2022-01-29 20:41:23 75

空空如也

空空如也