寒江陪烟火🔥
寒江陪烟火🔥
全部文章
分类
acm相关(6)
dp(68)
RMQ(5)
STL(6)
主席树(2)
二分匹配(23)
二分查找(2)
分治法(3)
划分树(1)
单调队列(2)
博弈(11)
字典树(3)
字符串处理(1)
学习(1)
并查集(4)
强联通分量(3)
归并排序(1)
拓扑排序(1)
搜索(1)
数论(8)
最小生成树(3)
最短路(5)
树状数组(7)
树链剖分(4)
欧拉回路(5)
简单模版(14)
简单题(24)
线段树(13)
网络流(6)
归档
标签
去牛客网
登录
/
注册
寒江陪烟火🔥的博客
全部文章
(共233篇)
POJ2594 Treasure Exploration(最小路径覆盖+传递闭包)
题意: 派机器人去火星寻宝,给出一个无环的有向图,机器人可以降落在任何一个点上, 再沿着路去其他点探索,我们的任务是计算至少派多少机器人就可以访问到所有的点。。 思路: 最小路径覆盖,只是点可以重复去,就需要求传递闭包,用floyd /* *******************...
2016-05-17
0
268
HDU1151 Air Raid(有向图最小路径覆盖)
题意: N个点M条边的有向图 意思就是问最小覆盖 思路: 有向图建单向边,然后匈牙利求最大匹配数 用N-最大匹配就可以了 /* *********************************************** Author :devil Created ...
2016-05-17
0
191
HDU1054 Strategic Game(二分匹配)
题意: 给你一个图,然后每个点被覆盖的时候,相邻的点也会被覆盖 求最小的数量使所有点被覆盖 思路: 学树形dp的时候做过这道题了,绝对比二分图快。。 现在刷二分图,n=1500,用匈牙利和HK算了下 先上匈牙利。。624ms /* ************************...
2016-05-17
0
223
POJ3020 Antenna Placement(最小边覆盖)
题意: 一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市。 问至少放置多少个基站才能使得所有的城市都覆盖无线? 思路: 给每个城市编号,建双向边,跑匈牙利,然后城市数量-匹配数/2就是答案 因为假设每个城市都要建基站,然后有多少个匹配...
2016-05-17
0
304
hihocoder1059 String Matching Content Length(带长度条件的最长公共子序列)
给定只包含字母的两个字符串A,B,求A,B两个字符串的最长公共子序列,要求构成子序列的子串长度都必须大于等于3。比如"abcdefghijklmn"和"ababceghjklmn",其最长满足题意要求的子序列为"abcjklmn",其由公共...
2016-05-16
0
159
SDUTOJ2880 Devour Magic(线段树两重延迟标记)
题意: 每个点能量每秒加1 按时间顺序给你N组时间+区间 表示在时间t时取走区间内的能量 问取走了多少能量 思路: 区间修改区间查询 加能量数延迟一下 去走后延迟一下 用两个flag保存延迟状态 /* ************************************...
2016-05-14
0
250
SDUTOJ2879 Colorful Cupcakes(dp)
山东省赛的一道题 题意: 聚会一个圆桌,相邻字母不能重复,有ABC三种字母 问有多少种方法 思路: dp 第一维滚动,第二维ABC当前位置,后三维存ABC用的个数 由于放在了UPCOJ上,判题比较慢,优化了一下, 在SDUTIJ上20ms /* ***************...
2016-05-14
0
219
HDU4185 Oil Skimming(匈牙利)
题意: n*n的图 相邻两##可除去 问最多除去多少 奇偶建图,OK /* *********************************************** //Author :devil //Created Time :2016/5/12 14:48:...
2016-05-12
0
214
HDU2389 Rain on your Parade(HK模版)
题意: 在一个二维坐标系上有n个人和m把伞,每个人都有自己的移动速度, 问有多少人可以在s min内移动到不同的雨伞处(不允许两个人共用一把伞)。 思路: 由于nm太大(3000),匈牙利会超时,就用HK算法 整理了HK的模版 /* ************************...
2016-05-10
0
221
HDU2819 Swap(二分匹配+输出结果)
题意: 给一个n*n的01矩阵,问能否通过行列交换使得 主对角线上的数都为1 如果能输出交换的过程,如果不能输出-1 思路: 线性代数学过,行列交换都不改变矩阵的秩 三秩相等 如果能改变成主对角线上的数都为1 则原矩阵必为满秩 /* *********************...
2016-05-10
0
221
首页
上一页
7
8
9
10
11
12
13
14
15
16
下一页
末页