- 博客(153)
- 收藏
- 关注
RSS订阅原创 洛谷$P3749$ [六省联考2017] 寿司餐厅 网络流
正解:网络流解题报告:传送门$QwQ$这道题好烦昂,,,就给了好多变量,,,但仔细读一遍题还是能$get$的所以我就不再提取一遍题目大意辣$QwQ$?显然考虑建两排点,一排收益一排支出然后最小流呗?考虑连边?寿司和编号之间连$inf$嘛,编号和$T$连$m\cdot x^{2}$嘛,然后关于这个$c\cdot x$显然可以归结到每个寿司上不用通过编号背锅嘛$QwQ$....
2019-08-01 22:38:00
117
原创 洛谷$P5038\ [SCOI2012]$奇怪的游戏 二分+网络流
正解:二分+网络流解题报告:传送门$QwQ$这种什么,"同时增加",长得就挺网络流的$QwQ$?然后看到问至少加多少次,于是考虑加个二分呗?于是就大体确定了做题方向,用的网络流+二分然后就考虑怎么建图呗$QwQ$首先考虑二分出每个点的值,然后就可以根据这个值求出每个点要增加的多少以及总的修改次数然后相邻显然考虑黑白染色黑连$S$白连$T$彼此之前连$inf$,跑个...
2019-07-30 20:42:00
103
原创 洛谷$P3756\ [CQOI2017]$老$C$的方块 网络流
正解:网络流解题报告:传送门$QwQ$看到不能出现给定的讨厌的图形,简单来说就,特殊边两侧的方格不能同时再连方格.所以如果出现,就相当于是四种方案?就分别炸四个格子.然后冷静分析一波之后发现对于特殊边两侧的格子炸那个是没有影响的?于是这两个格子就只用选较小的一个炸就好,于是现在就变成了三种方案,可以考虑和之前做的那道,酒店之王,差不多的建图,$over$#...
2019-07-30 20:29:00
103
原创 $CF809C\ Find\ a\ car$ 数位$dp$
正解:数位$dp$解题报告:传送门!然后因为没有翻译所以先放个翻译$QAQ$有一个无穷大的矩阵,第$i$行第$j$列的数是$(i-1)\ xor\ (j-1)+1$,有$q$次询问,每次询问一个矩形内$(x_{1},y_{1})(x_{2},y_{2})$小于等于$k$的数的和好像是考试题,,,?学长出的$QwQ$?然后考虑怎么做趴$QwQ$,发现这个式子其实要拆...
2019-07-29 20:13:00
73
原创 洛谷$P4126\ [AHOI2009]$最小割 图论
正解:网络流+$tarjan$解题报告:传送门$QwQ$$umm$最小割的判定问题$QwQ$,因为并不会做是看的题解才会的,所以也没什么推导过程直接放结论趴$QwQ$首先跑个最大流,然后有.1)可行流($x,y$)的充要条件:满流&残余网络中不存在$x$到$y$的路径2)必然流($x,y$)的充要条件:满流&残余网络中$ST$分别能到达$xy$...
2019-07-28 20:00:00
86
原创 洛谷$P2805\ [NOI2009]$植物大战僵尸 网络流
正解:网络流解题报告:传送门$QwQ$题面好长昂,,,我大概概括下$QwQ$?有个$n\cdot m$的网格,每个格子有一株植物,击溃一株植物$(x,y)$需要付出$S_{(x,y)}$的代价($S$可正可负.另外每株植物有$A_{(x,y)}$个可攻击位置,只要这株植物不死这些位置都是无法到达的$QwQ$.攻击规则是必须从右向左走,如果要攻击$(x,y)$位置的植物,需要把...
2019-07-28 10:07:00
84
原创 洛谷$P3308\ [SDOI2014]LIS$ 网络流
正解:网络流解题报告:传送门$QwQ$恩先不考虑关于那个附加属性的限制,考虑这题怎么做?首先这题从名字开始就让人忍不住联想起网络流24题里的那个最长不下降子序列?于是同样考虑预处理一个$f$呗然后再一看,长得就很最小割嘛,于是拆点,能构成最长不下降子序列的之间就连权值为$inf$的边,$f_{i}=1$的点和$S$.$f_{i}=mxf$的点和$T$连权值为$inf$...
2019-07-27 22:42:00
65
原创 洛谷$P4001\ [ICPC-Beijing 2006]$狼抓兔子 网络流+对偶图
正解:网络流+对偶图解题报告:传送门!$umm$日常看不懂题系列了$kk$.其实就是说,给定一个$n\cdot n$的网格图,求最小割$QwQ$然后网格图的话显然是个平面图,又看到数据范围$n\leq 1000$,显然就考虑平面图转对偶图呗然后好像就没有什么细节了,,,?对了,$bzoj$上的话要特判1,洛谷上没有这个数据就不用辣$QwQ$$QwQ$(在$...
2019-07-27 19:30:00
88
原创 洛谷$P2046\ [NOI2010]$海拔 网络流+对偶图
正解:网络流+对偶图解题报告:传送门$QwQ$$umm$之前省选前集训的时候叶佬考过?然而这和我依然不会做有什么关系呢$kk$昂这题首先要两个结论?第一个是说每个位置的海拔一定是0/1,还一个是说0/1一定都是连通块$QwQ$瞎证下?$QwQ$.结论一:若存在海拔大于1的点,下坡不变,上坡代价增加,显然改为1更优 若存在海拔在0到1之间的点,同样理由...
2019-07-27 16:30:00
104
原创 洛谷$P2570\ [ZJOI2010]$贪吃的老鼠 网络流+二分
正解:网络流+二分解题报告:传送门$QwQ$和上一题有点儿像,,,?$QwQ$但是比上一题要有趣很多$QwQ$首先把大致思路捋下?依然是.二分出每个奶酪的开始和结束时间,然后check下最大流的流量和$\sum p$的大小.做完了.$over$然后详细考虑过程,发现难点就在构图了呗,就,怎么构图能满足题目给定的条件先列出题目两个和普通网络流不同的点趴$QwQ$:...
2019-07-26 20:33:00
93
原创 洛谷$P3324\ [SDOI2015]$星际战争 网络流+二分
正解:网络流+二分解题报告:传送门$QwQ$其实我第一反应是费用流来着,,,但是仔细想了下发现我不会实现各个武器之间独立同时?而且攻击是连续的答案可能是小数嘛$QwQ$.所以显然不是递推就二分呗$QwQ$.然后依然是因为小数的约束,所以最后选择的二分$QwQ$$umm$然后就傻逼题了呗?$check$的话直接武器建一排点机器人建一排点,$S$和武器$i$连$B_{...
2019-07-26 16:51:00
75
原创 洛谷$P3227\ [HNOI2013]$切糕 网络流
正解:网络流解题报告:传送门!日常看不懂题系列,,,$QAQ$所以先放下题目大意趴$QwQ$,就说有个$p\cdot q$的矩阵,每个位置可以填一个$[1,R]$范围内的整数$a_{i,j}$,要求相邻格子之间差不超过$D$.求$\sum v_{i,j,a_{i,j}}$的$min$昂,先考虑如果没有$D$这个限制网络流怎么做鸭$QwQ$.就一个,比较显然的最小割,对...
2019-07-25 22:34:00
82
原创 洛谷$P$2472 蜥蜴 $[SCOI2007]$ 网络流
正解:网络流解题报告:传送门!$umm$一看就是个最大流呗,,,就直接考虑怎么建图趴$QwQ$首先看到这个高度减小其实就相当于对这个点的次数有约束,就显然拆点呗,流量为高度然后$S$连向左侧所有有蜥蜴的点,流量为1.右侧所有边界点连向$T$,流量为$inf$.然后就做完了?$QwQ$.#include<bits/stdc++.h>usi...
2019-07-25 14:49:00
79
原创 洛谷$P$1402 酒店之王 网络流
正解:网络流解题报告:传送门!一看就很网络流昂,,,于是现在的问题就变成怎么建图了$QwQ$首先如果只有一个要求,那就直接按要求建图然后跑个最大流就好.现在变成,有两个要求,必须同时满足,考虑怎么解决?考虑拆点,把人拆成两个点,分别连食物和酒店,然后跑个最大流,做完了$QwQ$$over$对了这题有三倍经验,,,讨论区有分享$QwQ$#incl...
2019-07-24 11:47:00
62
原创 网络流24题题解
其实只有23题有一题我不会嘤$QAQ$算了先把其它23题写了复健下,,,感$jio$不写题解的话就学了和没学似的嘤,,,然后先分别放个模板趴,,,因为并没学会有上下界的网络流所以只有最基础的最大流和费用流$QwQ$(upd:,,,我今天康了眼发现我似乎$dinic$打错了,,,有时间改下$QwQ$#include<bits/stdc++.h>usi...
2019-07-22 22:30:00
674
原创 $vjudge-$基本算法专题题解
考完期末又双叒回来刷普及题辣$kk$然后放个链接趴还是$QwQ$[X]$A$因为是嘤文($bushi$所以放个题意趴$QwQ$就汉诺塔问题,只是说有四个塔$A,B,C,D$,要求输出有1-12个盘子时的最少步数$QwQ$$umm$解法题目都给了昂$QwQ$,大致意思就说,可以先把$n-k$个盘子用四个塔的算法移到$B$,然后用三个塔的算法把剩下$k$个移到$D$,...
2019-07-13 17:21:00
186
原创 斜率优化入门题题单$QwQ$
其实就是这一篇的那个例题帕的大部分题目的题解就写这儿辣,,,因为都是些基础题不想专门给写题解,,,但是又掌握得差不得不写,,,麻油办法就写一块儿好辣$QwQ$当然辣比较难的我就没放进来辣$QwQ$[X]玩具装箱解析在上一篇就港辣_(:з」∠)_懒得复制辣,就只放个代码了昂$QwQ$#include<bits/stdc++.h>...
2019-06-13 11:03:00
86
原创 斜率优化学习笔记
斜率优化是个好东西,,,然而$sd\ gql$一直想学却一直没$get$嘤嘤嘤所以在拖了$inf$天之后总算还是来开个斜率优化的坑,,,然后因为斜率优化只是个方法,所以可能就不像别的知识点分好几个方面,我估计我就只港下原理,然后放几道经典题$QwQ$?$over$好然后接下来就要进入正题了嗷$QwQ$原理从一个例题入手港趴.玩具装箱(我感觉这是斜率优化最经典一道例...
2019-06-13 10:54:00
75
原创 洛谷$P$3066 逃跑的$BarnRunning\ Away\ From…$ $[USACO12DEC]$ 主席树
正解:主席树解题报告:传送门!1551做$dp$实在是做不下去了,,,于是来水点儿别的题$QAQ$然后这题,挺纸老虎的我$jio$得,,,看起来很难的样子然后仔细想下之后发现依然是个板子呢,,,$QwQ$首先显然先树剖昂$QwQ$,然后子树内这个条件就变成了在某给定区间$[l,r]$内嘛然后考虑这个所谓,距离$\leq x$怎么处理呢,不难想到先预处理出每个点距离...
2019-06-13 08:27:00
104
原创 洛谷$P$1486 郁闷的出纳员 $[NOI2004]$ $splay$
正解:$splay$解题报告:传送门!依然先考虑要呲呲些什么操作鸭$QwQ$其实就只要一个删除区间,一个查询第$k$大,还一个插入就欧克?删除区间的话直接旋转下根什么的然后直接把子树删了就好$QwQ$查询第$k$大和$insert$是基操不说$QwQ$然后还一个就集体扣除工资?本来一般这种还要考虑加个$ad[]$的$tag$,,,但因为这题太水了$QwQ$所以...
2019-06-10 11:58:00
78
原创 洛谷$P$2286 宠物收养场 $[HNOI2004]$ $splay$
正解:$splay$解题报告:传送门!$splay$板子,,,?先考虑这题要实现些什么东西嘛$QwQ$其实只要实现一个东西?就查询数列中与给定数字相差最小的数,显然用$splay$查询前驱后继,然后就没辣,,,?(哦还一个$insert$,,,$QwQ$记得分类讨论下是人有剩还是宠物有剩就好,$over$#include<bits/stdc++....
2019-06-10 11:37:00
62
原创 $splay$学习总结$QwQ$
省选之前就大概搞了下$splay$,然后因为时间不太够就没写总结了,,,然后太久没用之后现在一回想感觉跟没学过一样了嘤嘤嘤所以写个简陋的总结,,,肥肠简陋,只适合$gql$复习用,不建议学习用然后先推荐两篇博客,,,$orz\ yyb$的博客$QwQ$(我之前就是看这个学的$QwQ$).$orz\ xzy$学长的博客$QwQ$(这篇总结了支持的操作然后还提供了题单,解释也...
2019-06-10 11:14:00
76
原创 $CH$ $0x50$ & $0x51$ 做题记录
[X]$Mr.Young's\ Picture\ Permutations$前面这儿写了挺多道辣,,,懒得写辣$QAQ$(后面所有同上都是同这个$QwQ$[X]$LCIS$做过了,看这儿$upd$:,,,这题有猫饼,不呲呲快读,用快读会$T$一个点,,,然后我下了数据下来发现明明是数据的锅,,,?我感觉它给我的这个数据明明就不够,,,?但反正我改成$sca...
2019-06-08 09:40:00
98
原创 洛谷P3311 [SDOI2014]数数 AC自动机+dp
正解:AC自动机+dp解题报告:传送门!首先看到多串匹配balabala显然想到建个AC自动机?然后可以用一点儿数位dp的思想地想下(,,,其实并不算QAQ幸运数可以分为两类:位数<n的和位数=n的下面分别考虑下对位数<n的,相当于就没有任何约束,直接dp转移下就好然后对位数=n的,另外做一次dp,然后多设一组状态表示当前是否相等(就和数位dp...
2019-04-03 14:58:00
111
原创 POJ2274 Long Long Message 字符串
正解:SA/哈希+二分解题报告:传送门!啊先放下翻译,,,?大意就有两个字符串,求这两个字符串的最长公共子串先港SA的做法趴就把两个子串拼接起来,然后题目就变成了求后缀的最长公共前缀了所以就跑一下SA的模板就欧克了只是注意两个细节,,,一个是因为要求的是两个字符串的最长公共子串,所以要判断一下确保两个子串并不都属于一个串中的另一个是拼起来的时候要在中间...
2019-04-03 10:41:00
72
原创 洛谷$P4363$ 一双木棋$chess$ [九省联考2018] 搜索+$hash$/$dp$
正解:记搜+$hash$/$dp$解题报告:传送门!因为看到$n,m$范围特别小,,,所以直接考虑爆搜$(bushi$先考虑爆搜之后再想优化什么的嘛$QwQ$首先对这种都要最优的,就可以直接把答案设为针对某一方,然后题目就会变成,轮流的,一次最大一次最小这样子(,,,好像表述得不太好,,,不管了$QAQ$所以直接对每一步枚举所有状态,因为这样最优性的问题显然有每个...
2019-03-31 21:27:00
59
原创 洛谷P4562 [JXOI2018]游戏 数论
正解:数论解题报告:传送门!首先考虑怎么样的数可能出现在$t(i)$那个位置上?显然是$[l,r]$中所有无法被表示出来的数(就约数不在$[l,r]$内的数嘛$QwQ$所以可以先把这些数筛出来具体怎么筛的话,最原始的方法就埃氏筛?然后显然可以线性筛,但我$jio$得大概快不到哪儿去而且麻烦一些懒得打了所以直接用的埃氏筛然后现在就筛出来,有$sum$个满足条件的...
2019-03-31 18:53:00
106
原创 洛谷P3158 放棋子 [CQOI2011] dp+数论
正解:dp+数论解题报告:传送门!考虑对每种颜色的棋子单独考虑鸭,那显然有,当某一行或某一列已经被占据的时候,那一行/一列就不能再放别的颜色的棋子了,相当于直接把那一行/一列直接消了显然就能考虑到dp?设f[i][j]:剩余i行j列的方案数转移就枚举这个颜色的棋子放了p行q列,设g[d][p][q]:d个棋子恰好放了p行q列的方案数直接枚举pq,f[i][j]=∑...
2019-03-31 17:25:00
90
原创 洛谷P4570 [BJWC2011]元素 线性基
正解:线性基+贪心解题报告:传送门!这题其实没什么好写题解的,,,显然贪心一下尽量选魔力大的,不用证明趴挺显然的来着所以就直接按魔力排个序,插入线性基里面,能插就加个贡献,over放下代码趴QwQ(我好像,真的,写得越来越敷衍了TT#include<bits/stdc++.h>using namespace std;#define ...
2019-03-30 21:16:00
53
原创 bzoj3733 [Pa2013]Iloczyn 搜索
正解:搜索解题报告:先放下传送门QwQumm其实并不难,,,最近在复健基础姿势点所以都写的是些小水题QAQ首先考虑如果能构造出来一定是因数凑起来鸭,所以先把因数都拆出来,然后就爆搜几个常见的剪枝就不说了,想cue下最近碰到了好几次的一个是这样儿的,就以这题为例,可以对所有因数排序,强制从小到大选这种我就不说了太套路了,有一个小check是可以计算出还要乘几个数嘛,这里设已经算...
2019-03-29 17:05:00
73
原创 洛谷P4151 最大XOR和路径 [WC2011] 线性基+图论
正解:线性基+图论解题报告:传送门首先可以思考一下有意义的路径会是什么样子,,,那就一定是一条链+一些环挺显然的因为一条路径原路返回有没有意义辣?所以一定是走一条链+一些环(当然也可以麻油环,,,差不多差不多QAQ所以可以考虑先把所有环找出来,加入线性基中,现在要考虑的就只有找一条链这个事儿辣然后这儿可以发现一个性质,就是其实只要拿1号节点到n号节点的任意一条链出...
2019-03-27 20:29:00
84
原创 P3292 [SCOI2016]幸运数字 线性基
正解:线性基+倍增解题报告:先放下传送门QAQ然后这题,其实没什么太大的技术含量,,,?就几个知识点套在一起,除了代码长以外没任何意义,主要因为想复习下线性基的题目所以还是写下,,,随便写下思路趴,首先多个数异或显然线性基,然后因为是在树上所以可以考虑倍增预处理线性基,插入合并查询都基操我不说了QAQ然后因为我树剖不熟练所以我用的树剖,,,当然倍增一样的反正都差不多?...
2019-03-27 17:06:00
71
原创 洛谷P4495 奇怪的背包 [HAOI2018] 数论
正解:数论+dp解题报告:传送门!首先看到这题,跳无数次,自然而然可以想到之前考过好几次了的一个结论——如果只考虑无限放置i,它可以且仅可以跳到gcd(p,v[i])举一反三一下,如果有多个i,表示成a[i]好了,那就一定是能跳到gcd(p,v[a[1]],v[a[2]],..,v[a[n]]),因为这个太长了后面单一个gcd就指的它挺显然的这儿不证明了QAQ然后...
2019-03-27 16:50:00
98
原创 洛谷P2329 栅栏 [SCOI2005] 搜索
正解:搜索解题报告:先放下传送门!首先说下爆搜趴,就直接枚每个需求是否被满足以及如果满足切哪个板子,随便加个最优性剪枝,似乎是有80pts然后思考优化首先显然尽量满足需求比较小的,显然如果能满足边长大的替换成边长小的也欧克,所以先对需求都排个序,就不用考虑是否满足了一定都满足这样就可以发现变成了一个可二分的问题?然后爆搜check一下就好然后check中的剪枝...
2019-03-27 16:17:00
104
原创 洛谷P1955 程序自动分析 [NOI2015] 并查集
正解:并查集+离散化解题报告:传送门!其实题目还挺水的,,,但我太傻逼了直接想挂了,,,所以感觉还是有个小坑点所以还是写个题解记录下我的傻逼QAQ首先这题一看,就长得很像NOIp关押罪犯?然后就噼里啪啦打一个并查集上去,再随便离散化一下,就能获得90pts的好成绩,,,(因为数据太水了QAQ然后考虑为什么不能用那题的套路?仔细思考下,用并查集的条件是什么?——可传...
2019-03-26 19:47:00
80
原创 POJ2431 Expedition 贪心
正解:贪心解题报告:先放个传送门鸭,题目大意可以点$Descriptions$的第二个切换成中文翻译然后为了方便表述,这里强行改一下题意(问题是一样的只是表述不一样辣,,,就是说现在在高速公路上行驶,初始有$K$的油量,每走一公里要消耗一单位的油,然后路上有$N$个加油站,离终点的距离分别为$A_i$,每次经过一个加油站可以选择加或者不加,加就能加$B_i$的油量,然后要...
2019-03-26 19:37:00
68
原创 CF865D Buy Low Sell High 贪心
正解:贪心解题报告:传送门!这题首先有个很显然的dp,太基础了不说QAQ然后考虑dp是n2的,显然过不去,所以换一个角度然后发现这题和普通的dp的题有什么不同呢?就它这儿是一天只能买一支股,所以考虑怎么从这儿下手?为了方便表示这里先define一下,x表示卖出价格,y表示买入价格现在考虑如果是只考虑最后一天,那显然是从前面没买股票的日子中找到一天买股票的价格最低的,和最后一...
2019-03-24 13:46:00
96
原创 洛谷P4064 加法 [JXOI2017] 贪心
正解:贪心解题报告:传送门!首先最小值最大显然考虑二分?然后就二分一个值mid,从左往右考虑,对于小于等于mid的点显然可以求出这个点至少要加几次,然后找到覆盖这个点的右端点max的区间区间加上它要加的数就好然后具体的操作和短路那题差不多,,,同差分+开个数组+全局变量,over挺显然的贪心?不解释了QAQ那就等下直接放代码了QAQ(我怎么觉得我题解越来越简洁...
2019-03-23 17:52:00
89
原创 洛谷P4823 拯救小矮人 [TJOI2013] 贪心+dp
正解:贪心+dp解题报告:传送门!我以前好像碰到过这题的说,,,有可能是做过类似的题qwq?首先考虑这种显然是dp?就f[i][j]:决策到了地i个人,跑了j个的最大高度,不断更新j的上限就得到答案了(显然i可以省略但为了表述更清晰一点就懒得省辣?然后这时候就考虑一个问题,就是,dp的要求是无后效性嘛,但这里有个问题,假如有三个人,高度分别为(1,1)(1,1)(10...
2019-03-22 17:20:00
105
原创 CF720A Closing ceremony 贪心
正解:贪心解题报告:传送门!先考虑如果只有一列怎么搞?那就肯定是尽量走到最远的地方然后用点儿类似的思想,现在考虑有两列的情况QAQ为了方便表述,这里给每个位置两个值,a表示离一号入口的距离,b表示离二号入口的距离可以先把从一号入口进去的安排了,所以考虑按体力从小往大考虑,然后在能满足a的情况下尽量选b比较大的位置然后再处理二号入口的,就按体力从大往小考虑一下就...
2019-03-22 16:34:00
109
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人