Codeforces Round #538 (Div. 2) 解题报告

A Got Any Grapes?

顺序判断即

比赛的时候忘记写 else 既然 PP 了,然后就 FST

#include <cstdio>
int an,dm,mi;
int gr,pu,bl;
int main(){
    scanf("%d%d%d", &an, &dm, &mi);
    scanf("%d%d%d", &gr, &pu, &bl);
    if(an > gr) {
        printf("NO\n");
        return 0;
    }
    else gr -= an;
    if(pu + gr < dm){
        printf("NO\n");
        return 0;
    }
    else {
        if(pu <= dm) {dm -= pu; pu = 0;}
        else {pu -= dm; dm = 0;}
        if(gr < dm) {
            printf("NO\n");
            return 0;
        }
        else gr -= dm;
    }
    if(gr + pu + bl < mi) printf("NO\n");
    else printf("YES\n");
}
继续阅读“Codeforces Round #538 (Div. 2) 解题报告”

科学解决 RMQ 问题 — 线段树/(ST/稀疏表)/分块

RBQRMQ

区间最值问题
大概就是那种给你一串数字,然后问你在区间[l,r]内,求最小值或最大值 一般,我们的操作,就是暴力枚举 然后你就光荣的TLE/MLE 然后让我们来说说区间问题的三种解法—线段树/ST表与分块

线段树


预处理: O( n*log(n) )
查询: O( log(n) )
单点更新: 支持,不破坏查询复杂度
写的爽,调的更爽
线段树是一种数据结构 首先我们需要了解一种东西,哈弗曼树 显然,对于一颗二叉树,如果一个节点号为n那么它的左节点是2n,右节点是2n+1 然后我们就可以愉快的存树了 然后什么是线段树呢? 吃的 它是能够维护一定区间的树 他的根节点是[L,R](最左和最右)的最优值 然后左节点是[L,(L+R)/2]的最优值 右节点是[(L+R)/2+1,R]的最优值 往后以此类推 直到l==r为止 简单代码如下:
这个代码对应[https://www.luogu.org/problemnew/show/P4644]这道题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,e;
struct whi{
    int left,rig,cost;
}a[11000];
int f[110000];
int tree[11000000];
bool cmp(whi a,whi b){
    return a.rig<b.rig;
}
// 创建
void build(int p,int l,int r){// p 当前下标 l 左端点 r 右端点
    if(l==r) {tree[p]=f[l];return ;}
    build(p<<1,l,(l+r)>>1);
    build(p<<1|1,((l+r)>>1)+1,r);
    tree[p]=min(tree[p<<1],tree[p<<1|1]);
}
// 更新单点
void update(int p,int l,int r,int now,int val){// p 当前下表 l 当前左端点 r 当前右端点 now 当前点的边界 val 更新的值
    if(l==r&&l==now){tree[p]=val;return ;}
    if(now<=((l+r)>>1)) update(p<<1,l,(l+r)>>1,now,val);
    else update(p<<1|1,((l+r)>>1)+1,r,now,val);
    tree[p]=min(tree[p<<1],tree[p<<1|1]);
}
// 求区间最值
int query(int p,int l,int r,int ll,int rr){//p 当前下表  l 当前左端点 r 当前右端点 ll 需求左端点 rr 需求右端点
    if(ll<=l&&rr>=r){return tree[p];}
    int ans=0x7fffffff,mid=(l+r)>>1;
    if(ll<=mid) ans=min(ans,query(p<<1,l,mid,ll,rr));
    if(rr>mid) ans=min(ans,query(p<<1|1,mid+1,r,ll,rr));
    return ans;
}
int main(){
    memset(f,0x3f,sizeof(f));
    scanf("%d%d%d",&n,&m,&e);
    m++;e++;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].left,&a[i].rig,&a[i].cost);
        a[i].left++;a[i].rig++;
    }
    sort(a+1,a+n+1,cmp);
    /*for(int i=1;i<=n;i++){
        printf("%d %d %d\n",a[i].left,a[i].rig,a[i].cost);
    }*/
    f[m-1]=0;
    build(1,m-1,e);
    for(int i=1;i<=n;i++){
        if(a[i].rig<m) continue;
        if(a[i].left<=m) f[a[i].rig]=min(f[a[i].rig],a[i].cost);
        else f[a[i].rig]=min(f[a[i].rig],query(1,m-1,e,a[i].left-1,a[i].rig)+a[i].cost);
        update(1,m-1,e,a[i].rig,f[a[i].rig]);
    }
    if(f[e]>=1061109567) printf("-1");
    else printf("%d",f[e]);
}
当然这个并不是线段树的完整用法wq 更详细的用法,请看下篇题解

ST/稀疏表

> 速度虽快,更新却难
预处理: O( n*log(n) )
查询: O( 1 )
单点更新: 支持,需重新预处理
ST/稀疏表(以下统称)ST表,是一种基于倍增思想的玄学算法 比如说我们用f[i][j]储存从 i 位置开始的 2^j个数中的最大值 那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值 查询先计算出 log2(区间长度) 然后对于左端点和右端点分别进行查询,这样可以保证一定可以覆盖查询的区间 然后你就会发现一堆log和换底公式出现于你的程序中 感性理解吧~ 但是不难理解
对应例题:[https://www.luogu.org/problemnew/show/P3865]
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,l,r;
int a[110000];
int f[110000][110];
int st_query(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f[i][0]=a[i];
    }
    int t=log(n)/log(2)+1;
    for(int j=1;j<t;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        printf("%d\n",st_query(l,r));
    }
}
看起来是不是相当简单qwq 但是要千万注意log时该加1时不该加时不加1

分块


高端的模拟
预处理: O(n)
查询: O(sqrt(n))
更新: O(sqrt(n))
先说说什么是分块算法吧 分块,顾名思义,就是将一个数列分成几块单独处理,比如讲[1,5]分成三块就是[1,2] [3,4] [5]这三个 那么我们查找[1,3]的最小值,只需要查找第一个与第二个块的最小值 经过一些证明,我们可以知道,在分成sqrt(n)块的情况下最优 所以就有了复杂度中的一堆sqrt(n) 那么代码我相信大家心里都有数了 那么和线段树一样,代码下篇题解讲,毕竟都是一道题目嘛wq

End


这几种解法,只是一种板子,而真正的RMQ算法,可能会结合多种东西,或者被多种东西所结合,所以说活学活用是最重要的,无论如何,刷题是最重要的 “Happy Coding Life” ]]>