Set

题目链接 题意： 在二维坐标平面内进行 n (1 ≤ n ≤ 2·10^5) 次操作。一共有三种类型操作。 1.add x,y 将点 (x,y) 加进坐标系。 2.remove x,y 将点 (x,y) 移除。 3.find x,y 找到点 (x,y) 右上角的点 (xp>x,yp>y)。如果有多个输出 x 最小的。如果还有多个输出 y 最小的。

hdu 5842题目链接 题意：给一个只由小写字母组成的字符串，每个字符映射到一个数字，问映射之后的最长上升子序列的长度。。 思路：上来写nlogn的LIS是我无脑了。。。wa了之后想了下。。其实只要统计不同的字母数就好了啊。。。set一下

hdu 2609 题目链接 题意：给出n个循环字符串，问有多少种。 思路：将每个字符串换成最小表示，然后set存一下即可。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月13日 星期六 02时44分21秒 4File Name :code/hdu/2609.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E4+7; 34int n; 35char s[N][105]; 36set<string>se; 37int minRep(char *s) 38{ 39 int n = strlen(s); 40 int i = 0 ; 41 int j = 1 ; 42 int k = 0 ; 43 while (i<n&&j<n&&k<n) 44 { 45 int t = s[(i+k)%n] - s[(j+k)%n]; 46 if (t==0) k++; 47 else 48 { 49 if (t>0) 50 i+=k+1; 51 else j+=k+1; 52 if (i==j) j++; 53 k = 0 ; 54 } 55 } 56 return i<j?i:j; 57} 58int main() 59{ 60 #ifndef ONLINE_JUDGE 61 freopen("code/in.txt","r",stdin); 62 #endif 63 while (~scanf("%d",&n)) 64 { 65 ms(s,0); 66 se.clear(); 67 // cout<<"n:"<<n<<endl; 68 char tmp[105]; 69 for ( int i = 0 ; i < n; i++) 70 { 71 scanf("%s",tmp); 72// cout<<"tmp:"<<tmp<<endl; 73 int k = minRep(tmp); 74// cout<<"k:"<<k<<endl; 75 int cnt = 1; 76 int len = strlen(tmp); 77 for ( int j = k ; cnt <= len ; j++,cnt++) 78 s[i][cnt-1] = tmp[j%len]; 79 se.insert(string(s[i])); 80 } 81// for ( int i = 0 ; i < n; i++) cout<<"s[i]:"<<s[i]<<endl; 82// 83 int ans = se.size(); 84 printf("%d\n",ans); 85 } 86 #ifndef ONLINE_JUDGE 87 fclose(stdin); 88 #endif 89 return 0; 90}

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

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

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

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

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