首页 > 代码库 > hihocoder1251 Today Is a Rainy Day（暴力）

hihocoder1251 Today Is a Rainy Day（暴力）

2024-08-19 13:20:37   219人阅读

题意：

给你两个长度不超过110的数字串，只有1-6，让你把下面的串通过最少的操作变为上面的串

操作1：改变一个位置的数字

操作2：选取1-6其中的一个数字，让串中所有等于这个数字的数字全部变为一个其他的数字

思路：

当时做的时候一直在考虑怎么解决操作2的次序问题（如第四组样例，需要转换7次）

最后也是没能很好的实现，补题时原来是用bfs完成的这个操作

如果当前是123456的话不需要改变，也就是需要0次

然后将他所有能到的下一个串赋为1，再下一个赋为2。。。。一直到全部有值

这样每次暴力六位六进制（46656）来枚举操作2的所有结果，然后再加上操作1的次数就可以了

/* ***********************************************
Author        :devil
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <time.h>
#include <cmath>
#include <stdlib.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ou(a) printf("%d\n",a)
#define pb push_back
#define mkp make_pair
template<class T>inline void rd(T &x)
{
    char c=getchar();
    x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))
    {
        x=x*10+c-‘0‘;
        c=getchar();
    }
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=46656;
char a[111],b[111];
int dp[N],g[6],eg[6][6],c[6],t[6];
int idx(int c[])
{
    int ret=0;
    for(int i=0;i<6;i++) ret=ret*6+c[i];
    return ret;
}
void ridx(int s,int c[])
{
    for(int i=5;i>=0;i--)
    {
        c[i]=s%6;
        s/=6;
    }
}
void init()
{
    for(int i=0;i<6;i++) c[i]=i;
    int s=idx(c);
    memset(dp,inf,sizeof(dp));
    dp[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        s=q.front();
        q.pop();
        ridx(s,c);
        for(int i=0;i<6;i++)
            for(int j=0;j<6;j++)
            {
                memcpy(t,c,sizeof(t));
                for(int k=0;k<6;k++)
                    if(t[k]==i)
                        t[k]=j;
                int v=idx(t);
                if(dp[v]>dp[s]+1)
                {
                    dp[v]=dp[s]+1;
                    q.push(v);
                }
            }
    }
}
int main()
{
#ifndef ONLINE_JUDGE
IN
#endif
    init();
    while(~scanf("%s%s",a,b))
    {
        memset(g,0,sizeof(g));
        memset(eg,0,sizeof(eg));
        int n=strlen(a);
        for(int i=0;i<n;i++)
        {
            int u=b[i]-‘1‘,v=a[i]-‘1‘;
            g[u]++;
            eg[u][v]++;
        }
        int ans=inf;
        for(int s=0;s<N;s++)
        {
            ridx(s,t);
            int tmp=dp[s];
            for(int i=0;i<6;i++) tmp+=g[i]-eg[i][t[i]];
            ans=min(ans,tmp);
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

hihocoder1251 Today Is a Rainy Day（暴力）


联系
我们