【图灵杯 J】简单的变位词

Description

变位词是指改变某个词的字母顺序后构成的新词。蔡老板最近沉迷研究变位词并给你扔了一道题：

给你一些单词，让你把里面的变位词分组找出来。互为变位词的归为一组，最后输出含有变位词最多的前五组。如果有组数相同的按照字典序输出。

Input

输入包含由小写字母组成的单词，用换行分割，被EOF终止。 输入数据不超过30000个单词。

Output

输出五组包含单词数量最多的变位词，如果少于五组，输出全部。对每组输出，写出它的大小和成员词，成员词按字典序排序用空格分隔，每组输出之间用换行分隔，相同词只输出一次，但算个数。

Sample Input

neuq

tea

bate

beat

caret

trace

nueq

carte

cater

crate

abet

ate

eat

beta

eta

signal

Sample Output

Group of size 5: caret carte cater crate trace .

Group of size 4: abet bate beat beta .

Group of size 4: ate eat eta tea .

Group of size 2: neuq nueq .

Group of size 1: signal .

【题目链接】:http://oj.acmclub.cn/problem.php?cid=1162&pid=9

【题意】

【题解】



输入的每个单词,将它复印一份;

复印的那一份把它sort(s.begin(),s.end())处理;

这样就能把同一类的归到一起了;

dic< string,vector < string >>强搞就可以了;

然后把每一个出现过的单词(排序处理过后的单个字符)都记录一下;(去重后)

然后按照dic< string >那个vector的大小降序排;

(记录原来字符串的id和出现次数就好);

然后按照题目所说的字典序去搞;

这里出现次数一样的情况,字典序小的先,我是把要输出的东西都弄成字符串(string类),然后再强行排个序..

去重就不用说了,很简单的

(不一定是取前5个字符,可能第5大的字符有很多个,远远超过了5个呢?或者第3大的字符就超过5个了..你得在其中找字典序最小的)



【Number Of WA】



1



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 3e4+100;

struct abc{

    int id,num;

};

string s,ts[N],b[N];

map <string,vector <string> > dic;

int n;

abc a[N];

int main(){

    //Open();

    Close();

    while (cin >> s){

        string temp = s;

        sort(temp.begin(),temp.end());

        if (dic[temp].empty()) ts[++n] = temp;

        dic[temp].pb(s);

    }

    rep1(i,1,n){

        a[i].num = dic[ts[i]].size();

        a[i].id = i;

    }

    sort(a+1,a+1+n,[&] (abc a,abc b){return a.num>b.num;});

    int num = 0;

    rep1(i,1,n){

        int j = i;

        while (j+1<=n && a[j+1].num==a[i].num) j++;

        rep1(ii,1,j-i+1){

            b[ii]="";

            string temp = ts[a[i+ii-1].id];

            sort(dic[temp].begin(),dic[temp].end());

            rep1(j,0,a[i+ii-1].num-1){

                int k = j;

                while (k+1<=a[i+ii-1].num-1 && dic[temp][k+1]==dic[temp][j]){

                    k++;

                }

                b[ii]+=dic[temp][j];

                b[ii]+=' ';

                j = k;

            }

            b[ii]+='.';

        }

        sort(b+1,b+1+(j-i+1));

        rep1(ii,1,j-i+1){

            cout <<"Group of size "<<a[i].num<<": "<<b[ii]<<endl;

            num++;

            if (num==5) return 0;

        }

        i = j;

    }

    return 0;

}