【国庆集训】 10.1_系统运维

概述说实话，这次考试只有第三题恶心一点，太菜的我只有100，第二题写了正解没过 T1 1.爬山(mountain.cpp) 题目描述 FGD 小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。为了能够让他对他的旅程有一个安排，他想知道山峰和山谷的数量。给定一个地图，为 FGD 想要旅行的区域，地图被分为 n*n 的网格，每个格子(i,j) 的高度 w(i,j)是给定的。若两个格子有公共顶点(八

说实话，这次考试只有第三题恶心一点，太菜的我只有100，第二题写了正解没过

1.爬山(mountain.cpp)
题目描述
FGD 小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。为了能够让
他对他的旅程有一个安排，他想知道山峰和山谷的数量。给定一个地图，为 FGD
想要旅行的区域，地图被分为 n*n 的网格，每个格子(i,j) 的高度 w(i,j)是给定的。
若两个格子有公共顶点(八连通)，那么他们就是相邻的格子。我们定义一个格子
的集合 S 为山峰（山谷）当且仅当：
1. S 的所有格子都有相同的高度。
2. S 的所有格子都联通
3. 对亍 s 属亍 S，不 s 相邻的 s’丌属亍 S。都有 ws > ws’（山峰），戒者
ws < ws’（山谷）。
你的任务是，对亍给定的地图，求出山峰和山谷的数量，如果所有格子都有相同
的高度，那么整个地图即是山峰，又是山谷。
输入格式
第一行包含一个正整数 n，表示地图的大小（1<=n<=1000）。接下来一个 n*n
的矩阵，表示地图上每个格子的高度。 (0<=w<=1000000000)
输出格式
应包含两个数，分别表示山峰和山谷的数量。
输入输出样例

in：

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

好吧，一道小水题(捂脸)，也就想了半个小时(害羞)

直接贴代码，一道简单的搜索：

#include<bits/stdc++.h>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,0,1,1},dy[9]={-1,1};ll read(){    ll s=0,w=1;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]<mapp[nox][noy]&&!pd2)pd2=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;             bfs(i,j);       }    cout<<ans1<<" "<<ans2;    return 0;}

T2：

题目描述
小 A 为了计算一天能干多少事，他将一天划分为 n 个单位时间，并告诉你这天
他可以干的 m 项工作，其中第 i 项工作需要从第 Si 时刻开始连续做 Ei 个时刻才
能完成，同时完成这项工作能获得 Pi 的收入。小 A 在某一时刻只能干一项工作，
并且一旦选择某项工作，必须丌间断一次性做完，问他一天的工作中能获得最多
的收入为多少，请你帮帮他进行工作的选取。
输入格式
第一行，一个整数 n(n<=5000)
第二行，一个整数 m(m<=5000)
接下来 m 行，描述 m 件事情，每行包含 3 个整数 Si、 Ei、 Pi。
输出格式
仅包含一行，为小 A 在这一天内所能获得最大收入。
输入输出样例
输入 #1
8 1
1 8 3
输出 #1
3

这道题按照某巨佬来说就是：“有手就行”

一个dp就好了，可惜我没有做出来，我好菜啊---感叹

接下来是代码:

#include<cstdio>#include<algorithm>using namespace std;#define maxn 5005inline int read(){    int r=0,f=1;    char c=getchar();    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘)r=(r<<1)+(r<<3)+(c^48),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",stdin);    freopen("job.out",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,p);        n=max(n,t);    }    sort(w+1,w+1+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]);    return 0;}