不知道为什么连最小步数都会算错,苣蒻求助!
查看原帖
不知道为什么连最小步数都会算错,苣蒻求助!
648772
Liyuqiao11楼主2023/9/24 19:53
#include<bits/stdc++.h>
using namespace std;
const int N = 50,md=1e9+7,B=131;
#define int long long
int n,sta,stb,stc,eda,edb,edc,ans=1e9;
map<int,int> mp;
void dfs(int x,int y,int z,int d){
    if(x==eda&&y==edb&&z==edc){
        ans=min(ans,d);
        return;
    }
    if(x<y||y==0){
        int num=1;
        while(num<=x){
            num=num*2;
        }
        num=num/2;
        if(mp[((x-num)*B*B+(y+num)*B+z)%md]>d+1||mp[((x-num)*B*B+(y+num)*B+z)%md]==0){
            mp[((x-num)*B*B+(y+num)*B+z)%md]=d+1;
            dfs(x-num,y+num,z,d+1);
        }
    }
    if(x<z||z==0){
        int num=1;
        while(num<=x){
            num=num*2;
        }
        num=num/2;
        if(mp[((x-num)*B*B+y*B+z+num)%md]>d+1||mp[((x-num)*B*B+y*B+z+num)%md]==0){
            mp[((x-num)*B*B+y*B+z+num)%md]=d+1;
            dfs(x-num,y,z+num,d+1);
        }
    }
    if(y<z||z==0){
        int num=1;
        while(num<=y){
            num=num*2;
        }
        num=num/2;
        if(mp[(x*B*B+(y-num)*B+z+num)%md]>d+1||mp[(x*B*B+(y-num)*B+z+num)%md]==0){
            mp[(x*B*B+(y-num)*B+z+num)%md]=d+1;
            dfs(x,y-num,z+num,d+1);
        }
    }
    if(y<x||x==0){
        int num=1;
        while(num<=y){
            num=num*2;
        }
        num=num/2;
        if(mp[((x+num)*B*B+(y-num)*B+z)%md]>d+1||mp[((x+num)*B*B+(y-num)*B+z)%md]==0){
            mp[((x+num)*B*B+(y-num)*B+z)%md]=d+1;
            dfs(x+num,y-num,z,d+1);
        }
    }
    if(z<x||x==0){
        int num=1;
        while(num<=z){
            num=num*2;
        }
        num=num/2;
        if(mp[((x+num)*B*B+y*B+z-num)%md]>d+1||mp[((x+num)*B*B+y*B+z-num)%md]==0){
            mp[((x+num)*B*B+y*B+z-num)%md]=d+1;
            dfs(x+num,y,z-num,d+1);
        }
    }
    if(z<y||y==0){
        int num=1;
        while(num<=z){
            num=num*2;
        }
        num=num/2;
        if(mp[(x*B*B+(y+num)*B+z-num)%md]>d+1||mp[(x*B*B+(y+num)*B+z-num)%md]==0){
            mp[(x*B*B+(y+num)*B+z-num)%md]=d+1;
            dfs(x,y+num,z-num,d+1);
        }
    }
}
signed main(){
    cin>>n;
    int x;
    cin>>x;
    for(int i=1;i<=x;i++){
        int y;
        cin>>y;
        sta=sta+pow(2,y);
    }
    cin>>x;
    for(int i=1;i<=x;i++){
        int y;
        cin>>y;
        stb=stb+pow(2,y);
    }
    cin>>x;
    for(int i=1;i<=x;i++){
        int y;
        cin>>y;
        stc=stc+pow(2,y);
    }
    cin>>x;
    for(int i=1;i<=x;i++){
        int y;
        cin>>y;
        eda=eda+pow(2,y);
    }
    cin>>x;
    for(int i=1;i<=x;i++){
        int y;
        cin>>y;
        edb=edb+pow(2,y);
    }
    cin>>x;
    for(int i=1;i<=x;i++){
        int y;
        cin>>y;
        edc=edc+pow(2,y);
    }
    dfs(sta,stb,stc,1);
    cout<<ans<<endl;
    return 0;
}
2023/9/24 19:53
加载中...