博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
2019-8-5 考试总结
阅读量：5267 次
发布时间：2019-06-14

本文共 11046 字，大约阅读时间需要 36 分钟。

A. 矩阵游戏

是个水题，但是还是想了很长时间。

每个点对答案的贡献是$A[i][j]\times H[i]\times Z[j]$，

然后这个$sum$就是$\sum A[i][j]\times H[i]\times Z[j]$，

把$H[i]$提出来，也就是$\sum (H[i]\times \sum A[i][j]\times Z[j])$，

这个$A[i][j]$是有规律的，

这一行和上一行的差值就是$m\times \sum Z[j]$，

然后就可以逐行转移了。

最后是$O(n)$的。

丑陋的代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define Maxn 1000050#define Reg register#define INF 0x7ffffff#define int long long#define mod 1000000007using namespace std;int n,m,k,sum=0,ans=0,H[Maxn],Z[Maxn],dp[Maxn];string s;signed main(){    scanf("%lld%lld%lld",&n,&m,&k);    for(Reg int i=1;i<=n;++i) H[i]=Z[i]=1;    for(Reg int i=1;i<=m;++i) H[i]=Z[i]=1;    for(Reg int i=1,x,y;i<=k;++i)    {        cin>>s;        scanf("%lld%lld",&x,&y);        if(s[0]=='R') H[x]=(H[x]*y)%mod;        else Z[x]=(Z[x]*y)%mod;    }    for(Reg int i=1;i<=m;++i)    {        dp[1]=(dp[1]+i*Z[i]%mod)%mod;        sum=(sum+Z[i])%mod;    }    for(Reg int i=2;i<=n;++i)        dp[i]=(dp[i-1]+m*sum%mod)%mod;    for(Reg int i=1;i<=n;++i)        ans=(ans+H[i]*dp[i]%mod)%mod;    printf("%lld",ans);    return 0;}
View Code

 

B. 跳房子

正解：

看到$n$和$m$这么小，$k$这么大，这里面肯定有玄机。

所以就找循环节。。。

前$20$到$25$分可以暴力拿到。

后面的$50$到$60$分可以找循环节拿到。

正解用了分块的思想。

第一列跳$m$次又回到了第一列。

所以这样可以节省很多时间。

预处理出第一列的第$i$个点下一次到达的点$jump[i]$。

每次移动的时候只需先把棋子移动到第一列，然后再整块整块地移动。

这里也可以找循环节。

最后不满$m$步的要一步步地走。

修改的时候只需要第一列的$jump$即可。

咨询$Mr\_ zkt$大神，得到这么一个结论：到达一个点$(i,j)$的所有第一列的点一定是连续的。

稍微感性的理解一下。

假设现在有$1$个点，有$3$个点可以到达它，举个例子，

如果最上面的点和最下面的点都要走它的话，那么它在本列$5$个格子中是最大的，中间的格子肯定走它。

情况拓展到多个连续的格子。

所以我们找到要修改的点的左侧三个点。

对这三个点更改，找这三个点的上下界，然后各自更改成这个点到达的位置。

上下界要分开计算，最后会出现$2$中情况，

一种$max$在上，将$[1,min]$和$[max,n]$更改，

一种$max$在下，将$[min,max]$更改。

说起来简单，调代码。。。

丑陋的代码：

#include
      
       #include
       
        #include
        
         #include
         
          #define Maxn 2050#define Reg register#define INF 0x7ffffffffff#define int long long#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))using namespace std;bool vis[Maxn][Maxn];int n,m,add,q,mx,mn,typ,jump[Maxn],A[Maxn][Maxn],stack[Maxn],vap[Maxn];string s;int get_next(int x,int y){    int Nexy=(y+1)>m?1:(y+1);    int Nex[3]={(x-1)<1?n:(x-1),x,(x+1)>n?1:(x+1)};    int P[3]={A[Nex[0]][Nexy],A[Nex[1]][Nexy],A[Nex[2]][Nexy]};    if(P[0]>P[1]&&P[0]>P[2]) return Nex[0];    else if(P[1]>P[2]&&P[1]>P[0]) return Nex[1];    else return Nex[2];}int dfs(int x,int y,int cnt){    if(x==0) return 0;    if(y==1&&cnt!=0) return x;    return dfs(get_next(x,y),(y+1)>m?1:(y+1),cnt+1);}void move(int &x,int &y,int cnt){    while(y!=1&&cnt>=1)    {        x=get_next(x,y),y=(y+1)>m?1:(y+1);        --cnt;    }    while(cnt>=m)    {        stack[0]=0;        int p=0;        while(cnt>=m&&!vap[x])        {            vap[x]=p;            stack[++stack[0]]=x;            x=jump[x];            cnt-=m; ++p;        }        if(cnt>=m)        {            cnt-=m,++p; x=jump[x];            cnt%=(p*m-vap[x]*m);        }        for(Reg int i=1;i<=stack[0];++i) vap[stack[i]]=0;        stack[0]=0;    }    while(cnt>=1)    {        x=get_next(x,y),y=(y+1)>m?1:(y+1);        --cnt;    }    return;}bool get_pre(int x,int y,int opt){    #define judge(x,y,z) (get_next(x,y)==z)    if(y==1)    {        if(opt==1) mx=max(mx,x);        else mn=min(mn,x);        return 1;    }    int Prey=(y-1)<1?m:(y-1);    int Pre[3]={(x-1)<1?n:(x-1),x,(x+1)>n?1:(x+1)};    if(opt==1)    {        if(judge(Pre[2],Prey,x)) {
    if(get_pre(Pre[2],Prey,opt)) return 1;}        if(judge(Pre[1],Prey,x)) {
    if(get_pre(Pre[1],Prey,opt)) return 1;}        if(judge(Pre[0],Prey,x)) {
    if(get_pre(Pre[0],Prey,opt)) return 1;}    }    else    {        if(judge(Pre[0],Prey,x)) {
    if(get_pre(Pre[0],Prey,opt)) return 1;}        if(judge(Pre[1],Prey,x)) {
    if(get_pre(Pre[1],Prey,opt)) return 1;}        if(judge(Pre[2],Prey,x)) {
    if(get_pre(Pre[2],Prey,opt)) return 1;}    }    return 0;}void change(int x,int y,int z){    int Prey=(y-1)<1?m:(y-1);    int Pre[3]={(x-1)<1?n:(x-1),x,(x+1)>n?1:(x+1),};    int O[3];    for(Reg int i=0;i<3;++i) O[i]=dfs(Pre[i],Prey,0);    A[x][y]=z;        for(Reg int i=0,k;i<3;++i)    {        mx=-INF,mn=INF;        k=dfs(Pre[i],Prey,0);        if(k==O[i]) continue;        get_pre(Pre[i],Prey,0);        get_pre(Pre[i],Prey,1);        if(mx==-INF||mn==INF) continue;        if(mx
          
           >s;        if(s=="move")        {            int k; scanf("%lld",&k);            move(sx,sy,k);            printf("%lld %lld\n",sx,sy);        }        else        {            int x,y,z; scanf("%lld%lld%lld",&x,&y,&z);            change(x,y,z);        }    }    return 0;}
View Code

还有一种做法叫置换(蒟蒻不会)。

跑起来很快。

 

C. 优美序列

一开始想的莫队(为啥他们都先想到分治)，

想到可以向左右拓展，所以就朝莫队的方向想了。

最后发现，其实莫队还不如直接暴力。

开$2$颗线段树，一个是区间内的编号的最值，一个是一段编号的位置的最值。

每个询问直接找最远的两个值，向左向右拓展。

最后得到$80$分$TLE$。

丑陋的代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define int long long#define Maxn 100050#define Reg register#define INF 0x7ffffff#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))using namespace std;int n,m,ansm,ansn,maxx,minn,A[Maxn],pos[Maxn];struct Tree {Tree *lch,*rch; int mx,mn;};Tree *New(){    Tree *p=new Tree;    p->lch=p->rch=NULL;    p->mx=-INF,p->mn=INF;    return p;}Tree *rot1=New(),*rot2=New();void up(Tree *p){    p->mx=-INF,p->mn=INF;    if(p->lch!=NULL)    {        p->mx=max(p->lch->mx,p->mx);        p->mn=min(p->lch->mn,p->mn);    }    if(p->rch!=NULL)    {        p->mx=max(p->rch->mx,p->mx);        p->mn=min(p->rch->mn,p->mn);    }    return;}void build(Tree **p,int l,int r){    if(*p==NULL) *p=New();    if(l==r)    {        (*p)->mx=(*p)->mn=pos[l];        return;    }    int mid=(l+r)>>1;    if(l<=mid) build(&((*p)->lch),l,mid);    if(mid+1<=r) build(&((*p)->rch),mid+1,r);    up(*p);    return;}void bup(Tree **p,int l,int r){    if(*p==NULL) *p=New();    if(l==r)    {        (*p)->mx=(*p)->mn=A[l];        return;    }    int mid=(l+r)>>1;    if(l<=mid) bup(&((*p)->lch),l,mid);    if(mid+1<=r) bup(&((*p)->rch),mid+1,r);    up(*p);    return;}void ask(Tree *p,int l,int r,int sol,int sor){    if(p==NULL||(p->mx<=ansm&&p->mn>=ansn)) return;    if(sol<=l&&r<=sor)    {        ansm=max(ansm,p->mx);        ansn=min(ansn,p->mn);        return;    }    int mid=(l+r)>>1;    if(sol<=mid) ask(p->lch,l,mid,sol,sor);    if(mid+1<=sor) ask(p->rch,mid+1,r,sol,sor);    return;}void query(Tree *p,int l,int r,int sol,int sor){    if(p==NULL||(p->mx<=maxx&&p->mn>=minn)) return;    if(sol<=l&&r<=sor)    {        maxx=max(maxx,p->mx);        minn=min(minn,p->mn);        return;    }    int mid=(l+r)>>1;    if(sol<=mid) query(p->lch,l,mid,sol,sor);    if(mid+1<=sor) query(p->rch,mid+1,r,sol,sor);    return;}signed main(){//    freopen("text.in","r",stdin);    scanf("%lld",&n);    for(Reg int i=1;i<=n;++i)    {        scanf("%lld",&A[i]);        pos[A[i]]=i;    }    build(&rot1,1,n); bup(&rot2,1,n);    scanf("%lld",&m);    for(Reg int i=1,l,r;i<=m;++i)    {        maxx=-INF,minn=INF;        scanf("%lld%lld",&l,&r);        query(rot2,1,n,l,r);        int ln=l,rn=r;        while(1)        {            if(maxx-minn==rn-ln||(ln==1&&rn==n))            {                printf("%lld %lld\n",ln,rn);                break;            }            ansm=-INF,ansn=INF;            ask(rot1,1,n,minn,maxx);            ln=ansn,rn=ansm;            query(rot2,1,n,ln,rn);        }    }    return 0;}
View Code

正解：

这个区间是优美序列的条件是$max-min=r-l$，

然后就是玄学的操作，

把每两个数值相差$1$的元素称作一个二元组。

那么一个区间就会有$r-l$个二元组。

枚举右端点，维护一个后缀和$val[i]$表示$i$节点到$r$节点的二元组个数。

每次向右拓展$r$，那么相应的$num[r]-1$和$num[r]+1$的二元组个数会增加$1$。

那么我们维护后缀和，

如果$num[r]-1$和$num[r]+1$在这个序列里，就把$1$到它们的位置上的数值加一。

最后如果$val[i]+l=r$，那么$i$到$r$的序列就是合法的。

还要维护一个区间最大值的位置。

 

对于每个询问，离线操作，对它们按照$l$从大到小排序，存入一个优先队列里。

每次更新答案的时候一直取$top$。

如果从$1$到$l$中的最大的$val$值为$i$，则更新答案，否则直接$break$掉。

正确性？

因为这个询问按照$l$从大到小的顺序排列，

如果区间$[1,r](1<=r<=n)$不能更新区间$[i,j]$，那么：

对于区间$[i',j'](i'<i;j'<j)$，也就是说在此之前它并没有被更新，

假设现在存在一个合法区间满足题目要求，对于之前的$r$，它并没有被更新。

那么这个合法区间的右端点$j''$一定大于等于$j$，它肯定可以更新右侧区间$[i,j]$。

也就是说有一个合法区间可以更新$[i,j]$，与假设肯定不符。

其他的可以类推。

丑陋的代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define Maxn 100050#define Reg register#define INF 0x7ffffff#define New() new Tree#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))using namespace std;int n,m,mxx,maxx,pos[Maxn],num[Maxn];struct Tree {Tree *ch[2]; int val,flag,pm;};struct Node { int l,r,pos,al,ar;} Q[Maxn];struct cmp{ bool operator () (int a,int b) { if(Q[a].l!=Q[b].l) return Q[a].l
             
              Q[b].r; }};vector
              
               
                 > p(Maxn);priority_queue
                
                 
                  ,cmp> stack;Tree *root;bool comp(Node a,Node b) { return a.pos
                  
                   ch[0]==NULL&&p->ch[1]==NULL) return; if(p->ch[0]!=NULL&&p->ch[1]!=NULL) { if(p->ch[0]->val>p->ch[1]->val) p->pm=p->ch[0]->pm; else if(p->ch[0]->val
                   
                    ch[1]->val) p->pm=p->ch[1]->pm; else p->pm=max(p->ch[0]->pm,p->ch[1]->pm); p->val=max(p->ch[0]->val,p->ch[1]->val); } else if(p->ch[0]!=NULL||p->ch[1]!=NULL) { p->val=p->ch[0]==NULL?p->ch[1]->val:p->ch[0]->val; p->pm=p->ch[0]==NULL?p->ch[1]->pm:p->ch[0]->pm; } return;}void down(Tree *p){ if(p->ch[0]!=NULL) { p->ch[0]->val+=p->flag; p->ch[0]->flag+=p->flag; } if(p->ch[1]!=NULL) { p->ch[1]->val+=p->flag; p->ch[1]->flag+=p->flag; } p->flag=0; up(p); return;}void build(Tree **p,int l,int r){ if(*p==NULL) *p=New(); if(l==r) { (*p)->flag=(*p)->val=0; (*p)->pm=l; scanf("%d",&num[l]); pos[num[l]]=l; return; } int mid=(l+r)>>1; if(l<=mid) build(&((*p)->ch[0]),l,mid); if(mid+1<=r) build(&((*p)->ch[1]),mid+1,r); up(*p); return;}void add(Tree *p,int l,int r,int sol,int sor,int num){ if(p==NULL) return; if(sol<=l&&r<=sor) { p->val+=num; p->flag+=num; return; } down(p); int mid=(l+r)>>1; if(sol<=mid) add(p->ch[0],l,mid,sol,sor,num); if(mid+1<=sor) add(p->ch[1],mid+1,r,sol,sor,num); up(p); return;}void serch(Tree *p,int l,int r,int sol,int sor){ if(p==NULL||p->pm<=mxx) return; if(sol<=l&&r<=sor) { if(p->val>=maxx) { if(p->val==maxx) mxx=max(mxx,p->pm); else maxx=p->val,mxx=p->pm; } return; } down(p); int mid=(l+r)>>1; if(sol<=mid) serch(p->ch[0],l,mid,sol,sor); if(mid+1<=sor) serch(p->ch[1],mid+1,r,sol,sor); up(p); return;}int main(){ scanf("%d",&n); build(&root,1,n); scanf("%d",&m); for(Reg int i=1;i<=m;++i) { scanf("%d%d",&Q[i].l,&Q[i].r); p[Q[i].r].push_back(i); Q[i].pos=i; } for(Reg int i=1,len;i<=n;++i) { add(root,1,n,i,i,i); if(pos[num[i]-1]<=i) add(root,1,n,1,pos[num[i]-1],1); if(pos[num[i]+1]<=i) add(root,1,n,1,pos[num[i]+1],1); len=p[i].size(); for(Reg int j=0;j
View Code

 

总结：

$T1$乍一看没什么思路，

刚开始一直在想怎么用线段树。

不管怎样都是$O(nm)$的复杂度。

然后就弃掉了。

最后码完$T3$有回来看$T1$，想了一会儿。

式子写下来，发现其实很水。逐行转移就可以了。

开始看$T2$，也没什么思路。

码了一个暴力(最后还打错了)，先拿到这暴力分再说。

$T3$好像做过的样子，想到那个莫队专题里的$permu$，心态就炸了。

因为我没做那个题。

静下心来好好想，结果码了$2$颗线段树，然后水到$80$分。

最后回去看$T1$和$T2$，$T1$打完确实心态就稳了。

然后$T2$还是炸了，暴力分都没拿到。

所以最后$100+5+80=185$。

没什么水平。。。

转载于:https://www.cnblogs.com/Milk-Feng/p/11302189.html

你可能感兴趣的文章
vue2.x directive - 限制input只能输入正整数
查看>>
实现MyLinkedList类深入理解LinkedList
查看>>
自定义返回模型
查看>>
C#.NET 大型通用信息化系统集成快速开发平台 4.1 版本 - 客户端多网络支持
查看>>
HDU 4122
查看>>
Suite3.4.7和Keil u3自带fx2.h、fx2regs.h文件的异同
查看>>
打飞机游戏【来源于Crossin的编程教室 http://chuansong.me/account/crossincode 】
查看>>
[LeetCode] Merge Intervals
查看>>
【翻译自mos文章】当点击完 finishbutton后，dbca 或者dbua hang住
查看>>
Linux编程简介——gcc
查看>>
2019年春季学期第四周作业
查看>>
MVC4.0 利用IActionFilter实现简单的后台操作日志功能
查看>>
windows下mongodb安装与使用
查看>>
rotate the clock
查看>>
bugku 变量
查看>>
Python 环境傻瓜式搭建 ：Anaconda概述
查看>>
数据库01 /Mysql初识以及基本命令操作
查看>>
数据库02 /MySQL基础数据类型以及多表之间建立联系
查看>>
Python并发编程04/多线程
查看>>
CF461B Appleman and Tree
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-25 16:38:07   当前IP: 3.15.148.203   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我