1151专题

--hdu 1151 - 双向路径搜索解决覆盖问题

http://acm.hdu.edu.cn/showproblem.php?pid=1151 伞兵可以降落到图上的任意一个点，用最少的伞兵在单向道路上走完所有的点解决：对一个点双向dfs，目的在于找到任意一个其他伞兵未访问的非起点，只要找到这个点，则可以保证这条路径是最佳的；因为路是单向的，所以从这个点出发后，就不会再次回到这个点（题目中保证没有环）。 #in

HDU 1542 POJ 1151 Atlantis(线段树+扫描线）

题目地址：HDOJ地址：HDU 1542 POJ 地址：POJ 1151 第一发扫描线。。费了好大一番功夫。。构思用了半天。。写出来调试成功用了半天。。。真是弱渣。。所谓扫描线就是从上往下或从下往上扫描，每到一个边，就进行增或删的处理。最后出来的值就是总的面积。对于求面积并的问题，可以参考这篇博客（博客地址），讲的不错。具体实现过程是用lazy标记此时的边数量，如果大于0，说明这个地方

HDOJ 1151 二分匹配

我的AC代码 #include <iostream>#include <string.h>using namespace std;int n,m,k,t,s,e,result;int map[130][130],v[130],link[130];void init(){scanf("%d", &n);scanf("%d", &m);memset(map, 0, sizeof(map

POJ 1151 Atlantis 线段树/矩形面积并

题意：求矩形的面积并。题解：求矩形的并，由于矩形的位置可以多变，因此矩形的面积一下子不好求这个时候，可以采用“分割”的思想，即把整块的矩形面积分割成几个小矩形的面积，然后求和就行了这里我们可以这样做，把每个矩形投影到 y 坐标轴上来然后我们可以枚举矩形的 x 坐标，然后检测当前相邻 x 坐标上 y 方向的合法长度，两种相乘就是面积然后关键就是如何用线段树来

hdu 1151 Air Raid

主题思想： DAG 有向无环图，最少路径覆盖本质二分图最大匹配问题二分图最大匹配数=最小点覆盖数DAG最少路径覆盖数=DAG顶点数-二分图最大匹配数。特别的无向图的最大匹配数需要除以2。且顶点是全体。 AC代码： #include <iostream>#include<cstring>#include<cstdio>#include<vector>using namesp

1151 LCA in a Binary Tree 一种自己的解法

最近刷PAT的题目看到一个BST找最近共同祖先的新思路，大大化简了算法，给出链接： https://blog.csdn.net/ysq96/article/details/81746996 因为这种解法只适合BST且需要先序排序，所以只能针对A1143这种题目，根据这个思路对于A1151我进行了算法的迁移使用：将原来的树映射到一棵BST上，在BST上找到答案后映射回由原来的树，在此贴上代码

HDU 1151 Air Raid （最小路径覆盖入门级）

<span style="font-family: Arial, Helvetica, sans-serif; font-size: 12px; background-color: rgb(255, 255, 255);">若有错误，欢迎指出！！！</span> 题意：就是一堆岔道口（可以理解为节点），由街道连接着。求最小的几个伞兵可以遍历整个街道。（有向图）。题解：基本

【模拟】pjesma（jzoj 1151）

pjesma 题目大意：一首歌放出m个单词，M某知道n个关键词，当关键词放出一半以上时，M某就知道这是哪首歌，问在放出第几个单词时，M某知道这首歌是哪首歌样例输入 3 sedam gladnih patuljaka 7 sedam dana sedam noci sedam gladnih godina 样例输出 6 数据范围限制 1≤N≤50 1≤M≤10 000 歌名和专辑

POJ 1151 Atlantis

首先，我得吐个槽。陶叔果然是个诚实的孩子，今天的题简直坑爆了好么？先说A题，翻了一遍题目，觉得A题(SPOJ SUB_PROB)就是个KMP的模板题，心中大喜，套模板，欲A之，怎奈何居然是WA（我还提交了三遍T_T，再不济你给个TLE我也可以接受啊）。于是重新读题，发现应该拿AC自动机来搞！！！瞄一眼Rank，分析一下局势，决定不理A题了，开了E题(Aizu 0024)。由于E题是签到水题

PAT甲级1151 LCA in a Binary Tree (30 分)：[C++题解]LCA、最低公共祖先、哈希表映射

文章目录题目分析题目链接题目分析来源：acwing 分析：和下面这道题几乎是同一题：PAT甲级1143 Lowest Common Ancestor (30 分)：[C++题解]LCA、最低公共祖先这道题先是根据给定的中序遍历和先序遍历，建树。建树的时候需要用到点的深度和每个点的父节点是什么。然后是找LCA,有很多优秀的算法，这里使用朴素做法，O(n)复杂

UVA 1151 - Buy or Build（最小生成树，二进制子集生成）

自己实力有限。在为了K神之后。自己才写出来的。二进制子集生成又忘记了。又去前面翻书看的。（P 190）这个题。首先要去生成最小生成树（也就是不同套餐的情况）然后用二进制子集生成。枚举所有套餐的选择情况。比如套餐有 1 2 3 三种套餐则需要求出所有可能的组合。 1 ， 1 2， 1 3， 1 2 3，这样选择每一个子集对

[poj 1151] Atlantis：扫描线+线段树求面积并

想做APIO 2012 Kunai ，我要把虐过我的题虐回去。把问题转化为了平面中线段的并，或者说面积并。听说这道题要用线段树，大概就是这里了？除了二维线段树，我没有想到什么时间复杂度合理的好方法，而且二维线段树空间会爆。联想到数轴上的区间覆盖问题，我试着推广，但始终不能抓住要害，把二维的信息压缩到一维。数轴上的区间覆盖问题至少有两种方法，一是排序之后扫一遍，二是像差分数组一样+1、-1。