3 HermioneL

尚未进行身份认证

年轻的好处在于,你还没有太多经验,并天生相信一切皆可能。

等级
TA的排名 7w+

BZOJ 2217: [Poi2011]Lollipop

题目在这里呀!离NOIP就一周了喵 但感觉好累好傻什么都想不出来了 ,越听课越傻吗qwq博客也是一段时间没写了qaq(顺便乱入庆祝IG夺冠!金色的雨诶!!)题意很清楚了吧emmm题解首先对于一段区间的和为sum,那么sum-2一定可行。(好像并没怎么用到现在我们要知道对于一个前缀和sum,如何拼出sum-1。设sis_isi​为从i开始连续T的个数。1、如果s1<=...

2018-11-03 23:05:41

hdu3721 Building Roads

题目在这里呀~题意给你一棵树,改变一条边使得树的直径最小,求最小直径。题解这题在考试的题目有加强版然而暴力都没有写完qaq所以找到了这道题。这题还是挺友善的嗷(Case x忘记写了也是很迷了枚举删除哪一条边,把树分成了两棵树,然后加的那条边一定是两棵树中心的连线。(一棵树的中心到其他节点最深的深度最小)所以只要用树形DP求中心即可。最后整棵树的直径是两棵树的直径以及两棵树中心到其他节点...

2018-10-17 23:50:06

Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)

比赛链接A Make a triangle!题意三根棍子,你可以使任意的一根棍子长度加一,问至少要操作几次才能使这三根棍子能构成一个三角形。题解不需要循环的题[手动幽灵]。就不说了吧…//Leo#include <cstdio>#include <iostream>#include <cstring>#include &l

2018-10-15 15:19:09

牛客网NOIP赛前集训营-提高组(第四场)

这里是比赛wA 动态点分治题目在这里呀~题意输出所有[l,r][l,r][l,r]范围内能表示为k的若干次的数。(注意0^0=1)题解暴力做…k为2,r为2^63次时最多乘63次所以时间可行。emmm我特判掉了k=0和1的情况(不知道可不可以不特判?稍微注意一下细节即可。//Suplex#include <cstdio>#

2018-10-14 12:37:58

Codeforces 778 E. Selling Numbers

题目在这里呀~ 又是好长一段时间没写代码啦(学业繁忙咳咳) 但是这道题真的是道好题啊orz(超好超好的题题意有一个数A,它有些位上是已知的,有些位是”?”,有n个数B1,B2…,Bn,每个数位有一个贡献(c0,c1,c2,…,c9),要填上A中的问号使得这些数加上A后每个数位上的贡献和最大。题解考场上只会暴力了qwq 这道题DP挺好想的?(没看出来 fi,jfi,jf_{i,...

2018-08-28 23:49:11

POJ 2296 Map Labeler

题目在这里呀~题意有n个城市,每个城市需要贴上一个标签,所以的标签都是大小相同且不重叠的正方形,其对应的城市位于标签上边或下边的中点,最大化标签的边长。题解应该很明显有二分性的吧。二分出边长之后是不是可以得出一些限制? 假设二分的边长为d。 那么对于|xi−xj|>=d|xi−xj|>=d |xi-xj|>=d 的两个城市,不会造成什么影响所有也没有限制不需要考虑。...

2018-08-13 22:35:29

BZOJ 1823: [JSOI2010]满汉全席

题目在这里呀!题意真不知道这道题说了这么多有什么用。 就是每种菜有m和h两种,然后只能取其中一个,然后有M条限制,表示取了前一个就不能取后一个了,然后求可不可行?题解看懂题意就是很裸的2-SAT了(虽然我题意说的一点都不清楚//Suplex#include <cstdio>#include <iostream>#include <cst...

2018-08-11 15:41:05

2016计蒜之道复赛A 百度地图的实时路况 CDQ分治

题目在这里呀!题意定义d(u,v,w)为从u号点出发,严格不经过v号点,最终到达w号点的最短路径长度,如果不存在这样的路径,d(u,v,w)的值为-1。 计算每个d(u,v,w)的和。题解一开始没什么想法啊,枚举严格不经过的点然后做floyd复杂度O(n^4),为什么我感觉用dijkstra可以?? 不管不管还是用正经做法,这题可以用CDQ分治解决,l,r表示最后严格不经过的点...

2018-07-29 20:25:03

BZOJ 2287: [POJ Challenge]消失之物

题目在这里呀~题意ftiasch有N个物品, 体积分别是 W1, W2, …, WN。由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N - 1 物品装满容积为 x 的背包,有几种方法呢?” 她把答案记为 Count(i, x) ,想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。题解很经典的dp,类似于容...

2018-07-28 18:52:49

CODE FESTIVAL 2017 Final D-Zabuton

题目在这里呀~题意有n个演员,对于第i个演员,如果当前高度不超过hi,那么就可以“叠”在上面?高度将增加pi,问最大能到达的高度。题解方法挺妙的啦qwq 首先这些人一定有一个先后顺序对吧,那么这个顺序我们怎么给它排呢?考虑对于第a个人和第b个人,如果可以使两个人都能“叠”上去,那么哪一种更加容易达到呢(如果一定可以或者一定不可以的话,谁在前都无所谓) 设H为放a和b之前已经达到...

2018-07-26 22:31:57

Codeforces 888F Connecting Vertices 区间DP

题目在这里呀!题意有n个点,对于点i,j,a[i][j]=1表示i和j可以连通,现要把这n个点连成一棵树,并且边之间的交点不能是除了这n个点以外的点,问连边的方案数。题解好了一开始想七想八想了好多好多,没想到这是一道区间DP?! 之前还想什么正难则反…容斥…那个这个思维历程略略略 好那么这是道区间DP/托腮 知道了状态就很好转移啦(状态的意义代码里注释了)//Supl...

2018-07-24 16:34:36

BZOJ 3653: 谈笑风生

题目在这里呀! 个人认为是一道很好的题目,原来可持久化线段树还能这么用,看题解之前还是没有想到啦要批评!那就写个题解补偿一下?题意给你一棵有根树,n个节点,有q次询问,每次询问,给出两个数x(1<=x<=n),d,求有多少有序元组(y,z)满足 x,y,z互不相同,x,y均为z的祖先,且x,y之间的距离超过d。题解y的位置有两种情况 1、y是x的祖先 ...

2018-07-22 21:29:25

BZOJ 1833: [ZJOI2010]count 数字计数

题目在这里呀!题意不加描述啦qwq题解好像不太会写记忆化搜的,于是听取同学意见写了正常的dp。 然后这就是我第一次写不是记忆化的数位dp啦 用f[i][j][k][flag]表示前i位,前一位为j,是否抵上界的状态为flag,k数字出现的次数。 如果单单是这样子做的话会发现不行,因为你还不知道前一个状态有多少种这样的数字,所以还需要一个g[i][j][flag]表示前i位...

2018-07-21 16:03:41

BZOJ 1026: [SCOI2009]windy数

题目在这里呀! 看到这道题题目的时候以为这是一道很简单的题很简单的很简单很简很… 嗯结果做了好长时间啊qwq 可能是我对记忆化搜的数位dp情有独钟??题意emmm题目很短了不需要概括了吧qaq?题解一开始写了一个非常简单的数位dp,发现一开始的0没有处理好,然后就脑子一抽改啊改越改越错,最后终于从头开始,那么可以说就是枚举这个数字有几位,然后做数位dp即可,剩下就很简单了...

2018-07-21 14:38:43

BZOJ 4953: [Wf2017]Posterize

题目在这里呀~题意有256个位置,有n个位置上有人,你可以在至多k个位置上插旗,每个人都会走到离自己最近的旗子,求所有人走的距离的平方和的最小值。题解嗯听说这题难在题意??这是WF2017最简单的一道题qwq 一看就是dp吧。fi,jfi,jf_{i,j}表示前i个位置插了j面旗,且第i位置上必须插旗的最小代价。那么转移fi,j=min(fp,j−1+wp,i)fi,j=min(...

2018-07-21 14:22:49

BZOJ 1260 [CQOI2007]涂色paint

题目在这里呀!题意给你一个字符串,每次涂色只能将一段区间的颜色改为一种,问将一个空白的版涂成目标串最少需要几次。题解很明显是区间DP啊,fi,jfi,jf_{i,j}表示i到j这段区间涂成目标串最小代价。 那么有两种情况。 1、st[i]==st[j] 那么转移 fi,j=min(fi+1,j−1+1)fi,j=min(fi+1,j−1+1)f_{i,j}=min(f_{i+...

2018-07-21 11:57:11

BZOJ 2257: [Jsoi2009]瓶子和燃料

题目在这里呀!题意有n个瓶子,每个瓶子的容量为Vi,从中选出k个瓶子做如下操作 1、把一个瓶子倒满 2、把一个瓶子倒空 3、将燃料从a倒到b,直至a空或b满 4、将某个瓶子交给你 希望交给你的瓶子不空但尽可能少,求最优选择,使得获得的燃料尽可能多。题解对空瓶做操作1,对满瓶做操作2,假设第i个瓶子倒入ai次。 则最后的到燃料∑ki=1aiVi∑i=1kaiVi\su...

2018-07-12 22:48:21

BZOJ 2299: [HAOI2011]向量 数论

题目在这里呀! 那么开始切水题了?(划掉)题意题目很短了吧?题解表面上有八个向量,但它们合并一下就只剩下没几种情况了qwq 四种情况 1、x0+2a or y0+2b 2、x0+2b or y0+2a 3、x0+a,y0+b 4、x0+b,y0+a 然后如果3、4两种取两次又会回到1、2状态,所以下面两种暴力枚举取或不取。上面是可以用两个同余方程做滴,分别是x一个y一...

2018-07-10 22:37:08

NOI 2002 荒岛野人

题目在这里呀~ 现学现用嘻嘻~~题意有n个人和大小为m的环,每个人有个初始位置ci,每年顺时针方向走pi步,生存时间为li年。 求m的最小值,使得两两人在有生之年不会相遇。题解为什么要他们不能相遇呢?这么残忍的吗?难道连一点缘分都没有吗? 题目怎么这么决绝呢哼(纯属搞笑qwq) 考虑两个人相遇的时间t,那么 (ai−aj)∗t−m∗y=pj−pi(ai−aj)∗t−m...

2018-07-10 22:26:26

BZOJ 2006 [NOI2010]超级钢琴

题目在这里呀~题意好题好题 求k个区间使得和最大,要求区间的长度在L到R之间。题解非常有意思的一道题 考虑前缀和,那么以l为左端点的区间的和都是是s[i]-s[l-1]。 那么用RMQ来预处理出区间s[]的最大值。 可以想到取前k大的话,那应该是要用堆的。 堆中记录一个五元组(i,l,r,val,pos)表示左端点为i,右端点在[l,r]之间,最大价值为val,最大价值所...

2018-07-07 22:33:25

查看更多

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