2019.8.14 NOIP模拟测试21 反思总结

模拟测试20的还没改完先咕着

各种细节问题=错失190pts

T1大约三分钟搞出了式子，迅速码完，T2写了一半的时候怕最后被卡评测滚去交了，然后右端点没有初始化为n…但是这样还有80pts，而我后来还剩十分钟的时候写了个枚举用小数据把自己的80分代码卡掉了，后来交了个枚举60分…

T2枚举的30pts和exgcd的20pts都爆炸了。

T3还好，一眼数位DP也的确是数位DP，基本上推出正解来了，但是在前导0的地方卡了很久…最后急匆匆写了个枚举交上去了，加上特判一共40pts。

T1折纸：

思路很好想。首先询问次数就是一个提示，纸带长度直接变成1e18，但是操作次数仍然是3000，就要考虑在这里搞一些幺蛾子。

然后从题意正着推下来，画一两组小数据模拟一下，能发现在翻折点右边的点的位置每次会变成pos[翻折点]-(pos[这个点]-pos[翻折点])，也就是2*pos[翻折点]-pos[这个点]。一开始我把一个点的全部翻折路径和式子列在一起，发现是一加一减【废话】，在想可不可以直接把所有点的公共部分推出来，后来发现只有翻折点右边的点会受到影响。

然后又想，能不能只修改全部询问的点，在过程中通过计算维护纸带长度，于是列了一堆取min的式子…其实明明都想出来了但是没有理明白。

正解差不多出来了，每次操作完以后的右端点一定是当前的翻折点，而左端点是原来的左端点或者翻折过去的原来的右端点，那么就把l和2*pos[i]（当前询问点的位置）-r取个min。询问只有3000个，可以暴力维护它们的位置，也是按上面的式子。按我这样推下去的话一定会出现位置为负的情况，因为一直在减。但是它不会造成影响，因为长度是左右端点的相对距离。

#include<iostream>

#include<cstdio>

using namespace std;

long long n,m,q[],sum,minn,l=;

int main(){

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

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

        scanf("%lld",&q[i]);

    }

    minn=n;

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

        l=min(l,q[i]*-minn);

        minn=q[i];

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

            if(q[j]>q[i])q[j]=*q[i]-q[j];

        }

    }

    printf("%lld",minn-l);

    return ;

}

T2不等式：

就好像一开始说的，我的50分炸成了10分……

前段时间刚好好学习了exgcd，然后到现在忘得一干二净…赶紧考场上现推一下，好像是对的。但是算出和等于gcd（s，m）的一组解以后并且让m和L都除以gcd以后，我没有把这组解乘上L…这样最后推出来的只是s*x+m*y=1的最小正整数x，而不是s*x+m*y=L的最小正整数x…然后枚举的三十分是给num+s，大于m就减去m，完全忽略了s远大于m的可能性…

正解我还没有完全理解，只是讲题的时候他们是这么讲的orz先咕一下，我改完上一场的考试题，回来弄懂这份代码

#include<iostream>

#include<cstdio>

using namespace std;

int t;

long long m,s,l,r;

long long get(long long M,long long S,long long L,long long R){

    if(L>R||M-<L)return -;

    S%=M;

    long long x=(L-)/S+;

    if(S*x<=R)return x;

    long long l=(-R%S+S)%S,r=(-L%S+S)%S;

    long long y=get(S,M,l,r);

    if(y==-)return -;

    x=(R+M*y)/S;

    if(L<=S*x-M*y)return x;

    return -;

}

int main()

{

    scanf("%d",&t);

    while(t--){

        scanf("%lld%lld%lld%lld",&m,&s,&l,&r);

        printf("%lld\n",get(m,s,l,min(r,m-)));

    }

    return ;

}

T3reverse：

显然的数位DP！

我一开始的思路是分别求出l-r的范围内大于l的和大于r的然后各种减一下瞎搞一下再去个重balabala…但是且不论去重，各种前导零的细节我就处理不完…

正解同时考虑当前数字和l和r的关系，直接求满足两个限制的数字个数。具体来说，f数组开四维，记录当前到哪一位，前缀的长度【便于和l、r的对应数位比较】，s1【当前前缀与l的关系】，s2【当前前缀与r的关系】，存的是之后的位数有几个满足条件的数。s1s2只有三种取值，大于等于和小于，这样传递到最后根据s1和s2的值就可以判断当前数字是不是满足条件。

并且我看到的那份正解代码巧妙地处理了前导零，循环枚举每一位作为首位。虽然仔细一想不是很难想到，但是可能习惯了dfs里记录前导零就不太有信心这么处理…

另外，这题的数据范围是unsigned long long。就在我80pts代码刷屏的时候，dky大佬一语点醒梦中人…多谢大佬救我狗命orz

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int t,a,b;

unsigned long long l,r,ans;

int len[],lens,lenl[],lensl,lenr[],lensr;

unsigned long long f[][][][];

int nex(int x,int y,int lst){

    if(x<y)return ;

    if(x==y)return lst;

    else return ;

}

unsigned long long dfs(int pos,int lon,int s1,int s2,int iszero,int limit){

    if(pos<=){

        if(lon<lensl)s1=;

        if(lon<lensr)s2=;

        if(s1!=&&s2!=)return ;

        else return ;

    }

    if(!limit&&f[pos][lon][s1][s2]!=-)return f[pos][lon][s1][s2];

    int upp=(limit?len[pos]:);

    unsigned long long val=;

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

        val+=dfs(pos-,lon+,nex(i,lenl[lon+],s1),nex(i,lenr[lon+],s2),iszero&&i==,limit&&i==upp);

    }

    if(!limit)f[pos][lon][s1][s2]=val;

    return val;

}

unsigned long long ask(unsigned long long x){

    memset(len,,sizeof(len));

    lens=;

    memset(f,-,sizeof(f));

    while(x){

        len[++lens]=x%;

        x/=;

    }

    unsigned long long val=;

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

        int limit=(i==lens?len[lens]:);

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

            int s1=,s2=;

            val+=dfs(i-,,nex(j,lenl[],s1),nex(j,lenr[],s2),i==,i==lens&&j==limit);

        }

    }

    return val;

}

int main(){

    scanf("%d%d%d",&t,&a,&b);

    while(t--){

        scanf("%llu%llu",&l,&r);

        ans=;

        memset(lenl,,sizeof(lenl));

        memset(lenr,,sizeof(lenr));

        if(a&&b){

            printf("%llu\n",r);

            continue;

        }

        else{

            unsigned long long r1=r,l1=l;

            lens=lensl=lensr=;

            while(l1){

                lenl[++lensl]=l1%;

                l1/=;

            }

            while(r1){

                lenr[++lensr]=r1%;

                r1/=;

            }

            printf("%llu\n",ask(r)-ask(l-));

        }

    }

    return ;

}

这次失误太多了，一个可能是思路比平时更乱，这次基本上都在努力想正解，努力让思路跳起来但是失了稳妥，也被T3的细节搞得脑袋一团糟…这不能成为借口。硬要说的话还可以归咎于状态不好…但这也不能成为借口。除了细节以外对exgcd以及相关题目掌握不够完整，理解不够透彻，这也是很大的问题。比如刚刚我才想明白为什么exgcd求出x以后要加减y的系数…

考场上暴力分失误少是我的优势，这个不能丢掉啊…

这几次考试的代码都不是特别长，更考验思维能力，感觉挺有意义的。但是考炸就很…emm，然而我每次考炸都很喜欢折腾自己…

唔，总之加油吧，实在不行就放低期望……？毕竟我这种人竟然想向着省队努力什么的啊哈哈白日做梦也稍微看看自己到底是个什么垃圾吧

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