- 博客(83)
- 收藏
- 关注
RSS订阅原创 哈夫曼树c++实现（bupt信通大一下数据结构实验）
数据结构做到哈夫曼，找到了以前的代码使用时：按1回车，输入字符串，回车，然后依次2，3，…回车#include <iostream>#include <cstring>#include <iomanip>// #include "Huffman.h"using namespace std;char s[150]; //目标字符串char ch[150]; //出现过的字符int num[150];
2020-11-06 00:00:27
669
原创 洛谷 P3879 [TJOI2010]阅读理解
https://www.luogu.com.cn/problem/P3879思路直接用trie树模板代码#include <cstdio>#include <iostream>#include <string>#include <cstring>using namespace std;class Trie {private: bool isEnd; Trie *next[26];public: /** Ini.
2020-09-29 13:00:13
184
原创 leetcode 208 实现Trie (的插入，查找，前缀查询)
https://leetcode-cn.com/problems/implement-trie-prefix-tree/题目实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。示例Trie trie = new Trie();trie.insert(“apple”);trie.search(“apple”); // 返回 truetrie.search(“app”); // 返回 falsetrie.startsWit.
2020-09-29 12:28:35
79
原创 leetcode 13 罗马数字转整数
https://leetcode-cn.com/problems/roman-to-integer/想了个自认为有些怪的做法，不知道别人咋写的代码class Solution {public: int getVal(char c) { if (c == 'I') return 1; if (c == 'V') return 5; if (c == 'X') return 10; if (c == 'L') return 50.
2020-09-28 12:54:25
76
原创 表达式求值（+-*/^，栈）
题目已知运算符的优先级为先算乘方(‘^’)，再算乘除(‘*/‘)，再算加减(‘±‘)。输入包括一行，由数字和’()±*.^’和’sin’，’cos’组成，并以’#’结果。保证表达式合法，所有运算在double的精度范围之内。输出一个小数，表示表达式的值。保留三位有效数字。代码#include <cstdio>#include <cstdlib>#include <iostream>#include <cmath>#define Init_Si
2020-09-26 09:42:37
401
原创 洛谷 P1406 方格填数
https://www.luogu.com.cn/problem/P1406代码#include <bits/stdc++.h>using namespace std;int tot;int n, a[25], b[25];bool flag[25];int row[5];int line[5];int x1, x2, cnt;void dfs(int pos) { // if (b[1] == 2) { // cout << pos <<.
2020-08-30 14:49:21
138
原创 洛谷 P1991 无线通讯网（生成树，并查集）
https://www.luogu.com.cn/problem/P1991思路不是要给最大几条边的点装卫星电话，而是只要他们所在连通块之间有即可代码#include <bits/stdc++.h>using namespace std;const int M = 502;const int N = 502;struct edge { int u, v; double w;}e[M * M];bool cmp(edge a, edge b) { return a.w.
2020-08-25 16:16:16
112
转载 JDK1.8_API（转载）
https://blog.csdn.net/weixin_37012881/article/details/80499067链接：https://pan.baidu.com/s/1eWEG3YRne0UQDhV389c8HQ 密码：hg4w
2020-08-22 11:08:35
94
原创 洛谷 P1197 [JSOI2008]星球大战（并查集）
https://www.luogu.com.cn/problem/P1197思路先建好再拆不现实，想想就会超时，反着来，先拆了再慢慢复原代码#include <bits/stdc++.h>using namespace std;const int N = 400005;int n, m, k, tot, cnt;int fa[N], chai[N], ans[N], head[N];bool flag[N];struct edge { int u, v, next;.
2020-08-21 21:42:28
97
原创 并查集练习
洛谷 P3367 P1551 P3958 P1455洛谷 P3367 【模板】并查集https://www.luogu.com.cn/problem/P3367代码#include <bits/stdc++.h>using namespace std;const int N = 10004;int n, m;int a, b, k;int fa[N], Rank[N], cnt[N];int find(int x) { return fa[x] = x == fa[
2020-08-21 17:19:49
79
原创 Ubuntu终端下对拍
duipai.cpp#include <bits/stdc++.h>using namespace std;int main() { int cases = 0; do { if (cases) printf ("#%d AC\n",cases); cases++; system ("./make"); system ("./my"); system ("./std".
2020-08-20 21:01:50
125
原创 洛谷 P5905 【模板】Johnson 全源最短路（Johnson算法）
https://www.luogu.com.cn/problem/P5905思路先跑spfa找到“势能”以及是否有闭环，然后每个点Dijkstra找最短路。代码#include <bits/stdc++.h> using namespace std;const int N = 5005;const int M = 60006;const int INF = 1e9;struct edge { long long v, w, next;} e[M];struct nod.
2020-08-20 21:00:07
289
原创 洛谷 P3385 【模板】负环（SPFA）
https://www.luogu.com.cn/problem/P3385思路进行spfa的松弛操作，如果一个点松弛了n次则存在负环（一个憨批错误卡半天）代码#include <bits/stdc++.h>using namespace std;const int M = 6002;const int N = 2002;struct edge { int v, w, next;} e[M];int inq[N], head[N], dis[N];queue <.
2020-08-20 17:37:38
114
原创 洛谷 P3956 棋盘（记忆化DFS剪枝）
https://www.luogu.com.cn/problem/P3956思路直接搜会超时，保存到每个点的最优解，即记忆化，即可剪掉很多无用的分支。代码#include <bits/stdc++.h>using namespace std;const int M = 102;int mp[M][M];int dis[M][M];int vis[M][M];int m, n, ans = -1;int dx[4] = {-1, 1, 0, 0};int dy[4].
2020-08-20 16:43:09
214
原创 洛谷 P4779 【模板】单源最短路径（标准版）（Dijkstra）
https://www.luogu.com.cn/problem/P4779思路手打了一遍与上一题弱化版的一样的，过了，上一题叫弱化估计是能用SPFA，这题不行，SPFA，它死了#include <bits/stdc++.h> using namespace std;const int N = 100005;const int M = 200005;struct edge { int v; int w; int next;} e[M];int n, m, s, cnt.
2020-08-20 15:52:17
215
原创 洛谷 P3371 【模板】单源最短路径（弱化版）（Dijkstra链式前向星+堆优化）
https://www.luogu.com.cn/problem/P3371代码#include <bits/stdc++.h>using namespace std;const int N = 10002;const int M = 500002;const int INF = 2147483647;struct Edge { int v; int w; int next;};struct node { int id; long long w; const .
2020-08-19 17:43:23
166
1
原创 洛谷 P1119 灾后重建（Floyd）
https://www.luogu.com.cn/problem/P1119思路刚开始还感觉这用Floyd难道不会超吗，后来发现题目条件顺着下来给的 t 是不会减少的，然后经过这题对Floyd有了更好的理解，去枚举中转站。代码#include <bits/stdc++.h>using namespace std;const int N = 202;const int INF = 0x3f3f3f3f;int n, m, q;int t[N];int dis[N][N];.
2020-08-16 17:58:14
98
原创 洛谷 P1457 [USACO2.1]城堡 The Castle （搜索，枚举）
https://www.luogu.com.cn/problem/P1457思路深搜求出各个房间编号以及大小，前两问解决，三四问，枚举要拆的墙，当然每堵能拆的墙都能转换为相邻某区域的北面或东面，所以只用枚举这两个面，然后按照题目的优先级做好判断，有些坑，第一遍只得了75，下了数据看才知道有地方疏忽了。代码#include <bits/stdc++.h>using namespace std;const int N = 52;int n, m;int num, mx, nmx.
2020-08-16 17:01:37
601
原创 洛谷 P1938 [USACO09NOV]Job Hunt S（最长路，SPFA）
https://www.luogu.com.cn/problem/P1938思路将点权转换为边权跑一遍最长路即可，一开始还想着拓扑排序，忘了是有环的代码#include <bits/stdc++.h>using namespace std;const int N = 222;struct edge { int v; int w;};int money;int pay, m1, n, m2, s;vector <edge> g[N];int dis[N.
2020-08-16 15:25:31
172
原创 洛谷 P1359 租用游艇（Floyd， Dijkstra，SPFA）
https://www.luogu.com.cn/problem/P1359代码Floyd#include <bits/stdc++.h>using namespace std;const int N = 202;int n;int dis[N][N];int main() { cin >> n; for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { in.
2020-08-15 20:53:30
174
原创 洛谷 P1983 车站分级（拓扑排序）
https://www.luogu.com.cn/problem/P1983思路对于每一趟车，将其经过的车站中，停靠的和不停靠的连一条边，注意边的去重，这样拓扑排序递推一下就能分级出来代码#include <bits/stdc++.h>using namespace std;struct node{ int id; int level;};const int N = 1005;int n, m;int ru[N];vector <int> g[N];.
2020-08-15 15:33:55
176
原创 洛谷 P2853 Cow Picnic S（DFS）
https://www.luogu.com.cn/problem/P2853题目大意k头牛在n个点上，m条有向边，统计那些所有牛都能到达的点的个数思路很容易就想到，以每头牛为起点去深搜，能走到的地方数值加1，最后那些数值为k的点就是所有牛都能走到的点。ps: 本来还顺着这样想了一个优化，如果在牛 a 的路径上有另外一头牛 b，那么 b能走到的路径必定包含在a能走到的以内，那么我dfs加一个参数num，如果多碰到一头牛，num++，这样在牛a的深搜中就把牛b的也走完了，再标记一下后面不用走牛b了.
2020-08-14 19:14:01
296
3
原创 洛谷 P1807 最长路（拓扑排序）
https://www.luogu.com.cn/problem/P1807题目大意n个顶点的带权有向无环图，边权可能为负值，求1到n的最长路，无法到达则输出 -1思路拓扑排序，直接先将入度为0的入队，定义dis数组，先全部设置成一个极小值，dis[i]为i号顶点到1的距离，然后拓扑排序过程中更新dis，若最后dis[n]仍为极小值输出 -1，否则输出dis[n]代码#include <cstdio>#include <cstring>#include <i.
2020-08-14 15:49:03
383
原创 洛谷 P4017 最大食物链计数（拓扑排序）
https://www.luogu.com.cn/problem/P4017思路图为有向无环图，由于需要统计的是最大的食物链，也就是最低端为生产者，入度为0，最右端的消费者出度为0，我们可以这样，在拓扑排序的过程中，统计到各个点的方法数，也就是假如这个点就是顶端，有多少条，这个很简单，随着拓扑排序的进行逐步递推即可，到当前点的方案数为它上一级各方案数之和。故将每一个入度为0的点放到队列中，且方案数初始化为1，其他点为0，走一遍拓扑排序即可。代码#include <cstdio>#i.
2020-08-14 15:02:39
233
原创 洛谷 P1113 杂务 （图论，AOE网，递推）
https://www.luogu.com.cn/problem/P1113思路题意应该是这些杂务是个AOE网，要完成一个杂务首先要满足完成它的准备任务，所以每个任务的最早开始时间就是它的所有准备任务的最晚完成时间，这样直接递推一下即可代码#include <cstdio>#include <iostream>#include <vector>using namespace std;const int N = 100005;int n, ans;.
2020-08-14 13:56:25
119
原创 洛谷 P3916 图的遍历（搜索，反向建边）
https://www.luogu.com.cn/problem/P3916题目给出N个点，M条边的有向图，对于每个点v，求 A(v)， A(v) 表示从点v出发，能到达的编号最大的点。输入格式第1 行，2 个整数N,M。接下来M行，每行2个整数U_i,V_i，表示边 (U_i,V_i) 。点用1,2,⋯,N编号。输出格式N 个整数A(1),A(2),⋯,A(N)。示例输入：4 31 22 44 3输出：4 4 3 4对于60% 的数据， 1≤N.M≤1e3对于1.
2020-08-14 13:27:22
139
原创 luogu P5318 查找文献 (图遍历)
https://www.luogu.com.cn/problem/P5318题目小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。假设洛谷博客里面一共有 n(n <= 1e5) 篇文章（编号为 1 到 n）以及 m(m <= 1e6) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 .
2020-08-13 16:50:04
464
原创 nowcoder 传球游戏 （动态规划）
https://ac.nowcoder.com/acm/problem/16619题目上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球.
2020-08-11 16:54:26
146
原创 leetcode 701 二叉搜索树中的插入操作
https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/题目给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果示例给定二叉搜索树:和 插入的值: 5你可以返回这个二叉搜索树:或者这个树也是有效的:思路本来还以为.
2020-07-26 13:05:19
81
原创 leetcode 450 删除二叉搜索树中的节点（递归）
https://leetcode-cn.com/problems/delete-node-in-a-bst/题目给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。一般来说，删除节点可分为两个步骤：首先找到需要删除的节点；如果找到了，删除它。说明： 要求算法时间复杂度为 O(h)，h 为树的高度。示例思路用递归的方法如果当前节点不是要删除的节点，根据二.
2020-07-24 17:21:11
121
原创 leetcode 110 平衡二叉树（DFS）
https://leetcode-cn.com/problems/balanced-binary-tree/题目给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。示例给定二叉树 [3,9,20,null,null,15,7]返回 true 。给定二叉树 [1,2,2,3,3,null,null,4,4]返回 false思路深搜，以当前节点为根的子树是否为平衡二叉树取决于它的左右.
2020-07-23 17:22:34
75
原创 leetcode 前400
Array基础27 Remove Element 26 Remove Duplicates from Sorted Array80 Remove Duplicates from Sorted Array II 277 Find the Celebrity 189 Rotate Array 41 First Missing Positive 299 Bulls and Cows 134 Gas Station 118 Pascal’s Triangle 很少考119 Pascal’s
2020-07-22 23:11:01
164
原创 leetcode 46 全排列（DFS）
https://leetcode-cn.com/problems/permutations/题目给定一个 没有重复 数字的序列，返回其所有可能的全排列。示例输入: [1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]思路DFS，标记一下使用过的，回溯时删除标记即可代码class Solution {public: vector <vector<int>> ans; .
2020-07-22 18:40:58
81
原创 leetcode 40 组合总和 II（DFS回溯）
https://leetcode-cn.com/problems/combination-sum-ii/题目给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。说明所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例输入: candidates = [10,1,2,7,6,1,5], target = 8,所求解集为:[[.
2020-07-21 19:44:43
77
原创 leetcode 22 括号生成（回溯）
https://leetcode-cn.com/problems/generate-parentheses/题目数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。示例输入：n = 3输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]思路dfs回溯即可，首先写好边界，当前还未完全生成好的字符串中**’(’** 的数量一定大于等于 ‘)’ 的数量，不然不是可以匹配的括号，并且每一种的数.
2020-07-20 21:03:01
118
原创 leetcode 10 正则表达式匹配（动态规划）
https://leetcode-cn.com/problems/regular-expression-matching/题目给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。‘.’ 匹配任意单个字符‘*’ 匹配零个或多个前面的那一个元素示例输入:s = “aa”p = “a”输出: false解释: “a” 无法匹配 “aa” 整个字符串。输入:s = “aa”p = “a*”输出: true解释: 因为 ‘*’ .
2020-07-19 21:41:30
127
原创 leetcode 221 最大正方形
https://leetcode-cn.com/problems/maximal-square/题目在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例输入:1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4思路动态规划，与上题转移方程一样，都是 （i, j） 处代表以其为右下角延伸出的最大的符合条件的正方形//上题转移方程写错已改正代码#include <cmath>class Solut.
2020-07-18 20:03:54
101
原创 leetcode 1277 统计全为1的正方形子矩阵（动态规划）
https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/题目给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。示例输入：matrix =[[0,1,1,1],[1,1,1,1],[0,1,1,1]]输出：15解释：边长为 1 的正方形有 10 个。边长为 2 的正方形有 4 个。边长为 3 的正方形有 1 个。正方.
2020-07-16 22:35:17
240
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人