6.30集训模拟赛4(炸裂的一天qwq)

时间：2020-06-30 20:58:05 阅读：58 评论：0 收藏：0 [点我收藏+]

　　题目描述

　　在一条长n米，宽m米米的长方形草地上放置着k个喷水装置。假设长方形草地的坐标范围为[ 0 , 0 ] ~ [ n , m ]，那么第 i 个喷水装置的位置为（ai，m_/2），也就是说喷水装置全部位于一条直线上。此外第 i 个喷水装置能向半径r_i的圆形区域内喷水。
负责管理喷水装置的园丁老大爷想知道，要想覆盖整个草地，至少需要开启多少个喷水装置。

　　输入格式

第一行三个正整数 k , n , m 。其中 m 为偶数。
接下来 k 行，每行两个整数a_i 和r_i ，代表第 i 个喷水装置的横坐标和喷水半径。

　　输出格式

一个整数 ans 代表至少需要开启的喷水装置数量。若所有装置都开启依然不能覆盖整个草地则输出-1 。

　　样例输入1

　　样例输出1

　　样例输入2

　　样例输出2

样例1 解释开启位于4和12的喷水装置即可。
30%的数据中：k ≤ 20。
另有20%的数据中：r_i均相等。
100%的数据中：m≤20000,ri≤10000，n，k≤100000,a_i。

　　分析：

　　喷水装置在长方形的中线上，如果某个喷水装置能喷到左上角的地方，那左下角必定能喷到。
如果喷水装置的喷水半径小于此装置无用
所以我们可以预处理出每一个喷水装置能喷到的左、右最远的距离，然后对其左边界进行排序，从左到右，一次枚举花坛的未喷到的最远点，在能喷到的装置中找到右端点最远的装置。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int k,n,m;
int a,r;
int cnt;
struct wat{//记录一个点的左右最远的覆盖范围
    double L;//double！！！
    double R;
}w[N];

bool cmp(wat a,wat b){//按
    return a.L<b.L;
}

int main(){
    scanf("%d%d%d",&k,&n,&m);//输入
    for(int i=1;i<=k;i++){
        scanf("%d%d",&a,&r);
        if(r*2<=m)continue;//去除一些没用的喷水装置
        w[++cnt].L=a-sqrt(r*r-m*m/4.0);//等于也不行（喷一个线有啥用）
        w[cnt].R=a+sqrt(r*r-m*m/4.0);
    }
    sort(w+1,w+1+cnt,cmp);//排序
    double right=0;
    int ans=0;
    while(right<n){//
        ans++;
        double s=right;//用一个s保存right值因为后面的right值要变
        for(int i=1;i<=k&&w[i].L<=s;i++){
            if(right<w[i].R){
                right=w[i].R;//更新覆盖的最右边的值
            }
        }
        if(right==s&&s<n){//不满题意
            printf("-1\n");
            return 0;
        }
    }
    printf("%d\n",ans);
    return 0;
}

　　题目描述：

最新推出了一种叫做“免费馅饼”的游戏:
游戏在一个舞台上进行。舞台的宽度为 w格，天幕的高度为 h格，游戏者占一格。
开始时游戏者站在舞台的正中央，手里拿着一个托盘。下图为天幕的高度为 4 格时某一个时刻游戏者接馅饼的情景。
游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。
馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时，在电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。
当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。
写一个程序，帮助我们的游戏者收集馅饼，使得所收集馅饼的分数之和最大。

　　输入格式：

　　输入文件的第一行是用空格隔开的两个正整数，分别给出了舞台的宽度 w （ 1到 99之间的奇数）和高度 H（ 1到100 之间的整数）。
接下来依馅饼的初始下落时间顺序给出了所有馅饼的信息。每一行给出了一块馅饼的信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（1 到1000 秒），水平位置、下落速度（1 到 100 ）以及分值。游戏开始时刻为0从开始自左向右依次对水平方向的每格编号。
输入文件中同一行相邻两项之间用一个或多个空格隔开

　　输出格式：

输出文件的第一行给出了一个正整数，表示你的程序所收集的最大分数之和。

　　样例输入:

　　样例输出:

0≤馅饼个数 ≤2500。

　　分析：

一道移动DP题。这题初看无从下手，馅饼和人都在移动，但仔细分析可得：定馅饼不动，由人移动去接馅饼。
想好两点：
- 　　只有高度可以被下落速度整除时，改馅饼才有被接住的可能。
- 时间可以当作纵坐标处理，即
设f [ i ] [ j ]，i 表示时刻，j表示x坐标。用k枚举移动的距离（k只能取-2，-1，0，1，2）。
动态转移方程为：f [ i ] [ j ] = max（f [ i - 1 ] [ j + k ] + a [ i ] [ j ]）;

#include<bits/stdc++.h>
using namespace std;
const int N=2600;
int w,h;
int cnt;
int T,P,V,W,maxtime;
int t[N],p[N],v[N],val[N];
int f[N][N];
int hehe(int i,int j){
    int ans=0;
    for(int k=-2;k<=2;k++){
        if(j+k<0||j+k>w)continue;
        ans=max(ans,f[i+1][j+k]);
    }
    return ans;
}

int main(){    
    scanf("%d%d",&w,&h);
    h--;//注意减一
    while(scanf("%d%d%d%d",&T,&P,&V,&W)==4){
        if(h%V==0){
            t[++cnt]=T+h/V;//注意+T;
            p[cnt]=P;v[cnt]=V;val[cnt]=W;
            maxtime=max(maxtime,t[cnt]);//找出下落时间最大的值来
        }
    }
    if(cnt==0){//如果都不符合那就结束
        printf("0");
        return 0;
    }
    for(int i=1;i<=cnt;i++){//可能有不同时出发的但同时同地落下的馅饼。累加。
        f[t[i]][p[i]]+=val[i];
    }
    for(int i=maxtime-1;i>=0;i--){//从后往前
        for(int j=w;j>=0;j--){//maxtime注意减一因为转移有范围。
            f[i][j]+=hehe(i,j);
        }
    }
    printf("%d",f[0][(w+1)/2]);//f数组定义的是从i秒j地的最大分数
    return 0;
}

T3压缩：dp(★★★★★★★★★★★★★★★★★★★★★★★★★......)

呵呵，洛谷紫题，教练拿来当作入门题考，beng......

　　题目描述：

给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不是必需）包含大写字母R 与M ，其中 M 标记重复串的开始，重复从上一个 R（如果当前位置左边没有M ，则从串的开始算起）开始的解压结果（称为缓冲串）。
bcdcdcdcd可以压缩为bMcdRR。

　　输入格式：

输入仅一行，包含待压缩的字符串，仅包含小写字母，长度为n。

　　输出格式：

输出仅一行，即压缩后字符串的最短长度。

　　样例：

　　样例输入1：

aaaaaaa

　　样例输出1：

　　样例输入2：

bcdcdcdcdxcdcdcdcd

　　样例输出2：

　　50%的数据满足：1≤n≤20。

　　100%的数据满足：1≤n≤50。

　　分析：

设f[i][j][0]表示i到j的区间没有M的情况：
- 如果前半段与后半段相等，f[i][j][0] = min(f[i][j][0],f[i][mid][0]+1);
- 如果[i~j],但有可能[i~k](i<k<j)可以折叠，f[i][j][0] = min(f[i][j][0],f[i][k][0]+j-k);
f[i][j][1]表示i到j的区间内有M的情况：
- k枚举的是M的位置，即在k的后面放一个M：
- f[i][j][1] = min(f[i][j][1],min(f[i][k][0],f[i][k][1])+min(f[k+1][j][0],f[k+1][j][1]))
- 对区间[i , k]和[k+1,j]均有两种选择，然后加上M这个1。
最后输出ans = max（f[i][len][0],f[1][len][1]）。

#include <bits/stdc++.h>
using namespace std;
const int N=55;
char s[N];
int f[N][N][3];

bool judge(int l,int r){//判断前一半是否和后一半相等
    if((r-l+1)&1)return false;//长度为奇数
    int mid=(l+r)>>1;
    for(int i=l;i<=mid;i++)
        if(s[i]!=s[i+mid-l+1])return false;
    return true;
}


int main(){
    scanf("%s",s+1);
    int len = strlen(s+1);
    for(int i=1;i<=len;i++)//初始化为没有折叠
        for(int j=i;j<=len;j++)
            f[i][j][0]=f[i][j][1]=(j-i+1);
    for(int l=1;l<=len;l++){
        for(int i=1,j;(j=i+l)<=len;i++){//i为区间起点，j为区间终点
            if(judge(i,j))//区间[i,j]正好能折叠
                f[i][j][0]=min(f[i][(i+j)/2][0]+1,f[i][j][0]);
            for(int k=i;k<j;k++)//枚举区间的断点,有可能[i,k]能折叠
                f[i][j][0]=min(f[i][j][0],f[i][k][0]+j-k);    
            for(int k=i;k<j;k++)//枚举M的位置,即在k的后面加一个M
                f[i][j][1]=min(f[i][j][1],std::min(f[i][k][0],f[i][k][1])+min(f[k+1][j][0],f[k+1][j][1])+1);
        }
    }
    printf("%d\n",min(f[1][len][1],f[1][len][0]));
    return 0;
}

T4枪战Maf：（思维★★）

　　题目描述：

　　有 n

　　输出格式：

　　输出只有一行，共两行整数，为最后死亡的最小和最大人数。

8
2 3 2 2 6 7 8 5

　　样例格式：

3 5

　　分析：

　　设最大存活人数Max

#include<bits/stdc++.h>
using namespace std;
const int N=1000100;
int n;
int aim[N];
int Min,Max;
int q[N],rd[N];
bool die[N],live[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&aim[i]);
        rd[aim[i]]++;//存入度
    }
    for(int i=1;i<=n;i++){
        if(rd[i]==0){
            Min++;//最小必活数+1
            Max++;//队列维护的是入度为0的点
            q[Max]=i;
        }
    }
    int aa=1;
    while(aa<=Max){//扫描队列
        int front=q[aa++];//取出队首并出队
        if(die[aim[front]])continue;//队首目标已死(多个入度为0的点指向一个点)
        die[aim[front]]=1;//队首目标必死
        int faim=aim[aim[front]];//队首目标的目标可死可不死，看决策
        rd[faim]--;
        live[faim]=1;//可以让他活，但想死的时候随时可以让他死，在环可以最后死
        if(rd[faim]==0){//虽然入度为0，但不一定是必活，所以Min不加
            q[++Max]=faim;
        }
    }//下面处理只剩下环
    for(int i=1;i<=n;i++){
        if(rd[i]&&!die[i]){
            int l=0,flag=0;//l记录环大小,flag标记环上是否有live的点 
            for(int j=i;!die[j];j=aim[j]){
                l++;
                flag|=live[j];
                die[j]=1;//标记已死，避免其他的再来计算
            }
            if(!flag&&l>1)Min++;//l=1表示自环，必死
            Max+=l/2;
        }
    }
    printf("%d %d",n-Max,n-Min);
    return 0;
}

博主在没有任何编辑器的恶劣情况下成功夺得514高地（敲了一个多小时），点赞关注顶一下呗......@^_^@......

6.30集训模拟赛4(炸裂的一天qwq)

原文：https://www.cnblogs.com/LightyaChoo/p/13215436.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

6.30集训模拟赛4(炸裂的一天qwq)

T1浇水：

题目描述

输入格式

输出格式

样例

样例输入1

样例输出1

样例输入2

样例输出2

数据范围与提示

分析：

T2免费馅饼：

题目描述：

输入格式：

输出格式：

样例:

样例输入:

样例输出:

数据范围与提示:

分析：

T3压缩：dp(★★★★★★★★★★★★★★★★★★★★★★★★★......)

题目描述：

输入格式：

输出格式：

样例：

样例输入1：

样例输出1：

样例输入2：

样例输出2：

数据范围与提示：

分析：

T4枪战Maf：（思维★★）

题目描述：

输出格式：

样例输出：

样例格式：

分析：