A - keep passing the ball:
In PE class, Xiaoman's teacher often plays games with his classmates. This time, the teacher took the students to play a passing game. The rules of the game are as follows: n students stand in a circle, and one of them holds a ball. When the teacher blows the whistle, he starts to pass the ball. Each student can pass the ball to one of his left and right students (left and right). When the teacher blows the whistle again, the passing stops. At this time, the student who doesn't pass the ball is the loser, I'm going to give you a show. The clever Xiaoman asks an interesting question: how many different passing methods can make the ball that Xiaoman starts to pass, and then returns to Xiaoman's hand after passing it m times. The two methods of passing the ball are regarded as different methods, if and only if in the two methods, the sequence of students receiving the ball is different according to the order of receiving the ball. For example, there are three students, No. 1, No. 2 and No. 3. Assuming that Xiaoman is No. 1, there are two ways for the ball to return to Xiaoman after three passes: 1 - > 2 - > 3 - > 1 and 1 - > 3 - > 2 - > 1.
Enter the file ball In is a line with two integers n, m separated by spaces (3 < = n < = 30, 1 < = m < = 30).
Output file ball Out is a line with an integer indicating the number of methods that meet the meaning of the question.
40% of the data meet: 3 < = n < = 30, 1 < = m < = 20, 100% of the data meet: 3 < = n < = 30, 1 < = m < = 30
Sample Input
3 3
Sample Output
2
Problem analysis:
My first thought is actually to use violent search to simulate. The idea is the most direct, but there is a great chance that it will time out, but I tried it and it did time out; Then we need to change another way of thinking. The second idea is to use dynamic programming, dp[m][n] represents the transfer method to reach the nth position under m operations. According to previous experience, we need to summarize the recursive formula first. The nth position can be reached at the m-1 operation, which means that the position of the ball must be on the left and right of n, Then the small ball can be transferred from left to right to position n, so the recurrence formula is:
dp[m][n]=dp[m-1][n-1]+dp[m-1][n+1]
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int dp[32][32];
int main(){
cin>>n>>m;
dp[0][1]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(j==1){
dp[i][j]=dp[i-1][n]+dp[i-1][j+1];
}
else if(j==n){
dp[i][j]=dp[i-1][j-1]+dp[i-1][1];
}
else {
dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
}
}
}
cout<<dp[m][1];
}
Queen B - glori:
Nubia and Sudan had no children, so he had to choose one of the qualified successors to succeed to the throne. He wanted the successor to be smart enough, so he prepared a checkerboard with a number of 1 − 99 in each grid. He also prepared eight Queen pieces. The rule of Queen 8 is that there can be no pieces in the same row, column or slash. While meeting this rule, the heir to the throne also needs to make the sum of the numbers of the positions of the eight queens the largest.
Input format
Enter a number k(k ≤ 20) to represent the number of chessboards. Next, there are k chessboards. Each chessboard has 64 numbers, which are divided into 8 rows and 8 columns. For details, see the example. Each number is less than 100.
Output format
Each chessboard outputs the maximum value, a total of k lines.
Sample Input
1
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
Sample Output
260
Problem analysis:
In fact, it is a replica of the eight queens' question. My idea is a little violent, that is, to find out each arrangement and maintain a maximum value in the process. However, I made a small question when writing and forgot to reset MAX, resulting in the wrong answer.
code:
#include <bits/stdc++.h>
using namespace std;
int fs[100], bs[100], c[100], r[100], m[100][100],a[10][10];
int MAX;
int k;
void out(){
int ans=0;
memset(m, 0, sizeof(m));
for(int i = 1; i <= 8; i++){
for(int j = 1; j <= 8; j++)
if(r[j] == i) ans+=a[i][j];
MAX=max(MAX,ans);
}
}
void dfs(int x){
if(x > 8){
out();
return;
}
for(int i = 1; i <= 8; i++){
if(!c[i] && !fs[x + i] && !bs[x - i + 8]){
r[x] = i;
c[i] = 1, fs[x + i] = 1, bs[x - i + 8] = 1;
dfs(x + 1);
c[i] = 0, fs[x + i] = 0, bs[x - i + 8] = 0;
}
}
}
int main(){
cin>>k;
while(k--){
MAX=0;
memset(c,0,sizeof(c));
memset(r,0,sizeof(r));
memset(fs,0,sizeof(fs));
memset(bs,0,sizeof(bs));
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
cin>>a[i][j];
}
}
dfs(1);
cout<<MAX<<endl;
}
return 0;
}
Topic background:
trs likes skiing. He came to a ski resort, which is a rectangle. For simplicity, we use the matrix of r rows and c columns to represent each terrain. In order to get faster speed, the taxiing route must be inclined downward. For example, the rectangle in the sample can slide from a point to one of the four adjacent points up, down, left and right. For example, 24-17-16-1, in fact, 25-24-23... 3-2-1 is longer. In fact, this is the longest one.
Input format:
Line 1: two numbers r, c (1 < = r, c < = 100), representing the rows and columns of the matrix. Row 2... r+1: the number of c in each row represents this matrix.
Output format:
Only one line: output 1 integer, indicating the maximum length that can slide.
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25
Problem analysis:
The key point of this problem is how to realize the access from the lowest point. First, put the data in a one-dimensional array. At the same time, each element of this array should be able to deduce its position in the two-dimensional array, and then sort the one-dimensional array. I use a structure array that contains multiple sets of data.
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105][105];
int l[105][105];
struct node{
int x,y;
int data;
};
int cmp(node u,node v){
return u.data<v.data;
}
int n,m;
int main(){
cin>>n>>m;
node b[n*m];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
l[i][j]=1;
b[(i-1)*m+j-1].data=a[i][j];
b[(i-1)*m+j-1].x=i;
b[(i-1)*m+j-1].y=j;
}
sort(b,b+n*m,cmp);
for(int i=0;i<n*m;i++){
if(b[i].y+1<=m&&a[b[i].x][b[i].y+1]<a[b[i].x][b[i].y])l[b[i].x][b[i].y]=max(l[b[i].x][b[i].y],l[b[i].x][b[i].y+1]+1);
if(b[i].y-1>=1&&a[b[i].x][b[i].y-1]<a[b[i].x][b[i].y])l[b[i].x][b[i].y]=max(l[b[i].x][b[i].y],l[b[i].x][b[i].y-1]+1);
if(b[i].x+1<=n&&a[b[i].x+1][b[i].y]<a[b[i].x][b[i].y])l[b[i].x][b[i].y]=max(l[b[i].x][b[i].y],l[b[i].x+1][b[i].y]+1);
if(b[i].x-1>=1&&a[b[i].x-1][b[i].y]<a[b[i].x][b[i].y])l[b[i].x][b[i].y]=max(l[b[i].x][b[i].y],l[b[i].x-1][b[i].y]+1);
}
int c=0;
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++)
c=max(c,l[x][y]);
cout<<c;
}
F - all mine:
There is a box with a capacity of v (positive integer, O ≤ v ≤ 20000) and n items (o ≤ n ≤ 30), and each item has a volume (positive integer). It is required to take any number of n items into the box to minimize the remaining space of the box.
Input format:
The first line, an integer, represents the box capacity;
The second line, an integer, indicates that there are n items;
The next N lines represent the respective volumes of the n items.
Output format:
An integer representing the remaining space of the box.
Sample Input
24
6
8
3
12
7
9
7
Sample Output
0
Problem analysis:
Because the data is not large, at the beginning, my idea is still violent search. Of course, direct violence should not work, so I added some simple optimization later, which I didn't expect; Another idea of this problem is dynamic programming, which is more suitable for situations with larger data.
code:
//Violent search
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[35];
int V;//Original volume
int N;//number
int MIN;
int f(int u,int v){
return u>v;
}
void dfs(int v,int i){
if(v<0)return ;
if(i>N)return ;
if(MIN==0)return ;
MIN=min(v,MIN);
for(int j=i;j<N;j++){
if(a[j]==v)MIN=0;
}
dfs(v,i+1);
dfs(v-a[i],i+1);
}
int main(){
while(cin>>V>>N){
MIN=V;
for(int i=0;i<N;i++)cin>>a[i];
sort(a,a+N,f);
int i;//Record the serial number of the first item that can be accommodated
for(i=0;i<N;i++)
if(a[i]<=V)break;
dfs(V,i);
cout<<MIN<<endl;
}
}
//dynamic programming
#include<bits/stdc++.h>
using namespace std;
int V;
int N;
int a[35];
int dp[20005];//The subscript represents the volume that each volume can hold
int main(){
cin>>V>>N;
for(int i=0;i<N;i++)cin>>a[i];
sort(a,a+N);
for(int i=0;i<N;i++){
for(int j=V;j>=a[i];j-- )
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
}
cout<<V-dp[V]; //Output minimum volume
}
G - I have a pair of scissors:
There are n line segments on the coordinate axis. The left end point of each line segment is ai and the right end point is bi. Now you need to delete some segments so that the lower segment has no common part except the endpoint. Please calculate the maximum number of segments that can be reserved.
Input format
The first line is an integer
n(1 ≤ n ≤ 10 ^ 6) indicates the number of line segments. Next N lines, two integers AI, Bi in each line (0 ≤ a < Bi ≤ 10 ^ 6)
Output format
An integer representing the maximum number of segments that can be reserved.
Sample Input
3
0 2
2 4
1 3
Sample Output
2
Problem analysis:
The main test point of this question is actually thinking. The original question takes the competition time as an example. I think the competition time is easier to understand. Now there are multiple competitions. Each competition is based on its own start time and end time. Our goal is to participate in more competitions as much as possible. Let's first sort the end time of the competition, and then list it in turn, You can choose the most suitable one; If you choose to sort the start time and then enumerate it in turn, in fact, one game may take too long to replace several games, and the result is not our requirement.
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int l,r;
};
node a[1000005];
int cmp(node x,node y){
return x.r<y.r;
}
int main(){
int n;
while(cin>>n&&n){
for(int i=0;i<n;i++)cin>>a[i].l>>a[i].r;
sort(a,a+n,cmp);
int ans=1,cnt=a[0].r;
for(int i=1;i<n;i++){
if(a[i].l>=cnt){
cnt=a[i].r;
ans++;
}
}
cout<<ans<<endl;
}
}