题目链接：poj 1436 Horizontally Visible Segments
题目大意：给定n条垂直的线段，保证两两线段不重叠。问说有多少组三元线段可以互相看到。
解题思路：线段树+暴力。表示很不能理解的题目，复杂度略高。先将线段按照x坐标排序，然后为每个线段标号，从左向右每次修改区间。在修改之前查找一下该区间没有被完全覆盖的线段，用vector存小来，最后再暴力计数。
#include <cstdio>
#include <cstring>
#include &...
阅读全文
题目链接：poj 2991 Crane
题目大意：就是有一个机械手臂，有n结，给定每节的长度，一开始为垂直的。有m次操作，每次将x关节变成角度d，并且输出手臂末端的坐标。
解题思路：点的旋转公式(r为逆时针的角度):
x′=x∗cos(r)−y∗sin(r)
y′=x∗sin(r)+y∗cos(r)
没有做过类似的题目，线段树每个节点记录的为每节旋转的角度以及单节末端的位置。每次旋转新的角度，需要根据前一个节点的角度和当前节点的角度来计算（因为它不是再...
阅读全文
题目链接：poj 3225 Help with Intervals
题目大意：模拟集合操作，输出最终的集合。
解题思路：线段树。
U l r：[l,r]区间置为1
I l r：[0,l),(r,maxn]置为0
D l r：[l,r]区间置为0
C l r：[0,l),(r,maxn]置为0,[l,r]区间取逆
S l r：[l，r]区间取逆。
然后基本水水的线段树，注意一下区间开和闭。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn...
阅读全文
poj 3667 Hotel
题目大意：给定一个区间，两种操作：
1 x：找到区间中最左边，将长度为x的区间放入，要求尽量靠左。
2 l r：清空l，r + l - 1这段区间。
解题思路：线段树的区间合并，每个节点记录S，L，R即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn =50005;
int N, M;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<...
阅读全文
题目链接：poj 2001 Shortest Prefixes
题目大意：给定一个字符串集合，要求使得每个字符串尽量缩短，但是仍然能区分开。
解题思路：根据字符串集建立字典树，并且每插入一个字符串，所有路径上节点均加1，表示该子串是这个字符串的前
缀。然后对每个字符串进行一次查找，当碰到节点的统计值为1时，表示当前子串仅为该字符串的前缀，即为要找的字
符串。
#include <cstdio>
#include <cstring>
#include <...
阅读全文
题目链接：poj 2503 Babelfish
题目大意：给定若干个字符串间的映射关系，然后是若干次查询，每次查询一个字符串，判断该字符串是否有映射串，
有的话输出映射串，否则输出eh。
解题思路：字典树水题。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6+5;
const int maxm = 105;
const int sigma_size = 26;
struct Tire {
int sz;
i...
阅读全文
题目链接：poj 2513 Colored Sticks
题目大意：有N个木棍，每根木棍两端被涂上颜色，现在给定每个木棍两端的颜色，不同木棍之间拼接需要颜色相同的
端才可以，问最后能否将N个木棍拼接在一起。
解题思路：欧拉通路+并查集+字典树。欧拉通路，每个节点的统计度，度为奇数的点不能超过2个。并查集，判断节点
是否完全联通。字典树，映射颜色。
#include <cstdio>
#include <cstring>
#include <string>
#...
阅读全文
题目链接：poj 1204 Word Puzzles
题目大意：给定一个有字符组成的N行M列的矩阵，就这是Q次查询，每次查询包括一个字符串，要求在矩阵中找到起
始点以及方向。
解题思路：对查询建立字典树，然后暴力枚举矩阵中的起点和方向。数据有点弱，就这样给过了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6+5;
const int maxc = 1005;
const int ...
阅读全文
题目链接：poj 1816 Wild Words
题目大意：给定N个模板，即正则表达式，然后每次有一个询问串，输出能被哪些模板匹配。
解题思路：对模板建立字典树，然后每次询问即在字典树做DFS搜索，注意'*'的情况，可以匹配一个和多个，所以在结
尾的时候要注意。并且，模板串有重复的情况。
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
const int ma...
阅读全文