考砸了，~~还有原谅我代码十分有限的可读性。~~

一个人的真正伟大之处就在于他能够认识到自己的渺小。——保罗

从一年前初一九月到现在18年10月接触OI已经有一年了。几次模拟赛也自我感觉良好，都过了一等的线，自己考试的心态当时也放的挺平。但也没想到会考出这么差的分数。

于是乎今天来总结一下Noip 2018（普及组）的题目。希望自己能好好反思一下自己。

Tips:民间数据分数分别来自：某不明dalao;洛谷;某中学数据

初赛篇

这是整个比赛当中出问题最严重的地方，自己在几次模拟赛中初赛成绩普遍偏低，当晚上知道自己算出来才64分的时候心里那个慌呀，等了一个星期得到消息自己是62分，刚刚好61分是GD分数线，很幸运的自己过了初赛。

虽然初赛很水，但是自己真的得加强了，程序填空倒数第一题比倒数第二题还高几分，错误很zz，都是些没写Ans=***之类的问题。

复赛篇

去广州二中的路上非常ok，老师还给了我们棒棒糖和奶糖。几颗糖下肚，那份紧张感就完全消散了，在路上看看书，聊聊天，再玩下手机就到了地点。

T1 标题统计

T1 分析

我们可以非常清晰地得出这是一道喷香的水题，但有人用了gets()，不清楚会不会WA，我用了getline().然后判断空格。

民间数据分数：100;100;100

Noip官方分数：100

T1 程序

 #include<iostream>

 #include<fstream>

 using namespace std;

 string s;

 int Ans;

 int main()

 {

     getline(cin,s);

     for(int i=;i<s.size();i++)

     if(s[i]!=' ')Ans++;

     printf("%d",Ans);

 }

正解

T1 总结

奇怪函数别乱用，小心WA就不管用。

T2 龙虎斗

T2 分析

刚开始没开long long，令人着迷

枚举每一个点放置是否更优，更优就更替。

这道题不难，单纯模拟就可以做出来，需要注意的时要是双方势力相当时或 s2 放在哪里都不合适时要放在 m 点上。

T2 程序

 #include<iostream>

 #include<fstream>

 #include<cmath>

 using namespace std;

 const int N=;

 int n,m,p1,s1,s2,res;

 long long sumd,sumt,Ans,tmp;

 int c[N];

 int Find()

 {

     register long long i;

     Ans=abs(sumd-sumt);res=m;

     if(sumd<sumt)

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

         tmp=s2*(m-i);

         if(abs(tmp+sumd-sumt)<Ans)

         Ans=abs(tmp+sumd-sumt),res=i;

     }

     if(sumt<sumd)

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

         tmp=s2*(i-m);

         if(abs(tmp+sumt-sumd)<Ans)

         Ans=abs(tmp+sumt-sumd),res=i;

     }

     return res;

 }

 int main()

 {

     freopen("fight.in","r",stdin);

     freopen("fight.out","w",stdout);

     register int i,j;

     scanf("%d",&n);

     for(i=;i<=n;i++)scanf("%d",&c[i]);

     scanf("%d%d%d%d",&m,&p1,&s1,&s2);

     c[p1]+=s1;

     for(i=m-,j=m+;;){

         if(i==&&j==n+)break;

         if(i)sumd+=(long long)c[i]*(m-i),i--;

         if(j<=n)sumt+=(long long)c[j]*(j-m),j++;

         tmp=min(sumd,sumt);

         sumd-=tmp,sumt-=tmp;

     }

     printf("%d\n",Find());

     return ;

 }

正解

T2 总结

十年OI一场空，不开long long 见祖宗。

民间数据分数：100;100;100

Noip官方分数：100

T3 摆渡车

T3分析

比赛的时候看出来是dp，但是却没时间写，直接跳到第四题写。最后没时间打暴力还打错，估计只能拿5~10分。

正解思想(来自luogu大佬)：This

T3 程序

 #include<iostream>

 #include<fstream>

 #include<algorithm>

 using namespace std;

 const int Inf=;

 int n,m,maxn,Ans=Inf;

 int A[],cost[];

 void dfs(int bus,int now,int spen)

 {

     if(bus==n+)Ans=min(Ans,spen);

     register int i=bus+,j;

     int sum=,wait=;

     while(i<=n&&A[i]<=now)sum+=now-A[i++];

     for(i=bus;i<=n;i++){

         while(A[i]==A[i+])i++;

         dfs(i+,now+wait+m,spen+sum);

         wait+=i-bus;

     }

     return;

 }

 bool cmp(int A,int B)

 {

     return A<B;

 }

 int main()

 {

     freopen("bus.in","r",stdin);

     freopen("bus.out","w",stdout);

     register int i,j;

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

     for(i=;i<=n;i++)

     scanf("%d",&A[i]),maxn=max(maxn,A[i]);

     if(n==&&m==&&A[]==){printf("");return ;}

     if(n==){printf("");return ;}

     sort(A+,A++n,cmp);

     dfs(,A[i],);

     printf("%d",Ans);

     return ;

 }

乱写的错解

 #include<stdio.h>

 #include<algorithm>

 using namespace std;

 const int maxn=,maxm=;

 const int INF=0x7fffffff;

 int f[maxn][maxm];

 int Min[maxn];

 int a[maxn];

 struct Node

 {

     int pos,num;

 }Mem[maxn];

 int sz;

 int col(int l,int r,int pos)

 {

     int res=;

     for(int i=l;i<=r;i++)

         res+=(pos-Mem[i].pos)*Mem[i].num;

     return res;

 }

 int main(int argc, char const *argv[])

 {

     int n,m;

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

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

         scanf("%d",&a[i]);

     sort(a+,a+n+);

     Mem[].pos=-m*-;

     a[]=-;

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

     {

         if( a[i]^a[i-] )

             Mem[++sz].pos=a[i];

         Mem[sz].num++;

     }

     Mem[sz+].pos=Mem[sz].pos+m+;

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

     {

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

             f[i][j]=INF;

         Min[i]=INF;

     }

     Min[]=;

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

         for(int j=;j<min(m,Mem[i+].pos-Mem[i].pos);j++)

         {

             int pos=Mem[i].pos+j,lpos=pos-m;

             int val=col(,i,pos);

             f[i][j]=val;

             for(int k=; k<i and Mem[k].pos<=lpos ;k++)

             {

                 val-=(pos-Mem[k].pos)*Mem[k].num;

                 if( min( Mem[k].pos+m-,Mem[k+].pos- )<=lpos ) f[i][j]=min( f[i][j],Min[k]+val );

                 else

                 {

                     for(int kk=; Mem[k].pos+kk<Mem[k+].pos and Mem[k].pos+kk<=lpos and kk<m;kk++)

                         f[i][j]=min( f[i][j],f[k][kk]+val );

                 }

             }

             Min[i]=min( Min[i],f[i][j] );

         }

     printf("%d",Min[sz]);

     return ;

 }

dalao的正解

T3 总结

时间必须安排恰当，实在不行就舍弃。

民间数据分数：10;10;10

Noip官方分数：10

T4 对称二叉树

T4分析

今年t4考的是图论，但貌似今年数据过水导致暴力+剪枝就能AC，这道题自己认为不能做%100数据于是自己就自动屏蔽其他数据，只去写满二叉树的部分（考完后才发现自己能写AC的代码，有点后悔），思路：找根节点，将给出的数据规划成一颗二叉树，最后枚举。

T4 程序

 #include<iostream>

 #include<fstream>

 #include<cmath>

 using namespace std;

 const int N=;

 int n,Ans=,mi,what;

 int t[N],sonl[N],sonr[N];

 struct Node

 {

     int No,v;

     Node(int A=,int B=)

     {

         No=A;v=B;

     }

 }A[N];

 bool check(int st,int en)

 {

     if(st>pow(,mi))return ;

     bool Flag=;

     register int i=st,j=en;

     while(i<=j){

         if(A[i].v!=A[j].v){Flag=;break;}

         i++;j--;

     }

 //    cout<<st<<" "<<en<<" "<<Flag<<endl;

     if(!Flag&&check(st*,en*+))return ;

     return ;

 }

 int main()

 {

     register int i=,j;

     scanf("%d",&n);

     while(pow(,i)<n+)mi=i,i++;mi++;

     for(i=;i<=n;i++)scanf("%d",&t[i]);

     for(i=;i<=n;i++)

     scanf("%d%d",&sonl[i],&sonr[i]);

     A[]=Node(,t[]);

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

         if(i%==)

         A[i]=Node(sonl[A[i/].No],t[sonl[A[i/].No]]);

         else A[i]=Node(sonr[A[i/].No],t[sonr[A[i/].No]]);

     }

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

         if(pow(,what+)-<i)what++;

         if(sonl[i]!=-&&sonr[i]!=-&&check(i*,i*+)){

             Ans=max(Ans,(int)pow(,mi-what)-);

             break;

         }

     }

     printf("%d",Ans);

     return ;

 }

自己的错解

 #include <iostream>

 #include <fstream>

 #include <cstdio>

 #include <algorithm>

 #define MAX_N 1000001

 using namespace std;

 int n;

 struct Node

 {

     int val;

     int lt;

     int rt;

     int num;

 }a[MAX_N];

 int ans = ;

 void Get_Num(int x)

 {

     if(a[x].lt == - && a[x].rt == -)

     {

         a[x].num = ;

         return;

     }

     if(a[x].lt != - && !a[a[x].lt].num) Get_Num(a[x].lt);

     if(a[x].rt != - && !a[a[x].rt].num) Get_Num(a[x].rt);

     a[x].num = a[a[x].lt].num + a[a[x].rt].num + ;

     return;

 }

 bool DFS(int x, int y)

 {

 //    cout << "      " <<  x << ' ' << y << endl;

     if(a[x].val != a[y].val) return false;

     if(a[x].num != a[y].num) return false;

     if(a[x].num ==  && a[y].num == ) return true;

     if(a[x].lt != - && a[x].rt != - && a[y].lt != - && a[y].rt != -)

     {

         if(!DFS(a[x].lt, a[y].rt)) return false;

         if(!DFS(a[x].rt, a[y].lt)) return false;

         return true;

     }

     if(a[x].lt == - && a[x].rt != - && a[y].lt != - && a[y].rt == -)

     {

         if(!DFS(a[x].rt, a[y].lt)) return false;

         return true;

     }

     if(a[x].lt != - && a[x].rt == - && a[y].lt == - && a[y].rt != -)

     {

         if(!DFS(a[x].lt, a[y].rt)) return false;

         return true;

     }

     return false;

 }

 int main()

 {

     scanf("%d", &n);

     if(!n) return cout << , ;

     for(register int i = ; i <= n; ++i)

     {

         scanf("%d", &a[i].val);

     }

     for(register int i = ; i <= n; ++i)

     {

         scanf("%d%d", &a[i].lt, &a[i].rt);

 //        cout << a[i].lt << ' ' << a[i].rt << endl;

     }

     Get_Num();

     for(register int i = ; i <= n; ++i)

     {

         if(a[i].lt == - || a[i].rt == -) continue;

 //        cout << i << endl;

         if(DFS(a[i].lt, a[i].rt))

         {

             ans = max(ans, a[i].num);

         }

     }

     cout << ans;

     return ;

 }

同学的正解

T4 总结

相信自己，自己没有这么垃圾（其实是蒟蒻）

民间数据分数：32;45;64

Noip官方分数：40

比赛反思

这次比赛考得很差，低级错误犯了一大堆，考试前给自己的心理暗示也没有起到作用，自己终于认识到自己的渺小（水），自己的实力并没有想象中那么强，在dp、贪心方面总是脑子转不过来，搜索也写得效率极低，调试了好几遍才着边，自己在t4浪费的时间太多，导致t3根本没有好好做，最后只打了暴力了事.

老师之前一直跟我强调的话是正确的：就算平时模拟赛拿一等又怎么样，考试一样会失误拿二等，我现在就犯了这种错误，自己是应该好好反省了。

虽然一等已经没有希望了，但参加Noip的意义不止是拿一个奖，回想初衷，那个晚自习自己最初是抱着怎样的心思去学OI的，肯定不是为了那一个没有实质的奖项，我不能跌倒，我必须重拾信心，为下一个Noip做准备，为自己心中的梦作准备。

这次遇到了好多dalao，本蒟蒻总觉得自己只能在动荡当中存活下来。

就这样吧，结束了Noip2018。

有些尴尬

我又回来了，Noip分数为250；更令人惊讶的是GD排名70多orz；

怎么说，一次波澜起伏的Noip赛；

自己真是蒟蒻

希望下一次的比赛不犯这低级错误，自己更加进步！

祝大家在Noip2018取得自己理想的成绩！

巴特西

[OI]Noip 2018总结（普及）

初赛篇

复赛篇