当前位置:网站首页>J-luggage lock of ICPC Shenyang station in 2021 regional games (simple code)
J-luggage lock of ICPC Shenyang station in 2021 regional games (simple code)
2022-07-03 14:22:00 【Int me】
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;
}
边栏推荐
- 泰凌冲刺科创板:拟募资13亿 国家大基金与小米长江是股东
- 中国锂电池电解液行业市场专项调研报告(2022版)
- simpleParallax. JS (create poor visual effects for website pictures)
- Redis:字符串类型数据的操作命令
- 中感微冲刺科创板:年营收2.4亿净亏1782万 拟募资6亿
- Programmable logic device software testing
- 556. 下一个更大元素 III
- FPGA test method takes mentor tool as an example
- 7-20 print 99 formula table (format output)
- JS Part III
猜你喜欢
7-8 overspeed judgment
QT learning 25 layout manager (4)
中感微冲刺科创板:年营收2.4亿净亏1782万 拟募资6亿
556. 下一个更大元素 III
QT learning 20 standard dialog box in QT (middle)
Programmable logic device software testing
Scroll detection, so that the content in the lower right corner is not displayed at the top of the page, but is displayed as the mouse slides
Message subscription and publishing
Exercise 9-1 time conversion
GRPC的四种数据流以及案例
随机推荐
etcd集群权限管理和账号密码使用
NFT新的契机,多媒体NFT聚合平台OKALEIDO即将上线
7-16 find the set of integers that meet the given conditions
Example analysis of QT learning 18 login dialog box
js 2023. String pair equal to the target string after connection
Simulated access
Exercise 9-3 plane vector addition
[clean up the extraordinary image of Disk C]
7-2 and then what time (15 minutes)
Exercise 6-2 using functions to sum special A-string sequences
Too many files with unapproved license
Redis: commandes d'action pour les données de type chaîne
QT learning 17 dialog box and its types
Leetcode (4) -- find the median of two positively ordered arrays
Why are grass-roots colleges and universities with "soil and poverty" called "Northeast small Tsinghua"?
编程语言:类型系统的本质
Solve the problem of dormitory router campus network sharing login
Recent learning summary
JS get DPI, PX to cm, cm to PX
Exercise 10-3 recursive implementation of exponential functions