2002年NOIP普及组复赛题解

题目涉及算法：

级数求和：入门题；
选数：搜索；
产生数：搜索、高精度；
过河卒：动态规划。

级数求和

题目链接：https://www.luogu.org/problemnew/show/P1035

开一个for循环，每次加上1/i，知道和 \(\gt K\) 即可。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

double s, K;

int i;

int main() {

    cin >> K;

    for (i = 1; s <= K; i ++) s += 1. / (double) i;

    cout << i-1 << endl;

    return 0;

}

选数

题目链接：https://www.luogu.org/problem/P1036

直接搜索遍历所有的情况，再判断每一种情况下的和是否是素数，即可。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

int n, k, a[22], ans;

bool is_prime(int a) {

    if (a < 2) return false;

    for (int i = 2; i *i <= a; i ++)

        if (a % i == 0) return false;

    return true;

}

void dfs(int pre, int cnt, int tmp) {

    if (cnt >= k) {

        if (is_prime(tmp)) ans ++;

        return;

    }

    for (int i = pre+1; i <= n-k+cnt; i ++) {

        dfs(i, cnt+1, tmp+a[i]);

    }

}

int main() {

    cin >> n >> k;

    for (int i = 0; i < n; i ++) cin >> a[i];

    dfs(-1, 0, 0);

    cout << ans << endl;

    return 0;

}

产生数

题目链接：https://www.luogu.org/problemnew/show/P1037

这道题目就是要判断一下 \(0\) 到 \(9\) 这 \(10\) 个数分别能衍生出多少个数。

这里可以用搜索遍历一下，用 \(cnt[i]\) 来表示 \(i\) 可以达到的数的数量。

然后就去遍历一开始给我们的数的每一位，假设第i为对应的数字是 \(a\) ，那么答案将乘上 \(cnt[a]\) 。

最终输出答案即可。

不过由于答案有可能达到 \(30^{10}\) ，所以得用高精度。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100;

vector<int> g[11];

bool vis[11];

char s[33];

int n, cnt[11], ans[maxn] = { 1 }, tmp[maxn];

void dfs(int u) {

    if (vis[u]) return;

    vis[u] = true;

    int sz = g[u].size();

    for (int i = 0; i < sz; i ++) {

        int v = g[u][i];

        dfs(v);

    }

}

void multi(int a) {

    memset(tmp, 0, sizeof(tmp));

    for (int i = 0; i < maxn; i ++) {

        tmp[i] += ans[i] * a;

        tmp[i+1] += tmp[i] / 10;

        tmp[i] %= 10;

    }

    for (int i = 0; i < maxn; i ++) ans[i] = tmp[i];

}

int main() {

    cin >> s >> n;

    while (n --) {

        int a, b;

        cin >> a >> b;

        g[a].push_back(b);

    }

    for (int i = 0; i <= 9; i ++) {

        memset(vis, 0, sizeof(vis));

        dfs(i);

        if (i == 0) cnt[i] ++;

        for (int j = 1; j <= 9; j ++) if (vis[j]) cnt[i] ++;

    }

    n = strlen(s);

    for (int i = 0; i < n; i ++) {

        int a = s[i] - '0';

        multi(cnt[a]);

    }

    int i = maxn - 1;

    while (!ans[i] && i > 0) i --;

    while (i >= 0) cout << ans[i--];

    cout << endl;

    return 0;

}

过河卒

题目链接：https://www.luogu.org/problem/P1002

这道题目是一道动态规划题。

我们令 \(f[i][j]\) 表示从 \((0,0)\) 走到 \((i,j)\) 的方案数，那么：

如果 \((i,j)\) 对应就是马的位置或者在马的公鸡范围内，则 \(f[i][j] = 0\) ；
否则（注意，这个否则非常重要），如果 \(i=0,j=0\) ，则 \(f[i][j] = 1\) ；
否则，如果 \(i=0\) ，则 \(f[i][j] = f[i][j-1]\) ；
否则，如果 \(j=0\) ，则 \(f[i][j] = f[i-1][j]\) ；
否则，\(f[i][j] = f[i-1][j] + f[i][j-1]\) 。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 22;

int n, m, x, y;

long long f[maxn][maxn];

int main() {

    cin >> n >> m >> x >> y;

    for (int i = 0; i <= n; i ++) {

        for (int j = 0; j <= m; j ++) {

            if (x==i && y==j || abs(x-i)==1 && abs(y-j)==2 || abs(x-i)==2 && abs(y-j)==1)

                f[i][j] = 0;

            else if (!i && !j) f[i][j] = 1;

            else if (!i) f[i][j] = f[i][j-1];

            else if (!j) f[i][j] = f[i-1][j];

            else f[i][j] = f[i-1][j] + f[i][j-1];

        }

    }

    cout << f[n][m] << endl;

    return 0;

}

巴特西

2002年NOIP普及组复赛题解

级数求和

选数

产生数

过河卒

最新文章

热门文章