- 博客(58)
- 收藏
- 关注
RSS订阅原创 数据结构——七种排序算法
排序是指把一组无序的数据元素（或记录）按照关键字值非递减（或非递增）次序重新排列成一个有序的序列。下面介绍我所掌握的几种排序算法。插入排序排序方法 最好情况 平均情况 最坏情况 稳定性 备注 插入排序 O(n) O(n²) O(n²) 稳定 适用于大部分已有序排列好 插入排序的基本操作就是将一个数据插...
2019-08-21 17:43:31
342
2
原创 Marvolo Gaunt's Ring
DescriptionProfessor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Ho...
2019-08-20 10:38:14
252
原创 B. Rolling The Polygon
Bahiyyah has a convex polygon with n vertices P0, P1, · · · , Pn−1 in the counterclockwiseorder. Two vertices with consecutive(连续的) indexes are adjacent(邻近的), and besides, P0 and Pn−1 are adjacent....
2019-08-19 10:17:16
257
原创 Postal Delivery
The postal service is interested in cutting costs as an alternative to raising the postage rates. One way to do this is by minimizing the distance traveled when delivering mail from the post office ...
2019-08-14 10:00:46
323
原创 CFGym 101532C Large Summation （算法pair+暴力）
学到了一个pair函数，pair<变量类型1，变量类型2>，如pair<int,int>,pair<string,int>,pair<char,char>......make_pair用来建立并赋值。pair<int,int> a[N]: a[i].first和a[i].second分别访问pair中的第一个值和第二个值...
2019-05-07 20:30:58
216
原创 17级计科ACM程序设计(下)
最小生成树（并查集）hdu1233还是畅通工程 hdu1863畅通工程 hdu1879继续畅通工程 hdu1232畅通工程以hdu1878继续畅通工程为例#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream>#incl...
2019-04-12 19:52:23
230
转载 最短路径算法模板：Dijkstra/Floyd/Bellman-Ford模板
出处：https://blog.csdn.net/Akatsuki__Itachi/article/details/76082494邻接矩阵实现#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAX=0x3f3f3f3f;int ...
2019-03-06 21:42:55
170
原创 A Rational Sequence （UVALive 7786 && UVALive 7096）
两个题的区别在于，一个是给出n求第n个是多少。一个是已知这个数，求它的下一个数。在做第二题的时候，因为我做过第一题有一种先入为主的思想，以为求它的下一个数就是先求出它是这个数塔里的第n个，然后求n+1个即可。完全错误，直接找规律求解即可。7786Sample Input41 12 43 114 1431655765Sample Output1 1/1...
2019-03-05 15:43:42
173
原创 UVALive 7097 Growing Rectangular Spiral
Sample Input 3 1 1 1 2 3 5 3 8 4Sample Output 1 NO PATH 2 2 3 5 3 6 1 2 3 9 10 11题意：给定一个第一象限的点，求到达这个点的最短长度。(线段按右上左下，每次必须最少大于前一次一个单位)思路：找规律易得，如果x=y无法达到，如果x<y,通过两次即可达到。如果x>y，前三次一定是1,2,3，第四...
2019-03-05 15:33:18
211
原创 UVALive 7094 Happy Happy Prime Prime
Sample Input 4 1 1 2 7 3 383 4 1000Sample Output 1 1 NO 2 7 YES 3 383 YES 4 1000 NO题意：确定这个数是不是happy数。条件一是必须为素数，二是每个位数上的数的平方和只要不是等于一就继续拆解直到为1，如果无法得到1则也不满足。思路：判断素数好写，在求平方和的时候把每一次出现过的数记下来，如果再次出现则...
2019-03-04 21:39:36
192
原创 UVALive 7092 Islands in the Data Stream
Sample Input 4 1 0 0 1 1 2 2 1 1 0 1 2 0 2 0 1 2 4 3 1 3 4 5 2 1 0 3 0 1 2 4 4 1 0 2 4 1 0 0 4 0 1 2 3 4 5 6 7 8 9 10 0Sample Output 1 4 2 8 3 6 4 10题意：一个集合里边的所有元素都大于集合两端的前一个和后一个元素，则这个集合为一个岛，求岛的...
2019-03-04 21:32:25
182
原创 HDU-5510 Bazinga（利用strstr函数找子串）
思路借鉴：https://blog.csdn.net/floraqiu/article/details/78512986Problem DescriptionLadies and gentlemen, please sit up straight.Don't tilt your head. I'm serious.For n given strings S1,S2,⋯,Sn , la...
2019-02-26 20:01:56
149
转载 关于lower_bound( )和upper_bound( )的常见用法
原文：https://blog.csdn.net/qq_40160605/article/details/80150252 ower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。在从小到大的排序数组中，lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于nu...
2019-02-25 10:01:52
128
原创 Divisor Subtraction
DescriptionYou are given an integer number nn. The following algorithm is applied to it:if n=0n=0, then end algorithm; find the smallest prime divisor dd of nn; subtract dd from nn and go to ste...
2018-12-09 16:14:46
355
原创 UVALive 7292 Refract Facts(二分法)
B - Refract FactsA submarine is using a communications laser to send a message to a jet cruising overhead. The sea surface is flat. The submarine is cruising at a depth d below the surface. The jet ...
2018-11-23 20:21:36
162
原创 UVALive 7293 Pork (恶心模拟题！！！)
Poker is a family of gambling card games involving betting and individual play, whereby the winner is determined by the ranks and combinations of players' cards, some of which remain hidden until the ...
2018-11-22 21:37:50
404
原创 poj3253——Fence Repair
DescriptionFarmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer lengt...
2018-10-19 17:42:59
131
原创 并查集进阶———小希的迷宫，is it a tree
B - 小希的迷宫Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64uDescription上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一...
2018-09-26 10:10:52
181
原创 畅通工程（并查集模板）
Description某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？Input测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随...
2018-09-22 20:53:23
78
原创 【USACO】Barn Repair 修理牛棚
Description在一个夜黑风高,下着暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 剩下的牛一个紧挨着另一个被排成一行来过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,农民约翰必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是供应商只能提供有限数目的木板。 农民约翰想将他购买的木板总长...
2018-09-07 20:06:27
592
原创 CodeForces 1016B
DescriptionYou are given two strings ss and tt, both consisting only of lowercase Latin letters.The substring s[l..r]s[l..r] is the string which is obtained by taking characters sl,sl+1,…,srsl,sl+...
2018-08-10 11:37:54
214
原创 CodeForces 1017B——The Bits
DescriptionRudolf is on his way to the castle. Before getting into the castle, the security staff asked him a question:Given two binary numbers aa and bb of length nn. How many different ways of s...
2018-08-10 09:50:33
234
原创 CodeForces 996B World Cup（两种方法，int可过long long超时的恶心例题）
DescriptionAllen wants to enter a fan zone that occupies a round square and has nn entrances.There already is a queue of aiai people in front of the ii-th entrance. Each entrance allows one per...
2018-08-10 09:26:56
450
原创 HDU3555 Bomb (数位dp)
还有另一道例题，戳这里～---------------------------------------------------------------------我------是------分------割------线-------------------------------------------------------------------------Problem Descr...
2018-08-09 10:53:15
182
转载 划分树详解+划分树模板代码
转自博主语海与冰看了一些博客，感觉有些博客对建树写的挺好，但是对于查询区间却一笔带过。在看懂了之后决定自己写一篇，加深自己的理解，也希望对正在学习划分树的人能够有所帮助。如有错误，敬请大佬指出。进入正题：有这样一类题目，求的是区间内的第k大数。划分树的定义就是对整体的区间进行划分，把相对于原来序列中较小的值放在左子树，较大的放在右子树，最后按照它的性质进行查询以此找到要查询的区间...
2018-08-07 17:18:55
326
原创 CodeForces 1011B Planning The Expedition (map迭代器)
atasha is planning an expedition to Mars for nn people. One of the important tasks is to provide food for each participant.The warehouse has mm daily food packages. Each package has some food type a...
2018-08-05 21:11:37
176
原创 CodeForces - 869B The Eternal Immortality（8.3个人赛）
Even if the world is full of counterfeits, I still regard it as wonderful.Pile up herbs and incense, and arise again from the flames and ashes of its predecessor — as is known to many, the phoenix d...
2018-08-04 09:08:16
171
转载 数位DP详解和基础例题
转载自：http://www.cnblogs.com/itlqs/p/5935308.html数位DP其实是很灵活的，所以一定不要奢求一篇文章就会遍所有数位DP的题，这一篇只能是讲清楚一种情况，其他情况遇到再总结，在不断总结中慢慢体会这个思想，以后说不定就能达到一看到题目就能灵活运用的水平。（其实DP都是这样……） 这一篇要说的数位DP是一道最简单的数位DP：HDU2089 ...
2018-08-03 14:35:13
1110
4
原创 线段树——基础模板题
弱鸡一个，照着模板修修改改就能ac的模板题 A - 敌兵布阵C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手...
2018-08-02 17:23:57
148
转载 树状数组（码住细看）
1. 单点修改 + 区间查询最简单的树状数组就是这样的：void add(int p, int x){ //给位置p增加x while(p <= n) sum[p] += x, p += p & -p;}int ask(int p){ //求位置p的前缀和 int res = 0; while(p) res += sum[p], p -= p &...
2018-08-01 09:02:58
88
转载 树状数组详解
一、树状数组是干什么的？ 树状数组或者二叉索引树也称作Binary Indexed Tree，又叫做Fenwick树；它的查询和修改的时间复杂度都是log(n)，空间复杂度则为O(n)，这是因为树状数组通过将线性结构转化成树状结构，从而进行跳跃式扫描。通常使用在高效的计算数列的前缀和，区间和。二、树状数组怎么干的？ 在图中，a数组就是原数组，c数组则是树状数组，我...
2018-07-31 16:43:26
141
原创 Flip the Bit（第二次组队赛）
C. Flip the BitYou are given a positive integer n. Your task is to build a number m by flipping the minimum number of bits in the binary representation of n such that m is less than n (m < n) and...
2018-07-29 18:52:37
230
原创 Friends and Cookies（第二次组队赛）
Abood's birthday has come, and his n friends are aligned in a single line from 1 to n, waiting for their cookies, Abood has x cookies to give to his friends.Here is an example to understand how Aboo...
2018-07-29 18:13:44
279
原创 Polycarp's Practice(从一组数据中找出前n个最大的数的及其下标)
Polycarp is practicing his problem solving skill. He has a list of nn problems with difficulties a1,a2,…,ana1,a2,…,an, respectively. His plan is to practice for exactly kk days. Each day he has to sol...
2018-07-28 09:30:40
423
原创 Coins and Queries（map函数初体验）
map函数map<键，键值>实现一对一映射关系，以后再写博客详细说。Polycarp has nn coins, the value of the ii-th coin is aiai. It is guaranteed that all the values are integer powers of 22 (i.e. ai=2dai=2d for some non-negat...
2018-07-27 11:35:32
263
原创 Intense Heat（前缀和）
The heat during the last few days has been really intense. Scientists from all over the Berland study how the temperatures and weather change, and they claim that this summer is abnormally hot. But an...
2018-07-27 10:04:17
386
原创 Binary String Constructing（巨水，也证明我真的巨菜）
You are given three integers aa, bb and xx. Your task is to construct a binary string ss of length n=a+bn=a+b such that there are exactly aa zeroes, exactly bb ones and exactly xx indices ii (where 1≤...
2018-07-27 09:59:30
346
原创 广度优先搜索BFS——模板（附四维拓展：SDUT 3929魔戒）
广度优先搜索使用队列(queue)来实现，整个过程也可以看做一个倒立的树形：把根节点放到队列的末尾。每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。找到所要找的元素时结束程序。如果遍历整个树还没有找到，结束程序。 一般用于求起点到终点的步数。#include <stdio.h>#include...
2018-07-26 17:05:56
305
原创 Max Sum(最大连续子序列)
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14. InputThe...
2018-07-26 11:27:47
457
原创 Advanced Fruits(最长公共子序列)
The company "21st Century Fruits" has specialized in creating new sorts of fruits by transferring genes from one fruit into the genome of another one. Most times this method doesn't work, but sometime...
2018-07-25 11:47:36
661
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人