- 博客(54)
- 收藏
- 关注
RSS订阅原创 最小生成树模板及其dfs总结 （kruskal prim）
克鲁斯卡尔利用并查集，将排好序的每条边，如果不存在于并查集中就依次插入上模板，方便查阅#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 2e5 + 10;#define inf 0x3f3f3f3fint fa[N];int n, m;struct edge{ int u, v, w; bool operat
2020-08-07 20:43:03
366
原创 HDU - 5695（拓扑排序，最大权优先队列）
题意：1-n的同学排队，总有些奇葩的要求，比如a同学不想b同学站自己前面，也就是理解为b必须在a后面，这样的奇葩要求有m个，每个同学评价分为包括自己的前边最小id，求所有同学的最大分数和拿到这题，看到a后面是b的要求，就能想到一条a指向b的边，a入度为0应该先考虑，a考虑了，b的入度就变成了0就该接着考虑，就可以想到用拓扑排序，维护一个最大优先权队列，先将入度为0全部入列，然后挨个pop维护minn并累加进ans里，每次都要记得更新节点入度，出现0就入列，队列空时即为结束，输出anstm我比赛时定义的v
2020-08-05 19:13:07
200
原创 HDU6814（数学期望，分数取模）
传送门题意：已知直角四面体三个直角边长，求E(1/h^2)看了官方题解的高端解法，我比赛时就用的很朴素的高中做法：等体积法，把1/h^2表示出来E(1/h^2)=3E(1/a平方)超了好几次，最后将我总结的点分享出来1、尽量少开ll容易超时2、intll容易爆，llint不用担心3、做数学题要稳住，别推错了2333上代码#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#inclu
2020-08-04 23:38:19
466
原创 Interesting Computer Game（并查集，离散化）
题意：每次可以从两个数中选一个，求最多能选几个数每两个组合在一起，可以想到用并查集，开始可以用离散化处理数据（map真香），每一个并查集内部，如果成环就是n（n是点的个数），未成环就是n-1，具体看代码#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>.
2020-08-04 00:33:45
294
原创 树状数组总结
树状数组基础参考博文：https://bestsort.cn/2019/04/26/195/大赞！树状数组是一个查询和修改复杂度都为logn的数据结构，主要用于数组的单点修改&&区间求和，另外一个具有类似功能的是线段树具体区别和联系如下：1、两者复杂度统计，但树状数组的常熟明显优于线段树，编程码量复杂度也小于线段树2、树状数组的作用被线段树完全涵盖，凡是可以使用树状数组解决的问题，使用线段树一定可以解决，但反之未必3、树状数组的突出特点是码量小，简洁，使用了lowbit函数迅速
2020-08-03 15:06:22
106
原创 数据离散化模板
今天看视频注意到了这个点，有的题目数据较大，总过不了，得用到离散化首先适用的场合：有些数据本身很大，自身无法作为数组的下标保存对应的属性如果只是需要这堆数据的相对属性，就可以对其进行离散化处理离散化：与数据是多少无关，只与他们彼此间的相对大小有关，就可以离散化...
2020-08-03 00:36:49
122
原创 Dividing（除法分块总结）
传送门题意：横纵坐标均有个范围[1,N] [1,K],求在这个范围里满足要求点的数量，要求如下画图推点易得，每一列的点数利用O根号n除法分块就可以算出答案，最后还要注意第一列多算了n要减掉#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#i
2020-08-02 12:01:49
205
原创 Mask Allocation（思维，递归）
传送门题意：已知n，m，有n*m个物资，要求输出一个序列，具体一个数不能拆开，但多个数可以组合在一起，要求该序列可以平均组合成n组或m组，且必须字典序最大我想了半天，一直想着找规律把序列给凑出来，中间我好像也想到过递归，但停留时间太短，没有拿递归，谁知道递归这么简单，555菜哭了人，果然我还是差点火候，然后超级棒的队友貌似找到了规律，ac了，接下来是我补题时用的递归思考过程n*m个物资需要都能组合成n组或m组（让n始终>m），我们就可以先拎出m个m，然后剩下的left就可以转化成一个子问题（n
2020-08-01 19:16:20
312
原创 Codeforces Round #660 (Div. 2)B题（思维规律题、贪心）
传送门题目：Captain Flint and his crew keep heading to a savage shore of Byteland for several months already, drinking rum and telling stories. In such moments uncle Bogdan often remembers his nephew Denis. Today, he has told a story about how Denis helped him
2020-08-01 18:30:21
176
原创 CF1027D Mouse Hunt（topo总结）
题意：有n个房间和若干只老鼠（该题可直接当做一只处理），给定n值，以及每个房间来老鼠后下一个会去的房间号，还给了每个房间布置陷阱所需花的成本，求能让老鼠最终落网的布置陷阱的最小成本本题需要用的数据结构就是基础的图论，用个next数组存下个邻接节点，然后在线存好数据后，我们需要注意，有n个节点也有n个边，那必然会有回路，其余是链的形式，我们用topo排序挨个去掉入度为0的链，剩余环（不可能剩多余链的），再用dfs统计最小值，即为ansAC代码#include<cstdio>#include
2020-07-31 23:37:29
221
原创 并查集总结
并查集一、定义并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题集合定义方法：“代表元法”，每个集合选择一个节点作为整个集合的代表，最根部的父亲节点二、基本操作Find——查询一个元素属于哪一个集合Merge——把两个集合合并成一个大集合三、路径压缩与按秩合并①路径压缩将访问过的节点直接指向树根，均摊复杂度int find(int x) { return x == fa[x] ? fa[x] : fa[x] = find(fa[x]); }按秩合并“秩”：树的深度(
2020-07-28 21:50:12
132
原创 克鲁斯卡尔
克鲁斯卡尔（加边法）：先取最小的边，在判断是不是一个集合（不是舍去，是加上）普里姆（加点法）：先已经判断了不是一个集合，再从不是的集合中找出最小的边把点加入，最后更新（再取，再更新。。）都是加到n-1条边停止（n个点最少由n-1条边连通），另外，Kruskal不用考虑重边（并查集自动取舍），Prim需要考虑重边（不考虑必错！）上板子，方便查阅#include <iostream>#include <string>#include <algorithm>#in
2020-07-27 11:55:44
138
原创 Bellman-Ford(贝尔曼-福特)（单源最短路径，比迪杰斯特拉增加了能解决负边权）
Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法可能就会失效，求出的最短路径就可能是错的。这时候，就需要使用Bellman-Ford算法来求解最短路径，Bellman-Ford算法的流程如下：给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，1.数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；2.以下操作循环执行至多n-1次，n为顶点数：
2020-07-25 01:41:47
186
原创 迪杰斯特拉（单源最短路经）&弗洛伊德（任意两点最短路径）
总结一下两个最短路径的算法，这个博客总结的挺好，写的好的地方我直接贴过来了https://blog.csdn.net/daaikuaichuan/article/details/80586408迪杰斯特拉一、定义描述Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法的时间复杂度为O(N^2)，比如下图可求1号节点到其余所有节点的最短路径：二、算法思想设G=(V,E)是一
2020-07-24 22:48:15
604
原创 线段树的原理与模板（上）
昨天训练第一次做到了线段树的题，琢磨了两个小时代码，大概看懂了，今天特地来整理总结记录一下原理与模板昨天看的一篇很不错的博文，也推荐给大家：https://blog.csdn.net/iwts_24/article/details/81484561下面都是自己语言描述整理的首先为什么要使用线段树？假设医院有8种药，每次开药进药都会引起响应库存数量的变化，也需要记录方便管理，我们都会想到用数组去存储int a[8]={1,2,3,4,5,6,7,8};如果进药（比如都是八盒），那就是很常规的O
2020-07-24 18:54:39
113
原创 牛客暑假训练第四场F题
题意：依次给出AC,AD,BC,BD的边长，要求判断是AB//CD还是AB//DC根据三角形两边之和大于第三条边，可得中间交叉的两条边一定大于旁边两条边，根据这判断一下即可（怎么这么简单，我还分情况讨论了半天…输在了数学上了orz）上代码#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstring>#inclu.
2020-07-21 11:20:48
64
原创 牛客暑假训练第四场B题
题意：提供一个n和一个c求fc(n)的值由题目的数学表达式，易得n每整除变小一次，就乘一个c，一直变成1为止，即为max值，自己做是一层一层的做，后来队友告诉要用素数筛选和合数分解的模板，就ac了因为根据唯一分解定理，任何一个大于1且不为质数的自然数，都能分解成有限个质数的乘积上代码#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#incl.
2020-07-21 11:03:22
159
原创 HDU - 1874 （2020.6.11训练G题）
题意：有N个点，M个双向边且有输入距离，求起点到终点的最短距离单源最短路径算法题AC代码#include<iostream>using namespace std;typedef long long ll;const ll maxn = 0xfffffff;int N, M;int map[205][205];int a, b, x;int f, l;int main(){ while (scanf("%d%d", &N, &M)!=EOF) {
2020-06-14 13:58:37
101
原创 CodeForces - 731C
ProblemArseniy is already grown-up and independent. His mother decided to leave him alone for m days and left on a vacation. She have prepared a lot of food, left some money and washed all Arseniy’s clothes.Ten minutes before her leave she realized that
2020-06-06 00:50:49
196
原创 codeforces 500C （2020.5.24训练C题）
ProblemNew Year is coming, and Jaehyun decided to read many books during 2015, unlike this year. He has n books numbered by integers from 1 to n. The weight of the i-th (1 ≤ i ≤ n) book is w i.As Jaehyun’s house is not large enough to have a bookshelf, h
2020-05-28 18:05:56
158
原创 CodeForces - 1072D （2020.5.21训练G题）
ProblemYou are given a matrix of size n×n filled with lowercase English letters. You can change no more than kletters in this matrix.Consider all paths from the upper left corner to the lower right corner that move from a cell to its neighboring cell to
2020-05-23 23:28:48
268
原创 CodeForces - 655C （2020.5.17训练B题）
ProblemIn an attempt to escape the Mischievous Mess Makers’ antics, Farmer John has abandoned his farm and is traveling to the other side of Bovinia. During the journey, he and his k cows have decided to stay at the luxurious Grand Moo-dapest Hotel. The h
2020-05-19 12:57:11
481
原创 CodeForces - 484D（2020.5.17训练D题）
ProblemIn a kindergarten, the children are being divided into groups. The teacher put the children in a line and associated each child with his or her integer charisma value. Each child should go to exactly one group. Each group should be a nonempty segme
2020-05-18 00:18:32
138
原创 CodeForces - 730J （2020.5.14训练J题）
ProblemNick has n bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda a i and bottle volume bi( ai ≤ bi).Nick has decided to pour all remaining soda into minimal number of bottles, moreover he has to
2020-05-15 23:34:23
246
原创 POJ - 2342 （2020.5.13D题）
ProblemThere is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In orde
2020-05-13 00:04:35
112
原创 HDU3555
题意：给定数字N，求1~N，有多少个数含49数位dp+dfs，详见注释AC代码#include<iostream>using namespace std;typedef long long ll;int digit[20];ll dp[20][2];ll dfs(int len, bool if4, bool limit)//if4表示长为len上一位是否是4，limit表示最高位是否是上界（还是随机0~9）{ if (len == 0) return 1; if (!l
2020-05-10 23:14:12
92
原创 UVA - 11825 （2020.4.26训练B题）
题意：给定n个电脑编号0~n-1，每个电脑能连接num个其他编号电脑，求一个最优划分，划分最多且每个划分都能覆盖全集电脑状压dp，要用到枚举子集这个重要的东西，如下其他的工作便是更新dp值，详见代码注释AC代码#include<iostream>#include<algorithm>#include<string.h>using namespac...
2020-05-07 15:52:59
117
原创 POJ - 3254 （2020.4.23训练B题）
ProblemFarmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regre...
2020-05-06 18:11:47
285
原创 CodeForces - 366C（2020.4.19训练A题）
ProblemDima, Inna and Seryozha have gathered in a room. That’s right, someone’s got to go. To cheer Seryozha up and inspire him to have a walk, Inna decided to cook something.Dima and Seryozha have ...
2020-04-26 01:11:06
156
原创 HDU - 4745（2020.4.19训练B题）
ProblemLong long ago, there lived two rabbits Tom and Jerry in the forest. On a sunny afternoon, they planned to play a game with some stones. There were n stones on the ground and they were arranged...
2020-04-24 16:41:50
146
原创 POJ - 2955（2020.4.19训练C题）
ProblemWe give the following inductive definition of a “regular brackets” sequence: the empty sequence is a regular brackets sequence, if s is a regular brackets sequence, then (s) and [s] ar...
2020-04-23 12:52:16
220
原创 UVA - 10534 （2020.4.16训练A题）
题意：给定一个长为n的序列，求符合wavio sequences要求的最长序列长度分别顺向和逆向统计最长上升长度，取min，乘2减一即为wavio sequences长度，但要注意统计最长上升长度时，不能单纯从第一个开始，见一个大的更新一下，更新过的容器本身也需要更新（定义一个容器，遇到一个比top大的，就插入，遇到相等的就不作为（可以包含在小于的情况里），遇到小于的，就在容器里找不小于这个数...
2020-04-21 18:33:43
94
原创 LightOJ - 1248（2020.4.16训练H题）
ProblemGiven a dice with n sides, you have to find the expected number of times you have to throw that dice to see all its faces at least once. Assume that the dice is fair, that means when you throw...
2020-04-17 08:57:08
155
原创 HDU - 2844（2020.4.12训练H题）
ProblemWhuacmers use coins.They have coins of value A1,A2,A3…An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He...
2020-04-15 19:06:08
138
原创 CodeForces - 190C （2020.4.2训练K题）
ProblemVasya used to be an accountant before the war began and he is one of the few who knows how to operate a computer, so he was assigned as the programmer.We all know that programs often store se...
2020-04-04 00:48:12
199
原创 CodeForces - 190C （2020.4.2训练K题）
ProblemVasya used to be an accountant before the war began and he is one of the few who knows how to operate a computer, so he was assigned as the programmer.We all know that programs often store se...
2020-04-04 00:46:33
485
1
原创 CodeForces - 1080E （2020.3.29训练I题）
ProblemSonya had a birthday recently. She was presented with the matrix of size n×m and consist of lowercase Latin letters. We assume that the rows are numbered by integers from 1 to n from bottom to...
2020-04-02 16:53:16
139
原创 CodeForces - 128B （2020.3.29训练G题）
ProblemOne day in the IT lesson Anna and Maria learned about the lexicographic order.String x is lexicographically less than string y, if either x is a prefix of y (and x ≠ y), or there exists such ...
2020-04-01 14:47:31
155
原创 HDU - 5769 （2020.3.26训练D题）
Problem?? is practicing his program skill, and now he is given a string, he has to calculate the total number of its distinct substrings.But ?? thinks that is too easy, he wants to make this problem...
2020-03-27 16:55:11
108
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人