boxxxx

分类

学习(10) 并查集(1) 数位dp(1) 概率dp(1) 算法(38) 线性dp(1) 题解(3)

/ 注册

全部文章（共55篇）

hdu1045 行列缩点+二分图匹配

题意：目标是尽可能多地在城市中设置碉堡，这样就不会有两个碉堡相互摧毁。如果没有两个碉堡在地图的同一水平行或垂直列上，除非至少有一个墙将它们分开，否则碉堡的配置是合法的。在这个问题中，我们将考虑小方形城市（最多4x4），其中包含无法穿过子弹的墙壁。下图显示了同一块板的五张图片。第一张图片是空白板，第...

2019-09-21

0 483

hdu2255 KM（带权二分图匹配）

这道题就是一个裸的带权二分图(KM)匹配模板。首先关于KM算法，我概念是看的这个视频（在2P） https://www.bilibili.com/video/av60813417/?p=2&t=316 然后关于代码方面我是看的这个博客 https://blog.csdn.net/frank...

2019-09-21

0 570

hdu2444 染色法+二分图匹配

有n个关系，他们之间某些人相互认识。这样的人有m对。你需要把人分成2组，使得每组人内部之间是相互不认识的。如果可以，就可以安排他们住宿了。安排住宿时，住在一个房间的两个人应该相互认识。最多的能有多少个房间住宿的两个相互认识。首先题目是要问能不能分成两组，每组人之间互相不认识，每个人只与对面...

2019-09-21

0 497

洛谷p1062 找规律

看题解都是进制转换，本弱弱一开始没想到，但是搞出了点规律，一样可以过。上图规律就是第 2^n 个数字就是数字 k^n; 然后在第 2^n 到 2^n +1之间的数字，就是第 2^n 的数加上第一个数，第二个数,知道第2^n-1个数。然后我们只要把这个过程模拟出来就可以啦，代码也很短 #inc...

2019-09-20

0 440

洛谷p2055 二分图匹配

题目描述学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 ...

2019-09-20

0 628

洛谷p1233 sort+贪心

题目描述一堆木头棍子共有n根，每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的：第一根棍子的准备时间为1分钟；如果刚处理完长度为L，宽度为W的棍子，那么如果下一个棍子长度为Li，宽度为Wi，并且满足L>＝Li...

2019-09-19

0 323

poj3169 差分约束

关于差分约束，我强推这位大佬的博客。https://blog.csdn.net/consciousman/article/details/53812818 题目是有的牛互相之间最多只能有一个距离，有的牛最少要达到一个距离。很容易写出不等式，由于是要求最大值，所以是要化为小于等于号，求最短路。 F[...

2019-09-19

0 408

洛谷p1993 差分约束+dfs版spfa

这道题算作是差分约束模板题了，关于差分约束，我强推这位大佬的博客。https://blog.csdn.net/consciousman/article/details/53812818 里面博客这段话就是解决这些题目的精髓了； (下面这段话是上面博客里面的） /******************...

2019-09-18

0 615

hdu4123 树求每个节点的最长链+尺取法

题意：50000个点的树，每个点有一个人，每个人会跑到离自己初始点距离最远的点上，这个距离为distance[i]。给你500个查询，对于每个查询Q，找一段连续编号的人，比如[left,right]，满足 max( distance[i] i∈[left,right] ) – min( distan...

2019-09-15

0 452

poj1655 dfs序+暴力

题意就是给你一棵树，然后去掉一个节点，求去掉哪个节点他的剩下的树的最大节点数最少。输出节点和最大子树节点数。由树dp专题看见这题，但是嘛。。。。。我第一眼都没意识到他是个dp。我的做法是这样的，就跑就只跑一遍dfs序，然后途中记录一下每个节点的父亲是谁。在暴力跑每一个点的答案。遍历每一个点的答...

2019-09-12

0 453