hihocoder 1251 Today is a Rainy Day 六位六进制数+dp+BFS

　　题目链接：https://vjudge.net/contest/162845#problem/C

　　题目描述：给你两个只由1~6构成且长度相等的字符串，你的目标是使第二个字符串变成第一个字符串，只允许有两种操作：1.把某一个数字变成任意数字。2.把某一种数字变成任意数字。问最小步数

　　解题思路：一开始我想这两个字符都不超过110，可不可以直接BFS，事实证明当跑到第四个结果时就卡住了，时间复杂度太高，所以需要做一些预处理。然后就弃了........后来看了题解，简直神了。首先把一类数学变成另一类数字变动的字符肯定比操作一变得数字多，所以我们预处理操作二，首先创建一个六位的六进制数组记录映射， s[i]表示将i映射成s[i]这个数字，这样一共是6^6大约是50000种映射。用一个BFS就好，然后我们再处理单个字符， dp[i]表示：当六进制表示的数字为i时所走的最小步数。有好多坑啊

　　题目代码：这就很伤了，我改了好多遍还是WA，所以现在贴上TIMELIMITE的代码

#include <cstring>  
#include <algorithm>  
#include <iostream>  
#include <cstdio>  
#include <cmath>  
#include <string>  
#include <vector>  
#include <queue>  
#include <ctime>  
#include <cstdlib>  
#define For(x,a,b,c) for (int x = a; x <= b; x += c)  
#define Ffor(x,a,b,c) for (int x = a; x >= b; x -= c)  
#define cls(x,a) memset(x,a,sizeof(x))  
using namespace std;  
typedef long long ll;  
  
const int MAX_N = 50000 + 8;  
  
const int INF = 0x3f3f3f3f;  
const ll MOD = 1e12;  
  
char a[200],b[200];  
  
int dp[MAX_N];  
int f[10][10];  
int ct[10];  
int getId(int s[]){  
    int x = 0;  
    for (int i = 0 ;i < 6 ;i ++)  
        x = x * 6 + s[i];  
    return x;  
}  
  
void get_R(int x,int s[]){  
    for (int i = 5;i >= 0;i --){  
        s[i] = x % 6;  
        x /= 6;  
    }  
}  
  
void init(){  
    cls(dp,0x3f);  
    queue<int> que;  
    int c[10];  
  
    for (int i = 0 ; i < 6;i ++)  
        c[i] = i;  
    int s = getId(c);  
    que.push(s);  
  
    dp[s] = 0;  
  
    int tmp[10];  
    while(!que.empty()){  
        s = que.front();  
        que.pop();  
    //  cout << x++ << endl;  
        get_R(s,c);  
        for (int i = 0;i < 6 ;i ++)  
            for (int j = 0 ;j < 6 ;j ++){  
                memcpy(tmp,c,sizeof(tmp));  
                for (int k = 0 ; k < 6 ; k ++)  
                    if (tmp[k] == i)  
                        tmp[k] = j;  
                int u = getId(tmp);  
                if (dp[u] > dp[s] + 1){  
                    dp[u] = dp[s] + 1;  
                    que.push(u);  
                }  
            }  
    }  
}  
  
void solve(){  
    int len = strlen(a);  
    cls(ct,0);  
    cls(f,0);  
    for (int i = 0 ;i < len; i ++){  
        ct[b[i]-'1']++;  
        f[b[i]-'1'][a[i]-'1']++;  
    }  
    int mx = len;  
    int t[10];  
    for (int i = 0 ;i < MAX_N;i ++){  
        int sum = dp[i];  
        get_R(i,t);  
        for (int j = 0;j < 6;j ++){  
            sum += ct[j] - f[j][t[j]];  
        }  
        mx = min(mx,sum);  
    }  
    cout << mx << endl;  
}  
      
int main(){  
    ios::sync_with_stdio(false);  
    //freopen("1.in","r",stdin);  
    init();  
    while(cin >> a >> b){  
        solve();          
    }  
    return 0;  
}

View Code

　　思考：首先是不够熟练，还有就是这个六位六进制的思路根本想不到啊，多做题就好了。