拆点

hdu 3722题目链接 题意：n个串，a串放在b串前面的val值是“The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card”.问如何放使得总的val最大。 思路：先暴力处理出每两个的权值。。2002001000的复杂度。。还是可以接受的。。

hdu 3435题目链接 题意：给你一张图，图上可能有多个哈密顿回路。叫你求出形成多个哈密顿回路的总距离最小值 思路：题意杀啊。。。什么鬼了。。。然后时间。。1000的数据。。n3复杂度。。。还多组数据。。。。不是很懂这个时间是怎么算的。。为毛才2600MS啊。。。。

hdu 1853 题目链接 题意：一个带权有向图，要求找出若干的环，满足每个点恰好在一个环里，并且环的权值和最小……问最小权值和。 思路：没有思路，不知道怎么处理环的问题。于是去群里问了下。正确做法是拆点。

http://poj.org/problem?id=2926 题意：给出n(1E5)个五维空间内的坐标…问最远的两个点距离多少。 思路：拆点即可。去绝对值。可以由二维空间推广到k维空间。一个点可以拆成2^(k-1)个点。 具体见代码。

http://acm.split.hdu.edu.cn/showproblem.php?pid=5626 题意：给出n（1E6）个点的二维坐标，问距离最远的两个点的距离是多少。 思路：对曼哈顿距离进行变换。 先看曼哈顿距离的定义 |x1−x2|+|y1−y2| 拆绝对值 x1−x2+y1−y2或x1−x2+y2−y1

http://www.lydsy.com/JudgeOnline/problem.php?id=1604 题意：了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的： 1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi - Yil≤C. 2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群． 给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛