题意 : 一串数字变成另一串数字，可以单个数字转变，或者一类数字转变，问最少操作次数
分析 :
15年北京赛区的银牌题
首先有一个点需要想明白、或者猜得到
即最优的做法肯定是先做完 2 操作最后用 1 操作
2 操作单次可以改变的字符数远大于 1 操作 ( 当然这个不是证明上面的结论、只是给个灵感去猜
具体操作就是 s2 => 通过 2 操作变成中间状态 => 通过 1 操作变成 s1
对于 2 操作、与具体字符的数量无关、只和种类有关、即从一种数字变成另一种
那么就是一种映射关系、那么我们可以使用一个六位的六进制数来表示不同的状态
首先将字符集全部 -1 、即原来串是由 {1,2,3,4,5,6} 组成变成由 {0,1,2,3,4,5}组成 ( 方便进制转化 )
那么这种映射关系是什么呢？如何表示的 2 操作呢？
比如 012345 => 112345 表示将原来字符所有的 0 变成 1
012345 => 112344 表示将原来字符串所有的 0 变成 1、所有的 5 变成 4
所有对于所有的状态、可以使用 BFS 从初始状态 (012345) 开始、将它到其他状态的花费求出来
那么就可以统计出所有 2 操作能到达的状态的最小花费了、当然六进制的状态最后要用十进制存储才方便存储
最后就是像刚刚说的那样子、先枚举中间状态(6^6个最多)、然后计算出从中间状态通过 1 操作到达目标状态的花费即可
#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define scl(i) scanf("%lld", &i)
#define scll(i, j) scanf("%lld %lld", &i, &j)
#define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k)
#define scllll(i, j, k, l) scanf("%lld %lld %lld %lld", &i, &j, &k, &l)
#define scs(i) scanf("%s", i)
#define sci(i) scanf("%d", &i)
#define scd(i) scanf("%lf", &i)
#define scIl(i) scanf("%I64d", &i)
#define scii(i, j) scanf("%d %d", &i, &j)
#define scdd(i, j) scanf("%lf %lf", &i, &j)
#define scIll(i, j) scanf("%I64d %I64d", &i, &j)
#define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k)
#define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k)
#define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k)
#define sciiii(i, j, k, l) scanf("%d %d %d %d", &i, &j, &k, &l)
#define scdddd(i, j, k, l) scanf("%lf %lf %lf %lf", &i, &j, &k, &l)
#define scIllll(i, j, k, l) scanf("%I64d %I64d %I64d %I64d", &i, &j, &k, &l)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define lowbit(i) (i & (-i))
#define mem(i, j) memset(i, j, sizeof(i))
#define fir first
#define sec second
#define VI vector<int>
#define ins(i) insert(i)
#define pb(i) push_back(i)
#define pii pair<int, int>
#define VL vector<long long>
#define mk(i, j) make_pair(i, j)
#define all(i) i.begin(), i.end()
#define pll pair<long long, long long>
#define _TIME 0
#define _INPUT 0
#define _OUTPUT 0
clock_t START, END;
void __stTIME();
void __enTIME();
void __IOPUT();
using namespace std;
+ ;
;
+ ;
const int INF = 0x3f3f3f3f;
int to_ten(int c[])///将六进制转十进制
{
;
; i<; i++){
ret = ret * + c[i];
}return ret;
}
inline void to_six(int num, int c[])///十进制转六进制(存在 c 中)
{
; i>=; i--){
c[i] = num % ;
num /= ;
}
}
int Cost[mxState];///存储操作 2 的花费
][];///存储原本 s2 => s1 只通过 1 操作所用的花费
///比如 g[1][2] = 3 将 s2 的 1 变成 s1 的 2 只用 1 操作要进行 3 次
];///存储 s2 中每个数字出现的次数
char s1[maxLen], s2[maxLen];
inline void BFS()
{
] = {, , , , , };
int FirState = to_ten(c);
mem(Cost, INF);
Cost[FirState] = ;
queue<int> que;
que.push(FirState);
while(!que.empty()){
int T = que.front(); que.pop();
to_six(T, c);
; i<; i++){
; j<; j++){
];
memcpy(tmp, c, sizeof(tmp));
; k<; k++)
if(tmp[k] == i)
tmp[k] = j;
int newState = to_ten(tmp);
){
Cost[newState] = Cost[T] + ;
que.push(newState);
}
}
}
}
}
int main(void){__stTIME();__IOPUT();
BFS();
while(~scs(s1)){
scs(s2);
int len = strlen(s1);
mem(cnt, );
mem(g, );
; i<len; i++){
';
';
cnt[ch2]++;
g[ch2][ch1]++;
}
int ans = INF;
];
; i<mxState; i++){///枚举中间状态
to_six(i, c);
int cost = Cost[i];///将 s2 => 中间状态 的花费
; j<; j++)///进行操作 1 的花费计算
cost += cnt[j] - g[j][c[j]];///举个例子就好理解一点、比如 s1="001" 、s2="112"、用这个例子去模拟
ans = min(ans, cost);
}
printf("%d\n", ans);
}
__enTIME();;}
void __stTIME()
{
#if _TIME
START = clock();
#endif
}
void __enTIME()
{
#if _TIME
END = clock();
cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl;
#endif
}
void __IOPUT()
{
#if _INPUT
freopen("in.txt", "r", stdin);
#endif
#if _OUTPUT
freopen("out.txt", "w", stdout);
#endif
}