bzoj 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居 (曼哈顿距离的转化【拆点】+set+并查集)

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均同属一个群.
给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

思路:一开始并没有什么思路…入手点是关于曼哈顿距离的转化。

先看曼哈顿距离的定义

|x1x2|+|y1y2|

拆绝对值

x1x2+y1y2x1x2+y2y1

x2x1+y1y2x2x1+y2y1

|x1+y1(x2+y2)||x1y1(x2y2)|

x1+y1xx1y1y

|x1x2||y1y2|

所以原要求1转化为

max(|x1x2|,|y1y2|)<=c

引用自:http://blog.csdn.net/wzq_QwQ/article/details/47746091

 

这样就有思路了。如果两个点属于同一个群,那么必须这两个点的x的差在c范围内,并且两个点的y的差也在范围内。 我们可以先按照一个 坐标排序,不妨以x为关键字排序,然后维护一段点的序列,使得这段序列中的所有的点的横坐标(其实就是最大减去最小)的差都在c范围内。然后对于序列中的所有点,我们想要知道有没有群“接纳”最新加入的点,二分找到比当前新加入点的纵坐标大的最小值和比当前新加入点的纵坐标小的最大值(set的lower_bound 第一次用),判断是否满足纵坐标的差在c的范围内。如果是,则用并差集合合并一下。

用multiset的原因是经过变换后点的坐标可能重复,以及multiset删除元素的时候不能直接删,因为会把所有相同的值删掉。

 

重要的话再说一遍:这道题最关键也是最大的收货就是,关于曼哈顿距离的变换。

 

 

uva 10420 – List of Conquests

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1361
题意:给n个带空格的字符串,第一个单词是国家,统计每个国家的字符串的个数。
思路:getline函数。。。find函数。。。substr函数。。。map…..

codeforces 29 C. Mail Stamps

http://codeforces.com/contest/29/problem/C
题意:给出n个边的关系,保证可以构成一条链。正向或者反向输出这个链。
思路:由于下标很大(1E9),而关系个数只有1E5..需要离散化。。而且离散化的同时不能丢失边的关系。。。实际上。。直接用vector+map就好了。。。 map >e;即可。然后找到一个度为1的点。。做个dfs…

codeforces 12 C. Fruits

http://codeforces.com/contest/12/problem/C
题意:有n个价格价格,m个要买的东西(可能有相同的种类,设为k种),把n个标签中拿出k个给个贴上。。。问最大价钱和最少价钱分别是多少。
思路:贪心。不过要按照map的value排序。。然后发现其实不用排序。。因为map的key值其实不影响。

vector降序排列的话。。直接 sort(v.rbegin(),v.rend());就好。

 

 

 

codeforces 522 A. Reposts

http://codeforces.com/problemset/problem/522/A
题意:给定某条消息的传播路径。问最远传播的距离。。
思路:其实就是问树的深度。。直接dfs就行了。。

存的时候用map<string,vector<string> > mp;的方式存即可。

poj 2643 election

题目链接:http://poj.org/problem?id=2643

 

在考stl的map…

我是定义了一个string 指向string的,表示参选人和党派的关系,和一个string 指向int的,表示某个党派被投票的次数。

需要注意的是!!!

需要注意的是!!!

需要注意的是!!!

 

字符串读入部分…

在输入n和m之后,会有一个回车符没读进去…(大概是这样?)

如果不处理一下的话,后面的字符串就会少读入一个…(sad)

解决的办法是在读完n和m之后写一个getchar(); 把回车符读掉。