跳转至

NOIP2018 游记

就在两周之前,差不多这个时间段,人生中的第一次 NOIP 结束了。

这一次纵然有许多遗憾,也让我获取到了许多经验。

Day -3

屋漏偏逢连夜雨,学校的期中考试竟然在 11.8-11.9 号举行,而 10 号就要 NOIP 了啊!

Day 0

在叔叔家复习了模拟、搜索等基本内容。刷了 \(3\) 道水题。

Day 1

T1 铺设道路

我并不知道这是一道原题,因此我打了一个暴力搜索,小样例过了,大样例T了,慌得一批的我出了几组小的数据,过了,然后就没管这一题了。

我发现搜索的基本功很有用,毕竟它能使你暴力弄点分回来。

知道它是原题的我被震惊到了,立志下次NOIP之前要把以前的题都做一遍

我做题的思路大概是这样的:先遍历一遍,如果有地方是零,就左右分别递归

并不知道记录是否为0的book数组的优化是否有用……

 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
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>

using namespace std;

int n,cnt,minn=99999;
int d[100010],book[100010];

void search(int l,int r)
{
    if(l>=r)
    {
        cnt+=d[l];
        d[l]=0;
        return;
    }
    int flag=1;
    for(int i=l;i<=r;i++)
        if(d[i]==0)
        {
            flag=0;
            book[i]=1;
            int left=i-1,right=i+1;
            for(int j=i-1;j>=l;j--)
                if(book[j]==1)
                    left=j;
            search(l,left);//左右分别递归
            for(int j=i+1;j<=r;j++)
                if(book[j]==1)
                    right=j;
            search(right,r);//左右分别递归
        }
    if(flag==1)
    {
        cnt++;
        for(int i=l;i<=r;i++)
            d[i]--;
        search(l,r);
    }
}

int main()
{
    //freopen("road.in","r",stdin);
    //freopen("road.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&d[i]);
        minn=minn>d[i]?d[i]:minn;
    }
    for(int i=1;i<=n;i++)
        d[i]-=minn;//先处理一遍
    cnt+=minn;
    search(1,n);
    printf("%d",cnt);
    return 0;
}

T2 货币系统

并不会做这道题,所以就只准备拿前6个测试点的分(可是只得了15分???)(肯定有个地方出锅了)

话说

1
namespace point_x{ }

很好用,这让我的代码可读性很高,很容易调试

T3 赛道修建

然而还是不会做

分了namespace的我还是只得了5分

(肯定又有哪里出锅了)

原因暂未查明

普及组

T1 标题统计

这题甚是奇怪,在我的记忆中……NOIP普及组可是不曾考过字符串的啊

想都没想,5分钟就肝了这道题

考试源代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

string s;
int len;

int main()
{
    //freopen("title.in","r",stdin);
    //freopen("title.out","w",stdout);
    while(cin>>s)
        len+=s.length();
    cout<<len;
    return 0;
}

T2 龙虎斗

好复杂的模拟,为介绍清楚背景,CCF花了好多心思啊

不开 long$ $long 会后悔一生的!

考场上其实我是A了这道题的,但是莫名其妙洛谷只给了我80

考试源代码如下:

 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
#include <cstdio>

using namespace std;

long long n,m,p1,p2,s1,s2,sum,minn=2000000000;
long long c[100010];
long long tiger,dragon;
long long abs(long long a)
{
    if(a<0) return -a;
    else return a;
}

int main()
{
    //freopen("fight.in","r",stdin);
    //freopen("fight.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    scanf("%d %d %d %d",&m,&p1,&s1,&s2);
    c[p1]+=s1;
    for(int i=1;i<=m-1;i++)
        dragon+=(m-i)*c[i];
    for(int i=n;i>=m+1;i--)
        tiger+=(i-m)*c[i];
    for(int i=1;i<=n;i++)
    {
        if(i<=m)
            sum=abs(dragon+s2*(m-i)-tiger);
        else if(i>m)
            sum=abs(tiger+s2*(i-m)-dragon);
        if(sum<minn)
        {
            minn=sum;
            p2=i;
        }
        else if(sum==minn && i<=p2)
        {
            p2=i;
        }
    }
    printf("%d",p2);
    return 0;
}

T3 摆渡车

这是道dp题,刚出考场的我就意识到了这一点

可是考场上我却打的是个模拟

\(1\)\(m\)之间枚举车子出发的时间

于是我们得到了一个\(O(m\times max\sum\limits_{i=1}^{n}t_i+n)\)的算法:

 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
#include <cstdio>
#include <algorithm>

using namespace std;

int n,m,maxn=-99999;
int t[4000010];
long long ans=999999999;

int main()
{
    //freopen("bus.in","r",stdin);
    //freopen("bus.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int tim;
        scanf("%d",&tim);
        t[tim]++;
        if(tim>maxn)
            maxn=tim;
    }
    for(int i=0;i<m;i++)
    {
        long long tot=0;
        for(int j=0;j<=maxn;j++)
            if(t[j]>0)
                tot+=(m+i-j%m)%m;
        if(tot<ans)
            ans=tot;
    }
    printf("%d",ans);
    return 0;
}

然而只得了10分。希望有\(dalao\)能指出错误

T4 对称二叉树

当时时间不多了,再加上本来就没想着要得多少分,果断地放弃了正解,而是准备拿前三个测试点

然而事与愿违,我只拿到了前两个测试点得分

普及总分218,(在我们省)还算可以吧

这是我第一次也是最后一次参加普及组,以后要在提高组里被人虐啦!

Day 2

T1 旅行

dfs裸搜 感觉可以得 50,因为我自己造了几组m=n-1的数据,然而只得了 20。感觉还是特判没有判干净吧。

T2 填数游戏

考场上手算了几组数据,然而却CE了

原因竟是

1
rand()  #include <cstdlib> 

这导致我偷鸡不成蚀把米,要记住,下次可不能犯这样的错误啊!本可以再拿15分的。

T3 保卫王国

这道题完全没思路,不说了。

人生中的第一次NOIP就这么过去了,我懂得了许多:

  1. 练好基本功,搜索、模拟不能落下
  2. 要多熟悉各种基本算法
  3. 要多做历年的NOIP真题

NOIP,我们明年再见!