- 博客(117)
- 收藏
- 关注
RSS订阅原创 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
258
原创 hdu3721 Building Roads
题目在这里呀~题意给你一棵树，改变一条边使得树的直径最小，求最小直径。题解这题在考试的题目有加强版然而暴力都没有写完qaq所以找到了这道题。这题还是挺友善的嗷（Case x忘记写了也是很迷了枚举删除哪一条边，把树分成了两棵树，然后加的那条边一定是两棵树中心的连线。（一棵树的中心到其他节点最深的深度最小）所以只要用树形DP求中心即可。最后整棵树的直径是两棵树的直径以及两棵树中心到其他节点...
2018-10-17 23:50:06
231
原创 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
256
原创 牛客网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
397
原创 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
331
原创 POJ 2296 Map Labeler
题目在这里呀~题意有n个城市，每个城市需要贴上一个标签，所以的标签都是大小相同且不重叠的正方形，其对应的城市位于标签上边或下边的中点，最大化标签的边长。题解应该很明显有二分性的吧。二分出边长之后是不是可以得出一些限制？ 假设二分的边长为d。 那么对于|xi−xj|>=d|xi−xj|>=d |xi-xj|>=d 的两个城市，不会造成什么影响所有也没有限制不需要考虑。...
2018-08-13 22:35:29
151
原创 BZOJ 1823: [JSOI2010]满汉全席
题目在这里呀！题意真不知道这道题说了这么多有什么用。 就是每种菜有m和h两种，然后只能取其中一个，然后有M条限制，表示取了前一个就不能取后一个了，然后求可不可行？题解看懂题意就是很裸的2-SAT了（虽然我题意说的一点都不清楚//Suplex#include <cstdio>#include <iostream>#include <cst...
2018-08-11 15:41:05
217
原创 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
271
原创 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
220
原创 CODE FESTIVAL 2017 Final D-Zabuton
题目在这里呀~题意有n个演员，对于第i个演员，如果当前高度不超过hi，那么就可以“叠”在上面？高度将增加pi，问最大能到达的高度。题解方法挺妙的啦qwq 首先这些人一定有一个先后顺序对吧，那么这个顺序我们怎么给它排呢？考虑对于第a个人和第b个人，如果可以使两个人都能“叠”上去，那么哪一种更加容易达到呢（如果一定可以或者一定不可以的话，谁在前都无所谓） 设H为放a和b之前已经达到...
2018-07-26 22:31:57
306
原创 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
336
原创 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
231
原创 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
172
原创 BZOJ 1026: [SCOI2009]windy数
题目在这里呀！ 看到这道题题目的时候以为这是一道很简单的题很简单的很简单很简很… 嗯结果做了好长时间啊qwq 可能是我对记忆化搜的数位dp情有独钟？？题意emmm题目很短了不需要概括了吧qaq？题解一开始写了一个非常简单的数位dp，发现一开始的0没有处理好，然后就脑子一抽改啊改越改越错，最后终于从头开始，那么可以说就是枚举这个数字有几位，然后做数位dp即可，剩下就很简单了...
2018-07-21 14:38:43
139
原创 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
259
原创 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
208
原创 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
224
原创 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
208
原创 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
219
原创 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
171
原创 POJ 1185 炮兵阵地
题目在这里呀！ 个人觉得是一道挺好的状压DP，别人说转移一眼？题意炮兵只能布置在平地上，而且会攻击上下左右单位长度为2的点，所以这些点上就不能布置炮兵了，要求最多能放置多少炮兵？题解当前行的状态是从前两行的状态得来的。 前两行的一列上只有三种可能：01，10，00（0表示没有炮兵，1表示有炮兵） 三进制有点麻烦？那么就压成四进制，也就是2m的二进制位，可是细节不太会处理，...
2018-07-07 22:11:26
140
原创 Atcoder Grand Contest 024E Sequence Growing Hard
题目在这里呀！ 啊啊啊准备了一个月期末考的我终于飘回来啦~~ 真可谓在学OI的时候忘不了文化课，然后在学文化课的时候又想念编程啦qwq那那那开始我的七月第一篇题解？ （我七月想写很多很多题解的w）题意考虑 N +1 个数组 {A0,A1,…,AN}。 其中 Ai 的长度是 i，Ai 内的所有数字都在 1 到 K 之间。 Ai−1 是 Ai 的子序列，即 Ai 删一个数字可以...
2018-07-04 18:43:26
236
原创 luogu P4253 小白逛公园
题目在这里呀~题意1、单点修改 2、求区间[l,r]内的最大子序列题解做法还算好想吧（如果做过类似题目 比如poj 的 hotel ？好像没什么差别的。 就是一棵线段树每个节点要记四个值：左端点连续的和最大值，右端点连续的和的最大值，区间和，区间最大子序列和。 注意点： 1、在求和时因为这个询问区间是拼起来的，所以在query时返回最好是结构体，以便合并。（不用的话不...
2018-05-30 23:22:30
211
原创 BZOJ 1588: [HNOI2002]营业额统计
题目在这里呀！splay模板题qwq（用set也可以做题意有n天，每天有个营业额ai，波动定义为之前几天的营业额于这一天的差的绝对值的最小值（绕了qaq）。求波动指数。题解好像一段时间没管splay了呢，刚好老师讲到，那就提几题喽~ 这题明显就是求前驱后继，然后取个绝对值较小的，累加即可 很基础很基础的吧？（只是为了熟悉一下代码w）//Suplex#include &...
2018-05-30 22:51:55
236
原创 BZOJ 5343: [CTSC2018] 混合果汁
题目在这里呀~题意（迟到的题解吧，CTSC略略略，但这道题确实挺基础的qwq） 有n种果汁，m个小朋友，第i种果汁有个美味度di，每升的价格pi，和最多有li升。第i个小朋友付的价格不超过gi，但要获得至少Li升的果汁，问美味度最小值的最大值是多少？题解一眼可以看出是二分答案的吧，然后考虑贪心，暴力的话是把美味度>=d[i]的p数组排序，然后从小的开始取，这样子是正确的，但...
2018-05-29 23:02:05
438
原创 luogu P3605 [USACO17JAN]Promotion Counting晋升者计数 BZOJ 4756
题目链接1 题目链接2题意给出每个点的父亲节点，求每个点的孩子节点有多少个权值大于它。题解线段树合并模板题啦，从下往上合并权值线段树即可（略略略//Suplex#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#inc...
2018-05-29 11:19:08
226
原创 BZOJ 1879 [Sdoi2009]Bill的挑战
题目在这里呀！题意：问有多少个长度为N的字符串T，有K个Si能和T匹配。 Si 与 T 匹配的条件是： Si,j=’?’ || Si,j=Tj题解：也是道好题吧，建出AC自动机，然后跑DP？ a[i][j]表示字符串第i位填j能匹配字符串的状态 f[i][j]表示匹配到第i位，匹配字符串的状态为j的方案数。 自然地，f[i+1][sta &amp; a[i][j]...
2018-05-20 13:37:23
181
原创 BZOJ 3747 [POI2015]Kinoman
题目在这里呀！ 题意：m部电影，n天放映，第i天放映第f[i]部电影，第i部电影的好看值为w[i]。 一个区间[l,r]，在第l天到第r天内，如果第i部电影只被看过一遍，那么就有w[i]的贡献，求最大贡献。题解：感觉是一道好题哦~（5月份没更过博啊终于打算写几篇了qwq）从暴力入手吧，枚举左端点l，向右扫，每次cnt[f[i]]++，如果此时cnt[f[i]]=1，则加上贡...
2018-05-20 12:54:49
202
原创 BZOJ 2956 模积和 （分块）
题目在这里呀！题意BZOJ 1257的加强版，多了一个？那就把它展开来啦。 ∑i=1n∑j=1m(nmodi)∗(mmodj)(i!=j) \sum_{i=1}^n \sum_{j=1}^m (n mod i)*(m mod j) (i!=j) =∑i=1n∑j=1m(nmodi)∗(mmodj)−∑i=1n(n−⌊ni⌋∗i)∗(m−⌊mi⌋∗i)=\sum_{i=1}^n \sum_{j=1
2018-04-24 23:17:00
173
原创 BZOJ 1257 [CQOI2007]余数之和
题目在这里呀！题解一道会杜教筛或者分块的人都应该会写的题啦。 首先考虑简单简单版： ∑i=1n⌊ni⌋ \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor 这个问题我们直接对⌊ni⌋ \lfloor \frac{n}{i} \rfloor 分块即可。那么很好转换到这个问题， ∑i=1nnmodi=∑i=1n(n−⌊ni⌋∗i) \sum_{i=1}^n n
2018-04-24 22:54:07
181
原创 2018.3.20有感？
明天就是省选了qaq想了想，我才初三没什么压力？但或许到了高一我的水平还是跟现在差不多，我能不努力嘛。。 但轻松的心态也挺好（cha）的。 省选前一天emm提前回了宾馆，我们学校好像都回来了hhhh 讲课各种听不懂qwq 回来也累得不想敲题目看了会儿《大鱼海棠》，好感动啊w身体不是很舒服，但我肯定能挺住的。 那就早点洗洗睡了吧…人真的好累诶emm这个小日记（konghua）一点文化
2018-03-20 21:37:26
158
原创 BZOJ 3110 [ZJOI2013]K大数查询
题目在这里呀~这题被卡常了qaq（ZJOI临近了我也不想在这种题上花太多时间…） 可以想到要用二分答案（只是以前做过一道类似的题啦 然后常规的，求出左子树的贡献，如果大于c，就往左子树找，否则往右子树找。 然后就是树套树了？ 外层权值内层记区间和。 我没看懂他们说的标记永久化什么的，可听说是没负数的而且不会爆int？？ 然后就调了一个晚上，后来看评论发现…天呐要开longlong qwq
2018-03-19 23:38:30
185
原创 BZOJ 4555 [Tjoi2016&Heoi2016]求和 NTT
题目在这里呀题解题目给你的那个递推式好废啊（没有一点用还是要百度通项）。 知道第二类斯特林数时只要带入原式展开可以发现卷积式，对它做NTT即可。 详细见学姐的博客 这篇博客讲的很清晰很具体，不会展开的话就看这篇吧qaq（不是我懒，是因为我也是看了这篇才会的啦ww）//Suplex#include <cstdio>#include <iostream>#include <cstring>
2018-03-14 22:36:38
213
原创 BZOJ 2563 阿狸和桃子的游戏
题目在这里呀题意题面里的那个公式就是题意了qaq题解算是一道套路题吧w 把边上的权值转移到点上去，一个点上加边一半的权值。 为什么可以这样呢？ 1、如果一条边连接的两个点是同一个人，那么他能得到这条边的权值，由于分到两个点上了，对答案没有影响。 2、如果一条边连接的两个点不是同一个人取的，那么互相抵消，这条边没有贡献，也正确。最后排序贪心一下就行啦ww//Suplex#include <c
2018-03-14 21:46:37
174
原创 hdu 3308 LCIS
题目在这里呀这题真的是把我坑到了（其实很简单啊可我又傻了题意有两个操作，一个是将a位置上的数改成b，一个是计算a到b的区间内最长子序列的长度。题解很常规啊，线段树上做区间合并，线段树的每个点需要记下三个值，最左边的连续子序列长度t[rt].l，最右边的连续子序列长度t[rt].r，和整个区间的最长连续子序列长度t[rt].sum。pushup的地方注意几点。1、将两个小区间合并成大区间，将左区间的l
2018-03-10 23:30:41
210
原创 BZOJ 3669: [Noi2014]魔法森林
题目在这里呀这题是补上的题解，以前就A了，现在重新看了一遍qaq 题意：求1到n的路径上A的最大值+B的最大值最小？ 好像是这样的吧有点忘记了。题解LCT+并查集，很容易想到要降维，所以就把a从小到大插入，同时用并查集来维护b形成的生成树。 具体来说是，如果u到v已经联通，则找出u到v的路径上最大的b，如果大于bi，则删掉那条边替换为u-v。如果1和n已经属于一个块了，就可以去更新一下答案。差
2018-03-10 21:17:38
185
原创 BZOJ 3931: [CQOI2015]网络吞吐量
题目在这里呀emm昨天深夜急急地调完这题就睡了，今天补一下题解qaq 这题就是道模板题啦，题意怎么说的就怎么建边，注意需要裂点。 剩下就是一遍网络流就没啦ww 这题适合复习一下模板qwq//Suplex#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#include <cmath>#
2018-03-10 20:20:15
201
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人