# Summer training Day3

## #Plans and useless ideas

——————————————Training team -————————————

- My challenge program design and algorithm introduction are all here!
- It is not difficult to search the problem of pruning. The problem also needs to be based on the water problem.
- I insisted on playing cf in the summer vacation. Although I haven't scored recently, I hope I can form a team as soon as possible!!

——————————————Front end——————————————

- Continue to learn JS. As expected, JS is more advanced than HTML and CSS.
- I am always worried. If I learn from the front end that I can make a living, I may feel relieved.

-------Unity-------

- I've compiled some things for the beginner. I really use them well.

---------------

- Maybe he is really a person without any sense of security. From very early on, life has become like a fog to me. I can't be sure whether the choice is correct, and I don't know where all the possibilities lead. I hope I can firmly control the future in my own hands. Sometimes I wonder if I'm too greedy, because my energy is limited and I can't try everything. But I'm really afraid of the impasse, and I still hope I can be cunning.
- If you can make a little money by outsourcing front-end websites, acm can form a team, and the pressure will be reduced a lot. At first, I pulled him to run, then I followed him, and then I felt the reins dragging me along. Now my knees are almost worn away.
- I found that not giving up is really my only praiseworthy trait. Someone said, "I like the way you work hard." It sounds like I like the moth to the fire. Maybe it's really useless not to give up many times, unless the real world can also be archived, then I have the toughness to achieve the best again and again.
- I like to tell others that the solution to the problem is like a circle, but sometimes it may be more like a tangled thread, always in fear, things are chaotic and complex, the world is chaotic and complex, but no one likes chaos and complexity, and the pain in the coercion is probably inevitable.

When I first came into contact with Baudelaire's flower of evil in high school, I had a strong resonance. I knew that he and I were essentially the same kind of people. Knowing that he would be unlucky sooner or later, he had no scruples. He was overwhelmed by the feeling of original sin that he did not know where he came from. However, he chose to keep flying himself. When I released my nature, I occasionally felt that I could save myself. Although I lost my life, I can still lose my strength. I don't think it's much more positive than being strong.

I am here to confide in my blog and swear by the way:

I will certainly become a great man. I will not disappear or be destroyed.

Nearly ten years.

After all, creation and destruction are primitive desires. In this way, the former is much simpler than the latter, so I can certainly do it.

Finally:

Nobody doesn't like David Bowie. It's really too late to meet him!

A rock star of the zongyu family who looks like Yoshihiro Yoshihiro.

Strange infatuation seems to grace the evening tide

Inexplicable infatuation seems to make the night more charming

I'll take it by your side

I'm watching by your side

Such imagination seems to help the feeling slide

This illusion seems to be driving a change of heart

I'll take it by your side

I feel it by your side

Instant correlation sucks and breeds a pack of lies

The fast-food relationship is disgusting and breeds a lot of lies

I'll take it by your side

I stand by your side

Oversaturation curls the skin and tans the hide

Knowing everything about you too much, my heart is constantly hit

I'll take it by your side

I bear it by your side

tick - tock

Tick tick

tick - tock

Tick tick

tick - tock

Tick tick

tick - tick - tick - tick - tick - tock - tick

Tick, tick, tick, tick, tick, tick

I'm unclean, a libertine And every time you vent your spleen

I am debauchery and unclean

I seem to lose the power of speech

Every time you lose your temper

Your slipping slowly from my reach

I have nothing to say

You grow me like an evergreen

You're getting away from me

You never see the lonely me at all

You just keep me like an evergreen, regardless

I...

Never noticed my loneliness

Take the plan, spin it sideways

This kind of thought, constantly hovering in my mind

I...

But I still sink

Fall

Without you, I'm Nothing

What am I without you

Without you, I'm nothing

I am nothing without you

Without you, I'm nothing

I am nothing without you

Take the plan, spin it sideways

Thoughts are constantly circling in my mind

Without you, I'm nothing at all

I'm nothing without you

## #Deep search and pruning

### A-maze problem:

Define a two-dimensional array:

int maze[5][5] = {

0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0,

};

It represents a labyrinth, in which 1 represents the wall, 0 represents the path that can be taken. You can only walk horizontally or vertically, not diagonally. It requires programming to find the shortest path from the upper left corner to the lower right corner.

Input

One 5 × 5, representing a maze. The data is guaranteed to have a unique solution.

Output

The shortest path from the upper left corner to the lower right corner. The format is shown in the sample.

Sample Input

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

// // Created by Shenning on July 13, 2020 // #include<stdio.h> #include <iostream> using namespace std; struct node{ int x; int y; int pre; //Previous point }; int book[6][6]; //Cannot repeat int map[6][6]; //Record chart struct node queue[20]; //Queue for storage path void print(struct node a) //Functions that implement path output { if(a.pre==-1)//First point { printf("(%d, %d)\n",a.x,a.y); // return ; } else { print(queue[a.pre]); //If you keep playing with dolls, you can achieve from first to next!! printf("(%d, %d)\n",a.x,a.y); } } int main() { int i,j; int head,tail; for(i=0;i<5;i++) { for(j=0;j<5;j++) { scanf("%d",&map[i][j]); } } head=0; tail=0; queue[tail].x=0; queue[tail].y=0; queue[tail].pre=-1; book[0][0]=1; //Starting point configuration tail++; while(head<tail) //Jump out when the queue is empty, indicating that the search has not found a feasible path { int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //Define four directions int flag=0; for(i=0;i<4;i++) //Explore around from the current point { int nextx=queue[head].x+next[i][0]; int nexty=queue[head].y+next[i][1]; //Enable mobility if(nextx<0||nextx>5||nexty<0||nexty>5) //Jump out if beyond the boundary { continue; } if(book[nextx][nexty]==0&&map[nextx][nexty]==0) //Join the team only when the point has not been visited and is feasible { book[nextx][nexty]=1;//access queue[tail].x=nextx; queue[tail].y=nexty; //Join queue queue[tail].pre=head; tail++; } if(nextx==4&&nexty==4) //Arrived at the destination { flag=1; break; } } if(flag) //Call the function output path after reaching the destination { print(queue[tail-1]); break; } head++; //Leave the team } return 0; }

When the path coordinates are output, there is a first in first out characteristic, so I think of queue;

Realize the dfs of exploring around;

int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}// Define four directions

int flag=0;

For (i=0; i<4; i++) / / explore around from the current point

{

int nextx=queue[head].x+next[i][0];

Int next=queue[head] Y+next[i][1]// Enable mobility

Conditions for joining the team: have not been visited and can be reached;

Generally speaking, the idea is reverse enumeration + pruning search;

### B- birthday cake

July 17 is Mr.W's birthday. ACM-THU will make an M-layer birthday cake with a volume of N π. Each layer is a cylinder.

Let the I (1 < = I < = m) layer cake from bottom to top be a cylinder with radius Ri and height Hi. When I < m, RI > ri+1 and Hi > Hi+1 are required.

Since we need to spread cream on the cake, in order to save money as much as possible, we want the area Q of the outer surface of the cake (except the bottom surface of the lowest layer) to be the smallest.

Let Q = S π

Please program the given N and M to find out the cake making scheme (appropriate Ri and Hi values) to minimize S. (except for Q, all the above data are positive integers)

Input

There are two lines. The first line is N (N < = 10000), indicating that the volume of the cake to be made is N π; The second line M (M < = 20) indicates that the number of layers of cake is M.

Output

One line only, is a positive integer S (S = 0 if there is no solution).

Sample Input

100

2

Sample Output

68

Hint

Cylindrical formula

Volume V = π R2H

Side area A '= 2 π RH

Bottom area A = π R2

#include <iostream> using namespace std; int V (int r,int h) { return(r*r*h); } int S(int r,int h){ return(2*r*h); } int ans = 0; int N, M; void dfs( int m, int left_V, int A, int last_R, int last_H) { if( m*V(last_R -1,last_H-1) < left_V && m!=M) return; //Pruning 1: the remaining volume is greater than the maximum volume if( left_V < 0) return; //Pruning 2: the remaining volume is less than 0 //1. 2: in short, the volume should be just right if( A > ans&&ans) return; // Current area ratio minimum large pruning if( !m) { if( !left_V ) ans = A; return; } for( int r = last_R - 1; r >= m; r--) for( int h = last_H - 1; h >= m; h--){ int curV = V(r,h); int curA = S(r,h); if( m == M) curA+=r*r; dfs( m-1, left_V - curV, A+curA, r, h); } } int main() { cin >> N >> M; ans = 0; dfs( M, N, 0, 100, 1000); cout << ans << endl; }

Defines the concept of residual volume, which is used when searching recursion.

dfs( m-1, left_V - curV, A+curA, r, h);

Two prunes define that the volume cannot be too large or too small

The third pruning ensures Smin

### D-N queen problem

I want to vomit blood!!! Failed 5 times!!!

But I haven't planted any global variables. How can I call myself a programmer!

N queens are placed on the N*N checkerboard so that they do not attack each other (that is, any two queens are not allowed to be in the same row, the same column, or on the diagonal line at 45 angles to the checkerboard border.

Your task is to find out how many legal placement methods there are for a given N.

Input

There are several lines in total, and each line has a positive integer N ≤ 10, indicating the number of chessboards and queens; If N=0, it means the end.

Output

There are several rows in total, and each row has a positive integer, indicating the different placement quantities of queens corresponding to the input rows.

Sample Input

1

8

5

0

Sample Output

1

92

10

// // Created by Shenning on July 13, 2020 // #include <algorithm> #include <stdio.h> #include <iostream> int cnt[11]; int ans = 0; int N; int book[15]; int a[15]; using namespace std; void dfs(int n) { bool flag; if (n == N) { ans++; //This is the last queen. It was placed successfully return; } for (int i = 0; i < N; i++) { book[n] = i; //Put in row N, column i flag = 1; for (int j = 0; j < n; j++) { if (book[j] == i || (abs(n - j) == abs(book[j] - i))) { flag = 0; break; } } if (flag) dfs(n + 1); } } int main(){ for( N=1;N<11;N++) { ans = 0; dfs(0); a[N]=ans; } while(cin>>N){ if(N!=0) cout<<a[N]<<endl; if(N==0) break; } }

Through this pruning, diagonal

(book[j] == i || (abs(n - j) == abs(book[j] - i)))

Array subscripts are rows and array stored values are columns

When n==N is reached, the last one is placed. At this time, it is a scheme

if (n == N) {

ans++;

//This is the last queen. It was placed successfully

return; }

Last time limit remember to print the table

int main(){

for( N=1;N<11;N++) {

ans = 0;

dfs(0);

a[N]=ans;

}

while(cin>>N){

if(N!=0)

cout<<a[N]<<endl;

if(N==0) break;

}

Problem summary:

My problem lies in the definition of global variables.

First, the array book should be a global variable!

Secondly, the global variable N cannot be redefined in the main function!

So in the afternoon, I will take a special look at the definition of global variables.

Update JS learning and C++ content in the afternoon!

To be continued