題目連結 http://zerojudge.tw/ShowProblem?problemid=b050。
直接用 C++ STL algorithm 裡的 set_union、set_intersection、set_difference、includes來寫。
程式碼:
#include <iterator>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int n;
int count = 0;
while( cin >> n )
{
count = count + 1;
if( n == 0 ) break;
vector<char> *dataSet = new vector<char>[n];
for( int i = 0; i < n; i++ )
{
string input;
cin >> input;
for( unsigned j = 0; j < input.length(); j++ )
input[j] = tolower(input[j]);
for( unsigned j = 0; j < input.length(); j++ )
dataSet[i].push_back(input[j]);
sort(dataSet[i].begin(), dataSet[i].end());
}
cout << "Test Case " << count << ":\n";
for( int i = 0; i < n; i++ )
{
char name = 'A' + i;
cout << name << ": {";
copy(dataSet[i].begin(), dataSet[i].end(), ostream_iterator<char>(cout, ""));
cout << "}" << endl;
}
// Union and intersection
for( int i = 0; i < n; i++ )
{
char setName = 'A' + i;
for( int j = i + 1; j < n; j++ )
{
char name = 'A' + j;
vector<char> setUnion( dataSet[i].size() + dataSet[j].size() );
vector<char>::iterator iter = set_union( dataSet[i].begin(), dataSet[i].end(),
dataSet[j].begin(), dataSet[j].end(), setUnion.begin());
cout << setName << "+" << name << ": {";
copy(setUnion.begin(), iter, ostream_iterator<char>(cout, ""));
cout << "}" << endl;
vector<char> setIntersection( min(dataSet[i].size(), dataSet[j].size()) );
iter = set_intersection( dataSet[i].begin(), dataSet[i].end(),
dataSet[j].begin(), dataSet[j].end(), setIntersection.begin());
cout << setName << "*" << name << ": {";
copy(setIntersection.begin(), iter, ostream_iterator<char>(cout, ""));
cout << "}" << endl;
}
}
for( int i = 0; i < n; i++ )
{
char setName = 'A' + i;
for( int j = 0; j < n; j++ )
{
char name = 'A' + j;
if( i != j )
{
vector<char> difference( max(dataSet[i].size(), dataSet[j].size()) );
vector<char>::iterator iter = set_difference( dataSet[i].begin(), dataSet[i].end(),
dataSet[j].begin(), dataSet[j].end(), difference.begin());
cout << setName << "-" << name << ": {";
copy(difference.begin(), iter, ostream_iterator<char>(cout, ""));
cout << "}" << endl;
}
}
}
for( int i = 0; i < n; i++ )
{
char setName = 'A' + i;
for( int j = 0; j < n; j++ )
{
char name = 'A' + j;
if( i != j )
{
if(includes( dataSet[i].begin(), dataSet[i].end(),
dataSet[j].begin(), dataSet[j].end()) == true)
{
cout << setName << " contains " << name << endl;
}
else
{
cout << setName << " does not contain " << name << endl;
}
}
}
}
delete [] dataSet;
}
}
沒有留言:
張貼留言