POJ 3096 Surprising Strings(STL map string set vector)

题意：给定一个字符串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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <map>
 7 #include <algorithm>
 8 #define LL __int64
 9 const int maxn = 1e3 + 100;
10 using namespace std;
11 
12 int main()
13 {
14     int t, n, sum, v;
15     char s[200];
16     while(~scanf("%d", &t))
17     {
18          while(t--)
19         {
20             cin>>n;
21             sum = 0;
22             map<string, int>m1, m2;
23             map<string, int>::iterator it;
24             while(n--)
25             {
26                 scanf("%s%d", s, &v);
27                 if(m1[s]==0) m1[s] = v;
28                 else if(m2[s]==0)
29                 {
30                     m2[s] = v;
31                     if(m2[s]>m1[s])
32                     {
33                         int tmp = m1[s];
34                         m1[s] = m2[s];
35                         m2[s] = tmp;
36                     }
37                 }
38                 else
39                 {
40                     m2[s] = m2[s]>v?m2[s]:v;
41                     if(m2[s]>m1[s])
42                     {
43                         int tmp = m1[s];
44                         m1[s] = m2[s];
45                         m2[s] = tmp;
46                     }
47                 }
48             }
49             for(it = m1.begin(); it != m1.end(); it++)
50             sum += it->second;
51             for(it = m2.begin(); it != m2.end(); it++)
52             sum += it->second;
53             cout<<sum<<endl;
54         }
55     }
56     return 0;
57 }

 1 /*STL<map>标记*/
 2  
 3  //Memory Time 
 4  //212K   16MS 
 5  
 6  #include<iostream>
 7  #include<string>
 8  #include<map>
 9  using namespace std;
10  
11  int main(void)
12  {
13      char s[80];
14      while(cin>>s && s[0]!='*')
15      {
16          int len=strlen(s);
17          if(len<=2)  //长度小于等于2的串必定是surprising String
18          {
19              cout<<s<<" is surprising."<<endl;
20              continue;
21          }
22  
23          bool mark=true;  //标记s是否为Surprising String
24          for(int d=0;d<=len-2;d++)  //d为当前所选取的两个字母之间的距离，d(max)=len-2
25          {
26              map<string,bool>flag;
27  
28              bool sign=true;  //标记D-pairs字母对是不是D-unique
29              for(int i=0;i<=len-d-2;i++)  //i为所选取的两个字母中第一个字母的下标
30              {
31                  char pair[3]={s[i],s[i+d+1],''};  //构成D-pairs字母对
32                  
33                  if(!flag[ pair ])
34                      flag[ pair ]=true;
35                  else
36                  {
37                      sign=false;  //存在相同的D-pairs,该字母对不是D-unique
38                      break;
39                  }
40              }
41              if(!sign)
42              {
43                  mark=false;  //存在非D-unique，s不是Surprising String
44                  break;
45              }
46          }
47          if(mark)
48              cout<<s<<" is surprising."<<endl;
49          else
50              cout<<s<<" is NOT surprising."<<endl;
51      }
52      return 0;
53  }

 1 poj 2240 
 2 不是我写的代码，贴上是为了参考跌代器
 3  #include<iostream>
 4  #include<cstdio>
 5  #include<cstring>
 6  #include<map>
 7  using namespace std;
 8  struct node
 9  {
10      int a,b;
11      double v;
12  } g[3500];
13  int main()
14  {
15      int m,n,i,j,num=0;
16      double v,dis[3500];
17      char money[10000],moneyt[10000];
18      while(cin>>n&&n)
19      {
20          num++,n++;
21          map<string,int>mapp;
22          map<string,int>::iterator iter; //迭代器
23          for(i=1; i<n; i++)
24          {
25              cin>>money;
26              mapp.insert(pair<string,int>(money,i));//插入
27          }
28          cin>>m;
29          for(i=0; i<m; i++)
30          {
31              scanf("%s %lf %s",money,&v,moneyt);
32              iter=mapp.find(money);
33              g[i].a=iter->second;
34              g[i].v=v;
35              iter=mapp.find(moneyt);
36              g[i].b=iter->second;
37          }
38          memset(dis,0,sizeof(dis));
39          dis[1]=1;
40          for(i=2; i<n; i++)
41              for(j=0; j<m; j++)
42                  if(dis[g[j].b]<dis[g[j].a]*g[j].v)
43                      dis[g[j].b]=dis[g[j].a]*g[j].v;
44          int flag=0;
45          for(j=0; j<m; j++)
46              if(dis[g[j].b]<dis[g[j].a]*g[j].v)
47                  flag=1;
48          printf("Case %d: ",num);
49          if(flag)
50              printf("Yes
");
51          else
52              printf("No
");
53          }
54      return 0;
55  }
56  
57

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的函数

map相关博客：http://www.uml.org.cn/c++/200912111.asp

http://blog.163.com/sd_2618/blog/static/85162685201032922624439/

C++ stl Multimap 和C++ stl map 很相似，但是MultiMap允许重复的元素。

Multimap应用举例：

 1 //multimap允许重复的键值插入容器
 2 //        **********************************************************    
 3 //        * pair只包含一对数值:pair<int,char>                       *
 4 //        * map是一个集合类型，永远保持排好序的，                   *
 5 //  pair  * map每一个成员就是一个pair,例如：map<int,char>           *
 6 //        * map的insert()可以把一个pair对象作为map的参数,例如map<p> *
 7 //        ***********************************************************
 8 #pragma warning(disable:4786)
 9 #include<map>
10 #include<iostream>
11 using namespace std;
12 int main(void)
13 {
14  multimap<int,char*> m;
15  //multimap的插入只能用insert()不能用数组
16  m.insert(pair<int,char*>(1,"apple"));
17     m.insert(pair<int,char*>(1,"pear"));//apple和pear的价钱完全有可能是一样的
18  m.insert(pair<int,char*>(2,"banana"));
19  //multimap的遍历只能用迭代器方式不能用数组
20  cout<<"***************************************"<<endl;
21  multimap<int,char*>::iterator i,iend;
22  iend=m.end();
23  for(i=m.begin();i!=iend;i++)
24  {
25   cout<<(*i).second<<"的价钱是"
26    <<(*i).first<<"元/斤n";
27  }
28  cout<<"***************************************"<<endl;
29     //元素的反相遍历
30  multimap<int,char*>::reverse_iterator j,jend;
31  jend=m.rend();
32  for(j=m.rbegin();j!=jend;j++)
33  {
34   cout<<(*j).second<<"的价钱是"
35    <<(*j).first<<"元/斤n";
36  }
37  cout<<"***************************************"<<endl;
38  //元素的搜索find(),pair<iterator,iterator>equal_range(const key_type &k)const
39     //和multiset的用法一样
40  multimap<int,char*>::iterator s;
41  s=m.find(1);//find()只要找到一个就行了，然后立即返回。
42  cout<<(*s).second<<"    "
43   <<(*s).first<<endl;
44  cout<<"键值等于1的元素个数是："<<m.count(1)<<endl;
45  cout<<"***************************************"<<endl;
46  //删除 erase(),clear()
47  m.erase(1);
48     for(i=m.begin();i!=iend;i++)
49  {
50   cout<<(*i).second<<"的价钱是"
51    <<(*i).first<<"元/斤n";
52  }
53     return 0;
54 }

string

转载自：http://blog.csdn.net/chen_zhipeng/article/details/7883120

 1 #include <iostream>   
 2  #include <string>   
 3  using namespace std;  
 4    
 5  string data;  
 6    
 7  bool solve(){  
 8   if(data.size()<3)  
 9    return true;  
10   int i,j;  
11   for(int cnt=1;cnt<data.size();cnt++){  
12    for(i=0;i+cnt<data.size();i++){  
13     for(j=i+1;j+cnt<data.size();j++){  
14      if(data[i]==data[j] && data[i+cnt]==data[j+cnt])  
15       return false;  
16     }  
17    }  
18   }  
19   return true;  
20  }  
21    
22  int main(){  
23   while(cin>>data,data!="*"){  
24    if(solve())  
25     cout<<data<<" is surprising."<<endl;  
26    else  
27     cout<<data<<" is NOT surprising."<<endl;  
28   }  
29   return 0;  
30  }  
31

set

 1 #include<iostream>
 2 #include<set>
 3 #include<string>
 4 using namespace std;
 5 int main()
 6 {
 7  set<string> check;
 8  string str;
 9  string temp;
10  int i,j;
11  while(cin>>str && str != "*")
12  {
13   bool flag = false;
14   for(i = 1;i <= str.length() - 1; i++)
15   {
16    check.clear();
17    for(j = 0;j <= str.length() -1 - i;j++)
18    {
19     temp = "";
20     temp = str.substr(j,1) + str.substr(j + i,1);//string 的用法，分别从j开始截取1个字符
21     //和从j+i开始截取1个字符 并连接起来
22     if(check.count(temp) != 0)
23     {
24      flag = true;
25      break;
26     }
27     check.insert(temp);
28    }
29    if(flag == true)
30    break;
31   }
32   if(flag == false)
33   cout<<str<<" is surprising."<<endl;
34   else
35   cout<<str<<" is NOT surprising."<<endl;
36  }
37 }

vector

转自：http://blog.csdn.net/yzl_rex/article/details/7647532

 1 //这题的测试数据很水，以为下面的做法会超时的！呵呵！ 题意：在一个字符串中，给出一些字符间的距离，然后
 2 //让你根据这距离再重新组成字符串，检查是否有相同的字符串存在！ 
 3 #include <iostream>
 4 #include <string>
 5 #include <vector>
 6 using namespace std;
 7 
 8 vector<string> v;
 9 
10 int main()
11 {
12     string str, tmp;
13     int i, len, d, j, size, k, l;
14     bool flag1, flag2;
15     while (cin >> str)
16     {
17           if(str == "*")  break;
18           len = str.length();
19           flag2 = false;
20           if (len == 1)
21              cout << str << " is surprising." << endl;
22           else
23           {
24               d = len - 2;//字符的距离范围 
25               for (i = 0; i <= d; i++)//对每一种的距离暴力 
26               {
27                   v.clear();
28                   flag1 = false;
29                  for (j = 0; j < len; j++)
30                  {
31                      if (j+i+1 >= len)  break;
32                      else
33                      {
34                          tmp.clear();
35                          tmp.push_back(str[j]);
36                          tmp.push_back(str[j+i+1]);
37                          v.push_back(tmp);
38                      }
39                  }
40                  size = v.size();
41                  //对结果进行判断，如果有相同的字符串，就立刻退出，不用再往下判断！ 
42                  for (k = 0; k < size; k++)
43                     for (l = k+1; l < size; l++)
44                      {
45                          if (v[k] == v[l])
46                          {
47                              flag1 = true;
48                              break;
49                          }
50                      }
51                  if (flag1)
52                  {
53                      cout << str << " is NOT surprising." << endl;
54                      flag2 = true;
55                      break;
56                  }
57               }
58               if (!flag2)
59                  cout << str << " is surprising." << endl;
60           }
61     }
62     
63     system("pause");
64 }

vector知识:http://blog.163.com/lee_020/blog/static/12475560201242152530509/

http://blog.csdn.net/phoebin/article/details/3864590

http://blog.sina.com.cn/s/blog_9f1c0931010180cy.html