记得去年这个时候，大概刚接触OI。没想到时间这么快，第一次2017NOIP之旅已经结束。初测成绩出来了，100+100+95+50=345，有浙江三十几名（@Cptraser 机房370大佬）。总体感觉还可以吧，也发挥的不错。但有些地方还是有点可惜。学校里的学长（@Cptraser）让我开个博客，我也想谨以此记录一下自己的点滴吧。

　　贴的都是比赛时的原码

T1 太搞笑的一题，虽然有很多人因为精度爆60（还好手动整数除）

CODE

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

 

T2 感觉今年PJ前两题今年来算是最水的吧，刚开始想打字符串的，后来仔细一想%%%一下就水了

CODE

#include
     
      #include
      
       using namespace std;inline void read(int &x){    x=0; char ch=getchar();    while (ch<'0'||ch>'9') ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();}const int N=1005;int n,q,i,j,x,s[N],w;inline int Pow_10(int k){    int tot=1;    for (int i=1;i<=k;++i)    tot*=10;    return tot;}int main(){    freopen("librarian.in","r",stdin); freopen("librarian.out","w",stdout);    read(n); read(q);    for (i=1;i<=n;++i)    read(s[i]);    sort(s+1,s+n+1);    for (i=1;i<=q;++i)    {        bool flag=0;        read(w); read(x);        for (j=1;j<=n;++j)        if (s[j]%Pow_10(w)==x) { printf("%d\n",s[j]); flag=1; break; }        if (!flag) puts("-1");    }    return 0;}
      
     

 

T3 从T3开始难度就有提升。BFS很简单；SPFA很简单； 然而我考试时都没想到，对着一个记搜调了2个半小时，导致我T4最后想到了单调队列优化然后没时间了

先贴比赛CODE（158行）

#include
     
      #include
      
       using namespace std;inline void read(int &x){    x=0; char ch=getchar();    while (ch<'0'||ch>'9') ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();}const int M=105,fx[4]={
   0,1,0,-1},fy[4]={
   1,0,-1,0},INF=1e9;int map[M][M],n,m,i,j,x,y,z,ans=1e9,f[M][M][3],vis[M][M];inline int min(int a,int b) { return a
       
        0&&xx<=m&&yy>0&&yy<=m&&vis[xx][yy])        {            if (map[xx][yy])            {                if (f[xx][yy][0]!=INF)                 {                    if (flag)                     {                        int add;                        if (map[xx][yy]==1) add=0; else add=1;                        f[x][y][1]=min(f[x][y][1],f[xx][yy][0]+add+2);                        if (map[xx][yy]==2) add=0; else add=1;                        f[x][y][2]=min(f[x][y][2],f[xx][yy][0]+add+2);                     } else                    {                        int add;                        if (map[x][y]==map[xx][yy]) add=0; else add=1;                        f[x][y][0]=min(f[x][y][0],f[xx][yy][0]+add);                    }                } else                {                    vis[xx][yy]=0;                    dfs(xx,yy);                    vis[xx][yy]=1;                    if (flag)                     {                        int add;                        if (map[xx][yy]==1) add=0; else add=1;                        f[x][y][1]=min(f[x][y][1],f[xx][yy][0]+add+2);                        if (map[xx][yy]==2) add=0; else add=1;                        f[x][y][2]=min(f[x][y][2],f[xx][yy][0]+add+2);                     } else                    {                        int add;                        if (map[x][y]==map[xx][yy]) add=0; else add=1;                        f[x][y][0]=min(f[x][y][0],f[xx][yy][0]+add);                    }                }            } else            {                if (f[xx][yy][1]!=INF&&f[xx][yy][2]!=INF)                {                    if (!flag)                     {                        int add;                        if (map[x][y]==1) add=0; else add=1;                        f[x][y][0]=min(f[x][y][0],f[xx][yy][1]+add);                        if (map[x][y]==2) add=0; else add=1;                        f[x][y][0]=min(f[x][y][0],f[xx][yy][2]+add);                    }                 } else                 {                     if (!flag)                    {                        vis[xx][yy]=0;                         dfs(xx,yy);                         vis[xx][yy]=1;                         int add;                        if (map[x][y]==1) add=0; else add=1;                        f[x][y][0]=min(f[x][y][0],f[xx][yy][1]+add);                        if (map[x][y]==2) add=0; else add=1;                        f[x][y][0]=min(f[x][y][0],f[xx][yy][2]+add);                    }                }            }        }    }}void xz(){    for (int i=1;i<=m;++i)    for (int j=1;j<=m;++j)    {        if (map[i][j])         {            for (int k=0;k<4;++k)            {                int x=fx[k]+i,y=fy[k]+j;                if (x>0&&x<=m&&y>0&&y<=m)                 {                    if (map[x][y])                     {                        int add;                        if (map[x][y]==map[i][j]) add=0; else add=1;                        f[i][j][0]=min(f[i][j][0],f[x][y][0]+add);                    } else                    {                        int add;                        if (map[i][j]==1) add=0; else add=1;                        f[i][j][0]=min(f[i][j][0],f[x][y][1]+add);                        if (map[i][j]==2) add=0; else add=1;                        f[i][j][0]=min(f[i][j][0],f[x][y][2]+add);                    }                }            }        } else        {            for (int k=0;k<4;++k)            {                int x=fx[k]+i,y=fy[k]+j;                if (x>0&&x<=m&&y>0&&y<=m)                {                    if (map[x][y])                    {                        int add;                        if (map[x][y]==1) add=0; else add=1;                        f[i][j][1]=min(f[i][j][1],f[x][y][0]+add+2);                        if (map[x][y]==2) add=0; else add=1;                        f[i][j][2]=min(f[i][j][2],f[x][y][0]+add+2);                    }                }            }        }    }}int main(){    freopen("chess.in","r",stdin); freopen("chess.out","w",stdout);    memset(map,0,sizeof(map));    memset(vis,true,sizeof(vis));    read(m); read(n);    for (i=1;i<=m;++i)    for (j=1;j<=m;++j)    f[i][j][0]=f[i][j][1]=f[i][j][2]=INF;    f[1][1][0]=0;    for (i=1;i<=n;++i)    {        read(x); read(y); read(z);        map[x][y]=z+1;    }    vis[m][m]=0;    dfs(m,m);    xz();    bool flag=0;    if (map[m][m]==0) flag=1;    if (flag) { if (min(f[m][m][1],f[m][m][2])==INF) puts("-1"); else printf("%d",min(f[m][m][1],f[m][m][2])); }    else { if (f[m][m][0]==INF) puts("-1"); else printf("%d",f[m][m][0]); }    return 0;}
       
      
     

上面的dfs其实在搞笑，真正得（骗）了95分的是那个最后10分钟加上去的xz（），%%%%%%

 

回来后仔细想了想，打了个SPFA，就是建边的过程有点烦

对于每个有颜色的点

距离为1的有颜色的点颜色相同连1条0的边；颜色不同连一条1的边；

距离为2的有颜色的点颜色相同连1条2的边；颜色不同连一条3的边；

最后对于（m,m）有无颜色的问题特判一下就过了，代码量明显减少

CODE

#include
     
      #include
      
       #include
       
        using namespace std;const int fx1[4]={
   0,1,0,-1},fy1[4]={
   1,0,-1,0},fx2[8]={
   0,0,-2,2,-1,-1,1,1},fy2[8]={-2,2,0,0,-1,1,-1,1};const int M=105;int map[M][M],INF,father[M*M+10],i,x,y,z,n,m,j,dis[M*M+10],q[M*M*2+10],f[M*M+10],head,tail;vector 
        
          a[M*M+10],l[M*M+10];inline void read(int &x){    x=0; char ch=getchar();    while (ch<'0'||ch>'9') ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();}void build(int x,int y){    for (int i=0;i<4;++i)    {        int xx=x+fx1[i],yy=y+fy1[i];        if (map[xx][yy]!=INF&&xx>0&&yy>0&&xx<=m&&yy<=m)         a[(x-1)*m+y].push_back((xx-1)*m+yy),l[(x-1)*m+y].push_back(map[x][y]!=map[xx][yy]);    }    for (int i=0;i<8;++i)    {        int xx=x+fx2[i],yy=y+fy2[i];        if (map[xx][yy]!=INF&&xx>0&&yy>0&&xx<=m&&yy<=m)         a[(x-1)*m+y].push_back((xx-1)*m+yy),l[(x-1)*m+y].push_back(map[x][y]==map[xx][yy]?2:3);    }}int main(){    freopen("chess.in","r",stdin); freopen("chess.out","w",stdout);    read(m); read(n);    memset(map,63,sizeof(map));    memset(dis,63,sizeof(dis));    for (i=1;i<=n;++i)    {        read(x); read(y); read(z);         map[x][y]=z;    }    INF=map[0][0];    for (i=1;i<=m;++i)    for (j=1;j<=m;++j)    if (map[i][j]!=INF) build(i,j);    dis[1]=0; q[1]=1; f[1]=1;    head=0; tail=1;    while (head
         
          dis[now]+l[now][i])            {                dis[k]=dis[now]+l[now][i];                if (!f[k])                {                    q[++tail]=k;                    f[k]=1;                }            }        }    }    if (map[m][m]==INF)     {        if (map[m][m-1]!=INF) dis[m*m]=min(dis[m*m],dis[m*m-1]+2);        if (map[m-1][m]!=INF) dis[m*m]=min(dis[m*m],dis[m*m-m]+2);    }    if (dis[m*m]==INF) puts("-1"); else printf("%d",dis[m*m]);    return 0;}
         
        
       
      
     

 

T4 谨记机房大佬（@Cptraser）的教诲，NOIP已经很久很久没有考MST了。然而今年，一如既往的没考。

最后一题 看一眼 二分答案，check（）

　　        再一看 二维DP也许能行 20分钟打好

               然后优化第三题去了 然后再也没有回来

比赛CODE

#include
     
      #include
      
       typedef long long LL;using namespace std;inline void read(LL &x){    x=0; char ch=getchar(); LL flag=1;    while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); }    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    x*=flag;}const LL N=500005;struct data{    LL x,w;}a[N];LL n,d,k,i,j,ans=-1,sum=0,f[N];inline LL max(LL a,LL b) { return a>b?a:b; }bool check(LL x){    LL left=x
       
        =left&&a[i].x-a[j].x<=right)     {        f[i]=max(f[i],f[j]+a[i].w);        if (f[i]>=k) return 1;    }    return 0;}int main(){    freopen("jump.in","r",stdin); freopen("jump.out","w",stdout);    read(n); read(d); read(k);        for (i=1;i<=n;++i)    read(a[i].x),read(a[i].w),sum+=a[i].w>0?a[i].w:0;    if (sum
        
         =k) { puts("0"); return 0; }        }    }    a[0].x=a[0].w=0;    LL l=0,r=a[n].x;    while (l<=r)    {        LL mid=(l+r)>>1;        if (check(mid)) ans=mid,r=mid-1; else l=mid+1;    }    printf("%lld",ans);    return 0;}
        
       
      
     

               那个 d==1 的特判其实是在搞笑

　　　　 单调队列的优化还是很好想的

               在距离内的加入，距离外的弹出，为了取最大最优值只需要保持队列单调递减即可。

　　　　 借鉴了洛谷一名大佬的思路

CODE

#include
     
      #include
      
       typedef long long LL;using namespace std;inline void read(LL &x){    x=0; char ch=getchar(); LL flag=1;    while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); }    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    x*=flag;}const LL N=500005;struct data{    LL x,w;}a[N];struct dl{    LL x,s;}q[N*2+10];LL n,d,k,i,j,ans=-1,sum=0,f[N],head,tail,now;inline LL max(LL a,LL b) { return a>b?a:b; }bool check(LL x){    LL left=x
       
        right) head++;        if (head<=tail) f[i]=q[head].s+a[i].w;        if (f[i]>=k) return 1;    }    return 0;}int main(){    freopen("jump.in","r",stdin); freopen("jump.out","w",stdout);    read(n); read(d); read(k);        for (i=1;i<=n;++i)    read(a[i].x),read(a[i].w),sum+=a[i].w>0?a[i].w:0;    if (sum
        
         =k) { puts("0"); return 0; }        }    }*/    a[0].x=a[0].w=0;    LL l=0,r=a[n].x;    while (l<=r)    {        LL mid=(l+r)>>1;        if (check(mid)) ans=mid,r=mid-1; else l=mid+1;    }    printf("%lld",ans);    return 0;}
        
       
      
     

 

　　暑假才P->C，代码有点chou

　　其实今年的O气真的很足，第三题水了95

　　感觉今年总体难度比去年低吧，但浙江的分数线才280（据说）……

　　有点小兴奋吧，毕竟一年的付出没有白费

　　明年再接再厉，准备下提高吧

 

　　顺便宣传下大佬的博客（@Cptraser）