2 Hanks_o

尚未进行身份认证

一名。

等级
博文 228
排名 2w+

bzoj4240: 有趣的家庭菜园(树状数组)

题目传送门。解法:原数组下标为1~n。打乱后交换次数就为逆序对个数。因为交换一次就会产生一个逆序对。。要求逆序对个数尽量少。求的是一个山峰?就是中间高两边递减的东西。那么按高度排序。看下插在左边还是右边产生的逆序对较少。贪心嘛代码实现:#include<cstdio>#include<cstring>#includ...

2018-04-22 19:34:05

bzoj4465: [Jsoi2013]游戏中的学问(Dp)

题目传送门。解法:f[i][j]表示i个人分成j个圈的方案。那么每进来一个人。他可以不自成圈。他插进别人的圈。他也可以自成圈。从前面的人中选出两个人跟他成圈即可。代码实现:#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#i...

2018-04-22 19:28:41

bzoj4260: Codechef REBXOR(01Trie)

题目传送门。解法:01Trie。听名字大概就知道怎么回事了。自己yy了下也不知道对不对。。问题大概就是:很多个数,求他们异或某一个数的最大值。我的建法是这样的:每个数转化成二进制的01序列。从最高位开始建01trie。跟普通trie差不多。只是一个点只有两个儿子的区别。这里的最高位不是指数本身的最高位。而是最大数的最高位。那么此题中范围为int。我把...

2018-04-22 19:25:56

bzoj1222: [HNOI2001]产品加工(Dp)

题目传送门。解法:f[i]表示A机器加工i时间B机器用最少的时间。转移很好写代码实现:#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>...

2018-04-22 19:15:15

bzoj3124: [Sdoi2013]直径

题目传送门。解法:两个傻逼结论:首先肯定在同一条直径上。因为每条直径都要经过这一段。肯定是连续的一段。因为如果你有两段的话。那么敢问这两段之间的路径你是怎么走过去的(树上两点路径唯一!)这样的话就很好做了。随便找条直径。在这条直径上确定一条路径。使得这条路径上:任意一点都不可能从别的分支扩展出直径。懒得画图直接文字描述。假设求出了一条直径是1-&gt...

2018-04-22 19:13:15

bzoj4444: [Scoi2015]国旗计划

题目传送门好题解法:因为区间互不包含。那么左端点在区间内最右边的的区间一定是当前区间能扩展到最远的区间。这句话有点绕。举个例子。假设当前区间为1~5。那么我们往右扩展。找到左端点最右且小于等于5的区间。这个区间一定是最优解。因为区间互不包含啊。如果这个区间不是最优解的话那么就被别的包含了。。因为题目是环。需要转化成链。所以把环复制一份放在后面就变成了...

2018-04-22 16:45:23

bzoj3173: [Tjoi2013]最长上升子序列(树状数组)

题目传送门。解法:因为他是从小到大插。那么新插入一个值对于前面插入的点的影响是没有的。。所以树状数组直接求解答案。关键是插入的序列不知道啊。感觉这题难在这。。想了半天想了个O(n)求序列。结果wa美滋滋。发现错误后重新想。发现O(n)还求不了了。。一般位置都是满足二分性的。。如果很多权值插在同一位置。那么后面插入的位置是要在前面的。所以从后往...

2018-04-22 16:38:12

bzoj3289: Mato的文件管理(莫队+树状数组)

题目传送门。解法:刚才看到Gty的妹子序列。各种不会。。看到这道题。。不强制在线?莫队啊。进来的点树状数组求下逆序对就好了呀。以为复杂度很高会跑很慢谁知5s就过去了。。。代码实现:#include<cstdio>#include<cstring>#include<cstdlib>#include<iostr...

2018-04-22 16:31:57

bzoj2730: [HNOI2012]矿场搭建(tarjan)

题目传送门。解法:第一次写求割点。全程%。#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<queue>usi

2018-04-22 16:29:42

bzoj3531: [Sdoi2014]旅行(树链剖分+线段树)

题目传送门。解法:据说叫动态开点。需要用的点才建线段树。那么最多只有二十万种不同的信息。。跟主席树一样嘛。YY就好了代码实现:#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm...

2018-04-22 16:27:30

bzoj3670: [Noi2014]动物园(kmp)

题目传送门。解法:感觉上是kmp。然后码了个kmp。然后看成了num[i]是前缀后缀不相交的最长长度。然后样例出来个144。发现并没有什么问题。然后发现看错题了。。然后我就在此基础上继续做。s[i]表示前缀等于后缀且可以相交有多少个串。那么求出最长不相交长度。这个的s就是num[i]了。代码实现:#include<cstdio>...

2018-04-18 19:03:31

bzoj5301: [Cqoi2018]异或序列(莫队)

题目传送门。解法:莫队。怎么O(1)转移呢。那么假设i到j的异或和是k。sum[i]表示1到i的异或和。那么sum[i-1]^k=sum[j]。这样统计每个前缀和在区间内出现的次数。那你就可以O(1)转移了代码实现:#include<cstdio>#include<cstring>#include<cstdlib&g...

2018-04-18 16:17:23

bzoj5178: [Jsoi2011]棒棒糖(主席树)

题目传送门。解法:主席树求区间超过区间长度一半次数的数。代码实现:#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include&lt...

2018-04-18 10:18:11

bzoj3439: Kpm的MC密码(主席树+DFS序+字典树)

题目传送门做这题有人跟我说用链表。处理相同的串。网上都说要。。其实不用吧。。记录每个串的结尾是在字典树上哪个点就行啊。然后一个一个插啊。解法:因为是后缀所以到这建字典树。然后kpm串肯定是子树的所有串。那么用主席树维护子树第k小。要求编号连续就套个dfs序就行了。代码实现:#include<cstdio>#include<cstrin...

2018-04-18 10:12:56

bzoj4956: [Wf2017]Secret Chamber at Mount Rushmore(floyd)

题目传送门。解法:有向边判连通性。floyd代码实现:#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<que...

2018-04-18 08:08:58

bzoj5194: [Usaco2018 Feb]Snow Boots(线段树)

题目传送门。解法:线段树维护一个01序列。0表示不可以跳。1表示可以跳。那么每次只需要求最长一段连续的0的长度就行。如果可以跳过去那么其他也可以跳过去。如果跳不过去那就不行。然后那这样每次询问都插岂不是会爆。那离线一下咯。询问排下序。从小到大插。代码实现:#include<cstdio>#include<cstring&g...

2018-04-18 08:07:23

bzoj5293: [Bjoi2018]求和(Lca)

题目传送门。解法:k<=50暴力算每个点到根的每个次方和。然后求出lca差分减一下代码实现:#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#include<c...

2018-04-18 07:52:05

bzoj5168&5029: [HAOI2014]贴海报(线段树)

题目传送门5029一样解法:离散化。覆盖段。代码实现:#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#include<queue>#include<cma...

2018-04-17 19:14:42

bzoj3123: [Sdoi2013]森林(主席树+Lca+启发式合并)

题目传送门。解法:因为是森林。那么lca是必须求的。但是你连接两个点的话指向父亲的方向是会变的。比如说x原来的父亲fa。现在x要连向y了。那么fa的父亲变成了x。那我们合并两个块的时候。将点数小的往大的合并。这样的话总复杂度不会超过nlogn。据说这是启发式合并。维护就用主席树。x维护x到根的信息。合并的时候,由于方向会边。那么要先删除原来的主席树。...

2018-04-17 19:12:03

bzoj4448: [Scoi2015]情报传递(主席树+Lca)

题目传送门严重吐槽这题数据!!花了一下午一直在调一个AC代码。提交莫名WA。因为我建的是单向边。题目说明规定了父亲。那不就是单向边吗。。然后本机栈不够大RE了半天。然后肉老师告诉我一个本地扩栈的方法然后我过了。。然后又WA了。然后%题解。发现建的都是双向边。这题不是规定了父亲吗???然后建了双向才过了。。。数据跟题意不符啊。解法:当前第i天有个询...

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