微软夏令营编程测验第二题MSFT

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Little Ho has a string S consisting of only lowercase letters.

All letters in S are distinct except for ‘m’, ‘s’, ‘f’ and ‘t’. Which means the four magical letters ‘m’, ‘s’, ‘f’ and ‘t’ can show up at most twice, while other letters can show up at most once.

Now little Ho wants to change S into T by swapping a pair of letters in S.

He wants to know the minimum amounts of such swaps he needs to do so.

输入
The first line contains an integer N, indicating the number of test cases.

Each test case contains two lines. The first contains the string S and the second contains the string T.

It is guaranteed that changing S into T is possible.

For 30% of the data, 1 ≤ length(S) == length(T) ≤ 10.

For 100% of the data, 1 ≤ N ≤ 10, 1 ≤ length(S) == length(T) ≤ 30.

输出
For each test case output the minimum amounts of swaps needed to turn S into T on a separate line.

样例输入
2
msra
asmr
fsmambfcs
mfsmbfcsa
样例输出
2
6

思路因为msft最多出现两次，所以讲msft转换为其他字符用以区分两个相同的字符，如果有两个m则用‘0’和‘1’代替，两个s用‘2’和‘3’代替，依次类推，如果只出现一次则不转换，之后再交换两个字符的位置。这样最多产生16种转换之后的字符，之后便可以按照没有重复字符出现的方式进行逐一匹配，计算出这n中情况中最小转换次数，输出即可。

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <string>
#include <limits.h>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stdio.h>  
using namespace std;
int res = 0;
void my_swap(char &a, char &b)
{
    char temp;
    temp = a;
    a = b;
    b = temp;
}

int cal_sum(vector<string> vec, string b)
{
    int out=INT_MAX;
    for (auto a : vec){
        int res = 0;
        string temp = b;//每次要将temp的值恢复到初始的样子
        for (int i = 0; i < a.size(); ++i)
        {
            if (a[i] != temp[i]){
                auto pos = temp.find(a[i]);
                my_swap(temp[i], temp[pos]);
                ++res;
            }
        }
        if (res <= out)
            out = res;
    }
    return out;
}
vector<string> change_save(string &input,char par,int i)//字符转化
{
    vector<string> vec;
    auto pos1 = input.find(par, 0);
    if (pos1 != string::npos){
        auto pos2 = input.find(par, pos1 + 1);
        if (pos2 != string::npos){
            input[pos1] = '0' + i;
            input[pos2] = '1' + i;
            vec.push_back(input);
            my_swap(input[pos1], input[pos2]);
            vec.push_back(input);
        }
        else
            vec.push_back(input);
    }
    else{
        vec.push_back(input);
    }
    return vec;
}

void change_save_T(string &input,char par, int i)
{
    auto pos1 = input.find(par, 0);
    if (pos1 != string::npos){
        auto pos2 = input.find(par, pos1 + 1);
        if (pos2 != string::npos){
            input[pos1] = '0' + i;
            input[pos2] = '1' + i;
        }
    }
}
int main()
{
    vector<int> out;
    int n;
    cin >> n;
    int cnt = n;
    vector<string> S, T;
    while (cnt--){
        string temp1, temp2;
        cin >> temp1;
        cin >> temp2;
        S.push_back(temp1);
        T.push_back(temp2);
    }
    for (int beg = 0; beg < S.size(); ++beg){
            vector<string> vec;
            vector<string> fin;
            //字符串处理转化
            vec=change_save(S[beg], 'm', 0);
            for (auto c : vec){
                auto temp = change_save(c, 's', 2);
                for (auto b : temp)
                    fin.push_back(b);
            }
            vec = fin;
            fin.clear();
            for (auto c : vec){
                auto temp = change_save(c, 'f', 4);
                for (auto b : temp)
                    fin.push_back(b);
            }
            vec = fin;
            fin.clear();
            for (auto c : vec){
                auto temp = change_save(c, 't', 6);
                for (auto b : temp)
                    fin.push_back(b);
            }

            change_save_T(T[beg],'m', 0);
            change_save_T(T[beg],'s', 2);
            change_save_T(T[beg],'f', 4);
            change_save_T(T[beg],'t', 6);
            int num_sum=cal_sum(fin, T[beg]);
            out.push_back(num_sum);
    }
    for (auto c : out)
        cout << c << endl;
    return 0;
}