10 liurui39660

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 4w+

hdu 1520 && poj 2342

讨论树形dp,利用深搜处理每个人,对于每个人而言,都有自己来或不来所得到的活跃度,都要记录下来,每个人的活跃度初始化到自己来的状态上,对于每个人,如果自己不来,从每个直接下属来或不来中取较大者加到自己身上,如果自己来,把每个直接下属不来加到自己身上,最后取boss来或不来的最大值返回即可 实现上,没什么可说的,只是读题的时候需要仔细一点,前者是下属,后者是上司题解状态124MS,1544K,979

2016-09-20 21:51:41

hdu 5882

讨论水题,对于每种情况,如果能将这些节点划分为若干个强联通的三角形,那就是可以,否则就不行,再具体一点,从多边形里任选3个点,连有向边,如果到构成完全图为止都不会出现需要双向边的情况就是可以,再具体一点,只要节点是偶数个就不行,奇数个就可以题解状态0MS,1412K,406B,G++题解代码#include<cstdio>#include<cstring>#include<algorithm>

2016-09-17 18:59:49

hdu 5879

讨论水题,首先要知道这个数的极限是收敛的,收敛于π26\pi^2\over 6,得到估算值1.644934,然后打表找到这个数,不到12万,然后对于前面12万个数打表解决,往后的直接输出1.64493,但烦人的是题目的输入范围是很随便的,不但会有特别大的,而且会有带前导0的,简单利用字符串处理即可题解状态15M,2368K,662 B,G++题解代码#include<cstdio>#include

2016-09-17 18:53:45

hdu 5878

讨论水题,事先打好表,发现只有不到5200个不同的数,然后二分就可以了 怎么打表?写个四重循环,反正在本地跑,多跑一会也无所谓 所以下面给的代码不是提交的代码(5194个数,一点都不好看),而是生成的代码 其实生成代码里的另一部分是用另外一个代码生成的,那个就太好想了 然而比赛没想到……题解状态624MS,1432K,44328 B,G++题解代码#include<cstdio>#incl

2016-09-17 18:35:07

hdu 4417

讨论划分树,二分,以往是直接问区间第k个数是几,这回反过来,给数问是第几个,二分即可,划分树的构造是线性对数级,每次查询是对数级,这样综合复杂度就是构造的O(NlogN)O(NlogN)和查询的O(Q(logN)2)O(Q(logN)^2)题解状态343MS,15424K,1988 B,C++题解代码#include<cstdio>#include<cstring>#include<algori

2016-09-17 11:29:32

poj 2104

讨论划分树,模版题,题解状态14068K,1110MS,G++,1624B题解代码#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define INF 0x3f3f3f3f#define MAXN 100005#define memset0(a) memset(a,0,sizeof(a))i

2016-09-17 09:40:24

hdu 4112

讨论水题,只需要稍微开一下脑洞就能想到,人手和刀子的差别在于,人手一次只能把一块掰成两块,而刀子可以一次把若干块掰成两块,由于最后总是要弄成单位体积的,因而无可避免要将立体变平面,平面变线段,线段变成点这样三个过程,因而每次只需要考虑掰多少次就可以降维,然后对于掰成的每一块进行同样处理,对于刀子,由于一次可以处理若干块,因此每次切一块和每次切更多块是一样的,这个好处首先体现在降维上,只要每次都尽量沿

2016-09-17 07:27:15

hdu 4104

讨论递推,很巧妙,如果前i个价格,可以凑出1到S元,那么对于第i+1个价格A,只要他的价格在1到S+1之内(含),就可以将可以凑出的价格扩充到1到S+A元,这实际上就是个不等式的加法,而若A不在这个范围,则S+1就是第一个无法凑出的价格,之所以在S+1也行,是因为若这个物品价值S+1,而前面的物品可凑出S,中间并没有间断,而可凑出的价值也将被扩充到S+S+1 实现上,首先是一步排序,初始值为0,没

2016-09-16 21:56:22

hdu 5875

讨论单调栈,构图,还有预处理,显然朴素的思想不可能过的,需要一点优化,可以发现,如果某数先对一个较小的数取模,然后对一个较大的数取模,则对较大的数取模并不会影响结果,于是可想到令每次取模的操作数严格递减,基于如此思路,可以构造一张图,前面较大的数指向后面第一个比他小的数,没有更小数的就不用向后指了,因而每个数最多只有一条出边,透过这张图加速取模过程,不过这顶多算剪枝,因为复杂度仍然是平方级,但已经足

2016-09-15 08:46:29

hdu 5877

讨论树状数组,离散化,深搜,比较朴素的思想就是深搜时对于每个节点都直接从树上找满足条件的祖先,铁定超时,想到如何提升每次查找满足条件的点数,线段树/树状数组,以之将查询复杂度降低到对数级,故树上存每个点的值即可,但又数据规模巨大,再离散化处理之,得解 实现层面,综合复杂度是线性对数级,绝大多数操作都是这个复杂度,没什么需要特别注意的地方或坑 题目的数据其实是比较水的,深搜层数也很有限,为此额ro

2016-09-13 00:09:12

hdu 5876

讨论图论,广搜,确切说是补图的广搜,对于给定的图G,其补图H中,原来G中存在的边在H中都不存在,原来G中没有的边在H中都存在,把G和H拼在一起就是一个完全图,算法很简单,对于一个点,找出与其不直连的点,向这些点广搜,重复这个过程即可 实现层面上需要一点技巧,也只是一点,当已经处理过所有N个点之后就可以弹出了,这样虽然复杂度没有改进(每个点都要扫一遍与其直连的边),但是对于边数较少的图可以非常快的完

2016-09-11 11:20:04

hdu 5873

讨论水题,只需要判断总分够不够以及是否有明显得分过多的队就可以了 但是比赛的时候一着急就没读完输入到底是怎么结束的,然后就疯狂的WA 所有队总分是N(N-1),因为完全图是N(N-1)/2条边,而每次比赛,都会产生2分,无论落在谁手里,而每个队只能和N-1个对手打,最多赢N-1场,得到2N-2分,超过这个数的都是不可能的 后来看了别人题解才发现这事题解状态124MS,1780K,653B,C+

2016-09-10 21:07:37

poj 2112

讨论图论,最大流,isap+gap优化,floyd算法,二分思想,三者结合的好题,读图后以floyd求出多源最短路,这样一次立方级预处理,往后读取牛到挤奶器的最短距离都可以常数级查询,后面会发现这绝对是值得的,然后二分走最远的牛走的距离,以最大流判断可行性,具体说,每次二分先以平方级构造残量网络,只有距离小于二分答案的才有残量,之后以isap检查之并更新二分上下界 在实现层面上,需要注意不少细节,

2016-09-08 16:08:27

hdu 5437

题目概述你邀请了K个朋友参加派对,每个朋友都有名字name,来的时候都带了价值v的礼物,但是你屋子太小没法让他们一次都进来,于是你让他们在门口排队,期间你会开M次门,每次开门发生在第T个朋友到来之后,你会让至多P个朋友进来,在门口排队的朋友按照带的礼物价值降序排列,价值相同的先到的排前面,当最后一个朋友到门口时时,你会敞开大门让所有朋友按排队顺序进来,这里有Q次询问,每次询问第q个进来的朋友的姓名时

2016-09-02 21:32:12

hdu 5443

题目概述给定由N个数构成的数列,进行Q次查询,回答区间[l,r]中最大的数时限1000ms/1500ms输入第一行整数times,其后times组数据,每组数据第一行整数N,下一行N个整数,下一行整数Q,其后Q行,每行两个整数l,r限制1<=times<=10;0<=N<=1000;0<=Q<=1000;输出每行一个数,为查询的回答样例输入 3 1 100 1 1 1

2016-09-02 19:43:05

poj 2393

题目概述一个工厂,每周可产任意多的货,每个货在该周生产单价为c,货可以在仓库存放,每个货每周贮存费S,工厂接了连续N周的订单,每周要供货y,求最低总成本 仓库无穷大,货可以永久存放时限1000ms/3000ms输入第一行两个整数N,S,其后N行,每行两个整数c,y,输入只有一组限制1<=N<=10000;1<=S<=100;1<=c<=5000;0<=y<=10000输出一个数,为所求最低成本,需

2016-08-31 21:36:35

poj 1456

题目概述有N个商品,在其保质期dl天内卖掉可得利润v,否则没有利润,卖掉每个商品需要1天,求最大利润时限2000ms/6000ms输入每组数据第一个整数N,其后N对整数v,dl,输入中空白符会任意出现,输入到EOF为止限制1<=N,dl,v<=10000输出每行一个数,为所求最大利润样例输入 4 50 2 10 1 20 2 30 1 7 20 1 2

2016-08-31 18:55:31

poj 1089

题目概述给定N个闭区间,将有重叠部分的区间合并,求最后得到的(那些)区间时限1000ms/3000ms输入第一行整数N,其后N行,每行两个整数l,r,描述一个区间,输入只有一组限制1<=N<=50000;1<=l<=r<=1000000输出每行两个数,为一个区间的左右边界,按左边界升序输出每个区间样例输入 5 5 6 1 4 10 10 6 9 8 10样例输出

2016-08-31 15:50:33

poj 1328 && uva 1193 && la 2519

题目概述在直角坐标系中,x轴为海岸线,其上方为海,海上有N个小岛位于x,y,现要在海岸线建雷达站,所有雷达覆盖范围都是R,问所有岛可否被雷达覆盖,若可,求最少雷达数 海岛不会在陆地上时限1000ms/3000ms输入第一行两个整数N,R,其后N行,每行两个整数x,y,输入到N=R=0为止限制1<=N<=1000输出每行一个字符串 Case A: B 其中A为数据序数,从1开始,若有岛无法被雷达

2016-08-31 15:28:44

poj 1700

题目概述N个人在河边,有一条船,每次可载2人,每个人单独划船渡河时间为num,船每次渡河用时为船上划船用时较长者的用时,问最快多久可让所有人过河时限1000ms/3000ms输入第一行整数times,其后times组数据,每组数据第一行整数N,下一行N个整数num限制N<=1000输出每行一个数,为所求渡河总用时样例输入 5 4 1 2 5 10 5 1 1000 100

2016-08-31 13:42:28

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!