- 博客(40)
- 收藏
- 关注
RSS订阅
原创 叶子清除计划【第五周】 题解
叶子清除计划【第五周】题目描述⼩Y同学是⼀位数据结构⼤师同时也是⼀位园艺⼤师。秋天到了，⼩Y同学需要对学校内的⼀棵树展现他顶尖的修叶⽔平。学校内的这棵树是⼀颗拥有n个点的⽆根树，每次⼩Y会删去所有的叶⼦节点（即度数小于等于1的节点)，直到所有的点都被删除了为⽌。⼩Y现在想问你对于每个点，求出它是第⼏次操作中被删除的。输入格式第⼀⾏⼀个数字n，表⽰树上节点个数接下来n−1⾏，每⾏两个数字u,v，表⽰树上的⼀条边。输出格式⼀⾏n个数字，第i个数字表⽰节点i在第⼏次操作中被删除。样例样例输
2020-08-19 20:21:02
438
原创 构造完全图 题解
题目链接分析假设有如下图两个集合 xxx & yyy。因为要构造一个完全图，所以应该将xxx中的s[x]s[x]s[x]个节点与yyy中的s[y]s[y]s[y]个节点一一连接即连接s[x]∗s[y]−1s[x] * s[y] - 1s[x]∗s[y]−1（此处减一是为了在后面单独处理原图中的dis[i].wdis[i].wdis[i].w）个节点，为了保证此完全图的最小生成树所以要用(s[x]∗s[y]−1)∗(dis[i].w+1)(s[x] * s[y] - 1) * (dis[i].w
2020-08-17 20:56:16
291
原创 秘密的牛奶运输 题解
题目连接分析一道可以暴力水过去的次小生成树step1首先用KruskalKruskalKruskal||PrimPrimPrim求出原图的一颗最小生成树，在连边的时候，用一个visvisvis记录一下那些已经在最小生成树里面。step2提前暴力dfsdfsdfs或者bfsbfsbfs求出任意两点构成的环之间的最大权值具体操作定义函数dfs(ints,intu,intfather,intmw1,intmw2)dfs(int s, int u, int father, int m
2020-08-17 20:55:39
168
原创 「一本通 3.1 练习 4」Tree 题解
题目地址分析第一眼看到此题，感觉就是一道水题，直接加上前needneedneed小的白边就行了，再处理到n−1n-1n−1条黑边，但是，打完后突然发现有问题。。。 虽然加上了前needneedneed小的白边，但是会出现树不连通的现象，即无法构成生成树。正解思路二分一个增量midmidmid(可正可负)。跑一遍KruskalKruskalKruskal，将所有的白边都加上aaa，记录构成生成树后所用到的白边，如果数量小于needneedneed就将右端点往左移，否则往右移。最后的ansansan
2020-08-17 20:55:08
232
原创 数星星 Stars 题解
题目链接分析一道树状数组，但坑点比较多。。。首先在草稿纸上画图可以得知：星星的等级与xxx无关，至于yyy的大小有关，于是我们可以根据输入顺序一一将其插入树状数组进行维护，此星星的等级其实就是在插入前以111~星星的yyy的星星数量和。注意星星的坐标是从(0,0)(0, 0)(0,0)开始存，但树状数组不能够维护，所以要提前将所有星星的xxx加上一。(如果在求和函数中把限度跳到0就会卡死循环我就错了)代码#include <cstdio>#include <cstring&
2020-08-17 20:54:05
631
原创 SCOI 滑雪与时间胶囊 题解
SCOI 滑雪与时间胶囊题目描述a180285 非常喜欢滑雪。他来到一座雪山，这里分布着MMM条供滑行的轨道和NNN个轨道之间的交点（同时也是景点），而且每个景点都有一编号i(1<=i<=n)i(1<=i<=n)i(1<=i<=n)和一高度$。a180285能从景点。a180285 能从景点。a180285能从景点i滑到景点滑到景点滑到景点j当且仅当存在一条当且仅当存在一条当且仅当存在一条i和和和j之间的边，且之间的边，且之间的边，且i的高度不小于的高度不小于的高度
2020-08-15 21:10:13
288
原创 图论学习笔记3
图论学习笔记3Bellman-Ford 算法松弛负边权操作负权环判定朴素实现Spfa思想实现Bellman-Ford 算法Bellman-Ford算法：DijkstraDijkstraDijkstra类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。松弛每次松弛操作实际上是对相邻节点的访问，第 n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过 |
2020-07-30 22:11:36
138
原创 图论学习笔记2
最短路多源最短路Floyd多源最短路FloydFloydFloydFloyd是基于DPDPDP思想。设kkk为中转点，与iii, jjj都有边相连。那么可以得到dis[i][j]dis[i][j]dis[i][j]的最短路径的状态转移方程为：dis[k,i,j]=min(dis[k−1,i,j],dis[k−1,i,k]+dis[k−1,k,j]dis[k,i,j]=min(dis[k-1,i,j], dis[k-1,i,k]+dis[k-1,k,j]dis[k,i,j]=min(dis[k−1
2020-07-29 21:15:21
145
原创 图论学习笔记1
图论学习笔记 图的基本概念图的存储结构邻接矩阵邻接表存点加边图的遍历深度优先广度优先图的基本概念图：由**顶点（vertex）和边（edge）**组成。顶点—具体事物边—具体事物之间的联系顶点的集合VVV，边的集合EEE，图记为G=(V,E)G = (V,E)G=(V,E)图的存储结构一般分为两种 ： 邻接矩阵、邻接表邻接矩阵由一个二维数组实现,比较简单，但是在存储稠密图时比较不划算。G[i][j]G[i][j]G[i][j]表示的是顶点i与顶点j的关系。如果顶点i和顶点j之间有边相连
2020-07-28 21:58:15
125
原创 火柴排队 详解
火柴排队内存限制：128 MiB时间限制：1000 ms题目描述涵涵有两盒火柴，每盒装有n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为： ∑(ai−bi)2∑(ai-bi)^2∑(ai−bi)2其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数
2020-07-12 18:07:56
1081
3
原创 【NOIP2009】最优贸易 题解
今天考了一道分层图，本来是一道板题，结果我被误导了，想成了 架设电话线一题，考完写炸了才发现，架设电话线只需要求出第k+1大的长度，只需要满足局部最优，但是飞行线路要使总和最小，只能用分层图，然后我翻了半天标签，找到了这道题。link但是当旁边LH看到之后，他告诉我，这是一道DP。结果我没看出来。。。分层图倒是很简单。Sulotionstep1首先，他可以在图上到处走动，所以很自然地可以建一张图，所有的边权都是0。然后这道题只与水晶球的价格有关，所以我们把点权搬到边权上面。step2因为
2020-10-07 17:31:19
161
原创 假日住宿 题解
假日住宿题目描述给出一棵NNN节点的树，每个节点代表一个城市，每个城市有一个人，每个人离开自己的城市到另一个城市，每个城市只能有一个人，问这NNN个人移动距离和的最大值。输入格式输入的第一行包含一个整数T(1<=t<=10)T(1<=t<=10)T(1<=t<=10)，表示测试用例的数量。每个测试用例包含几行。 第一行包含一个整数2<=N<=1052<=N<=10^52<=N<=105，代表城市数。 然后接下来的行分别包含三
2020-10-04 14:57:52
366
原创 初二普及组全真模拟赛 题解
数你太美【第一周】题目描述PB 获得了两个正整数数列 ai{a_i}ai , bi{b_i}bi ，长度分别为 n , m ，其中每个数都小于 10。 定义一个正整数是“美丽的正整数”，当且仅当:这个数的十进制表示中，至少有一个 数位上的数在数列 a_i 出现过，至少有一个数位上的数在数列 b_i 出现过。现在 PB 希 望求出最小的“美丽的正整数”。输入格式第一行，两个正整数 n , m ;第二行，n 个正整数，第 i 个为 a_i ;第三行，m 个正整数，第 i 个为 b_i 。输出格
2020-09-12 13:28:27
341
原创 RMQ算法总结
RMQRMQ 即范围最小值问题 (Range(Range(Range MinimumMinimumMinimum Query)Query)Query)支持查询从Al,Al+1,Al+2...，ArA_l, A_{l+1},A_{l+2}...，A_rAl,Al+1,Al+2...，Ar中的极值(Max(Max(Max ororor Min)Min)Min)算法思想设dpi,jdp_{i,j}dpi,j为左端点为iii， 右端点为2j(1<<j)2^j(1 << j)
2020-08-24 21:41:07
153
原创 Ant Trip 题解
Ant Trip分析题意很简单，爆搜的时间复杂度比较高，不考虑。应该使用欧拉回路的相关知识求解。intn()输入时将两个节点的入度都加一（无向），然后将两个节点合并在一个连通图中.for (int i = 1, u, v; i <= m; i++) { scanf ("%d %d", &u, &v); in[v] ++, in[u] ++; UnionSet(u, v);}TFW居然都不知道要将两个节点合并在一个连通图中work(
2020-08-20 20:43:03
190
1
原创 From Hero to Zero 题解
题目地址分析考试时的一道水题但是还是没拿满，按题目意思模拟即可#include <cstdio>#include <iostream>#include <algorithm>#define LL long longusing namespace std;LL t, n, k, step;int main() {// freopen("game.in", "r", stdin);// freopen("game.out", "w", stdout)
2020-08-17 20:54:38
242
原创 最小生成树 学习笔记1 - Kruskal
最小生成树定义Kruskal算法算法流程具体实现建立结构体存边并查集维护完整代码定义给定一个带权图，满足以下条件：1.保证图中所有的点都联通2.在满足条件1的情况下尽可能去掉多的边，使得所有的边权之和最小，即Σi=1i<=mwi\Sigma_{i=1}^{i<=m}w_iΣi=1i<=mwi最小。Kruskal算法Kruskal是基于贪心的思想，根据以上的定义描述依次枚举1−m1-m1−m条边，如果两个点没有存在于一个连通分量中，那么就连上这一条边。此算法的难点在于查
2020-08-05 18:34:56
148
原创 树状数组学习笔记
定义树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。 —— by baidu实现用一个数组bit[i]bit[i]bit[i]表示从[i−lowbit(x)+1,x][i - lowbit(x) + 1
2020-07-26 22:16:18
111
原创 数三角 题解
数三角题目描述输入格式输出格式样例样例输入样例输出分析预处理求出连通性判断是否构成三角形完整代码题目描述这是一个数三角的游戏。长度为1或SQRT(2)的小木棍放在一个网格上。如图所示，有水平的，垂直的或对角的。对角放置的木棍可以交叉。将木棍随意地放在网格上得到的图案可能不含三角形，也可能含一个或多个三角形。如下图所示，(a),(b),©,(d)和(e)分别含有2,5,12,0,0个三角形。你的任务是写一个程序数出一个图案中的三角形个数。。cpp输入格式输入文件count.in包括N+1行：
2020-07-25 21:16:09
308
原创 分离与合体题解 区间DP + DFS
题目描述经过在机房里数日的切磋，LYD 从杜神牛那里学会了分离与合体，出关前，杜神牛给了他一个测试……杜神牛造了n 个区域，他们紧邻着排成一行，编号 1 ~ n 。在每个区域里都放着一把 OI 界的金钥匙，每一把都有一定的价值，LYD 当然想得到他们了。然而杜神牛规定 LYD 不能一下子把他们全部拿走，而是每次只可以拿一把。为了尽快得到所有金钥匙，LYD 自然就用上了刚学的分离与合体特技。一开始 LYD 可以选择 1 … n - 1 中的任何一个区域进入，我们不妨把这个区域记为k 。进入后 LYD
2020-07-19 20:32:10
225
原创 拓扑排序学习笔记
拓扑排序拓扑排序是对一张 有向 并且 无环 的图进行遍历排序。如果在图中所有的节点构成的序列AAA中，对于每一条边(x,y)(x, y)(x,y)：xxx都出现在yyy的前面，则序列AAA就为这张图的拓扑序。关于入度和出度入度 ：以节点xxx为终点的有向边的条数被称为xxx的入度。记作 deg(x)deg(x)deg(x) .出度 ：以节点xxx为起点的有向边的条数被称为xxx的出度。例如在此图中，节点3的入度就为2 ，节点4的入度也为2.思想不断选择图中入度为0的节点入队（如上图中的节点
2020-07-11 12:25:54
176
原创 STL 技巧整理 7/22
STL 目录一览vectorqueuepriority_queuedequesetmultisetmapbitsetvector变长数组，内部基于倍增思想。声明#include <vector>vector<int> a;vector<int> b[250];struct node{...};vector<node> c;size/empty...
2020-07-07 14:11:17
202
1
原创 贪心 - 老鼠与猫的交易
题目描述有一只老鼠很喜欢奶酪，但是奶酪被分别放在N个房间里，而且这些房间都有一只猫咪看守，现在它准备和猫咪们做个交易。它有M磅的猫食，想用这M磅猫食换取奶酪。在猫咪看守的每一个房间里有奶酪J[i] 磅，同时猫咪需要F[i]磅的食物，如果老鼠给猫咪F[i] * (a)%的猫食，那么它就可以得到J[i] * (a)%的奶酪。现在已知每只猫咪对猫食的需求量和每个房间的奶酪数，那老鼠怎样才能换得最多的奶酪呢？输入格式第一行输入两个正整数M和N（M和N不大于10000），后面跟N行（每个房间的奶酪数和猫食的需求
2020-07-05 11:24:33
463
原创 防线
防线 2020/3/31题目描述达达学习数学竞赛的时候受尽了同仁们的鄙视，终于有一天…受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。就如同中二漫画的情节一样，怪兽达达打算毁掉这个世界。数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋，于是她集合了一支由数学竞赛选手组成的超级行动队。由于队员们个个都智商超群，很快，行动队便来到了怪兽达达的黑暗城堡的下方。但是，同样强大的怪兽达达在城堡周围布置了一条“不可越过”的坚固防线。防线由很多防具组成，这些防具分成了 N 组。我们可以认为防线是一维的，那么每一
2020-06-21 20:45:26
193
原创 bfs&dfs模板
摘自几个月前的帖子。。。DFS模板：向深处搜索，直到找到解或者走不下去。这一般解决全排列问题//No.1Void DFS（deep，...）{ if(找到解 || 走不下去了){ ......//根据题意添加 return; } for(扩展方式){ if(扩展方式所能达到的状态合法){ 修改操作；//根据题意添加 标记； DFS(deep+1,...); //根据题意是否要还原 } } }//No.
2020-06-21 19:09:09
133
原创 并查集学习总结
定义并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。并查集是一种树型的数据结构，用于处理一些
2020-06-21 15:13:49
166
1
原创 二叉树相关代码
小球#include <cstdio>#include <cstring>const int MAXN = 25; int d, i;int s[1 << MAXN];int main() { memset(s, 0, sizeof(s)); scanf("%d %d", &d, &i); int k, n = (1 << d) - 1; for(int j = 1;j <= i;j ++) { k = 1;
2020-06-21 14:47:50
140
原创 区间DP学习笔记
区间DP定义顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。实现思路既然是在区间里进行DP：以‘区间长度’作为阶段状态为某区间内的最有解，即将长度为1的元区间作为DP的最小状态。使用 dp[l,r]dp[l, r]dp[l,r] 描述每一个维度。典型例题删除字符串题目描述给出一个长度为n的字符串，每次可以删除一个字母相同的子串，问最少需要删多少次。 数据规模：n <= 500输入格式
2020-06-20 16:59:47
228
1
原创 多算法模板整理
1.递归int name(int n) { if(满足边界条件) return ...; if(满足边界条件) return ...; ... else { sbproblems... ... return name(...) + ... }}2.二分2.1 左边界int left_bound(int[] nums, int target) { if (nums.length == 0) return -1; int
2020-06-20 16:05:54
145
原创 防线题解
防线 2020/3/31题目描述达达学习数学竞赛的时候受尽了同仁们的鄙视，终于有一天…受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。就如同中二漫画的情节一样，怪兽达达打算毁掉这个世界。数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋，于是她集合了一支由数学竞赛选手组成的超级行动队。由于队员们个个都智商超群，很快，行动队便来到了怪兽达达的黑暗城堡的下方。但是，同样强大的怪兽达达在城堡周围布置了一条“不可越过”的坚固防线。防线由很多防具组成，这些防具分成了 N 组。我们可以认为防线是一维的，那么每一
2020-06-20 16:04:30
366
原创 搜索考试总结
关于昨天搜索考试的题目考察内容大体如下:1.有重复元素的排列问题dfs + STL大法(去重)2.烈火金刚bfs板子题3.剪纸记忆化搜索4.玛丽有只小羔羊二分 + bfs难度排序1 < 2 < 3 < 41.有重复元素的排列问题此题可以用STL模板自带的去重完成,其思想和全排列类似上代码#include<cstdio>#include<algorithm>#include<cstring>usin
2020-06-20 16:03:17
208
原创 二分总结
施工完毕二分算法是分治中的一种，所谓二分，其实就是将一个较大的问题缩小x区间去求解废话不多说详情请见百度我个人认为二分有点儿难，主要要将l,r与mid处理好Knuth(好像 是他发明的KMP 来着）曾经说过Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky思路很简单，细节是魔鬼。First二分查找额，k才开始学习
2020-06-20 15:54:58
211
原创 递推总结
递推总结首先：什么是递推递推中文名外文名递推The Recursive定义“递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。”“所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。从已知条件出发逐步推到问题结果
2020-06-20 15:41:43
689
原创 区间DP学习笔记 6/20
区间DP定义顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。实现思路既然是在区间里进行DP：以‘区间长度’作为阶段状态为某区间内的最有解，即将长度为1的元区间作为DP的最小状态。使用 $dp[l, r]$ 描述每一个维度。典型例题删除字符串题目描述给出一个长度为n的字符串，每次可以删除...
2020-06-19 14:05:00
111
原创 搜索考试
关于昨天搜索考试的题目考察内容大体如下: 1.有重复元素的排列问题dfs + STL大法(去重) 2.烈火金刚bfs板子题 3.剪纸记忆化搜索 4.玛丽有只小羔羊二分 + bfs 难度排序 1 < 2 < 3 < 41.有重复元素的排列问题此题可以用STL模板自带的去重完成,其思想和全排列类似上代码 #include<cst...
2020-04-06 18:20:05
347
原创 模板整理
1.递归int name(int n) { if(满足边界条件) return ...; if(满足边界条件) return ...; ... else { sbproblems... ... return name(...) + ... }}2.二分2.1 左边界int left_bound(in...
2020-04-04 14:06:05
105
原创 防线 2020/3/31
防线 2020/3/31题目描述达达学习数学竞赛的时候受尽了同仁们的鄙视，终于有一天......受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。就如同中二漫画的情节一样，怪兽达达打算毁掉这个世界。数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋，于是她集合了一支由数学竞赛选手组成的超级行动队。由于队员们个个都智商超群，很快，行动队便来到了怪兽达达的黑暗城堡的下方。但是，同样强大的怪兽达达在...
2020-03-31 20:04:24
122
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人