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已经过去，明年再战！