- 博客(175)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 线性基例题
最大异或和，第k小异或和最大异或和12345678910111213141516171819202122232425262728293031323334353637383940414243#include<bits/stdc++.h>#define INIT(a,b) memset(a,b,sizeof(a))#d...
2019-08-13 00:24:43
265
原创 进阶训练-数论
>质数对于一个足够大的整数N，不超过N的质数大约有N/lnN个；求出L，R(1<=L<=R<=2^31,R-L<=1e6)之间相邻两个质数的差的最大值是多少。解：筛出2~sqrt(R)间所有的素数，用这些素数筛掉[L,R]之间的合数，然后扫描即可。将N!分解质因数。解：N！的每个质因子都不会超过...
2019-08-12 14:16:04
542
原创 进阶训练-基本算法
位运算，递推与递归，前缀和与差分，二分，排序，倍增，贪心位运算移位运算快速幂，快速乘（1e18），状态压缩，成对变换，lowbit。12345678910//快速乘ll mul(ll a,ll b,ll p){ ll ans=0; while(b){ if(b&1) a=(ans+a)%p; ...
2019-08-10 20:32:44
310
原创 进阶训练-基本数据结构
单调栈，单调队列，双端队列，邻接表，Hash，字符串，trie单调栈借助单调性处理问题的思想在于及时排除不可能的选项，保证策略集合的高度有效性和秩序性，从而为我们做出的决策提供更多的条件和可能方法。例题：直方图的最大矩形面积单调队列同单调栈一样，也是在决策集合中及时排除一定不是最优解的选择，是优化动态规划的一个重要手段...
2019-08-10 08:46:09
172
原创 进阶练习-搜索
树与图的遍历，DFS，剪枝，迭代加深，BFS，双端队列BFS，优先队列BFS，A，K短路，IDA树与图的遍历DFS序：每个节点x的编号在序列中恰好出现两次。设这两次出现的位置为L[x]和R[x]，那么闭区间[L[x],R[x]]就以x为根的子树的DFS序。树的重心，树的深度，图的连通块划分拓扑排序：拓扑排序可以判定有向图是否...
2019-08-10 03:43:27
333
原创 Kth number———主席树模板
传送门HDU2665描述Give you a sequence and ask you the kth big number of a inteval.输入The first line is the number of the test cases.For each test case, the first line cont...
2019-07-27 13:30:22
239
原创 Keen On Everything But Triangle——主席树
传送门HDU6601描述N sticks are arranged in a row, and their lengths are a1,a2,…,aN.There are Q querys. For i-th of them, you can only use sticks between li-th to ri-th. Plea...
2019-07-27 09:24:10
201
原创 luogu P2617——树状数组套主席树
传送门luogu P2617描述给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这...
2019-07-27 05:47:42
151
原创 Atlantis(扫描线面积并)
传送门 HDU1542描述There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the islan...
2019-07-24 14:23:58
155
原创 Picture(扫描线周长并)
传送门 HDU1828描述A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each r...
2019-07-24 06:04:25
327
原创 Farming(扫描线体积并)
传送门 HDU3255描述You have a big farm, and you want to grow vegetables in it. You’re too lazy to seed the seeds yourself, so you’ve hired n people to do the job for you.Eac...
2019-07-24 02:18:22
205
原创 Pots
传送门POJ3414描述You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:FILL(i) fill the pot i (1 ≤ i ...
2019-07-14 23:06:17
291
原创 Magic Cube
传送门ZOJ2477描述This is a very popular game for children. In this game, there’s a cube, which consists of 3 3 3 small cubes. We can unwrap the cube, it will become like ...
2019-07-14 21:52:07
1166
原创 Gap
传送门HDU1067描述Let’s play a card game called Gap.You have 28 cards labeled with two-digit numbers. The first digit (from 1 to 4) represents the suit of the card, and the ...
2019-07-14 14:19:36
377
原创 Travelling(三进制状压dp)
传送门HDU3001描述After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He has decided to visit n cities(he insists on seeing all the...
2019-07-14 13:58:25
548
原创 DNA Sequence(IDA*,迭代深搜)
传送门HDU1560描述The twenty-first century is a biology-technology developing century. We know that a gene is made of DNA. The nucleotide bases from which DNA is built are A...
2019-07-14 12:58:25
245
原创 Fire Game(双起点BFS)
传送门FZU2150描述Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of this board is consisti...
2019-07-14 08:03:32
153
原创 Eight2
传送门HDU3567描述Eight-puzzle, which is also called “Nine grids”, comes from an old game.In this game, you are given a 3 by 3 board and 8 tiles. The tiles are numbered from...
2019-07-14 06:32:08
135
原创 Escape
传送门HDU3533描述The students of the HEU are maneuvering for their military training.The red army and the blue army are at war today. The blue army finds that Little A is t...
2019-07-14 05:17:04
226
原创 Fliptile
传送门POJ3279描述Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they man...
2019-07-14 04:23:21
272
原创 Find a way
传送门HDU2612描述Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good ...
2019-07-14 02:52:40
86
原创 Fire
传送门UVA11624描述Joe works in a maze. Unfortunately, portions of the maze havecaught on fire, and the owner of the maze neglected to create a fireescape plan. Help Joe esc...
2019-07-14 01:46:44
99
原创 Eight
传送门HDU1043描述The 15-puzzle has been around for over 100 years; even if you don’t know it by that name, you’ve seen it. It is constructed with 15 sliding tiles, each wit...
2019-07-14 01:40:09
185
原创 非常可乐
传送门HDU1495描述大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升 (正好...
2019-07-14 00:58:02
82
原创 Nightmare2
传送门HDU3085描述Last night, little erriyue had a horrible nightmare. He dreamed that he and his girl friend were trapped in a big maze separately. More terribly, there are...
2019-07-14 00:52:03
250
原创 Edit Distance
描述设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括(1)删除一个字符；(2)插入一个字符；(3)将一个字符改为另一个字符。将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2 个字符串A和B，计算出它们的编辑距离...
2019-06-30 23:11:21
127
原创 Jack Straws —— 判断直线相交
传送门Poj1127描述In the game of Jack Straws, a number of plastic or wooden “straws” are dumped on the table and players try to remove them one-by-one without disturbing the...
2019-06-30 14:23:10
301
原创 Independent Task Scheduling
传送门SwustOj698描述用2 台处理机A 和B 处理n 个作业。设第i 个作业交给机器A 处理时需要时间ai ，若由机器B 来处理，则需要时间bi 。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai >=bi，而对于某些j,j≠i，有aj < bj 。既不能将一个作业分开由2 台机器处理，也没有一台机器能...
2019-06-30 12:41:06
956
原创 Roadblocks——次短路
传送门POJ3255描述Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, bec...
2019-06-29 07:04:56
125
原创 迷宫城堡——Tarjan
传送门HDU1269描述为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是...
2019-05-07 18:42:12
135
原创 Summer Holiday——Tarjan缩点
传送门HDU1827描述To see a World in a Grain of SandAnd a Heaven in a Wild Flower,Hold Infinity in the palm of your handAnd Eternity in an hour. —— William B...
2019-05-07 14:06:27
93
原创 最小圆覆盖
传送门HDU3007描述Each person had do something foolish along with his or her growth.But,when he or she did this that time,they could not predict that this thing is a mistake...
2019-05-03 21:46:58
123
原创 确定比赛名次——拓扑排序
传送门HDU1285描述有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。输入输入有...
2019-05-03 14:59:12
226
原创 归并求逆序数
思路在归并排序的同时求逆序数区间[l,r]中，mid=(l+r)/2，i从l到mid,j从mid+1到r，当a[i]>a[j]的时候，a[i~mid]一定都大于a[j]，因为单独看左右区间是已经排好序的，sum+=mid-i+1即可Code12345678910111213141516171819202122232425...
2019-05-03 01:52:38
334
原创 最近点对
传送门最近对问题题目描述设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。输入多组测试数据，第一行为测试数据组数n（0<n≤100），每组测试数据由两个部分构成，第一部分为一个点的个数m（0<m≤1000），紧接着是m行...
2019-04-27 04:10:10
2661
原创 凸包面积
传送门凸包面积题目描述麦兜是个淘气的孩子。一天，他在玩钢笔的时候把墨水洒在了白色的墙上。再过一会，麦兜妈就要回来了，麦兜为了不让妈妈知道这件事情，就想用一个白色的凸多边形把墙上的墨点盖住。你能告诉麦兜最小需要面积多大的凸多边形才能把这些墨点盖住吗？ 现在，给出了这些墨点的坐标，请帮助麦兜计算出覆盖这些墨点的最小凸多边形的面积。输...
2019-04-26 22:35:34
659
原创 全排列康托展开
传送门 排列的字典序问题题目描述n个元素{1,2,…, n }有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下： 0 1 2 3 4 5123 132 213 231 312 321任务：给定n 以及n 个...
2019-04-26 12:58:37
194
原创 二分图性质
最小点覆盖=最大匹配最小边覆盖=v-最大匹配=最大独立集点覆盖、最小点覆盖 点覆盖集即一个点集，使得所有边至少有一个端点在集合里。或者说是“点” 覆盖了所有“边”。。极小点覆盖(minimal vertex covering)：本身为点覆盖，其真子集都不是。最小点覆盖(minimum vertex covering)：点最少的...
2019-04-13 03:58:35
522
1
原创 Going Home (最小权值完备匹配)
传送门HDU1533描述On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an ad...
2019-04-07 23:27:02
152
原创 奔小康赚大钱（KM模板题）
传送门HDU2255描述传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。另一方面,村长和另外的村领导希望得到最大...
2019-04-07 15:26:38
93
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人