STL map string
http://t.csdnimg.cn/H8dhK
http://t.csdnimg.cn/KQBbU
1.寄包柜
超市里有 n ( 1 ≤ n ≤ 1 0 5 ) n(1\le n\le10^5)n(1≤n≤10 5 ) 个寄包柜。每个寄包柜格子数量不一，第 i ii 个寄包柜有 a i ( 1 ≤ a i ≤ 1 0 5 ) a_i(1\le a_i\le10^5)a i (1≤a i ≤10 5) 个格子，不过我们并不知道各个 a i a_ia i的值。对于每个寄包柜，格子编号从 1 开始，一直到 a i a_ia i。现在有 q ( 1 ≤ q ≤ 1 0 5 ) q(1 \le q\le10^5)q(1≤q≤10 5） 次操作：
1 i j k：在第 i ii 个柜子的第 j jj 个格子存入物品 k ( 0 ≤ k ≤ 1 0 9 ) k(0\le k\le 10^9)k(0≤k≤10
9 )。当 k = 0 k=0k=0 时说明清空该格子。
2 i j：查询第 i ii 个柜子的第 j jj 个格子中的物品是什么，保证查询的柜子有存过东西。
已知超市里共计不会超过 1 0 7 10^710 7 个寄包格子，a i a_ia i是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。输入格式
第一行 2 个整数 n nn 和 q qq，寄包柜个数和询问次数。接下来 q qq 个整数，表示一次操作。
输出格式
对于查询操作时，输出答案，以换行隔开。样例输入 #1
5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1
1
2
3
4
5
样例输出 #1
118014
1
STL map
learn 红黑树 AVL树
http://t.csdnimg.cn/VRZMN
map 是具有唯一键值对的容器，通常使用红黑树实现。
map 中的键值对是 key value 的形式，比如：每个身份证号对应一个人名（反过来不成立哦！），其中，身份证号就是 key，人名便是 value，是单项的关系，可以与 hash 作类比。
//使用 map 需要引入头文件，如下所示：
#include <map>
//定义形式如下所示：
map<key_type, value_type>变量名
//注意：如果没有 using namespace std, map需要写成 std:map//常用
size() // 计算元素个数
empty() // 判断是否为空，空返回 true
clear() // 清空容器
erase() // 删除元素
find() // 查找元素
insert() // 插入元素
count() // 计算指定元素出现的次数
begin() // 返回迭代器头部
end() // 返回迭代器尾部
//非常用
swap() // 交换两个map容器，类型需要相同
max_size() // 容纳的最大元素个数
rbegin() // 指向map尾部的逆向迭代器
rend() // 指向map头部的逆向迭代器
lower_bound() // 返回键值大于等于指定元素的第一个位置
upper_bound() // 返回键值大于指定元素的第一个位置
equal_range() // 返回等于指定元素的区间忘了换行符了。
#include<cstdio>
#include<map>
using namespace std;
map<long long,long long>a[100001];
int main()
{
int n,m,x;
scanf("%d %d",&n,&m);
long long i,j,k;
while(m--)
{
scanf("%d",&x);
if(x==1)
{
scanf("%lld %lld %lld",&i,&j,&k);
a[i][j]=k;
}else if(x==2)
{
scanf("%lld %lld",&i,&j);
printf("%lld\n",a[i][j]);
}
}
return 0;
}
2.不重复数字
/*给定 n 个数，要求把其中重复的去掉，只保留第一次出现的数。
Input
本题有多组数据。
第一行一个整数
T，表示数据组数。对于每组数据：
第一行一个整数
n。第二行
n 个数，表示给定的数。
Output
对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。Sample 1
Inputcopy Outputcopy */
C++中的set是一个集合容器，它存储唯一且已排序的元素。具体来说，set容器内部的元素总是按照一定的规则排好序的，而且这些元素必须是唯一的，即不允许存储重复的元素。
//头文件
#include<set>
//初始化定义
set<int> s;
在c++中，如果a前面啥也没有，默认访问局部变量；
前面加上::，访问全局变量；
s.count函数 判断集合中是否有该元素，有的话返回true
/*给定 n 个数，要求把其中重复的去掉，只保留第一次出现的数。
Input
本题有多组数据。
第一行一个整数
T，表示数据组数。对于每组数据：
第一行一个整数
n。
第二行
n 个数，表示给定的数。
Output
对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。*/
#include<cstdio>
#include<set>
using namespace std;
set<int>s;//构造一个容器 set，存储唯一的且已经排序的元素
int main()
{
int t,n,r,i,k;
scanf("%d",&t);//组数
for(k=1;k<=t;k++)
{
scanf("%d",&n);//每组内元素个数
s.clear();//清空容器
scanf("%d",&r);//第一个元素
printf("%d",r);
s.insert(r);//第一个元素插入到set
for(i=2;i<=n;i++)
{
scanf("%d",&r);//剩余元素
if(s.count(r)==0)//有该元素，s.count返回1
{
printf(" %d",r);//没有的话，输出
s.insert(r);
}
}
printf("\n");
}
return 0;
}
3.文字处理软件
你需要开发一款文字处理软件。最开始时输入一个字符串作为初始文档。可以认为文档开头是第 00 个字符。需要支持以下操作：
1 str：后接插入，在文档后面插入字符串 strstr，并输出文档的字符串；2 a b：截取文档部分，只保留文档中从第 𝑎a 个字符起 𝑏b 个字符，并输出文档的字符串；3 a str：插入片段，在文档中第 𝑎a 个字符前面插入字符串 strstr，并输出文档的字符串；4 str：查找子串，查找字符串 strstr 在文档中最先的位置并输出；如果找不到输出 −1−1。为了简化问题，规定初始的文档和每次操作中的 strstr 都不含有空格或换行。最多会有 𝑞q 次操作。
Input
第一行输入一个正整数 𝑞q，表示操作次数。
第二行输入一个字符串 strstr，表示最开始的字符串。
第三行开始，往下 𝑞q 行，每行表示一个操作，操作如题目描述所示。
Output
一共输出 𝑞q 行。
对于每个操作 1,2,31,2,3，根据操作的要求输出一个字符串。
对于操作 44，根据操作的要求输出一个整数。
Sample 1
Inputcopy Outputcopy Hint
数据保证，1≤𝑞≤1001≤q≤100，开始的字符串长度 ≤100≤100。
学习：http://t.csdnimg.cn/HlzVt
在第二个那里卡了好久，还不是很理解
#include<stdio.h>
#include<string.h>
char search(char *s,char *t);
char temp[1000];
int main()
{
char a[1110];
char b[111];
int n,m,i,l,r,k;
scanf("%d",&n);
scanf("%s",a);
for(i=0;i<n;i++)
{
scanf("%d",&m);
if(m==1)
{
//后接插入
scanf("%s",b);
strcat(a,b);
printf("%s\n",a);
}else if(m==2)
{
//截取部分文档
scanf("%d %d",&l,&r);
a[l+r]='\0';
strcpy(temp, &a[l]);
strcpy(a, temp);
printf("%s\n",a);
/*int y=strlen(a);
l=l%y; r=r%y;
for(int x=l;x<l+r;x++)
{
printf("%c",a[x]);
}
a[l+r]='\0';
printf("\n");*/
}else if(m==3)
{
//前面插入
scanf("%d%s",&k,temp);
strcat(temp,&a[k]);//temp和a的后半部分连接
a[k]='\0';//截取前面
strcat(a,temp);//连接前半部分和后面
printf("%s\n",a);
}else if(m==4)
{
//查找子串
scanf("%s",temp);
int x;
x=search(a,temp);
printf("%d\n",x);
}
}
return 0;
}
char search( char *s, char *t )
{
int i=0,j=0,k;
for(i=0;s[i]!='\0';i++)
{
k=i;
j=0;//每次比较都从t所指的第一个开始比较
while(s[k]==t[j]&&s[k]!='\0'&&t[j]!='\0')
//判断时要考虑两个是否为\0，如果有一个是则跳出
{
k++;
j++;
}
if(j!=0&&t[j]=='\0')
break;
}
if(s[i]!='\0')
{
return i;
}
else return -1;
}
4.ICPC Ballons
在ICPC比赛中，气球的分配如下:
每当一个团队解决了一个问题，这个团队就会得到一个气球。
第一个解决问题的队伍将获得一个额外的气球。
一场比赛有26道题，标为ABC,……, Z
你会得到比赛中已解决问题的顺序，用字符串s表示，我在哪里?
-该字符表示问题为si
已经被某个团队解决了。没有团队会两次解决同一个问题。
确定每队收到的气球总数。请注意，有些问题可能没有一个团队可以解决。输入
输入的第一行包含一个整数t
(1≤t≤100
)——测试用例的数量。每个测试用例的第一行包含一个整数n
(1≤n≤50
) -字符串的长度。每个测试用例的第二行包含一个字符串s
长度为n的
由大写英文字母组成，表示已解决问题的顺序。输出
对于每个测试用例，输出单个整数—团队接收到的气球总数。例子
inputcopy outputcopy
6
3
阿坝
1
一个
3
五体投地
5
BAAAA
4
BKPT
10
CODEFORCES
5
2
6
7
8
17
请注意
在第一个测试用例中，5
发放气球:问题
是解决。那个队得到2分
气球:一个是因为他们解决了问题，另一个是因为他们是第一个解决问题A的团队
．
问题B
是解决。那个队得到2分
气球:一个是因为他们解决了问题，另一个是因为他们是第一个解决问题B的团队
．
问题
是解决。那个队只得到1分
气球，因为他们解决了这个问题。注意，他们没有得到额外的气球，因为他们不是第一个解决问题A的团队
．
发出的气球总数是2+2+1=5
．
在第二个测试用例中，只解决了一个问题。解决问题的队伍得到2分
气球:一个是因为他们解决了问题，另一个是因为他们是第一个解决问题A的团队
．
网易翻译的，沉默
参考：http://t.csdnimg.cn/k90N3
看了一下，解题说明：用数组统计每个字母出现的个数，直接遍历，当字母第一次出现时加2，否则只加1。
