T1浇水：

　　题目描述

　　在一条长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+;

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=;i<=k;i++){

        scanf("%d%d",&a,&r);

        if(r*<=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+,w++cnt,cmp);//排序

    double right=;

    int ans=;

    while(right<n){//

        ans++;

        double s=right;//用一个s保存right值因为后面的right值要变

        for(int i=;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 ;

        }

    }

    printf("%d\n",ans);

    return ;

}

T2免费馅饼：

　　题目描述：

最新推出了一种叫做“免费馅饼”的游戏:
游戏在一个舞台上进行。舞台的宽度为 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=;

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=;

    for(int k=-;k<=;k++){

        if(j+k<||j+k>w)continue;

        ans=max(ans,f[i+][j+k]);

    }

    return ans;

}

int main(){

    scanf("%d%d",&w,&h);

    h--;//注意减一

    while(scanf("%d%d%d%d",&T,&P,&V,&W)==){

        if(h%V==){

            t[++cnt]=T+h/V;//注意+T;

            p[cnt]=P;v[cnt]=V;val[cnt]=W;

            maxtime=max(maxtime,t[cnt]);//找出下落时间最大的值来

        }

    }

    if(cnt==){//如果都不符合那就结束

        printf("");

        return ;

    }

    for(int i=;i<=cnt;i++){//可能有不同时出发的但同时同地落下的馅饼。累加。

        f[t[i]][p[i]]+=val[i];

    }

    for(int i=maxtime-;i>=;i--){//从后往前

        for(int j=w;j>=;j--){//maxtime注意减一因为转移有范围。

            f[i][j]+=hehe(i,j);

        }

    }

    printf("%d",f[][(w+)/]);//f数组定义的是从i秒j地的最大分数

    return ;

}

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=;

char s[N];

int f[N][N][];

bool judge(int l,int r){//判断前一半是否和后一半相等

    if((r-l+)&)return false;//长度为奇数

    int mid=(l+r)>>;

    for(int i=l;i<=mid;i++)

        if(s[i]!=s[i+mid-l+])return false;

    return true;

}

int main(){

    scanf("%s",s+);

    int len = strlen(s+);

    for(int i=;i<=len;i++)//初始化为没有折叠

        for(int j=i;j<=len;j++)

            f[i][j][]=f[i][j][]=(j-i+);

    for(int l=;l<=len;l++){

        for(int i=,j;(j=i+l)<=len;i++){//i为区间起点，j为区间终点

            if(judge(i,j))//区间[i,j]正好能折叠

                f[i][j][]=min(f[i][(i+j)/][]+,f[i][j][]);

            for(int k=i;k<j;k++)//枚举区间的断点,有可能[i,k]能折叠

                f[i][j][]=min(f[i][j][],f[i][k][]+j-k);

            for(int k=i;k<j;k++)//枚举M的位置,即在k的后面加一个M

                f[i][j][]=min(f[i][j][],std::min(f[i][k][],f[i][k][])+min(f[k+][j][],f[k+][j][])+);

        }

    }

    printf("%d\n",min(f[][len][],f[][len][]));

    return ;

}

T4枪战Maf：（思维★★）

　　题目描述：

　　有 n个人，用1～n进行编号，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。

　　输入格式：

　　输入n 人数n<1000000
接下来n个数，依次为每个人的aim。

　　输出格式：

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

　　样例输出：

　　样例格式：

　　分析：

　　设最大存活人数Max，最少存活人数Min

#include<bits/stdc++.h>

using namespace std;

const int N=;

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=;i<=n;i++){

        scanf("%d",&aim[i]);

        rd[aim[i]]++;//存入度

    }

    for(int i=;i<=n;i++){

        if(rd[i]==){

            Min++;//最小必活数+1

            Max++;//队列维护的是入度为0的点

            q[Max]=i;

        }

    }

    int aa=;

    while(aa<=Max){//扫描队列

        int front=q[aa++];//取出队首并出队

        if(die[aim[front]])continue;//队首目标已死(多个入度为0的点指向一个点)

        die[aim[front]]=;//队首目标必死

        int faim=aim[aim[front]];//队首目标的目标可死可不死，看决策

        rd[faim]--;

        live[faim]=;//可以让他活，但想死的时候随时可以让他死，在环可以最后死

        if(rd[faim]==){//虽然入度为0，但不一定是必活，所以Min不加

            q[++Max]=faim;

        }

    }//下面处理只剩下环

    for(int i=;i<=n;i++){

        if(rd[i]&&!die[i]){

            int l=,flag=;//l记录环大小,flag标记环上是否有live的点 

            for(int j=i;!die[j];j=aim[j]){

                l++;

                flag|=live[j];

                die[j]=;//标记已死，避免其他的再来计算

            }

            if(!flag&&l>)Min++;//l=1表示自环，必死

            Max+=l/;

        }

    }

    printf("%d %d",n-Max,n-Min);

    return ;

}

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

巴特西

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

T1浇水：

题目描述

输入格式

输出格式

样例

样例输入1

样例输出1

样例输入2

样例输出2

数据范围与提示

分析：

T2免费馅饼：

题目描述：

输入格式：

输出格式：

样例:

样例输入:

样例输出:

数据范围与提示:

分析：

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

题目描述：

输入格式：

输出格式：

样例：

样例输入1：

样例输出1：

样例输入2：

样例输出2：

数据范围与提示：

分析：

T4枪战Maf：（思维★★）

题目描述：

输入格式：

输出格式：

样例输出：

样例格式：

分析：

最新文章

热门文章

　　题目描述

　　输入格式

　　输出格式

　　样例

　　样例输入1

　　样例输出1

　　样例输入2

　　样例输出2

　　数据范围与提示

　　分析：

　　题目描述：

　　输入格式：

　　输出格式：

　　样例:

　　样例输入:

　　样例输出:

　　数据范围与提示:

　　分析：

　　题目描述：

　　输入格式：

　　输出格式：

　　样例：

　　样例输入1：

　　样例输出1：

　　样例输入2：

　　样例输出2：

　　数据范围与提示：

　　分析：

　　题目描述：

　　输入格式：

　　输出格式：

　　样例输出：

　　样例格式：

　　分析：