NOIP2017普及组比赛总结

期中考总结&NOIP2017总结

2017年11月11日，我第二次参加NOIP普及组复赛。上一年，我的得分是250分，只拿到了二等奖。我便把目标定为拿到一等奖，考到300分以上。

早上8点多，我们去302教室，听同学讲考试注意事项（有十几条），有两条令我受益匪浅——要吃饱；不要定义与自带函数重名的变量或函数（如x0，y0什么的）。

我们看了自己的考试信息后，就上车了。11点多就到达广州了。

吃中午饭的地方是一间名叫都城快餐的快餐店，我们却吃了一个多小时的快餐（有人等饭等了四十多分钟）

吃完饭后，我们走去广州六中，接着在那里休息（睡午觉）。2点钟就去考场了。

比赛2点半开始，6点钟结束。开始考试后，我用了40分钟看了一下题目。

T1:
哇！好水呀！
直接输出2a10+3b10+5c10不就完事了吗？
这题不会那么水的！我又看了看题，确保万无一失，以防把这唾手可得的100分弄丢了。
然后就AC了。

T2:
嗯，挺水的。
一眼出正解——暴力！
我的方法就是暴力，只不过加了一点优化（因为比赛时我担心此题有坑）
考场AC！
ＰＳ：此题用字典树是最快的。

T3:
一开始想到了DFS，又想到了DP，到了动手做题前，才发现DP过不了，就打了个记忆化搜索。

相信许多人都觉得魔法特难搞，其实并不难。

通过找规律，我们不难发现，从有颜色的格子开始走，可以走到任意格子，不管它有没有颜色。

而没有颜色的格子却只能走到那些有颜色的格子上（不能连续两次用魔法）

那怎么计算使用魔法的花费呢？我发现，可以分成两种情况判断：

然后记录一下上一个格子坐标就好了。

考场AC！

T4:
这题我0分。
比赛时，我一眼出正解，哈哈，太水了！

这题不就是一个二分+DP+单调队列吗？

然而，细节决定成败。

我错了许多细节，就挂了。
我只考了0分。。。

首先，这题满足一个条件：

保证g变大后，如果原来满足条件，现在也会满足条件；而如果原来不满足条件，现在就有可能满足条件。
g变小后，如果原来满足条件，现在不一定会满足条件；而如果原来不满足条件，现在就一定不可能满足条件。

所以，我们可以用二分找出最合适的g的值。

已知，0≤g≤109，且跳跃的范围是 Max(1,d-g) ~ d+g。

我们就可以列出状态转移方程了：

Fi=max(Fj)+Si   (Xj+a≤Xi⋀Xj+b≥Xi)

其中，a为跳跃最短距离，b为跳跃的最长距离。

这样做的时间复杂度是O(log2109n2)，很明显会时超50分。

所以，我们就要把DP优化一下了。

我们很容易发现，状态转移方程中，对于不同的i，max(Fj)的值可能是一样的，但我们的程序却会从一个较大的区间 上一次最后一个 找到的位置+1 ~ i-1 中找 ，这就是程序中最耗时的地方。

怎么优化呢？

我们有多种优化方式，其中我推荐两种：大根堆，还有单调队列。大根堆码量大，而单调队列方便快捷，因此我比较喜欢用单调队列。

用queuei表示单调队列的第i个元素，用head表示单调队列中有效范围内的第一个元素的下标，用tail表示单调队列中有效范围内的最后一个元素的下标。

单调队列存的是元素的下标，即Fi，Xi中的 i ，这样能方便判断。

由于这个单调队列是递减的（即第一个元素最大，第二个元素比第一个小，第三个比第二个小……最后一个是最小的），所以我们每次使用的最大值就是单调队列中有效范围内的第一个元素对应的值。

那么我们的状态转移方程就可以变成这个样子了：

Fi=Fqueuehead+Si  (Xqueuehead+a≤Xi⋀Xqueuehead+b≥Xi)

其中，a为跳跃最短距离，b为跳跃的最长距离。

这样用起来是很方便的，但是，重点来了——

怎样才能保持单调队列的单调性（使单调队列递减）和有效性（使(Xqueuehead+a≤Xi⋀Xqueuehead+b≥Xi)）呢？

首先，我们每一次加入元素时，如果 （new是新加入的元素），也就是说这个样子（越高的值越大）：

许多人都会认为要变成下面这个样子：

第i个柱子上面的数字是X[queue[i]]的值。
由于新加入单调队列的数，都是可以跳到第i个格子上的，即

Xnew+a≤Xi⋀Xnew+b≥Xi

而X又是递增的，所以Xnew+a≤Xi≤Xi+1≤Xi+2⋯Xn 。

但是从5（Xnew）这个位置出发，能跳到的最远距离绝对比4远，所以当5不能跳到某一个地方时，4也绝对跳不到那个位置。所以4就没用了。

因此我们可以把4删掉（即tail-1），最后再把5加入，变成下面这个样子：

有时候我们要删除很多元素，如下面这个例子：
变成
我们就要用一个while循环来删除F值小于等于F[new]的数。

---

但我们的queue[head]是会过期的（queue[head]跳不到第i个格子），这时我们的queue[head]就不能用了。

我们要删掉queue[head]，怎么删掉呢？直接head+1就好了。

最后一点，建议同学们把不能到达的点的F赋值为-maxlongint！

---

比赛结束后，我忐忑不安地离开考场。不知道今年我能考到多少分呢？应该是310~320吧（然而只拿了300分）！

晚饭我们不是在都城快餐吃了，我们去到了一间饭店吃。不知为何，老师点了特别多的菜，每一桌的菜数比人数还要多！

最后我们当然是没吃完的。有诗云：

锄禾日当午，汗滴禾下土。
谁知盘中餐，粒粒皆辛苦。

我的良心受到了谴责！

---

代码

T1：

#include<cstdio>
using namespace std;
int main()
{
    freopen("score.in","r",stdin);
    freopen("score.out","w",stdout);
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    printf("%d\n",a/10*2+b/10*3+c/10*5);
    return 0;
}

T2：

#include<cstdio>
using namespace std;
int a[1010],s[11];
void qsort(int l,int r)
{
    int i=l,j=r,mid=a[(l+r)/2],t;
    while(i<=j)
    {
        while(a[i]<mid) i++;
        while(a[j]>mid) j--;
        if(i<=j)
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;j--;
        }
    }
    if(i<r) qsort(i,r);
    if(l<j) qsort(l,j);
}
int main()
{
    freopen("librarian.in","r",stdin);
    freopen("librarian.out","w",stdout);
    int n,q,i,j=0,need,len,k=1;
    bool haveFind_theBook;
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    qsort(1,n);
    for(i=0;i<11;i++) s[i]=1;
    for(i=1;i<=n;i++)
    {
        while(a[i]>=k)
        {
            j++;s[j]=i;
            k=k*10;
        }
    }
    while(q--)
    {
        scanf("%d%d",&len,&need);
        if(len==0)
        {
            printf("-1\n");
            continue;
        }
        k=1;haveFind_theBook=false;
        for(i=1;i<=len;i++) k=k*10;
        for(i=s[len];i<=n;i++)
        {
            if(a[i]%k==need)
            {
                haveFind_theBook=true;
                printf("%d\n",a[i]);
                break;
            }
        }
        if(!haveFind_theBook) printf("-1\n");
    }
    return 0;
}

T3：

#include<cstdio>
using namespace std;
#define maxlongint 0x7fffffff
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
int n,c[101][101],f[101][101];
void dfs(int x,int y,int cost,int X,int Y)
{
    if(f[x][y]<=cost) return;
    f[x][y]=cost;
    int i,xx,yy;
    for(i=0;i<4;i++)
    {
        xx=x+dx[i];yy=y+dy[i];
        if(xx>0&&yy>0&&xx<=n&&yy<=n)
        {
            if(c[x][y]==0)
            {
                if(c[xx][yy]==0) continue;
                else
                {
                    if(c[X][Y]==c[xx][yy])
                    {
                        dfs(xx,yy,cost,1,1);
                    }
                    else dfs(xx,yy,cost+1,1,1);
                }
            }
            else
            {
                if(c[xx][yy]==0)
                {
                    dfs(xx,yy,cost+2,x,y);
                }
                else
                {
                    if(c[x][y]==c[xx][yy])
                    {
                        dfs(xx,yy,cost,1,1);
                    }
                    else dfs(xx,yy,cost+1,1,1);
                }
            }
        }
    }
}
int main()
{
    freopen("chess.in","r",stdin);
    freopen("chess.out","w",stdout);
    int m,i,j,x,y,z;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        c[x][y]=z+1;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            f[i][j]=maxlongint;
        }
    }
    dfs(1,1,0,1,1);
    if(f[n][n]==maxlongint) printf("-1\n");
    else printf("%d\n",f[n][n]);
    return 0;
}

T4：

#include<cstdio>
using namespace std;
#define maxlongint 1999999999//事实证明，用-maxlongint的效果最好
int f[500001],queue[500001],x[500001],s[500001];
int main()
{
    freopen("jump.in","r",stdin);
    freopen("jump.out","w",stdout);
    int n,d,k,l=0,r=1000000000,mid,i,j,t,ans=-1,maxx,minn,head,tail,last;
    bool bk,bz;
    scanf("%d%d%d",&n,&d,&k);
    for(i=1;i<=n;i++) scanf("%d%d",&x[i],&s[i]);
    l=0;r=1000000000;
    while(l<=r)
    {
        mid=(l+r)/2;
        maxx=d+mid;bk=false;bz=true;
        minn=d-mid;last=0;
        if(minn<1) minn=1;
        tail=head=1;
        queue[1]=0;
        for(i=1;i<=n;i++)
        {
            if(maxx>=x[i]&&minn<=x[i])
            {
                bz=false;
                break;
            }
        }
        if(bz)
        {
            l=mid+1;
            continue;
        }
        for(i=1;i<=n;i++)
        {
            f[i]=maxlongint;
            for(j=last+1;j<i;j++)
            {
                if(x[j]+minn>x[i]) break;
                if(x[j]+maxx<x[i]) continue;
                last=j;
                if(f[j]==maxlongint) continue;
                while(head<=tail&&f[queue[tail]]<=f[j]) queue[tail--]=0;
                queue[++tail]=j;
            }
            while(head<tail&&x[queue[head]]+maxx<x[i]) head++;
            if(x[queue[head]]+maxx<x[i]||x[queue[head]]+minn>x[i]) f[i]=maxlongint;
            else f[i]=f[queue[head]]+s[i];
            if(f[i]<maxlongint&&f[i]>=k)
            {
                bk=true;
                break;
            }
        }
        if(bk)
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}