【国庆集训】 10.1

发布时间：2020-12-14 00:18:03 所属栏目：Linux 来源：网络整理

导读：说实话，这次考试只有第三题恶心一点，太菜的我只有100，第二题写了正解没过 T1 1.爬山(mountain.cpp) 题目描述 FGD 小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。为了能够让他对他的旅程有一个安排，他想知道山峰和山谷的数量。给定一个地图，

说实话，这次考试只有第三题恶心一点，太菜的我只有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 5005

inline 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;
}

这个看起来好像不是我的风格，那就对了，我复制别人的，我的代码不见了

T3：

详情请见：https://www.cnblogs.com/GMSD/p/11616346.html

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!