STL

T1

P1691 有重复元素的排列问题

题目描述

设R={r1，r2，……，rn}是要进行排列的n个元素。其中元素r1，r2，……，rn可能相同。使设计一个算法，列出R的所有不同排列。

给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。

输入输出格式

输入格式：

 

第1行：元素个数n（1<=n<500）

第2行：一行字符串，待排列的n个元素

 

输出格式：

 

计算出的n个元素的所有不同排列，最后一行是排列总数。

 

输入输出样例

输入样例#1： 复制

4
aacc

输出样例#1： 复制

aacc
acac
acca
caac
caca
ccaa
6

说明

输出按字典顺序排

next_permutation的用法

#include <iostream>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
    int n,num=1;
    cin >> n;
    string s;
    cin >> s;
    sort(s.begin(),s.end());
    cout << s <<endl;
    while(next_permutation(s.begin(),s.end()))
    {
        num++;
        cout << s <<endl;
    }
    cout<<num<<endl;
    return 0;
}

T2

P2814 家谱
题目背景
现代的人对于本家族血统越来越感兴趣。

题目描述
给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

输入输出格式
输入格式：

 

输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。

 

输出格式：

 

按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。

 

输入输出样例
输入样例#1： 复制

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$
输出样例#1： 复制

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur
说明
规定每个人的名字都有且只有6个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。

 

 

此题将并查集和字符串结合在一起

因为此题目的输入格式是一个父节点+很多个子节点

所以可以采用map将父节点和子节点一一对应起来

#include <iostream>
#include<string>
#include<algorithm>
#include<map>
 
using namespace std;
map<string,string> p;
string find1(string r)
{
    string t;
    t=r;
    while(t!=p[t])
    {
        t=p[t];
    }
    return t;
}
int main()
{
    string s,flag;
    char a;
 
    while(cin >> a&&a!='$')
    {
        cin >> s;
        if(a=='#')
        {
            if(p[s]=="")
            p[s]=s;
            flag=s;
        }
        else if(a=='+')
        {
            p[s]=flag;
        }
        else
        {
            cout<<s<<" "<<find1(s)<<endl;
        }
    }
    return 0;
}