Preparation of Blue Bridge Cup (I) recursion and recursion
1. Time complexity
One second can count 100 million times, that is, the 8th power of 10. If the topic is limited to 1 second, 8 times more than 10 times may timeout. The algorithm you choose depends on the data range.
2. The choice of cin,cout and scanf,printf
The main difference between Cin,cout, and scanf,printf is the speed. When the data scale is large, scanf,printf speed is significantly faster.
3. About recursion: a function calls itself. The classic example is Fibonacci sequence
Acwing 92. Recursive implementation of exponential enumeration
Randomly select any number of integers from 1 to n to output all possible selection schemes.
Input format
Enter an integer n.
Output format
Output one scheme per line.
The numbers in the same row must be arranged in ascending order, and two adjacent numbers are separated by exactly one space.
For schemes without any number selected, output blank lines.
This question has the custom calibrator (SPJ), each row (different plan) between the order is arbitrary.
Data range
1≤n≤151≤n≤15
Input example:
3
Output example:
3
2
2 3
1
1 3
1 2
1 2 3
#include<iostream> #include<cstdio> int n; int st[16]; //st [] indicates status, 0 indicates no judgment, 1 indicates selection, and 2 indicates no selection void dfs(int step) { //Write boundaries first if(step>n) { for(int i=1;i<=n;i++) //Judge whether it has been selected for each number in turn if(st[i]==1) printf("%d ",i); puts(""); //A simple way to write carriage return return ; } //Imagine a search tree with n locations in total. There are two choices for each location: select or not //First branch, select this number st[step]=1; dfs(step+1); st[step]=0; //Back up, back to the scene //Second branch, do not select this number st[step]=2; dfs(step+1); st[step]=0; //Restore scene } int main() { scanf("%d",&n); dfs(1); getchar();getchar(); return 0; }
Acwing 94. Recursive implementation of permutation enumeration
Arrange the nn integers of 1~nn into a row and randomly disturb the order, then output all possible orders.
Input format
An integer n.
Output format
Output all schemes from small to large, one for each line.
First, two adjacent numbers in the same line are separated by a space.
Secondly, for two different lines, the number of corresponding subscripts is compared one by one, and the dictionary with smaller order is in the front.
Data range
1≤n≤91≤n≤9
Input example:
3
Output example:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#include<iostream> #include<cstdio> using namespace std; int n; int a[10]; bool vis[10]; void dfs(int step) { //boundary if(step>n) { for(int i=1;i<=n;i++) printf("%d ",a[i]); puts(""); } for(int i=1;i<=n;i++) //Start enumerating each number that can be filled for each location { if(vis[i]==false) { a[step]=i; vis[i]=true; dfs(step+1); vis[i]=false; //Restore scene } } } int main() { cin>>n; dfs(1); getchar();getchar(); return 0; }
Note: order is considered for arrangement, and order is not considered for combination
Acwing 93. Recursive implementation of combinatorial enumeration
From the N integers 1~n, m are randomly selected to output all possible selection schemes.
Input format
Two integers, n,mn,m, are separated by spaces on the same line.
Output format
Output all schemes from small to large, one for each line.
First, the numbers in the same row are arranged in ascending order, and two adjacent numbers are separated by a space.
Secondly, for two different rows, the number of corresponding subscripts is compared one by one, and the smaller one is in front of the dictionary (for example, 1 355 7 is in front of 1 368).
Data range
n>0n>0 ,
0≤m≤n0≤m≤n ,
n+(n−m)≤25n+(n−m)≤25
Input example:
5 3
Output example:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
//Using full permutation output directly will cause repetition //Arrange output from small to large by start #include<iostream> #include<cstdio> using namespace std; int n,m; int a[100]; void dfs(int step,int start) //start represents the current minimum number that can be enumerated to control the arrangement of a [] from small to large { if(n-start<m-step) return ; //Cut the branch and return directly when the remaining optional number is not enough //boundary if(step>m) { for(int i=1;i<=m;i++) printf("%d ",a[i]); puts(""); return ; } for(int i=start;i<=n;i++) { a[step]=i; dfs(step+1,i+1); //Make the next number bigger than the previous one a[step]=0; //Restore scene } } int main() { cin>>n>>m; dfs(1,1); getchar();getchar(); return 0; }
Acwing 1209. With score
100100 can be expressed in the form of fraction: 100 = 3 + 69258714100 = 3 + 69258714
It can also be expressed as: 100 = 82 + 3546197100 = 82 + 3546197
Note: in the band score, the number 1 ∼ 91 ∼ 9 appears respectively and only once (excluding 00).
With scores like this, there are 1111 representations of 100100.
Input format
A positive integer.
Output format
The output and input numbers are represented by numbers 1 ∼ 91 ∼ 9, which do not repeat or omit to form all kinds of numbers with scores.
Data range
1≤N<1061≤N<106
Enter example 1:
100
Output example 1:
11
Enter example 2:
105
Output example 2:
6
Method 1: violence method: first output the full array, then split it into three numbers, and then judge
#include<iostream> #include<cstdio> using namespace std; int n,ans; int str[100]; bool vis[100]; int cal(int l,int r) //Computation function { int s=0; for(int i=l;i<=r;i++) s=s*10+str[i]; return s; } void dfs(int step) { if(step>9) { //Divide the array into three parts, two baffles for(int i=1;i<8;i++) //First baffle for(int j=i+1;j<9;j++) //Second baffle { int a=cal(1,i); int b=cal(i+1,j); int c=cal(j+1,9); if(c*n==c*a+b) //Pay attention to the judgment conditions. Since division in C + + is integral division, it should be converted into addition and subtraction multiplication to calculate ans++; } return ; } for(int i=1;i<=9;i++) //Full Permutation { if(vis[i]==false) { str[step]=i; vis[i]=true; dfs(step+1); vis[i]=false; //Restore scene } } } int main() { cin>>n; dfs(1); cout<<ans; getchar();getchar(); return 0; }
4. recursion
Recursion is to push from front to back step by step. There is no function like recursion that calls itself
Acwing 717. Simple Fibonacci
The following sequence 0 1 1 2 3 5 8 13 21 It is called Fibonacci series.
This sequence starts with Item 3, each of which is equal to the sum of the first two items.
Enter an integer N. please output the first N items of this sequence.
Input format
An integer N.
Output format
Output the first N items of Fibonacci series in a row, and separate the numbers with spaces.
Data range
0<N<460<N<46
Input example:
5
Output example:
0 1 1 2 3
#include<iostream> #include<cstdio> using namespace std; int n; int a[100]; int main() { a[1]=0; a[2]=1; cin>>n; for(int i=3;i<=n;i++) a[i]=a[i-1]+a[i-2]; for(int i=1;i<=n;i++) cout<<a[i]<<" "; getchar();getchar(); return 0; }
Acwing 95. Inexplicable switch
Have you ever played "pull the light"? 25 lamps are arranged in a 5x5 square. Each light has a switch, and the player can change its state. At each step, the player can change the state of a light. Players change the state of a light will produce a chain reaction: and the light up and down the left and right adjacent lights should also change their state accordingly.
We use the number "1" to indicate an on lamp and the number "0" to indicate a off lamp. The following state
10111
01101
10111
10000
11011
After changing the state of the lamp in the top left corner, it will become:
01111
11101
10111
10000
11011
After changing the lamp in the middle, the status will become:
01111
11001
11001
10100
11011
Given the initial state of some games, a program is written to determine whether the player can make all the lights on within 6 steps.
Input format
In the first line, enter the positive integer nn, which represents the initial state of the game with nn data to be solved.
The following lines of data are divided into nn groups, each group of data has 5 lines, each line has 5 characters. Each set of data describes the initial state of a game. Each group of data is separated by a blank row.
Output format
A total of nn lines of data are output, each line has an integer less than or equal to 6, which means that it takes at least a few steps for the corresponding game state in the input data to make all the lights on.
For the initial state of a game, if all lights cannot be turned on within 6 steps, output "- 1".
Data range
0<n≤5000<n≤500
Input example:
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
Output example:
3
2
-1
//I find that I'm too busy to do bit arithmetic at all. Woohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoohoo~~~ #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n; char a[6][6],backup[6][6]; //Backup is a backup of a int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,1,-1}; void turn(int x,int y) { for(int i=0;i<5;i++) { int xi=x+dx[i],yi=y+dy[i]; if(xi>=0&&xi<5&&yi>=0&&yi<5) //Judge whether it is out of bounds a[xi][yi]=a[xi][yi]^1; //If two corresponding bits are the same, the result is 0; otherwise, it is 1 } } int main() { cin>>n; while(n--) { for(int i=0;i<5;i++) cin>>a[i]; //input //Enumerate first row status int s=10; //Record number of steps for(int op=0;op<1<<5;op++) //5-bit binary number indicates the first line status, equivalent to 0 to 32 decimal (1 < < 5 indicates 32) { int step=0; memcpy(backup,a,sizeof(a)); //Backup one copy and restore it when judging the next matrix //Operate on the first line as enumerated above for(int i=0;i<5;i++) { if(op>>i&1) //Whether the i-th bit of op is 1 { step++; turn(0,i); } } //Operate on the remaining 4 lines for(int i=0;i<4;i++) for(int j=0;j<5;j++) { if(a[i][j]=='0') { step++; turn(i+1,j); //Ensure that the lights in the previous line are off by pressing the next line } } //Judge whether the last row of lights are all off int k; for(k=0;k<5;k++) { if(a[4][k]=='0') break; } if(k==5) s=min(s,step); memcpy(a,backup,sizeof(backup)); //Remember to restore the original state } //output if(s>6) cout<<-1; else cout<<s; puts(""); } getchar();getchar(); return 0; }
Acwing 1208. Flip coins
Xiao Ming is playing a game of "flipping coins".
There are several coins in a row on the table. We use * for the front and o for the back (lowercase, not zero).
For example, the possible situation is: * * OO * * oooo
If you flip the two coins on the left at the same time, it becomes: oooo * * oooo
Now Xiaoming's question is: if the initial state and the target state are known, only two adjacent coins can be flipped at the same time at a time, then how many times should be flipped at least for a specific situation?
We agreed that turning two adjacent coins is a one-step operation.
Input format
Two equal length strings representing the initial state and the target state to be achieved.
Output format
An integer representing the minimum number of steps
Data range
The length of the input string does not exceed 100.
The data guarantee that the answer is certain.
Enter example 1:
********** o****o****
Output example 1:
5
Enter example 2:
*o**o***o*** *o***o**o***
Output example 2:
1
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; string a,b; void turn(int i) { if(a[i]=='*') a[i]='o'; else a[i]='*'; } int main() { int step=0; cin>>a>>b; for(int i=0;i<a.length();i++) { if(a[i]!=b[i]) //Each time, make sure that the front status is correct. Push down one by one { turn(i); turn(i+1); step++; } } cout<<step; getchar();getchar(); return 0; }
About vector
https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html
https://blog.csdn.net/weixin_41743247/article/details/90635931
acwing 116. Pilot brother
The game of "pilot brothers" requires players to open a refrigerator with 16 handles smoothly.
Each handle is known to be in one of two states: on or off.
The refrigerator will only open when all the handles are open.
The handle can be represented as a matrix of 4 х 4, and you can change the state of the handle at any position [i,j].
However, this also changes the state of all handles on rows i and j.
Please find out the minimum number of times you need to switch the handle.
Input format
The input consists of four lines, each containing the initial state of four handles.
The symbol "+" indicates that the handle is closed, while the symbol "-" indicates that the handle is open.
The initial state of at least one handle is off.
Output format
The first line outputs an integer N indicating the minimum number of toggle handles required.
Next, line N describes the switching order. Each line is input with two integers, representing the row number and column number of the handle in the switched state. The numbers are separated by spaces.
Note: if there are multiple ways to open the refrigerator, it shall be opened from top to bottom as a whole according to the priority and from left to right.
Data range
1≤i,j≤41≤i,j≤4
Input example:
-+-- ---- ---- -+--
Output example:
6
1 1
1 3
1 4
4 1
4 3
4 4
Dish chicken method: (I don 't know how to use vector. It' s strange that it 's faster than the method of using vector. Hee hee)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define x first //x instead of first #define y second //y for second using namespace std; char a[5][5],backup[5][5]; int get(int i,int j) { return 4*i+j; } void turn(int x,int y) { if(a[x][y]=='+') a[x][y]='-'; else a[x][y]='+'; } void turn_all(int x,int y) { for(int i=0;i<4;i++) { turn(x,i); turn(i,y); } turn(x,y); } int main() { for(int i=0;i<4;i++) cin>>a[i]; int res[100][3];int step=100; memset(res,0,sizeof(res)); memcpy(backup,a,sizeof(a)); for(int op=0;op<1<<16;op++) //Enumerate all possible { int temp[100][3]; int k=0; for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(op>>get(i,j)&1) //Judge whether it is 1 { temp[k][0]=i; temp[k][1]=j; turn_all(i,j); k++; } //Judge whether all lights are on bool p=false; for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(a[i][j]=='+') p=true; //Deposit if it meets the requirements if(p==false) { if(k<step) { step=min(step,k); memcpy(res,temp,sizeof(temp)); //Take it if the current step is less } } memcpy(a,backup,sizeof(backup)); //Remember to restore before each cycle } //output cout<<step<<endl; for(int i=0;i<step;i++) cout<<res[i][0]+1<<" "<<res[i][1]+1<<endl; getchar();getchar(); return 0; }
Use vector approach:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define x first #define y second using namespace std; typedef pair<int,int> PII; char a[5][5],backup[5][5]; int get(int x,int y) //Map a matrix to a row { return x*4+y; } void turn_one(int x, int y) { if (a[x][y] == '+') a[x][y] = '-'; else a[x][y] = '+'; } void turn_all(int x, int y) { for (int i = 0; i < 4; i ++ ) //Flip rows and columns { turn_one(x, i); turn_one(i, y); } turn_one(x, y); //As the middle is turned twice, it needs to be offset once } int main() { for(int i=0;i<4;i++) cin>>a[i]; vector<PII> res; for(int op=0;op<1<<16;op++) //Binary enumeration of each switch { vector<PII> temp; //Store current scenario memcpy(backup,a,sizeof(a)); //backups for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(op>>get(i,j)&1) //If it is 1, operate the press switch { temp.push_back({i,j}); //Save the scheme to temp turn_all(i,j); //Flip } //Judge whether all bulbs are on bool has_closed=false; for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(a[i][j]=='+') has_closed=true; if(has_closed==false) { if(res.empty()||res.size()>temp.size()) res=temp; } memcpy(a,backup,sizeof(backup)); //reduction } cout<<res.size()<<endl; for(int i=0;i<res.size();i++) cout<<res[i].x+1<<' '<<res[i].y+1<<endl; getchar();getchar(); return 0; }
