技术教程 编程代码 2019.8.1 NOIP模拟测试11 反思总结 正文

2019.8.1 NOIP模拟测试11 反思总结

2023-07-30,,

延迟了一天来补一个反思总结

急匆匆赶回来考试，我们这边大家的状态都稍微有一点差，不过最后的成绩总体来看好像还不错XD

其实这次拿分的大都是暴力【？】，除了某些专注于某道题的人以及远程爆踩我们的某学车神犇

大约不粘题面也是可以的【越来越懒】

T1：

当时我甚至完全没有正解的思路，最后sort骗了四十分跑路

【某种意义上还挺友好的？送你四十分】

然后接下来的六十分，出题人：想都别想

看看正解，线段树分别维护区间里26个字母出现的数量，每次操作变成查询26次【或者一次查询统计26个】，然后修改最多26次

时间复杂度是O(mlogn*26)，以及大到吓死人的常数

接下来出现了机房全体绞尽脑汁卡常的神奇场面，除了一些正在思索其他方法的人，这是个伏笔

而我还在为正确性的问题苦恼。我经常结果输出只留一个字母，于是开始纠结是不是tag下放顺序的问题，然后在每次修改前先清零，还是不对。后来又尝试修改一个的时候同时清零其它字母，理所当然是不对的…最后得到别人的肯定答案，说修改前先清零就可以，当成普通的线段树来写，不能在修改一个的时候清零其它字母

于是自信地又打了一遍第一次修改，认真查错，最后找到问题是区间覆盖赋值的时候没有考虑到区间的范围…orz

姗姗来迟并不妨碍我被卡在常数上疯狂tle

怎么办，好在其他人已经研究好久了【？】学习Gekoo大佬循环展开。因为展错东西居然变慢了…变慢了…

于是把大佬展开的东西都展开了一遍，终于强行卡过…

#include<iostream>

#include<cstdio>

using namespace std;

int n,m,num[];

char s[];

int read(){

    char ch=getchar();

    int val=;

    for(;(ch<'')||(ch>'');ch=getchar());

    for(;(ch>='')&&(ch<='');val=val*+ch-'',ch=getchar());

    return val;

}

struct node{

    int l,r,sum[],tag[];

}t[];

void build(int p,int l,int r){

    t[p].l=l,t[p].r=r;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    t[p].tag[]=-;

    if(l==r){

        t[p].sum[s[l]-'a'+]=;

        return;

    }

    int mid=(l+r)/;

    build(p<<,l,mid);

    build(p<<|,mid+,r);

    for(int i=;i<=;i++)t[p].sum[i]=t[p<<].sum[i]+t[p<<|].sum[i];

}

void pushdown(int p,int x){

    if(t[p].tag[x]!=-){

        t[p<<].tag[x]=t[p].tag[x];

        t[p<<|].tag[x]=t[p].tag[x];

        t[p<<].sum[x]=(t[p<<].r-t[p<<].l+)*t[p].tag[x];

        t[p<<|].sum[x]=(t[p<<|].r-t[p<<|].l+)*t[p].tag[x];

        t[p].tag[x]=-;

    }

}

void pushdown(int p){

    for(int x=;x<=;x++){

        if(t[p].tag[x]!=-){

            t[p<<].tag[x]=t[p].tag[x];

            t[p<<|].tag[x]=t[p].tag[x];

            t[p<<].sum[x]=(t[p<<].r-t[p<<].l+)*t[p].tag[x];

            t[p<<|].sum[x]=(t[p<<|].r-t[p<<|].l+)*t[p].tag[x];

        }

    }

}

void change(int p,int l,int r,int x,int y){

    if(l<=t[p].l&&t[p].r<=r){

        t[p].sum[x]=(t[p].r-t[p].l+)*y;

        t[p].tag[x]=y;

        return;

    }

    pushdown(p,x);

    int mid=(t[p].l+t[p].r)/;

    if(l<=mid)change(p<<,l,r,x,y);

    if(r>mid)change(p<<|,l,r,x,y);

    t[p].sum[x]=t[p<<].sum[x]+t[p<<|].sum[x];

}

void ask(int p,int l,int r){

    if(l<=t[p].l&&t[p].r<=r){

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        num[]+=t[p].sum[];

        return;

    }

    pushdown(p);

    int mid=(t[p].l+t[p].r)/;

    if(l<=mid)ask(p<<,l,r);

    if(r>mid)ask(p<<|,l,r);

}

void print(int p){

    if(t[p].l==t[p].r){

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

            if(t[p].sum[i]){

                printf("%c",(char)i+'a'-);

                break;

            }

        }

        return;

    }

    pushdown(p);

    print(p<<);

    print(p<<|);

}

int main()

{

    n=read(),m=read();

    scanf("%s",s+);

    build(,,n);

    for(int i=,x,y,opt;i<=m;i++){

        x=read(),y=read(),opt=read();

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        num[]=;

        ask(,x,y);

        if(opt==){

            int l=x,r;

            for(int j=;j<=;j++){

                if(num[j]){

                    r=l+num[j]-;

                    change(,x,y,j,);

                    change(,l,r,j,);

                    l=r+;

                    if(l>y)break;

                }

            }

        }

        else{

            int r=y,l;

            for(int j=;j<=;j++){

                if(num[j]){

                    l=r-num[j]+;

                    change(,x,y,j,);

                    change(,l,r,j,);

                    r=l-;

                    if(r<x)break;

                }

            }

        }

    }

    print();

    return ;

}

展开还是和大佬有些区别

而就在前一天晚上，我正在苦苦纠结正确性的某个时候，突然一份爆踩了标算的代码横空出世，空间和时间都远小于正解。伏笔回收，这份代码的创造者表示：这就是个暴力。

还真就是暴力…因为每一次操作，内部的元素经常是分成一大块一大块的，所以可以维护这一大块的边界以及所存元素，每个操作用桶排序来实现。每次会一次性往桶里丢一大堆东西，并且数据都是卡线段树正解的，所以最后跑出来的时间极为优秀。

怎么说呢，分别维护26个字母也不是很难想，好多人都想到了【只是没有写】，我还是比较垃圾…好好记一下这种思路吧。

T2：

神级DP，我是真的想不到。

切入点是，这道题是对列有着每列只能放一个1的限制要求，所以可以把整个矩阵拍扁，感觉上就成了从左到右扫的序列上的问题。

记录l[i]，r[i]表示右端点在第i列及之前的左区间个数，以及左端点在第i列及之前的右区间个数。设f[i][j]表示已经处理到第i列，有j列放置了属于右区间的1。转移的时候先考虑右端区间，分新的这一列放不放1两种情况。f[i][j]=f[i-1][j]（不放）+f[i-1][j-1]*(r[i]-j+1)（放）。

r[i]-j+1，也就是r[i]-(j-i)。这个转移很显然，新的这一列能放置的1，对应的只能是右区间还没放的1。

然后考虑左区间。这里没听懂排列的那个解法，于是去翻了神犇们的博客。在某隔空爆踩我们的神仙的博客里有一个循环的写法。循环k从l[i-1]到l[i]，表示对于必须放在左边的新增的左区间个数个1，一个一个考虑它们。【有一点绕，感觉没有说清…】

然后再循环一层j（从0开始），与上面f[i][j]里的j是同样的意义。那么f[i][j]=f[i][j]*（i-j-k），i-j-k表示还有多少个空位给你放新的这个1。

循环k从l[i-1]到l[i]，记得左闭右开，即循环到l[i]-1。不然就相当于算重XD

#include<iostream>

#include<cstdio>

using namespace std;

int n,m;

const long long mod=;

long long f[][],l[],r[];

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=,ll,rr;i<=n;i++){

        scanf("%d%d",&ll,&rr);

        l[ll]++,r[rr]++;

    }

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

        l[i]+=l[i-];

        r[i]+=r[i-];

    }

    f[][]=;

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

        f[i][]=f[i-][];

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

            f[i][j]=(f[i-][j]+(f[i-][j-]*(r[i]-j+)%mod))%mod;

        }

        for(int j=l[i-];j<l[i];j++){

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

                f[i][k]=f[i][k]*(i-k-j)%mod;

            }

        }

    }

    printf("%lld",f[m][n]);

    return ;

}

T3：

先来看对手的那个奇怪的式子，（经过大佬讲解后）发现它就是把一个二进制下的数逻辑左移，就是整体左移，原来的最高位补到最低位，像环转了一圈。

那么对手在任意时间点左移，等价于先让初始选择的数左移，然后把操作时间点以前要求异或的数都左移（可以看作把一个整体的数拆开异或）。

知道这个以后，对手的m+1个操作（包括初始的时候让你左移），等价于让你选择一个数字并左移，然后异或上a1,a2,a3,a4或者(a1<<1),a2,a3,a4或者(a1<<1),(a2<<1),a3,a4...【当然逻辑左移不是这种直接左移】

每个操作就是让你异或上一串已经确定的数字，等价于让你异或一个已经确定的数。那么我们可以把这m-1个数字求出来，用b数组来存（a1<<1）^（a2<<1）^（a3<<1）...一个前缀异或和，同样用c数组来存am^am-1^am-2...一个后缀异或和。然后前后缀一组合就是一个操作。

得到了m+1个数字，怎么求题目要求的最大值及方案数呢？

我们发现，从所选数字（左移以后的）高位往低位推，例如对于最高位，如果有操作的这一位是0，那么这一位选1就可以不被异或成0。如果这一位是1，同理选0就一定会让答案得到一位1。最后如果这一位是0、1的操作都存在，那么就继续考虑这个操作后面的几位能不能让答案取到1…

发现这个过程很像在走01trie树。对于每一个操作的最高位，如果在这里让答案取到1，那么必须沿着这个操作继续往下走，而不能跳到别的地方去让低位贡献答案。对于m+1个数字建立一棵trie树，然后在上面按上面说的那样跑下来就可以。跑完一串操作后，与答案比较取最大，更新数量。

因为这题问的是可选的初值的数量，没有问具体是什么。那么所有的初值都要考虑逻辑左移，等于所有的初值都不用考虑逻辑左移。（一个初值逻辑左移以后一定能成为另一个初值并且这个对应关系不重不漏）直接从深度为n的trie树顶部往下走就可以。

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int n,m,a[],b[],c[],trie[][],cnt=,maxx,ans;

void ins(int x){

    int now=;

    for(int i=n-;i>=;i--){

        if(!trie[now][(x>>i)&])trie[now][(x>>i)&]=++cnt;

        now=trie[now][(x>>i)&];

    }

}

void work(int now,int x,int sum){

    if(trie[now][]&&trie[now][]){

        work(trie[now][],x-,sum);

        work(trie[now][],x-,sum);

    }

    else if(trie[now][]){

        work(trie[now][],x-,sum+(<<x));

    }

    else if(trie[now][]){

        work(trie[now][],x-,sum+(<<x));

    }

    else{

        if(sum>maxx){

            maxx=sum;

            ans=;

        }

        else if(sum==maxx){

            ans++;

        }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)scanf("%d",&a[i]);

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

        b[i]=b[i-]^((*a[i]/(<<n)+*a[i])%(<<n));

    }

    for(int i=m;i>=;i--){

        c[i]=c[i+]^a[i];

    }

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

        ins(b[i]^c[i+]);

    }

    work(,n-,);

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

    return ;

}

马上就要考模拟测试12了，希望自己rp充足OWO

【打满暴力就gg】

2019.8.1 NOIP模拟测试11 反思总结的相关教程结束。

《2019.8.1 NOIP模拟测试11 反思总结.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!