NOIP2016总结

NOIP2016!

总的来说,这次NOIP已经结束了,成绩也不尽人意原因又很多,但是最主要还是自身的原因。

比赛概况

这次联赛普遍比较难,自己之所以考的很烂最主要的原因就是该拿到的分数没有拿到,两个T1都写挂了。

Day1-T1

第一题TOY是因为判断错误,一个 “ = ” 的问题,结果一个简单的模拟题只拿到了10分,修改了判断之后就能AC了(NOIP的水数据),但是在OJ上还需要对读入进行处理一下,因为到后面4组数据用string来读入人名是会超时的,需要用到字符数组。

Day2-T1

重点是第二题,第二题需要的递推公式我是已经想出来的,而且实现的也很好,失败就失败在了后面的优化上,也就是空间换时间上面。为了不超时,我使用了一个一维数组来存入每一排前面所有的答案,但是忽略的题意,没有注意到枚举的范围,所以导致后面一片WA,我删除了优化之后,OJ上拿到了80分,是很有可能AC掉NOIP的水数据的,但是自己画蛇添足,自作自受。

Day1-T2&&Day2-T2

然后就是两个第二题,分别都拿到了一些步骤分,30分和20分(好像),按照这样,不算Day2 T1自己真的有可能想不出来的优化:30+20+100+80=230 说不定可以拿到国一,其实这是我很容易就能到达的,然而……

总结

但是原因不能总归根于人品,运气,状态什么的,最重要的还是自己的实力,我之所以犯一些简单的错误,和我的代码熟练度,做题认真程度,读题认真程度还是有很大关系的。MH之所以能拿机房第一,其实很简单,写好了暴力和模拟。

他前面一些很麻烦的模拟题他都没有像我一样跳过,而是写了下来,这需要不停不停的死磕才行,但是这些也锻炼了他的模拟能力,也使得他能拿到不错的成绩。

下一步需要静下心来,认真的赶进度,认真的写代码了。

题解

至于题解,我就简单说说吧:

NOIP Day1-T1

Toy:读入的时候用字符数组,不要用字符串,超级慢,OJ上会超时的.

1
2
3
4
5
6
7
8
ios::sync_with_stdio(false);
struct mans
{
int stand;
char name[20];
};
for(int i=1;i<=n;i++)
cin>>a[i].stand>>a[i].name;

就像这样,直接读入就好,比较快的顺便提一下,不喜欢使用c语言的读入输出但是cin又太慢的,在程序开头加上这一句:ios::sync_with_stdio(false);

然后就是判断,核心代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i=1;i<=m;i++)
{
d=b[i].go%n;
if(a[c].stand!=b[i].to)
{
if(c+d>n)
c=c+d-n;
else c+=d;
}
else
{
if(c-d<=0)
c=c-d+n;
else c=c-d;
}
}

NOIP Day2-T1

题解

Toy我也没有什么可以说的了,很简单的一道模拟题。
然后是Problem,一道递推题,只要找到公式+RP就可以不经过优化AC;
其实核心就是杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
using namespace std;
int t,k,a[20010],b[20010];
int c[5001][5001],e[2001]={0};
int ans[2005][2005]={0},f=0;
int main()
{
ios::sync_with_stdio(false);
cin>>t>>k;
for(int i=1;i<=t;i++)
cin>>a[i]>>b[i];
for(int i=1;i<=2000;i++)
{
c[i][1]=i%k;
c[i][i]=1%k;
}
for(int i=3;i<=2000;i++)
{
for(int j=2;j<i;j++)
{
c[i][j]=c[i-1][j-1]+c[i-1][j];
c[i][j]%=k;
}
}
for(int i=1;i<=2000;i++)
{
for(int j=1;j<=i;j++)
{
if(c[i][j]==0) f++;
if(i==j)
ans[i][j]=ans[i-1][j-1]+f;
else
ans[i][j]=ans[i-1][j]+f;
}
f=0;
}
for(int i=1;i<=t;i++)
cout<<ans[a[i]][min(b[i],a[i])]<<endl;
return 0;
}

优化

但是写出来杨辉三角后不经过优化会超时,所以我们可以把每一个答案事先算出来,然后需要用的时候调出来就好了:

我们其实分析答案之后不难发现,当前数组的答案比如a[5][4]就等于a[4][4]加上第五行1——4所有符合的情况而已,所以只需要一个二重循环,就可以了。代码在上面。

NOIP的总结就到这里吧,接下来是真的该沉下心了,月考之后,就剩一个月期末考试了,所以为了寒假能一整天一整天泡在机房里刷题,晚上一整夜一整夜的瘫在沙发上玩游戏,努努力吧,争取期末考试取得一个好一些的成绩,NOIP已经过去,明年再战!