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