Problem Description: 1 Band fraction
100 can be expressed as a fractional form: 100 = 3 + 69258 / 714.
It can also be expressed as: 100 = 82 + 3546 / 197.
Note: in the band fraction, the numbers 1 ~ 9 appear respectively and only once (excluding 0).
Like this band fraction, 100 has 11 representations.
Solution:
#include<iostream>
#include<string.h>
using namespace std;
int a[10]={0};
bool Division(int m) //Split number
{
int t;
while(m)
{
t=m%10;
if(t==0) //Zero does not meet the meaning of the question
return 0;
a[t]++;
m=m/10;
}
return 1;
}
int main()
{
int n,ans=0;
cin>>n;
for(int i=1;i<n;i++)
{
for(int j=1;j<=4938;j++)
{
memset(a,0,sizeof(a)); //Each bit of array a is set to zero
int k=(n-i)*j;
if(Division(i)&&Division(j)&&Division(k))
{
int flag=1;
for(int x=1;x<10;x++) //Determine whether the number is repeated
{
if(a[x]!=1)
{
flag=0;
break;
}
}
if(flag==1)
ans++;
}
}
}
cout<<ans;
return 0;
} Problem Description: 2 Li Bai makes wine
It is said that Li Bai, a great poet, likes drinking all his life. Luckily he never drives.
One day, he came out of the house with a wine pot. There were two buckets of wine in the wine pot. He sang as he walked:
Walk down the street and fetch a pot of wine.
Double every shop and drink a bucket of flowers.
Along the way, he met the store 5 times and flowers 10 times. It is known that the last time he met flowers, he just drank up the wine.
Please calculate the order in which Li Bai meets the shop and flowers. You can record the shop as a and the flower as b. Then:
Babaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb. How many answers are there like this?
Please calculate the number of all possible schemes (including those given in the title).
Solution: 14
#include <iostream>
using namespace std;
int ans;
void f(int hua,int dian,int jiu)
{
if(hua==1&&dian==0&&jiu==1)
ans++;
if(hua>1)
f(hua-1,dian,jiu-1);
if(dian>0)
f(hua,dian-1,jiu*2);
}
int main()
{
f(10,5,2);
cout<<ans<<endl;
return 0;
}Problem Description: 3 39th step
Xiao Ming has just finished watching the movie "the 39th step". When he left the cinema, he counted the number in front of the auditorium
The number of steps is exactly 39!
Standing in front of the steps, he suddenly thought of another question:
If I can only take one or two steps at a time. Take the left foot first, then turn left and right, and the last one
Step is to take the right foot, that is, take an even number of steps. So, how many different methods are there after 39 steps?
Solution: 51167078
#include <iostream>
using namespace std;
int ans=0;
void solve(int n,int step)
{
if(n==0 && step % 2==0)
ans++;
if(n<0)
return;
solve(n-1,step+1);
solve(n-2,step+1);
}
int main()
{
solve(39,0);
cout<<ans<<endl;
return 0;
}Problem Description: 4 Crossing minefield
The known map is A square matrix, on which areas A and B are marked with letters, and other areas are marked with plus or minus signs
Respectively represent positive and negative energy radiation areas.
For example:
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
Tanks can only move horizontally or vertically to adjacent areas.
Data format requirements:
The first input line is an integer n, indicating the size of the square matrix, 4 < = n < 100
Next, there are n rows. Each row has n data, which may be one of A, B, +, - separated by spaces.
A. B only appears once.
It is required to output an integer indicating the minimum moving steps of the tank from area A to area B. If there is no scheme, output - 1
For example: user input:
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
The program should output:
10
Solution:
#include<iostream>
#include<queue>
using namespace std;
const int M = 100,INF = 0x3f3f3f3f;
const int move[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
int n,endx,endy;
char ch[M+5][M+5];
int a[M+5][M+5];
struct Coordinate
{
int x,y;
Coordinate(int x,int y):x(x),y(y){}
};
queue<Coordinate>q;
void bfs()
{
Coordinate t = q.front();
q.pop();
//cout<<t.x<<' '<<t.y<<endl;
for(int i=0;i<4;i++)
{
int tx = t.x + move[i][0];
int ty = t.y + move[i][1];
if(tx<1||ty<1||tx>n||ty>n||a[tx][ty]||ch[tx][ty]==ch[t.x][t.y])
continue;
a[tx][ty]=a[t.x][t.y]+1;
if(tx==endx&&ty==endy)
{
while(!q.empty())
q.pop();
return;
}
q.push(Coordinate(tx,ty));
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>ch[i][j];
if(ch[i][j]=='A')
{
q.push(Coordinate(i,j));
a[i][j]=0;
}
if(ch[i][j]=='B')
{
endx=i;
endy=j;
}
}
while(!q.empty())
bfs();
cout << a[endx][endy];
return 0;
}Problem Description: 5 maze
The following figure shows the plan of a maze, where the one marked with 1 is an obstacle and the one marked with 0 is an accessible place.
010000
000100
001001
110000
The entrance of the maze is the upper left corner and the exit is the lower right corner. In the maze, you can only walk to it from one position
One of the four directions of up, down, left and right. For the maze above, starting from the entrance, you can press
The order of DRRURRDDDR passes through the maze, a total of 10 steps. Where D, U, L and R respectively represent
Go down, up, left, right. For this more complex maze (30 rows and 50 columns), please find
Find a way through the maze, which uses the least number of steps. On the premise of the least number of steps, please find the word
Take the smallest one as the answer. Please note that in the dictionary order, d < l < R < U.
Solution:
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
const int move[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
const string S[4] = {"D","L","R","U"};
bool a[31][51];
struct Coordinate
{
int x,y;
string s;
Coordinate(int x,int y,string s):x(x),y(y),s(s){}
};
queue<Coordinate> q;
void bfs()
{
Coordinate t = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int tx = t.x + move[i][0];
int ty = t.y + move[i][1];
if(tx<1||tx>30||ty<1||ty>50||a[tx][ty])
continue;
string ts = t.s + S[i];
if(tx==30&&ty==50)
{
while(!q.empty())
q.pop();
cout<<ts;
return;
}
a[tx][ty]=true;
q.push(Coordinate(tx,ty,ts));
}
}
int main()
{
for(int i=1;i<=30;i++)
for(int j=1;j<=50;j++)
{
char ch;
cin>>ch;
a[i][j] = (ch=='1');
}
q.push(Coordinate(1,1,""));
while(!q.empty())
bfs();
return 0;
}Problem Description: 6 vaulting horse
The half board of Chinese chess is shown in Figure 1. The horse jumps from the lower left corner (0,0) to the upper right corner (m, n). It is stipulated that you can only jump to the right, not to the left. For example, figure 1 shows a skip route and prints the total number of routes.
Input format:
There is only one line: two numbers n, m
Output format:
There is only one number: total number of schemes.
Solution:
#include <iostream>
using namespace std;
int n,m,ans;
const int move[4][2]={{1,2},{2,1},{2,-1},{1,-2}};
void dfs(int x,int y)
{
if(x==m&&y==n)
ans++;
for (int i = 0 ; i< 4 ;i++)
{
int tx = x + move[i][0];
int ty = y + move[i][1];
if(tx<0||tx>m||ty<0||ty>n)
continue;
else
dfs(tx,ty);
}
}
int main()
{
cin>>m>>n;
dfs(0,0);
cout<<ans<<endl;
return 0 ;
}Problem Description: 7 The mystery of the path
Xiao Ming pretends to be the knight of Planet X and enters a strange castle.
There was nothing in the castle, only the ground made of square stones.
Suppose the castle ground is n x n squares. [as shown in Figure 1.png].
According to custom, knights walk from the northwest corner to the southeast corner.
It can move horizontally or vertically, but it can't walk obliquely or jump.
Every time you come to a new square, you have to shoot an arrow to the north and West.
(there are n targets in the west wall and N targets in the north wall of the castle)
The same square can only pass once. But you don't have to finish all the squares.
If you only give the number of arrows on the target, can you infer the knight's route?
Sometimes it is possible, such as Figure 1 Png example.
The requirement of this question is to know the target number and find the knight's walking path (the test data ensure that the path is unique)
Input:
The first line is an integer n (0 < n < 20), indicating that there are N x N squares on the ground
The second line contains N integers, separated by spaces, indicating the number on the North target (from west to East)
The third line contains N integers, separated by spaces, indicating the number on the target in the West (from north to South)
Output:
Several integers on a line represent the knight path.
For convenience, we agree that each small grid is represented by a number, starting from the northwest corner: 0,1,2,3
For example, figure 1 The block number in PNG is:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Example:
User input:
4
2 4 3 4
4 3 3 3
The program should output:
0 4 5 1 2 3 7 11 10 9 13 14 15
Solution:
#include<iostream>
using namespace std;
const int move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,p=0,a[21],b[21],step[401];
bool st[21][21];
bool dfs(int x,int y)
{
if(!a[y]||!b[x])
return false;
a[y]--,b[x]--;
if(x==n&&y==n)
{
bool st = true;
for(int i=1;i<=n;i++)
if(a[i]||b[i])
st = false;
if(st)
{
step[p++]=(x-1)*n+y-1;
return true;
}
}
for(int i=0;i<4;i++)
{
int tx=x+move[i][0];
int ty=y+move[i][1];
if(tx<1||tx>n||ty<1||ty>n)
continue;
if(dfs(tx,ty))
{
step[p++]=(x-1)*n+y-1;
return true;
}
}
a[y]++,b[x]++;
return false;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int j=1;j<=n;j++)
cin>>b[j];
dfs(1,1);
for(int i=p-1;i>=0;i--)
cout<<step[i]<<' ';
return 0;
}Problem Description: 8 Troubles by Weiming Lake
Every winter, Weiming Lake in Peking University is a good place for skating. The sports team of Peking University has prepared many skates, but there are too many people. After work every afternoon, there is often no pair of skates left.
Every morning, there will be a long queue at the shoe rental window. Suppose there are m who return shoes and n who need to rent shoes. The question now is how many arrangements these people have to avoid the embarrassing situation that the sports group has no skates to rent. (two people with the same needs (for example, both rent shoes or return shoes) exchange positions in the same arrangement)
Input format: two integers representing m and n
Output format: an integer indicating the number of schemes for the arrangement of the team.
Sample input: 3 2
Sample output: 5
Data scale and agreement: m,n ∈ [0,18]
Solution:
#include<iostream>
using namespace std;
int solve(int x,int y)
{
if(x<y)
return 0;
if(y==0)
return 1;
return solve(x-1,y)+solve(x,y-1);
}
int main()
{
int m,n;
cin>>m>>n;
int ans=solve(m,n);
cout<<ans<<endl;
}Problem Description: 9 Minister's travel
Long ago, the kingdom of T prospered unprecedentedly. In order to better manage the country, the Kingdom has built a large number of expressways to connect the capital and the major cities in the kingdom.
In order to save money, the ministers of T country have formulated an excellent construction scheme after thinking, so that any big city can reach directly from the capital or indirectly through other big cities. At the same time, if you do not repeat passing through big cities, the scheme from the capital to each big city is unique.
J is an important Minister of state T. he patrols among major cities and observes the people's conditions. Therefore, from one city to another has become J's most common thing. He has a money bag for the transportation between cities.
Smart J found that if he didn't stop to repair in a city, in the process of continuous travel, the toll he spent was related to the distance he had traveled. In the kilometer from kilometer x to kilometer x+1 (x is an integer), the toll he spent was so much as x+10. In other words, it costs 11 to walk 1 km and 23 to walk 2 km.
Minister J wants to know: what is the maximum cost of all possible travel expenses when he starts from one city and doesn't rest in the middle to another city?
The first line of input contains an integer n, which represents the number of cities in T kingdom including the capital
Cities are numbered from 1, and city 1 is the capital.
Next, line n-1 describes the expressways in country T (the expressways in country T must be n-1)
Three integers Pi, Qi and Di in each line indicate that there is a highway between city Pi and city Qi, with a length of Di km.
An integer is output to indicate the maximum travel cost of minister J.
Sample input 1
5
1 2 2
1 3 1
2 4 5
2 5 4
Sample output 1
135
Solution:
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int MAX=10000; //Maximum number of cities
int maxFarNode; //maxFarNode is the farthest node from the specified node
int maxLen=-1; //maxLen is the longest distance from a specified node
bool st[MAX]; //Mark whether a point has been accessed
struct Node
{ // Store the weights of child nodes and edges of a point
int child,length;
Node(int a,int b):child(a),length(b){};
};
vector<Node> v[MAX]; //Linked storage, adjacency list
void dfs(int node,int nowLen)
{
if(st[node])
return;
st[node]=true;
for(int i=0;i<v[node].size();i++)
{
int child =v[node][i].child;
int length=v[node][i].length;
if(st[child])
continue;
if(nowLen+length>maxLen)
{
maxLen=nowLen+length;
maxFarNode=child;
}
dfs(child,nowLen+length);
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int x,y,len;
cin>>x>>y>>len;
v[x].push_back(Node(y,len));
v[y].push_back(Node(x,len));
}
dfs(1,0);
memset(st,false,sizeof(st));
maxLen=-1;
dfs(maxFarNode,0);
cout<<(maxLen*10+maxLen*(1+maxLen)/2)<<endl;
return 0;
}Problem Description: 10.2n queen problem
Given an n*n chessboard, there are some positions in the chessboard that cannot put queens. Now put n black queens into the chessboard
And n white queens so that any two black queens are not on the same row, column or diagonal
The white queens are not in the same row, column or diagonal. How many kinds of playing methods are there in total? n is less than or equal to 8.
Input
The first line of input is an integer n, which represents the size of the chessboard.
In the next N lines, each line has n integers of 0 or 1. If an integer is 1, it means that the corresponding position can be placed,
If an integer is 0, it means that the corresponding position cannot be placed.
Output
Output an integer indicating the total number of playback methods.
Sample Input
No.1
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
No.2
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Sample Output
No.1
2
No.2
0
Solution:
#include<iostream>
#include<stdlib.h>
using namespace std;
const int maxn=10;
int n,ans=0;
int posb[maxn]={0}; //Black queen
int posw[maxn]={0}; //White Queen
int map[maxn][maxn];
bool checkw(int cur)
{
for(int i=1;i<cur;i++)
if(posw[i]==posw[cur]||abs(i-cur)==abs(posw[i]-posw[cur]))
return false;
return true;
}
bool checkb(int cur)
{
for(int i=1;i<cur;i++)
if(posb[i]==posb[cur]||abs(i-cur)==abs(posb[i]-posb[cur]))
return false;
return true;
}
void dfs_white(int cur)
{
if(cur==n+1) //The White Queen is also finished, times + 1
ans++;
for(int i=1;i<=n;i++)
{
if(posb[cur]==i) //Indicates that the position of row i in column cur has been occupied by the black queen,
continue; //End current cycle, i+1
if(map[cur][i]==0) //Then judge whether the preconditions are tenable
continue;
posw[cur]=i; //Try putting the white queen in cur column on line i
if(checkw(cur)) //Judge whether the white queen can be placed
dfs_white(cur+1); //recursion
}
}
void dfs_black(int cur)
{
if(cur==n+1) //When the black queen is finished, deal with the White Queen
dfs_white(1);
for(int i=1;i<=n;i++)
{
if(map[cur][i]==0) //If row I of column cur meets the precondition of Queen release, that is mp[cur][i] == 1
continue; //If not, end the current cycle and proceed to the next cycle, i.e. i+1.
posb[cur] = i; //Just try to put the black queen in cur column on line i
if(checkb(cur)) //Then judge whether the attempt is true. If it is true, perform recursion. If it is not true, try to put the black queen of the current column on the next row (i+1 row).
dfs_black(cur+1); //recursion
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) //Define chessboard
for(int j=1;j<=n;j++)
cin>>map[i][j];
dfs_black(1); //First put the black queen in the first column
cout<<ans<<endl;
return 0;
}