考试策略

这个里面的花,我看了一下,啊,T2和T3是比较简单的原题啊,匆匆写完过了对拍,看了一下T4,T4有思路但是这个离散太恶心了有点思考不清楚,怕写错就打了暴力。T1完全没思路就打了暴力。

T1

期望得分:20 实际得分:0
题目描述
我们生活的星球对于整个宇宙来说,只不过是沧海一粟,宇宙到底有多大,到现在还没人知道,其实我们无时无刻不在面临着来自外太空的威胁,当然你也不会知道在我们的身边,有很多人自愿参加了一个叫 FLYIOI 的秘密组织,QZC 就是其中一员,公元 2007 年 4 月 21日早上 8:00,他截获了一份来自外太空的信息,这份信息是一大串毫无规律的数字,在众多大牛的努力帮助之下,QZC终于发现这是来自OIBH星球的一份密文,由于QZC经常去OIBH星球参观访问,附带潜水旅游,所以很快知道了他的加密格式。
密文的格式如下:
在第一行有两个数,不妨设为 N,M。
第二行有 N 个数,设为 a1,a2,……,an。
接下来有 M 行,每行有三个数字设为 x,y,z。
如果对于 M 行的每一行 x,y,z,得到一个数字 Q,Q 代表有多少个不同的数字,在 ax…ay和 ay+1…az 中都不得出现过,将这 M 个数字顺次连起来,就是解密后的信息。保卫世界和平的任务就落在你的肩上了,请你编写一个数字统计程序来解开来自 OIBH 星球的密文。
数据范围
对于 20%的数据,N<=1000,M<=1000;
对于 100%的数据,N<=200000,M<=40000;0<=ai<=Maxlongint。
题目分析
感谢pyh大佬的帮助。
pyh大佬说,假如某一元素在序列里出现了若干次,位置为a1,a2…an,我们就在平面上建立点(a1,a2),(a2,a3),(a3,a4)….[我的思路是离散出现的数字]
然后对于每一个询问(x,y,z),建立一个左上角坐标为(x,z),右下角坐标为(y,y+1)的矩形,然后求里面的点的数量即可。
为什么呢?因为我们要求相同元素的两个区间是相邻的,所以我们从左区间拿一个该元素,右区间拿一个,如果他们中间还有一个该元素,就不会被计算,如果没有,才会被计算。这就皆大欢喜了,不会重复计算元素呢。
那么我们要怎么求呢?pyh大佬提供的思路是扫描线。对于每一个矩形,我们可以看作是在其右边界限以前的所有点数-在其左边界限以前的所有点数。这样我们把点和矩形的线从小到大排个序后,加点进一个树状数组,加的位置是其y坐标的位置,然后看矩形的界限上下y坐标统计点的个数,即可很快的求出答案。
最后%%%pyh大佬。
代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
const int N=200005,M=40005;
int n,m,cn,ds,bs;
int a[N],b[N],pre[N],in[M],le[M],tr[N];
struct nn{int x,y;}po[N];
struct node{int xx,ll,rr,id,num;}s[M<<1];
bool cmp1(nn s,nn t){return s.x<t.x;}
bool cmp2(node s,node t){return s.xx<t.xx;}
int lowbit(int x){return x&(-x);}//树状数组
void add(int x){while(x<=n)++tr[x],x+=lowbit(x);}
int find(int x){
    int re=0;
    while(x>0)re+=tr[x],x-=lowbit(x);
    return re;
}
void work(){//扫描线
    int now=1,i;
    for(i=1;i<=bs;++i){
        while(po[now].x<=s[i].xx&&now<=ds)add(po[now].y),++now;
        if(s[i].num==1)in[s[i].id]=find(s[i].rr)-find(s[i].ll-1);
        else le[s[i].id]=find(s[i].rr)-find(s[i].ll-1);
    }
    for(i=1;i<=m;++i)printf("%d",le[i]-in[i]);
}
int main(){
    freopen("secret.in","r",stdin);
    freopen("secret.out","w",stdout);
    int i,kx,ky,kz;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    cn=1;for(i=2;i<=n;++i)if(b[i]!=b[cn])b[++cn]=b[i];//离散出现的数字
    for(i=1;i<=n;++i){
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
        if(pre[a[i]])po[++ds].x=pre[a[i]],po[ds].y=i;
        pre[a[i]]=i;
    }
    for(i=1;i<=m;++i){
        scanf("%d%d%d",&kx,&ky,&kz);
        s[++bs].xx=kx-1,s[bs].ll=ky+1,s[bs].rr=kz,s[bs].id=i,s[bs].num=1;//建立扫描线
        s[++bs].xx=ky,s[bs].ll=ky+1,s[bs].rr=kz,s[bs].id=i,s[bs].num=-1;
    }
    sort(po+1,po+1+ds,cmp1);sort(s+1,s+1+bs,cmp2);
    work();
    return 0;
}

T2

期望得分:100 实际得分:100
题目描述
由于你即将参加选拔赛,会有麻烦的问题等你解决,不过之前,我们还是请你先解决下面的问题,问题很简单:
有一个长度为 L 的长木板,将其均匀的分成 L 段,从 1…L 标号,可以对木板进行下列两种操作
C(A, B, C) 将第 A 段到第 B 段全部涂成颜色 C
P(A, B) 计算第 A 段到第 B 段间不同的颜色数(包含 A 和 B 段)
颜色从 1..T 开始顺次表示,最开始的时候整个木板被涂成颜色 1。
数据范围
第一行 L(1≤L≤100000), T(1≤T≤30), O(1≤O≤10000)表示木板的段数,颜色总数和
操作的个数。接下来 O 行,每行包含上述两种操作之一。
题目分析
状态压缩,用一个二进制数来表示一段区间内颜色的集合,最后求出颜色集合,并统计其中颜色个数即可。
有一个坑点,就是数据里有右区间大于左区间的情况,要注意特判。
代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int n,t,m;
int c[N<<2],laz[N<<2],bin[32];
void up(int i){c[i]=c[i<<1]|c[(i<<1)|1];}
void pd(int i){
    int l=(i<<1),r=(i<<1)|1;
    laz[l]=laz[r]=laz[i],c[l]=c[r]=bin[laz[i]];
    laz[i]=0;
}
void chan(int l,int r,int s,int t,int i,int z){
    if(l<=s&&t<=r){laz[i]=z,c[i]=bin[z];return;}
    int mid=(s+t)>>1;
    if(laz[i])pd(i);
    if(l<=mid)chan(l,r,s,mid,i<<1,z);
    if(mid+1<=r)chan(l,r,mid+1,t,(i<<1)|1,z);
    up(i);
}
int query(int l,int r,int s,int t,int i){
    if(l<=s&&t<=r)return c[i];
    int mid=(s+t)>>1,re=0;
    if(laz[i])pd(i);
    if(l<=mid)re=query(l,r,s,mid,i<<1);
    if(mid+1<=r)re=re|query(l,r,mid+1,t,(i<<1)|1);
    return re;
}
void build(int s,int t,int i){
    if(s==t){c[i]=1;return;}
    int mid=(s+t)>>1;
    build(s,mid,i<<1),build(mid+1,t,(i<<1)|1);
    up(i);
}
int find(int x){
    int re=0;
    while(x){x-=(x&(-x));++re;}
    return re;
}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int i,x,y,z;char ch[5];
    scanf("%d%d%d",&n,&t,&m);
    build(1,n,1);
    bin[1]=1;
    for(i=2;i<=t;++i)bin[i]=bin[i-1]<<1;
    for(i=1;i<=m;++i){
        scanf("%s",ch);
        if(ch[0]=='C'){
            scanf("%d%d%d",&x,&y,&z);
            if(y<x)swap(x,y);
            chan(x,y,1,n,1,z);
        }
        else {
            scanf("%d%d",&x,&y);
            if(y<x)swap(x,y);
            printf("%dn",find(query(x,y,1,n,1)));
        }
    }
    return 0;
}

T3

期望得分:100 实际得分:100
题目描述
XXX 最近的旅游计划,是到 XXXX 湖畔,享受那里的湖光山色,以及明媚的阳光。你作为整个旅游的策划者和负责人,选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50000)间客房,它们在同一层楼中顺次一字排开,在任何一个房间里,只需要拉开窗帘,就能见到波光粼粼的湖面。
所有的旅游者,都是一批批地来到旅馆的服务台,希望能订到 Di (1 <= Di <= N)间连续的房间。服务台的接待工作也很简单:如果存在 r 满足编号为 r..r+Di-1 的房间均空着,他就将这一批顾客安排到这些房间入住;如果没有满足条件的 r,他会道歉说没有足够的空房间,请顾客们另找一家宾馆。如果有多个满足条件的 r,服务员会选择其中最小的一个。
旅馆中的退房服务也是批量进行的。每一个退房请求由 2 个数字 Xi、Di 描述,表示编号为 Xi..Xi+Di-1 (1 <= Xi <= N-Di+1)房间中的客人全部离开。退房前,请求退掉的房间中的一些,甚至是所有,可能本来就无人入住。
你的工作,就是写一个程序,帮服务员为旅客安排房间。你的程序一共需要处理 M (1 <=M <=50000)个按输入次序到来的住店或退房的请求。第一个请求到来前,旅店中所有房间都是空闲的。
题目分析
区间线段树,维护一个区间从左边开始数最多连续空房数量和从右边开始数的,那么对于一个区间[x,y],将其分为[x,mid]和[mid+1,y]后,最多连续空房数是左边区间最多连续空房数,右边区间最多连续空房数,跨越两个子区间的最多连续空房数的最大值。
这样就easy了,退房很简单,入住的花只要左区间房间苟去左区间找,否则看跨越两个子区间的区间,否则看右区间这样的顺序寻找即可。注意寻找的时候如果找到了一个s==t(意思看代码),要return否则会RE
代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=50005;
int num[N<<2],ls[N<<2],rs[N<<2],laz[N<<2];
//1:empty 2:you ren
int n,m;
void pd(int i,int s,int t){
    int l=i<<1,r=(i<<1)|1,mid=(s+t)>>1;
    laz[l]=laz[r]=laz[i];
    if(laz[i]==1){
        num[l]=ls[l]=rs[l]=mid-s+1;
        num[r]=ls[r]=rs[r]=t-mid;
    }
    else {
        num[l]=ls[l]=rs[l]=0;
        num[r]=ls[r]=rs[r]=0;
    }
    laz[i]=0;
}
void up(int i,int s,int t){
    int l=i<<1,r=(i<<1)|1,mid=(s+t)>>1;
    num[i]=max(num[l],num[r]);
    if(rs[l]+ls[r]>num[i])num[i]=rs[l]+ls[r];
    ls[i]=ls[l];
    if(ls[l]==mid-s+1)ls[i]+=ls[r];
    rs[i]=rs[r];
    if(rs[r]==t-mid)rs[i]+=rs[l];
}
int query(int x,int s,int t,int i){
    if(s==t)return s;//注意别漏了这句
    int mid=(s+t)>>1;
    if(laz[i])pd(i,s,t);
    if(num[i<<1]>=x)return query(x,s,mid,i<<1);
    if(rs[i<<1]+ls[(i<<1)|1]>=x)return mid-rs[i<<1]+1;
    return query(x,mid+1,t,(i<<1)|1);
}
void chan(int l,int r,int s,int t,int i,int z){
    if(l<=s&&t<=r){
        laz[i]=z+1;
        if(!z)num[i]=ls[i]=rs[i]=t-s+1;
        else num[i]=ls[i]=rs[i]=0;
        return;
    }
    if(laz[i])pd(i,s,t);
    int mid=(s+t)>>1;
    if(l<=mid)chan(l,r,s,mid,i<<1,z);
    if(mid+1<=r)chan(l,r,mid+1,t,(i<<1)|1,z);
    up(i,s,t);
}
void build(int s,int t,int i){
    if(s==t){ls[i]=rs[i]=num[i]=1;return;}
    int mid=(s+t)>>1;
    build(s,mid,i<<1),build(mid+1,t,(i<<1)|1);
    up(i,s,t);
}
int main()
{
    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);
    int i,x,y,bj,re;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(i=1;i<=m;++i){
        scanf("%d",&bj);
        if(bj==1){
            scanf("%d",&x);
            if(num[1]<x)printf("0n");
            else {
                re=query(x,1,n,1);printf("%dn",re);
                chan(re,re+x-1,1,n,1,1);
            }
        }
        else {
            scanf("%d%d",&x,&y);
            chan(x,x+y-1,1,n,1,0);
        }
    }
    return 0;
}

T4

期望得分:50 实际得分:52
题目描述
Mountain Amusement公园新添了一台过山车,模拟轨道由n个首尾相连的铁轨构成,第一根铁轨的首端的高度为0。操作员Byteman可以随意调整一些铁轨两端的高度差,而其他铁轨两端的高度差不受影响。每当一根铁轨的高度差被调整后,与它相连的下一根铁轨将相应地被抬高或被降低,而其首端与前一根铁轨的尾端高度差仍然为0。下一页的图示说明了轨道调整的两个例子。
过山车的每次运行都被赋予能达到高度h的能量。这就是说,只要高度不超过h,过山车就将一直前进,直至终点。给出每天过山车运行和轨道调整的记录,计算出每次过山车在停止前通过的轨道的长度。
在内部,模拟器将轨道表示为n段铁轨两端高度差的序列。第i个数di表示第i段铁轨两端的高度差(单位为厘米)。假定在通过第i−1段铁轨后的过山车的高度为 h厘米,在经过第i段铁轨后,其高度将达到h+di厘米。
开始时所有的铁轨都是水平的,也就是说,对所有的i, di = 0。过山车的运行和轨道的调整在一天之中交错进行。每次轨道调整由三个数描述,a、b、和D。被调整的区间包含
从a到b的所有铁轨(a和b都包括在内)。区间内的每根铁轨两端的高度差都被设置为D。这也就是说,对于所有的a<= i<= b , di = D 。
每一次过山车的运行用一个数h来表示过山车所能到达的最大高度。
任务
写出程序
从标准输入上读入交错输入的轨道调整和过山车运行的数据。
对过山车的每一次运行,计算它所能通过的铁轨的数量。
将结果写到标准输出上。
数据范围
输入第一列包含一个正整数n,1 <= n <=1,000,000,000,表示过山车的运行次数。以
下各行交错包含着轨道调整和过山车运行的数据,以及结束符。每一行可以是下列情况之一:
– 轨道的调整:单个字符 “I” 以及整数a, b和D,及由单个空格符分隔(1 <= a <= b
<= n, −1,000,000,000 <= D <= 1,000,000,000)。
– 过山车的运行:单个字符 “Q” 和整数h (0 <= h <= 1,000,000,000)由单个空格
符分隔。
– 单个字符 “E”:结束符。说明输入数据结束。
你可以假定在任何时候,任何点的高度都在[0, 1,000,000,000]厘米之内。输入数据不超
过100,000行。
50%的数据保证1 <=n <=20,000,以及输入数据不超过1,000行。


题目分析
一开始虽然想到了线段树解法,但奈何离散使我面目全非,最后只打了暴力……
那么这个里面的花,离散要怎么搞呢?
离开了代码根本不好讲,大约是首先将所有修改区间弄成左闭右开区间(为什么之后就知道了),然后离散要用到的区间节点,离散数组a,线段树中[s,t]表示[a[s],a[t]-1]这一段(明白为什么是左闭右开了吧),这样线段树左右子树应该是[s,mid]和[mid,t]而不是我们常用的[s,mid]和[mid+1,t]。
然后线段树维护的是表明每一个铁轨左右高度差的数组,需要维护:sum区间和,ma区间高度最大值。注意,如果我们只考虑[s,t]区间,我们可以运用物理里常说的”转换参考系“的技巧,即把最左端的铁轨的左端看作高度为0.这样的花在pushup这个ma的时候应该是:ma[i]=max(ma[左子树],sum[左子树]+ma[右子树]),以此类推。
然后查询时,如果左边区间的ma要比h高的花,车在左边区间就停下来了,就去左边区间找,否则去右边找,并根据参考系的调整对一些参数进行相应的调整(具体看代码)
这题在实现上有很多值得注意的细节,都在代码里打出注释表明了。


代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define LL long long
const int N=100005,inf=-(1e9+1);
int a[N<<1],cn=1;
int x[N],y[N],z[N];
LL ma[N<<3],sum[N<<3],laz[N<<3];
int n,m;
void make(int i,LL l,LL h){
    sum[i]=h*l,laz[i]=h;
    if(h<0)ma[i]=h;//注意这里
    else ma[i]=sum[i];
}
void pd(int i,int s,int t){
    int l=i<<1,r=(i<<1)|1,mid=(s+t)>>1;
    make(l,a[mid]-a[s],laz[i]),make(r,a[t]-a[mid],laz[i]);
    laz[i]=inf;
}
void chan(int l,int r,int s,int t,int i,int zz){
    if(l<=a[s]&&a[t]<=r){make(i,a[t]-a[s],zz);return;}
    int mid=(s+t)>>1;
    if(laz[i]!=inf)pd(i,s,t);
    if(l<a[mid])chan(l,r,s,mid,i<<1,zz);
    if(r>a[mid])chan(l,r,mid,t,(i<<1)|1,zz);
    sum[i]=sum[i<<1]+sum[(i<<1)|1];
    ma[i]=max(ma[i<<1],sum[i<<1]+ma[(i<<1)|1]);
}
void query(int h,int s,int t,int i){
    if(s==t-1){
        int re=a[t];
        if(laz[i]>0)re=a[s]+h/laz[i];//laz[i]就是a[s]~a[t]-1中铁轨高度
        //不能写laz[i]!=inf,否则等着除以0来RE吧 
        if(re-1<=a[n]-1)printf("%d\n",re-1);//注意特判,有可能延伸出了a[n]-1啊 
        else printf("%d\n",a[n]-1);
        return;
    }
    int mid=(s+t)>>1;
    if(laz[i]!=inf)pd(i,s,t);
    if(h<ma[i<<1])query(h,s,mid,i<<1);
    else query(h-sum[i<<1],mid,t,(i<<1)|1);
}
int main(){
    freopen("mou.in","r",stdin);
    freopen("mou.out","w",stdout);
    char ch[5];int i;
    scanf("%d",&a[1]);++a[1];//s~t:从a[s]到a[t]-1.
    while(1){
        scanf("%s",ch);
        if(ch[0]=='E')break;
        ++m;
        if(ch[0]=='I'){
            scanf("%d%d%d",&x[m],&y[m],&z[m]);//改成左闭右开区间
            if(y[m]<x[m])swap(x[m],y[m]);
            ++y[m];a[++cn]=x[m],a[++cn]=y[m];
        }
        else scanf("%d",&z[m]);
    }
    sort(a+1,a+1+cn);
    n=1;for(i=2;i<=cn;++i)if(a[i]!=a[n])a[++n]=a[i];
    for(i=1;i<(N<<3);++i)laz[i]=inf;
    for(i=1;i<=m;++i){
        if(x[i])chan(x[i],y[i],1,n,1,z[i]);
        else query(z[i],1,n,1);
    }
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *