[National Day Training] 10.1

To be honest, only the third question in this exam is a bit disgusting. I only have 100 if I’m too bad, and I haven’t written the correct answer for the second question.

T1

1. Mountain climbing (mountain.cpp)
Title description
FGD Children like to climb mountains very much. Studying the peaks and valleys. In order to be able to
he have a plan for his journey, he wants to know the number of peaks and valleys. Given a map, which is the area where FGD
wants to travel, the map is divided into n*n grids, and the height w(i,j) of each grid (i,j) is given.
If two grids have a common vertex (eight connected), then they are adjacent grids. We define a set S of lattices
as mountain peaks (valleys) if and only if:
1. All lattices of S have the same height.
2. All grids of S are connected
3. For s, it belongs to S, and s’adjacent to s is not. All have ws> ws’ (mountain), or
ws Your task is to find the number of peaks and valleys for a given map. If all the grids have the same
height, then the entire map is both a peak and a valley.
input format
The first line contains a positive integer n, which represents the size of the map (1<=n<=1000). The next n*n
matrix represents the height of each grid on the map. (0<=w<=1000000000)
The output format
should contain two numbers, representing the number of peaks and valleys.
Sample input and output

in: span>

5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8

out:

2 1

< p align="left">Well, for a small water question (cover your face), I thought about it for half an hour (shy)

Post the code directly, a simple search:

#include

using namespace std;

#define ll long long

#define cg ch=getchar()



const int _=1002;

ll number,mapp[_][_],ans1,ans2,pd1,pd2,res[_][_];

ll q[_*_][4],hd,tl,dx[9]={-1,-1,- 1,0,0< /span>,1,1,1},dy[9]={-1, 0,1,-1 ,1,-1,0,1};



ll read(){

 ll s=0,w=1;< span style="color: #0000ff;">char cg;

 while(ch<'0'||ch>' 9')w=(ch=='-')?-1:1,cg;

 while(ch>='0'&&ch<=' 9')s=s*10+ch-'0',cg;

 return s*w;

}



void bfs(int x,int y){

 hd=0;tl=1;res[ x][y]=1;q[1][0]=x;q[1][1 ]=y;

 while(hd<tl){

 hd++;

 ll nox=q[hd][0],noy=q[hd][1];

 for(int i=0;i<8;i++){

 ll nx=nox+dx[i],ny=noy+dy[i];

 if(nx<1||nx>number ||ny<1||ny>number)continue;

 if(mapp[nx][ny]==mapp[nox][noy]&&!res[nx][ny]){

 res[nx][ny]=1;tl++;q[tl][0]=nx;q[tl][1]=ny;

}

 else {

 if(mapp[nx][ny]>mapp[nox][noy]&&!pd1)pd1=1,ans1--;

 if(mapp[nx][ny]1,ans2--;

}

}

}

}



int main(){

 freopen("mountain.in","r",stdin);

 freopen("mountain.out","w",stdout);

 number=read();

 for(int i=1;i<=number;i++)

 for(int j=1;j<=number;j++)

 mapp[i][j]=read();

 for(int i=1;i<=number;i++)

 for(int j=1;j<=number;j++){

 if(res[i][j])continue;

 ans1++;ans2++;pd1=0;pd2=0< /span>;

 bfs(i,j);

}

 cout<" "<< ans2;

 return 0;

}

T2:

Title Description
In order to calculate how many things he can do in a day, he divides a day into n unit times and tells you the m tasks he can do on this day. Among them The i-th job needs to be done continuously from the Si-th moment to Ei moments before it can be completed, and at the same time, completing this job can earn Pi’s income. Little A can only do one job at a certain time,
and once he chooses a job, he must do it all at once without interruption. Ask him how much income he can get in a day
, please help Help him choose the job.
input format
The first line, an integer n(n<=5000)
The second line, an integer m(m< =5000)
The next m lines describe m things, each line contains 3 integers Si, Ei, Pi.
The output format
contains only one line, which is the maximum income that A can get in this day.
Input and output sample
input#1
8 1
1 8 3
output#1
3

According to a giant, this question is: “Just have a hand”

One ​​dp is fine, but I didn’t do it. Come out, I’m so good—sigh

Next is the code:

#include

#include

using namespace std;



#define maxn 5005



inline int read(){

 int r=0,f=1;

 char c=getchar();

 while(c<'0'||c>' 9'){if< /span>(c=='-')f=-1;c=getchar();}

 while(c>='0'&&c<=' 9')r=(r<<1)+(r<<3)+(c^48< /span>),c=getchar();

 return r*f;

}



inline int max(int a,int b){

 return a>b?a:b;

}



struct W{

 int s,t,p;

 W() {}

 W(int s,int t,int p):s(s),t(t),p(p) {};

 bool operator <(const W &work) const{

 return s>work.s;

}

}w[maxn];



int s_n,n,m,s_m,f[2][maxn];



int main(){

 freopen("job.in","r",stdin);

 freopen("job.out","w",stdout);

 n=read(),s_m=read();

 for(int i=1;i<=s_m;i++){

 int s=read(),t=s+read()-1,p=read();

 if(s<1||t>n )continue;

 w[++m]=W(s,t,p);

 n=max(n,t);

}

 sort(w+1,w+1+< span style="color: #000000;">m);

 for(int i=1;i<=m;i++)

 for(int j=1;j<=n;j++){

 if(j<=w[i].s)f[i%2][j]=max(w[i].p+f[(i%2)^1][w[i].t+1],f[(i%2)^1][j]);

 else f[i%2][j] =f[(i%2)^1][j];

}

 printf("%d",f[m%2][1< /span>]);

 return 0;

}

This doesn’t seem to be my style, that’s right, I copied someone else’s, my code is gone

T3:

For details, please see: https://www.cnblogs.com/GMSD/p/11616346.html

< pre>#include

using namespace std;

#define ll long long

#define cg ch=getchar()

const int _=1002;

ll number,mapp[_][_],ans1,ans2,pd1,pd2,res[_][_];

ll q[_*_][4],hd,tl,dx[9]={-1,-1,- 1,0,0< /span>,1,1,1},dy[9]={-1, 0,1,-1 ,1,-1,0,1};

ll read(){

ll s=0,w=1;< span style="color: #0000ff;">char cg;

while(ch<‘0‘||ch>‘ 9‘)w=(ch==‘–‘)?-1:1,cg;

while(ch>=‘0‘&&ch<=‘ 9‘)s=s*10+ch-‘0‘,cg;

return s*w;

}

void bfs(int x,int y){

hd=0;tl=1;res[ x][y]=1;q[1][0]=x;q[1][1 ]=y;

while(hd<tl){

hd++;

ll nox=q[hd][0],noy=q[hd][1];

for(int i=0;i<8;i++){

ll nx=nox+dx[i],ny=noy+dy[i];

if(nx<1||nx>number ||ny<1||ny>number)continue;

if(mapp[nx][ny]==mapp[nox][noy]&&!res[nx][ny]){

res[nx][ny]=1;tl++;q[tl][0]=nx;q[tl][1]=ny;

}

else {

if(mapp[nx][ny]>mapp[nox][noy]&&!pd1)pd1=1,ans1–;

if(mapp[nx][ny]1,ans2–;

}

}

}

}

int main(){

freopen(“mountain.in“,“r“,stdin);

freopen(“mountain.out“,“w“,stdout);

number=read();

for(int i=1;i<=number;i++)

for(int j=1;j<=number;j++)

mapp[i][j]=read();

for(int i=1;i<=number;i++)

for(int j=1;j<=number;j++){

if(res[i][j])continue;

ans1++;ans2++;pd1=0;pd2=0< /span>;

bfs(i,j);

}

cout<“ “<< ans2;

return 0;

}

#include

#include

using namespace std;



#define maxn 5005



inline int read(){

 int r=0,f=1;

 char c=getchar();

 while(c<'0'||c>' 9'){if< /span>(c=='-')f=-1;c=getchar();}

 while(c>='0'&&c<=' 9')r=(r<<1)+(r<<3)+(c^48< /span>),c=getchar();

 return r*f;

}



inline int max(int a,int b){

 return a>b?a:b;

}



struct W{

 int s,t,p;

 W() {}

 W(int s,int t,int p):s(s),t(t),p(p) {};

 bool operator <(const W &work) const{

 return s>work.s;

}

}w[maxn];



int s_n,n,m,s_m,f[2][maxn];



int main(){

 freopen("job.in","r",stdin);

 freopen("job.out","w",stdout);

 n=read(),s_m=read();

 for(int i=1;i<=s_m;i++){

 int s=read(),t=s+read()-1,p=read();

 if(s<1||t>n )continue;

 w[++m]=W(s,t,p);

 n=max(n,t);

}

 sort(w+1,w+1+< span style="color: #000000;">m);

 for(int i=1;i<=m;i++)

 for(int j=1;j<=n;j++){

 if(j<=w[i].s)f[i%2][j]=max(w[i].p+f[(i%2)^1][w[i].t+1],f[(i%2)^1][j]);

 else f[i%2][j] =f[(i%2)^1][j];

}

 printf("%d",f[m%2][1< /span>]);

 return 0;

}