题目：http://poj.org/problem?id=3096
题意：给定一个字符串S，从中找出所有有两个字符组成的子串，每当组成子串的字符之间隔着n字符时，如果没有相同的子串出现，则输出 "S is surprising." ，
反之，则输出 "S is NOT surprising." 。 例如 AABA 把它分成两个字符为一个整体的，1..相邻两个字符 AA,AB,BA 没有相同的; 2.隔一个字符的 AB AA 没有相同; 3.隔两个字符的 AA 没有相同
map:转载自：http://blog.csdn.net/lyy289065406/article/details/6648624
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <algorithm>
#define LL __int64
const int maxn = 1e3 + ;
using namespace std; int main()
{
int t, n, sum, v;
char s[];
while(~scanf("%d", &t))
{
while(t--)
{
cin>>n;
sum = ;
map<string, int>m1, m2;
map<string, int>::iterator it;
while(n--)
{
scanf("%s%d", s, &v);
if(m1[s]==) m1[s] = v;
else if(m2[s]==)
{
m2[s] = v;
if(m2[s]>m1[s])
{
int tmp = m1[s];
m1[s] = m2[s];
m2[s] = tmp;
}
}
else
{
m2[s] = m2[s]>v?m2[s]:v;
if(m2[s]>m1[s])
{
int tmp = m1[s];
m1[s] = m2[s];
m2[s] = tmp;
}
}
}
for(it = m1.begin(); it != m1.end(); it++)
sum += it->second;
for(it = m2.begin(); it != m2.end(); it++)
sum += it->second;
cout<<sum<<endl;
}
}
return ;
}
/*STL<map>标记*/ //Memory Time
//212K 16MS #include<iostream>
#include<string>
#include<map>
using namespace std; int main(void)
{
char s[];
while(cin>>s && s[]!='*')
{
int len=strlen(s);
if(len<=) //长度小于等于2的串必定是surprising String
{
cout<<s<<" is surprising."<<endl;
continue;
} bool mark=true; //标记s是否为Surprising String
for(int d=;d<=len-;d++) //d为当前所选取的两个字母之间的距离，d(max)=len-2
{
map<string,bool>flag; bool sign=true; //标记D-pairs字母对是不是D-unique
for(int i=;i<=len-d-;i++) //i为所选取的两个字母中第一个字母的下标
{
char pair[]={s[i],s[i+d+],'\0'}; //构成D-pairs字母对 if(!flag[ pair ])
flag[ pair ]=true;
else
{
sign=false; //存在相同的D-pairs,该字母对不是D-unique
break;
}
}
if(!sign)
{
mark=false; //存在非D-unique，s不是Surprising String
break;
}
}
if(mark)
cout<<s<<" is surprising."<<endl;
else
cout<<s<<" is NOT surprising."<<endl;
}
return ;
}
poj
不是我写的代码，贴上是为了参考跌代器
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
struct node
{
int a,b;
double v;
} g[];
int main()
{
int m,n,i,j,num=;
double v,dis[];
char money[],moneyt[];
while(cin>>n&&n)
{
num++,n++;
map<string,int>mapp;
map<string,int>::iterator iter; //迭代器
for(i=; i<n; i++)
{
cin>>money;
mapp.insert(pair<string,int>(money,i));//插入
}
cin>>m;
for(i=; i<m; i++)
{
scanf("%s %lf %s",money,&v,moneyt);
iter=mapp.find(money);
g[i].a=iter->second;
g[i].v=v;
iter=mapp.find(moneyt);
g[i].b=iter->second;
}
memset(dis,,sizeof(dis));
dis[]=;
for(i=; i<n; i++)
for(j=; j<m; j++)
if(dis[g[j].b]<dis[g[j].a]*g[j].v)
dis[g[j].b]=dis[g[j].a]*g[j].v;
int flag=;
for(j=; j<m; j++)
if(dis[g[j].b]<dis[g[j].a]*g[j].v)
flag=;
printf("Case %d: ",num);
if(flag)
printf("Yes\n");
else
printf("No\n");
}
return ;
}
map的基本操作函数
C++ Maps是一种关联式容器，包含“关键字/值”对
begin() 返回指向map头部的迭代器
clear(） 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数
C++ stl Multimap 和C++ stl map 很相似，但是MultiMap允许重复的元素。
Multimap应用举例：
//multimap允许重复的键值插入容器
// **********************************************************
// * pair只包含一对数值:pair<int,char> *
// * map是一个集合类型，永远保持排好序的， *
// pair * map每一个成员就是一个pair,例如：map<int,char> *
// * map的insert()可以把一个pair对象作为map的参数,例如map<p> *
// ***********************************************************
#pragma warning(disable:4786)
#include<map>
#include<iostream>
using namespace std;
int main(void)
{
multimap<int,char*> m;
//multimap的插入只能用insert()不能用数组
m.insert(pair<int,char*>(,"apple"));
m.insert(pair<int,char*>(,"pear"));//apple和pear的价钱完全有可能是一样的
m.insert(pair<int,char*>(,"banana"));
//multimap的遍历只能用迭代器方式不能用数组
cout<<"***************************************"<<endl;
multimap<int,char*>::iterator i,iend;
iend=m.end();
for(i=m.begin();i!=iend;i++)
{
cout<<(*i).second<<"的价钱是"
<<(*i).first<<"元/斤n";
}
cout<<"***************************************"<<endl;
//元素的反相遍历
multimap<int,char*>::reverse_iterator j,jend;
jend=m.rend();
for(j=m.rbegin();j!=jend;j++)
{
cout<<(*j).second<<"的价钱是"
<<(*j).first<<"元/斤n";
}
cout<<"***************************************"<<endl;
//元素的搜索find(),pair<iterator,iterator>equal_range(const key_type &k)const
//和multiset的用法一样
multimap<int,char*>::iterator s;
s=m.find();//find()只要找到一个就行了，然后立即返回。
cout<<(*s).second<<" "
<<(*s).first<<endl;
cout<<"键值等于1的元素个数是："<<m.count()<<endl;
cout<<"***************************************"<<endl;
//删除 erase(),clear()
m.erase();
for(i=m.begin();i!=iend;i++)
{
cout<<(*i).second<<"的价钱是"
<<(*i).first<<"元/斤n";
}
return ;
}
string
#include <iostream>
#include <string>
using namespace std; string data; bool solve(){
if(data.size()<)
return true;
int i,j;
for(int cnt=;cnt<data.size();cnt++){
for(i=;i+cnt<data.size();i++){
for(j=i+;j+cnt<data.size();j++){
if(data[i]==data[j] && data[i+cnt]==data[j+cnt])
return false;
}
}
}
return true;
} int main(){
while(cin>>data,data!="*"){
if(solve())
cout<<data<<" is surprising."<<endl;
else
cout<<data<<" is NOT surprising."<<endl;
}
return ;
}
string 的相关博客：http://www.cnblogs.com/aicro/archive/2010/01/15/1642659.html
set
#include<iostream>
#include<set>
#include<string>
using namespace std;
int main()
{
set<string> check;
string str;
string temp;
int i,j;
while(cin>>str && str != "*")
{
bool flag = false;
for(i = ;i <= str.length() - ; i++)
{
check.clear();
for(j = ;j <= str.length() - - i;j++)
{
temp = "";
temp = str.substr(j,) + str.substr(j + i,);//string 的用法，分别从j开始截取1个字符
//和从j+i开始截取1个字符 并连接起来
if(check.count(temp) != )
{
flag = true;
break;
}
check.insert(temp);
}
if(flag == true)
break;
}
if(flag == false)
cout<<str<<" is surprising."<<endl;
else
cout<<str<<" is NOT surprising."<<endl;
}
}
vector
转自：http://blog.csdn.net/yzl_rex/article/details/7647532
//这题的测试数据很水，以为下面的做法会超时的！呵呵！ 题意：在一个字符串中，给出一些字符间的距离，然后
//让你根据这距离再重新组成字符串，检查是否有相同的字符串存在！
#include <iostream>
#include <string>
#include <vector>
using namespace std; vector<string> v; int main()
{
string str, tmp;
int i, len, d, j, size, k, l;
bool flag1, flag2;
while (cin >> str)
{
if(str == "*") break;
len = str.length();
flag2 = false;
if (len == )
cout << str << " is surprising." << endl;
else
{
d = len - ;//字符的距离范围
for (i = ; i <= d; i++)//对每一种的距离暴力
{
v.clear();
flag1 = false;
for (j = ; j < len; j++)
{
if (j+i+ >= len) break;
else
{
tmp.clear();
tmp.push_back(str[j]);
tmp.push_back(str[j+i+]);
v.push_back(tmp);
}
}
size = v.size();
//对结果进行判断，如果有相同的字符串，就立刻退出，不用再往下判断！
for (k = ; k < size; k++)
for (l = k+; l < size; l++)
{
if (v[k] == v[l])
{
flag1 = true;
break;
}
}
if (flag1)
{
cout << str << " is NOT surprising." << endl;
flag2 = true;
break;
}
}
if (!flag2)
cout << str << " is surprising." << endl;
}
} system("pause");
}
vector知识:http://blog.163.com/lee_020/blog/static/12475560201242152530509/