codeforces 19 D. Points (离散化+树套树(线段树+set))

题目链接

题意:

在二维坐标平面内进行n (1 ≤ n ≤ 2·105) 次操作。一共有三种类型操作。

1.add x,y 将点(x,y)加进坐标系。

2.remove x,y 将点(x,y)移除.

3.find x,y 找到点(x,y)右上角的点(xp>x,yp>y)。如果有多个输出x最小的。还是有多个输出y最小的。

x,y均为非负数。以上操作均合法。

思路:没有思路。。。不会啊。。。以为要二维线段树什么的。。。。总之是不会做。。。

大概从中午开始看题解。。。8个小时。。。。终于完全搞懂了orz

很巧妙得把二维问题转化成了一维问题。。。

我来说一下大概做法,具体的细节见代码注释:

在x轴方向维护一课线段树,线段树的数组tree[i]存储的信息是以i节点为根节点的子树所对应的区间能达到的最大的y值。线段树的叶子节点上是一个set,set[i]是横坐标为i时的纵坐标集合,也就是所谓的树套树。

由于x很大,但是n比较小,所以我们这里采用了stl+去重的办法离散化离散化的三种办法

对于添加和删除点的操作,我们更新完对应的set把相应的x(离散化后的)在线段树中更新就好(因为线段树的update操作是和set有关的)

对于find操作,我们首先从线段树中找到(下标大于x且最小且集合中存在大于y的元素的集合)的下标

这样我们确定了x,再upper_bound一下找到对应的集合中最小的y.

初始化由于没有插入y,所以tree可以初始化为-1,不用建树。。。(反正建了也都是-1)

 

hdu 5842 || 2016 ccpc 网络赛 1011 Lweb and String(set)

hdu 5842题目链接

题意:给一个只由小写字母组成的字符串,每个字符映射到一个数字,问映射之后的最长上升子序列的长度。。

思路:上来写nlogn的LIS是我无脑了。。。wa了之后想了下。。其实只要统计不同的字母数就好了啊。。。set一下

 

 

hdu 2609 How many (字符串的最小表示法+set)

hdu 2609 题目链接

题意:给出n个循环字符串,问有多少种。

思路:将每个字符串换成最小表示,然后set存一下即可。

 

codeforces #346 div 2 C. Tanya and Toys (暴力乱搞)

题目链接
题意:有1E9个礼物,第i个礼物价钱是i,然后现在已经有n个不重复的礼物,a[i],m元钱,想尽可能多得买不同种类的礼物,还能买多少个。
思路:先不考虑已经买的,从1连续买到k,然后考虑子啊这个区间内已经买的,等于实际上没有花钱。
反正就是暴力搞啊搞啊。。我也不知道怎么搞。。
结果最后。。方案数为0的时候。。。最后一个答案我是单独输出的。。忘了判断了。。。所以会输出两个0.宝宝心里苦啊。。。。。。。。

codeforces 274 A. k-Multiple Free Set (set的妙用)

题目链接
题意:给出n个互不相同的元素和k,构成一个集合,使得集合中不存在两个元素满足y=k*x,问能构成这样的集合的最大size是多少。
思路:set大法好。很重要的一点是题目中明确说每个元素都不重复。然后每次删掉元素x和元素x*k,因为这两个元素最多留一个,然后答案+1. 需要注意k=1的特殊情况。

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删除元素的时候不能直接删,因为会把所有相同的值删掉。

 

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

 

 

codeforces #332 div 2 D. Spongebob and Squares

http://codeforces.com/contest/599/problem/D
题意:给出总的方格数x,问有多少种不同尺寸的矩形满足题意,输出方案数和长宽(3,5和5,3算两种)
思路:比赛的时候gg了。。其实稍微在纸上推一下。就会得到对于n,m的矩形,一共会有-n*n*n+3*n*n*m+n+3*n*m的方格。数量级是n3。
我们可以实际跑一遍。发现对于x1E18的数量级,n不会超过1442550,1E6,可以搞。

需要注意的是,一个是会爆int,所以记得用long long

另一个是如果两个数相等,记得只输入一组,并且方案数-1

我是用set +pair存的答案。。反向遍历set的时候要用reserve_iterator…

 

 

codeforces #333 div 2B. Approximating a Constant Range

http://codeforces.com/contest/602/problem/B
题意:给定n个数,问最大连续区间长度,满足这段区间内最大值和最小值的差的绝对值小于等于1.
思路:尺取+set。尺取法,由于要时刻得到一段区间的最大值和最小值,而且可能有重复元素,所以用multiset.

需要注意的是,set里最小值是*se.begin() ,最大值是*se.rbegin()这样比较好。。不要用se.end()之类。。。

另一个需要注意的是,multiset里用erase的时候。如果se.erase(x)会把集合里所有的x都删除掉。如果指向删除一个,那么应该写成se.erase(se.find(x))