2019牛客暑期NOIP真题班普及组3-枚举1

1. 数字统计

来源：NOIP2010普及组 https://ac.nowcoder.com/acm/contest/238/D

算法：枚举

复杂度：

解题思路：

直接枚举 到 中的每个数，再依次判断每一位是否等于 即可。

C++ 代码：

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

int main()
    {
        int l, r;
        cin >> l >> r;

        int res = 0;
        for (int i = l; i <= r; i++)
            for (int j = i; j; j /= 10)
                if (j % 10 == 2)
                    res++;

        cout << res << endl;

        return 0;

2. 导弹拦截

来源：NOIP2010普及组 https://ac.nowcoder.com/acm/contest/238/B

算法：枚举,排序

复杂度：

解题思路：

先用第一个雷达包围所有点，然后不断缩小第一个雷达的半径，每次圆边缘的点会从圈内出来，我们用第二个雷达去包含它 即可。

枚举半径的方法：先将所有点按到第一个雷达的距离从大到小排序，依次枚举所有点所在的圆的半径即可。

用第二个雷达去包含新点的方法：如果新点到第二个雷达的距离大于当前半径长度，则将半径更新成新的距离。

C++ 代码：

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

int n;
int a1, b1, a2, b2;

struct Point
{
    int x, y;
    int d;
    bool operator < (const Point &W) const
    {
        return d < W.d;
    }
}
point[N];

int get_dist(int x1, int y1, int x2, int y2)
{
    int dx = x1 - x2;
    int dy = y1 - y2;
    return dx *dx + dy *dy;
}

int main()
{
    scanf("%d%d%d%d", &a1, &b1, &a2, &b2);
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        point[i] = {
            x, y, get_dist(x, y, a1, b1)
        };
    }

    sort(point, point + n);
    reverse(point, point + n);

    int res = point[0].d, r = 0;
    for (int i = 1; i <= n; i++)
    {
        r = max(r, get_dist(point[i - 1].x, point[i - 1].y, a2, b2));
        res = min(res, point[i].d + r);
    }

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

3. 质因数分解

来源：NOIP2012普及组 https://ac.nowcoder.com/acm/contest/240/D

算法：枚举,数学

复杂度：

解题思路：

所有约数都是成对出现的：如果 是 的约数，那么 也是 的约数。

我们可以只枚举较小的约数，然后计算出较大的约数即可。那么需要枚举的范围满足： ，则 。因此只需要枚举 次。

C++ 代码：

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 2;; i++)
        if (n % i == 0)
        {
            cout << n / i << endl;
            break;
        }

    return 0;
}

4. 计数问题

来源：NOIP2013普及组 https://ac.nowcoder.com/acm/contest/241/D

算法：枚举

复杂度：

解题思路：

直接枚举 到 中的每个数，再依次判断每一位是否等于 即可。

C++ 代码：

#include <iostream>
using namespace std;

int main()
{
    int n, x;
    cin >> n >> x;

    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j; j /= 10)
            if (j % 10 == x)
                res++;

    cout << res << endl;

    return 0;
}

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