容器之set使用

D - Problem D
Time Limit:2000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu

Description

With water from the stream Galadriel filled the basin to the brim, and breathed on it, and when the water was still again she spoke. 'Here is the Mirror of Galadriel,' she said. 'I have brought you here so that you may look in it, if you will. For this is what your folk would call magic, I believe; though I do not understand clearly what they mean; and they seem also to use the same word of the deceits of the Enemy. But this, if you will, is the magic of Galadriel. Did you not say that you wished to see Elf-magic?' - Galadriel to Frodo and Sam, describing her Mirror.
We call a string S magical if every substring of S appears in Galadriel's Mirror (under lateral inversion). In other words, a magical string is a string where every substring has its reverse in the string.
Given a string S, determine if it is magical or not.
Input (STDIN):
The first line contains T, the number of test cases. The next T lines contain a string each. 
Output (STDOUT):
For each test case, output "YES" if the string is magical, and "NO" otherwise.
Constraints:
1 <= T <= 100
1 <= |S| <= 10
S contains only lower-case characters.
Time Limit: 1s
Memory Limit: 64MB
Sample Input:
2
aba
ab
Sample Output:
YES
NO
Notes/Explanation of Sample Input:
For the first test case, the list of substrings are : a, b, ab, ba, aba. The reverse of each of these strings is present as a substring of S too.
For the second test case, the list of substring are : a, b, ab. The reverse of "ab", which is "ba" is not present as a substring of the string.

With water from the stream Galadriel filled the basin to the brim, and breathed on it, and when the water was still again she spoke. 'Here is the Mirror of Galadriel,' she said. 'I have brought you here so that you may look in it, if you will. For this is what your folk would call magic, I believe; though I do not understand clearly what they mean; and they seem also to use the same word of the deceits of the Enemy. But this, if you will, is the magic of Galadriel. Did you not say that you wished to see Elf-magic?' - Galadriel to Frodo and Sam, describing her Mirror.

We call a string S magical if every substring of S appears in Galadriel's Mirror (under lateral inversion). In other words, a magical string is a string where every substring has its reverse in the string.

Given a string S, determine if it is magical or not.

Input (STDIN):

The first line contains T, the number of test cases. The next T lines contain a string each. 

Output (STDOUT):

For each test case, output "YES" if the string is magical, and "NO" otherwise.

Constraints:

1 <= T <= 100

1 <= |S| <= 10

S contains only lower-case characters.

Sample Input:

2

aba

ab

Sample Output:

YES

NO

Notes/Explanation of Sample Input:

For the first test case, the list of substrings are : a, b, ab, ba, aba. The reverse of each of these strings is present as a substring of S too.

For the second test case, the list of substring are : a, b, ab. The reverse of "ab", which is "ba" is not present as a substring of the string.

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <cstdlib>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <cassert>
11 #include <set>
12 #include <sstream>
13 #include <map>
14 using namespace std ;
15 #ifdef DeBUG
16 #define bug assert
17 #else
18 #define bug //
19 #endif
20 #define zero {0}
21 
22 int main()
23 {
24     #ifdef DeBUG
25         freopen("C:\Users\Sky\Desktop\1.in","r",stdin);
26     #endif
27     
28     set<string>a;
29     set<string>::iterator it;
30     int T;
31     int i,j,k;
32     scanf("%d",&T);
33     while(T--)
34     {
35         string s;
36         string s1;
37         string s2;
38         int _flag=0;
39         cin>>s;
40         for(i=0;i<s.size();i++)
41         {
42             s1="";
43             for(j=i;j<s.size();j++)
44             {
45                 s1+=s[j];
46                 a.insert(s1);
47             }
48         }
49         for(it=a.begin();it!=a.end();it++)
50         {
51             s2=*it;
52             reverse(s2.begin(),s2.end());
53             if(a.count(s2)==0)
54             {
55                 printf("NO
");
56                 _flag=1;
57                 break;
58             }
59         }
60         if(_flag==0)
61         printf("YES
");
62         a.clear();
63     }
64     return 0;
65 }
View Code

小结

  1 set/multiset会根据待定的排序准则，自动将元素排序。两者不同在于前者不允许元素重复，而后者允许。
  2 1) 不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，则插入新元素
  3 2) 不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取，而且从迭代器角度来看，元素值是常数
  4 3) 元素比较动作只能用于型别相同的容器(即元素和排序准则必须相同)
  5 set模板原型：//Key为元素(键值)类型
  6 template <class Key, class Compare=less<Key>, class Alloc=STL_DEFAULT_ALLOCATOR(Key) >
  7 从原型可以看出，可以看出比较函数对象及内存分配器采用的是默认参数，因此如果未指定，它们将采用系统默认方式，
  8 另外，利用原型，可以有效地辅助分析创建对象的几种方式
  9 */
 10 #include <iostream>
 11 #include <string>
 12 #include <set>
 13 
 14 using namespace std;
 15 
 16 struct strLess
 17 {
 18    bool operator() (const char *s1, const char *s2) const
 19    {
 20     return strcmp(s1, s2) < 0;
 21    }
 22 };
 23 
 24 void printSet(set<int> s)
 25 {
 26 copy(s.begin(), s.end(), ostream_iterator<int>(cout, ", ") );
 27 
 28 // set<int>::iterator iter;
 29 // for (iter = s.begin(); iter != s.end(); iter++)
 30 //    //cout<<"set["<<iter-s.begin()<<"]="<<*iter<<", "; //Error
 31 //    cout<<*iter<<", ";
 32 cout<<endl;
 33 }
 34 
 35 void main()
 36 {
 37 //创建set对象，共5种方式，提示如果比较函数对象及内存分配器未出现，即表示采用的是系统默认方式
 38 //创建空的set对象，元素类型为int，
 39 set<int> s1; 
 40 //创建空的set对象，元素类型char*，比较函数对象(即排序准则)为自定义strLess
 41 set<const char*, strLess> s2( strLess); 
 42 //利用set对象s1,拷贝生成set对象s2
 43 set<int> s3(s1); 
 44 //用迭代区间[&first, &last)所指的元素，创建一个set对象
 45 int iArray[] = {13, 32, 19};
 46 set<int> s4(iArray, iArray + 3);
 47 //用迭代区间[&first, &last)所指的元素，及比较函数对象strLess，创建一个set对象
 48 const char* szArray[] = {"hello", "dog", "bird" };
 49 set<const char*, strLess> s5(szArray, szArray + 3, strLess() );
 50 
 51 //元素插入：
 52 //1,插入value，返回pair配对对象，可以根据.second判断是否插入成功。(提示:value不能与set容器内元素重复)
 53 //pair<iterator, bool> insert(value)
 54 //2,在pos位置之前插入value，返回新元素位置，但不一定能插入成功
 55 //iterator insert(&pos, value)
 56 //3,将迭代区间[&first, &last)内所有的元素，插入到set容器
 57 //void insert[&first, &last)
 58 cout<<"s1.insert() : "<<endl;
 59 for (int i = 0; i <5 ; i++)
 60     s1.insert(i*10);
 61 printSet(s1);
 62 
 63 cout<<"s1.insert(20).second = "<<endl;;
 64 if (s1.insert(20).second)
 65     cout<<"Insert OK!"<<endl;
 66 else
 67     cout<<"Insert Failed!"<<endl;
 68 
 69 cout<<"s1.insert(50).second = "<<endl;
 70 if (s1.insert(50).second)
 71 {cout<<"Insert OK!"<<endl; printSet(s1);}
 72 else
 73     cout<<"Insert Failed!"<<endl;
 74 
 75 cout<<"pair<set<int>::iterator::iterator, bool> p;
p = s1.insert(60);
if (p.second):"<<endl;
 76 pair<set<int>::iterator::iterator, bool> p;
 77 p = s1.insert(60);
 78 if (p.second)
 79 {cout<<"Insert OK!"<<endl; printSet(s1);}
 80 else
 81    cout<<"Insert Failed!"<<endl;
 82 
 83 //元素删除
 84 //1,size_type erase(value) 移除set容器内元素值为value的所有元素，返回移除的元素个数
 85 //2,void erase(&pos) 移除pos位置上的元素，无返回值
 86 //3,void erase(&first, &last) 移除迭代区间[&first, &last)内的元素，无返回值
 87 //4,void clear()， 移除set容器内所有元素
 88 
 89 cout<<"
s1.erase(70) = "<<endl;
 90 s1.erase(70);
 91 printSet(s1);
 92 cout<<"s1.erase(60) = "<<endl;
 93 s1.erase(60);
 94 printSet(s1);
 95 
 96 cout<<"set<int>::iterator iter = s1.begin();
s1.erase(iter) = "<<endl;
 97 set<int>::iterator iter = s1.begin();
 98 s1.erase(iter);
 99 printSet(s1);
100 
101 //元素查找
102 //count(value)返回set对象内元素值为value的元素个数
103 //iterator find(value)返回value所在位置，找不到value将返回end()
104 //lower_bound(value),upper_bound(value), equal_range(value) 略
105 cout<<"
s1.count(10) = "<<s1.count(10)<<", s1.count(80) = "<<s1.count(80)<<endl;
106 cout<<"s1.find(10) : ";
107 if (s1.find(10) != s1.end()) 
108     cout<<"OK!"<<endl;
109 else
110     cout<<"not found!"<<endl;
111 
112 cout<<"s1.find(80) : ";
113 if (s1.find(80) != s1.end()) 
114     cout<<"OK!"<<endl;
115 else
116     cout<<"not found!"<<endl;
117 
118 //其它常用函数
119 cout<<"
s1.empty()="<<s1.empty()<<", s1.size()="<<s1.size()<<endl;
120 set<int> s9;
121 s9.insert(100);
122 cout<<"s1.swap(s9) :"<<endl;
123 s1.swap(s9);
124 cout<<"s1: "<<endl;
125 printSet(s1);
126 cout<<"s9: "<<endl;
127 printSet(s9);
128 //lower_bound,upper_bound,equal_range(略)
129 }
130 
131 
132 /**////////////////i测试结果/////////////////////////
133 s1.insert() :
134 0, 10, 20, 30, 40,
135 s1.insert(20).second =
136 Insert Failed!
137 s1.insert(50).second =
138 Insert OK!
139 0, 10, 20, 30, 40, 50,
140 pair<set<int>::iterator::iterator, bool> p;
141 p = s1.insert(60);
142 if (p.second):
143 Insert OK!
144 0, 10, 20, 30, 40, 50, 60,
145 
146 s1.erase(70) =
147 0, 10, 20, 30, 40, 50, 60,
148 s1.erase(60) =
149 0, 10, 20, 30, 40, 50,
150 set<int>::iterator iter = s1.begin();
151 s1.erase(iter) =
152 10, 20, 30, 40, 50,
153 
154 s1.count(10) = 1, s1.count(80) = 0
155 s1.find(10) : OK!
156 s1.find(80) : not found!
157 
158 s1.empty()=0, s1.size()=5
159 s1.swap(s9) :
160 s1:
161 100,
162 s9:
163 10, 20, 30, 40, 50,
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Skyxj/p/3198127.html