Noip 2016

Day1

　　　　思路：

　　　　大致是把一个环拆成链，找某个人无非是向右找或向左找（即对当前点加或减）

　　　　若加上要移动的位置后坐标大于总人数，就把当前坐标减去总人数，

　　　　若减去要移动的位置后坐标小于0，就把当前坐标加上总人数

　　　　另外要注意的就是每个小人的朝向问题，这个也很好解决。

　　　　通过观察不难发现，小人面朝里，向右移动的话，就是加，向左为减。

　　　　　　　　　　　　　小人面朝外则反之。

　　　　最后输出当前坐标小人的名称。

#include <iostream>

#include <cstdio>

#include <cstring>

#define Max 100003

using namespace std;

int N, M;

struct node

{

    int towards;

    string name;

}people [Max];

int main()

{

    scanf ("%d%d", &N, &M);

    int f;

    string a;

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

    {

        scanf ("%d", &people [i].towards);

        cin >> people [i].name;

    }

    int x, y;

    int now = ;

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

    {

        scanf ("%d%d", &x, &y);

        if (people [now].towards ==  && x == )

        {

            now -= y;

            if (now <= )

                now = N + now;

        }

        else if (people [now].towards ==  && x == )

        {

            now += y;

            if (now > N)

                now = now - N;

        }

        else if (people [now].towards ==  && x == )

        {

            now += y;

            if (now > N)

                now = now - N;

        }

        else if (people [now].towards ==  && x == )

        {

            now -= y;

            if (now <= )

                now = N + now;

        }

    }

    cout << people [now].name;

    return ;

}

第二题天天爱跑步

　　不会，当时做时就是骗的分

　　由数据范围可知：　　

　　前两个点所有玩家的起点等于终点，那么就好办了。

　　扫一遍所有的点，如果有玩家的起点在这个点上（因为起点与终点相同所以只需要判起点就好了），那么这个观察员可观察的人数加1。如此，最后输出即可

　　第三和第四个点是观察员的观测时间都是0，

　　那么只要扫一遍所有玩家的起点，把起点上的观测员可观察到的人数加一即可。

　　但是！！当时考试时我就是这么打的，结果一分没得。（原因不明）

　　（把自己的答案与标准答案比了半天也没发现哪有不同）。

第三题换教室

　　不会当时打的是暴力

　　当时思路就是先跑一边floyed 找处所有点的最短路

　　然后搜索可能的情况（类似于全排列），挨个算，算完后刷新最小值

　　但是还是写崩了，枚举可能的情况那一步怎么也打不对。

　　无奈想放弃治疗时，突然发现有些数据是m = 0 的，即只需跑一边裸的floyed。

　　找出最短路即可，结果floyed 初始化时忘记把对角线赋值为零（即当 i = j的情况）。

　　于是GG。 0分

Day2

第一题组合数

思路：

　　当时考场上时，由于未接触过组合数什么的

　　所以做此题时一头扎进他给的公式中出不来了

　　想了很久，大多是围绕直接算阶乘的方法。最后无果，只能打了个30%数据的表

　　骗了30.。

　　AC做法。。

　　动态规划，恩，好吧。。一点也没想到

　　大体上是运用递推，推出

　　公式为 number[i][j] = number[i-1][j-1]+number[i-1][j] 注意还要mod K，反正都是要求的是K的倍数，mod K一举两得

　　因为可能这个数会很大。。。。爆long long

　　如果mod K 后等于0，那么说明符合题意 i的计数器加一

　　最后再加到答案dp[i][j]中去 , dp[i][j] = dp[i-1][j] + 计数器

　　最后再注意判断一下 m 和 n 的关系这个题就OK了。。

#include <iostream>

#include <cstdio>

#include <cstring>

#define Max 2000

using namespace std;

long long number [Max][Max]; // 组合数 。number [i][j]表示i个东西选出j个东西的方案数

long long dp [Max][Max]; // dp[i][j] 表示的是i个东西选出j个东西 方案中是k的倍数 的方案数

long long Total [Max];

inline void read (int &now)

{

    char word = getchar ();

    now = ;

    while (word > '' || word < '')

        word = getchar ();

    while (word <= '' && word >= '')

    {

        now = now *  + (int)(word - '');

        word = getchar ();

    }

}

int main()

{int T, K;

    read (T);

    read (K);

    number [][] = ; //初始化

    for (int i = ; i <= Max; i++)  //先把所有的预处理出来， 否则 每次都查询会超时。。

    {

        number [i][] = ; //初始化 i个物品选0个的方案数为 1

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

        {

            number [i][j] = (number [i - ][j - ] + number [i - ][j]) % K; // 递推求组合数  number[i][j]是由上一个物品选或不选递推而来

            if (number [i][j] == )  //如果能被K整除  计数器加一

                Total [i]++;

            dp [i][j] = dp [i - ][j] + Total [i];  //i个物品选出j个 的方案数满足条件的 是上一个状态加上这一个状态的总数得出

            if (i == j) // 注意判断一下i == j 即i个物品选i个 的情况 。

                dp [i][j] = Total [i] + dp [i - ][j - ];

        }

    }

    while (T--)

    {

        int n, m;

        read (n);

        read (m);

        cout << dp [n][m > n ? m = n : m] << endl; //因为 0 <= m <= min (m, n), 所以要判断一下

    }

    return ;

}

第二题蚯蚓

　　非常苦逼

　　当时做的时候加了一堆特判。

　　不能特判的就打了个十分十分朴素的做法。结果拿了20.

　　可当我拿过程序来自己测试的时候，竟神奇的得了25分。

　　然后把所有的特判都去掉，就拿了35分。。。。。。。。。。。

　　当时的做法就是用优先队列存所有蚯蚓的长度。

　　每次取出堆顶元素，后将堆顶元素弹出。

　　再开个临时数组，存堆中的元素，然后在把他们加上特定长度后再扔到堆里。

　　再是对堆顶元素的操作，模拟一下，把它分成两段，都扔到堆里。

　　最后把堆里的元素都输出。。这是35分。。

第三题愤怒的小鸟

　　不会。

　　当时是想直接枚举 for（-10.00 to 10.00 )

　　但是时间不太够了，前两题耗费了太多时间。。只能弃了。

　　于是，蒟蒻的Noip2016 就这样画上了句号

　　说到此次noip的感想。。。

　　由于自己是去当分母的，所以并没有什么太大的想法。

　　考试前是抱着不爆零的心态去的。

　　但是实际做了一下题目后发现实际上是可以骗到很多分的，即使你不会做。

　　可还是由于种种失误，分数与自己的预期差别很大。。

　　所以先简单反思一下自己出现的问题

1 . 时间分配非常不合理。无论是哪一次考试我都或多或少的存在这个问题。当拿到一个题看似很简单时，就会不假思索的去写。写的过程中经常会出现很多问题。比如写着写着发现这个地方自己实现不了了，又或者是写出来了但是写崩了。这时候心态就会爆炸，变的很慌，越是写不出来，就越要把它写出来，然而这样就陷入到了恶性循环中。。。。

2 . 丢三落四。比如这次day1的T3， floyed竟然忘了初始化邻接矩阵的对角线为0,就这样很坑的丢掉了至少30分(数据有些是直接跑一次多源最短路就可以过的)。

3 . 思路不清晰就开始写。。。肯定吃枣药丸。很多时候写着写着就不会写了。更有甚者写着写着发现思路根本不对，当时只是想当然的认为是这样做，就不去多深究，急急忙忙开始写。下场大多都比较惨。

4 . 基础不牢，一些简单的东西打不出来，就像day1 T3 当时是能打出暴力的(虽然会比骗的分少)，但是有一个类似于全排列的东西打不出来了。。就挂了。

所以问题大致有这么几个。。以后还要改正。

　　再一个就是平时上课了。。效率很低。

　　做题慢，整理算法也不快。

　　我觉得自己知识上薄弱的方面是动规和数论。。一看见就头疼。

　　这个原因也是多方面的，一是动规当时学的时候就学的不好。学完后没做多少练习题，就转到别的方面去了。。。并且之后一见到动规题就想跳，导致动规一直很渣。

　　二是数论，关于数论，做过的学习就只有听了一节数学课。。。。并且平时还是缺少练习。数论的一些思想，原理，公式都不知道怎么应用。。数论也是渣。

　　当然这也并不代表我别的方面就很好。。比如和我相同的人，有时他们说的算法根本就不会。。所以说，我要走的路还很长。

　　以后的努力方向我个人觉得要是做题为主，我的目标是把洛谷试炼场上的题从入门到提高专题挨个做一遍。。

巴特西

Noip 2016

最新文章

热门文章