当前位置:网站首页>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;
}
边栏推荐
- QT learning 21 standard dialog box in QT (Part 2)
- Leetcode (4) - - trouver la médiane de deux tableaux ordonnés positifs
- Convert string to decimal integer
- 好看、好用、强大的手写笔记软件综合评测:Notability、GoodNotes、MarginNote、随手写、Notes Writers、CollaNote、CollaNote、Prodrafts、Noteshelf、FlowUs、OneNote、苹果备忘录
- 7-10 calculate salary
- Solve the problem of dormitory router campus network sharing login
- 常见问题之PHP——ldap_add(): Add: Undefined attribute type in
- Thread.sleep和TimeUnit.SECONDS.sleep的区别
- Vite project commissioning
- Mysql多表查询 #子查询
猜你喜欢
Understanding of closures
QT learning 17 dialog box and its types
Configure stylelint
Redis: commandes d'action pour les données de type chaîne
Programmable logic device software testing
concat和concat_ws()区别及group_concat()和repeat()函数的使用
八大排序
x86汇编语言-从实模式到保护模式 笔记
Exercise 8-7 string sorting
Solution to failure or slow downloading of electron when electron uses electron builder to package
随机推荐
TS code automatically generates JS
etcd集群权限管理和账号密码使用
剑指 Offer 28. 对称的二叉树
How to bold text in AI
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
Reflection -- basic usage
SSH access control, blocking the IP when logging in repeatedly to prevent brute force cracking
Redis:字符串類型數據的操作命令
simpleParallax. JS (create poor visual effects for website pictures)
Redis: redis data structure and key operation commands
js 2023. String pair equal to the target string after connection
必贝特医药冲刺科创板:年营收97万亏损1.37亿 拟募资20亿
Why are grass-roots colleges and universities with "soil and poverty" called "Northeast small Tsinghua"?
八大排序
NFT新的契机,多媒体NFT聚合平台OKALEIDO即将上线
Redis: operation command of string type data
Configure stylelint
泰凌冲刺科创板:拟募资13亿 国家大基金与小米长江是股东
Exercise 10-1 calculate the sum of 1 to n using recursive functions
Exercise 10-3 recursive implementation of exponential functions