1. 珠心算测验

来源：NOIP2014提高组

算法知识点: 枚举，哈希，预处理

复杂度：

解题思路：

由于每个数的范围都在10000以内，因此两个数的和在20000以内，所以可以开一个长度是20000的bool数组，然后枚举所有数对，将所有计算出的两数之和标记一下。

然后再枚举每个数，利用bool数组判断它是否是某两个数的和。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 110;

int n;
int a[N];
bool st[20010];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            st[a[i] + a[j]] = true;

    int res = 0;
    for (int i = 0; i < n; i++) res += st[a[i]];

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

    return 0;
}

 

2. 比例简化

来源：NOIP2014提高组 https://ac.nowcoder.com/acm/contest/242/C

算法知识点: 枚举，欧几里得算法，数论)

复杂度：

解题思路：

由于 在100以内，因此可以枚举 的所有组合，然后判断：

  • 是否互质；
  • 是否大于等于 ，并且最小

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int A, B, L;
    cin >> A >> B >> L;

    int a, b;
    double delta = 1e9;
    for (int i = 1; i <= L; i++)
        for (int j = 1; j <= L; j++)
            if (gcd(i, j) == 1)
            {
                double x = i * 1.0 / j;
                double X = A * 1.0 / B;

                if (x >= X && x - X < delta)
                {
                    delta = x - X;
                    a = i, b = j;
                }
            }

    cout << a << ' ' << b << endl;

    return 0;
}

 

3. 扫雷游戏

来源：NOIP2015提高组 https://ac.nowcoder.com/acm/contest/243/C

算法知识点: 枚举

复杂度：

解题思路：

依次枚举每个空格，然后统计八个方向上的相邻格子有没有地雷即可。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 110;

int n, m;
char g[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) cin >> g[i];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if (g[i][j] == '*') cout << '*';
            else
            {
                int s = 0;
                for (int x = i - 1; x <= i + 1; x++)
                    for (int y = j - 1; y <= j + 1; y++)
                        if (x != i || y != j)
                        {
                            if (x >= 0 && x <n && y>= 0 && y < m && g[x][y] == '*') s++;
                        }
                cout << s;
            }
        cout << endl;
    }

    return 0;
}

 

4. 回文日期

来源：NOIP2016提高组

算法知识点: 枚举,模拟

复杂度：

解题思路：

由于只有八位数，而且回文串左右对称，因此可以只枚举左半边，这样只需枚举 总共一万个数，然后判断：

  • 整个八位数构成的日期是否合法；
  • 是否在范围内

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int months[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

bool check(int date)
{
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;

    if (!month || month > 13 || !day) return false;

    if (month != 2 && day > months[month]) return false;
    if (month == 2)
    {
        bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }

    return true;
}

int main()
{
    int date1, date2;
    cin >> date1 >> date2;

    int res = 0;
    for (int i = 0; i < 10000; i++)
    {
        int x = i, r = i;
        for (int j = 0; j < 4; j++) r = r * 10 + x % 10, x /= 10;

        if (r >= date1 && r <= date2 && check(r)) res++;
    }

    printf("%d\n", res);
    return 0;
}

 
另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ