J-luggage lock of ICPC Shenyang station in 2021 regional games (simple code)

The question ： One will be given 4 Turn the lock of position to another four position lock , You can turn multiple consecutive locks at a time +1 perhaps -1, Ask how many times you can turn it into a target lock

Input

6
1234 2345
1234 0123
1234 2267
1234 3401
1234 1344
1234 2468

Output

1
1
4
5
1
4

General idea ：

What I do with this question is to divide it into two questions ：

1. One is to give an array of positive numbers , such as 4,5,6,2, You can drop a continuous interval at a time , How many times at least .

It's harder , If there is a negative number , What if it can rise and fall continuously ：4,-2,5 The answer is 11.

2. And then calculate 4 Bit difference , such as 4562 To 5671 The difference is -1,-1,-1,1, As long as the above problems are solved , Bring in this array to get the answer .

however 4562 To 5671 just so so 9,-1,-1,1, Each person can add or subtract 2^4 Second case , Search lists this 16 Array to find the minimum answer .

Specific solution ：

The first 1 A question ：

With the original title ：[NOIP2018 Improvement group ] Lay the road - Luogu

For arrays that are all positive numbers, it's simple ： The answer is sum

for(int i=1;i<=n;i++)
    if(a[i-1]<a[i])
        sum+=a[i]-a[i-1];

For arrays with negative numbers , You can add one more between positive and negative numbers 0, A negative number becomes its absolute value

1,2,-1,-2,3  ->  1,2,0,1,2,0,3

Of course, this is just an easy way to understand , add 0 too troublesome , It can be calculated directly , In fact, it means adding 0 Calculation after ：

void solve(){
    int sum=0;
    for(int i=1;i<=4;i++){
        if(ans[i-1]*ans[i]<0) sum+=abs(ans[i]);      //ans It's a length of 5 Array of ,ans[0]=0, Back 4 One is effective 
        else if(abs(ans[i])>abs(ans[i-1])) sum+=abs(ans[i])-abs(ans[i-1]);
    }
    minn=min(minn,sum);
}

The first 2 A question ：

It's not a problem , But point it out ans Array Is the difference array of input data

If you know this bit ans[i]<0, Then again +10, If ans[i]>=0, Then again -10, Enumerate 16 Array of

Because the first 1 Problem time complexity O（n） It's solved ,3^4 Enumeration of is also ok ：

void dfs(int d){
    if(d==5){
        solve();        // Array ans Produce a result 
        return;
    }
    ans[d]=x[d-1]-y[d-1];       // Take difference 
    dfs(d+1);
    ans[d]=x[d-1]-y[d-1]+10;        // This bit +10
    dfs(d+1);
    ans[d]=x[d-1]-y[d-1]-10;        // This bit -10
    dfs(d+1);
}

Code ：

#include<bits/stdc++.h>
using namespace std;
#define fo(a) for(int i=0;i<a;i++)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define M 1000005
int T,minn;
string s;
vector<int>x,y;
vector<int>ans(5);
void solve(){
    int sum=0;
    for(int i=1;i<=4;i++){
        if(ans[i-1]*ans[i]<0) sum+=abs(ans[i]);
        else if(abs(ans[i])>abs(ans[i-1])) sum+=abs(ans[i])-abs(ans[i-1]);
    }
    minn=min(minn,sum);
}
void dfs(int d){
    if(d==5){
        solve();
        return;
    }
    ans[d]=x[d-1]-y[d-1];       // Take difference 
    dfs(d+1);
    ans[d]=x[d-1]-y[d-1]+10;        // This bit +10
    dfs(d+1);
    ans[d]=x[d-1]-y[d-1]-10;        // This bit -10
    dfs(d+1);
}
signed main(){
    cin>>T;
    while(T--){
        minn=1e9;
        x.clear();y.clear();
        cin>>s;
        fo(4) x.push_back(s[i]-'0');
        cin>>s;
        fo(4) y.push_back(s[i]-'0');
        dfs(1);
        cout<<minn<<'\n';
    }
    return 0;
}