2012年NOIP普及组复赛题解

题目涉及算法：

• 质因数分解：入门；
• 寻宝：模拟；
• 摆花：动态规划；
• 文化之旅：搜索。

质因数分解

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

这道题目只需要开个 for 循环就能够把书求出来。

开一个循环变量 i 从 2 开始一直加加，碰到的第一个能够整除n的i，就输出 \(n/i\) 然后 break 即可。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

int n;

int main() {

    cin >> n;

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

    return 0;

}

寻宝

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

标准模拟题，模拟一下爬房间的过程即可。

但是我语文不好，这道题目读了半天才读懂。

可以优化，优化原理是去除没存寻找的循环。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int MOD = 20123;

int n, m, has_key[10010][110], num[10010][110], sum[10010], id, ans;

int main() {

    cin >> n >> m;

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

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

            cin >> has_key[i][j] >> num[i][j];

            if (has_key[i][j]) sum[i] ++;

        }

    cin >> id;

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

        int cnt = 0;

        int x = num[i][id] % sum[i];

        if (x == 0) x = sum[i];

        ans = (ans + num[i][id]) % MOD;

        while (true) {

            if (has_key[i][id]) {

                cnt ++;

                if (cnt == x) break;

            }

            id = (id + 1) % m;

        }

    }

    cout << ans << endl;

    return 0;

}

摆花

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

这道题目用动态规划求解。

我们令状态 \(f[i][j]\) 表示前 \(i\) 种花一共放了 \(j\) 盆的方案数，则：

• \(f[0][0] = 0\) ；
• \(f[i][j] = \sum_{k=0}^{\min(a[i], j)} f[i-1][k]\)

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000007;

const int maxn = 110;

int n, m, a[maxn], f[maxn][maxn];

int main() {

    cin >> n >> m;

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

    f[0][0] = 1;

    for (int i = 1; i <= n; i ++)

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

            for (int k = 0; k <= a[i] && j-k >= 0; k ++)

                f[i][j] = (f[i][j] + f[i-1][j-k]) % MOD;

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

    return 0;

}

文化之旅

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

建图，按条件深度优先搜索一下。

然后这道题目的数据可能比较水，所以我在其中加了一个条件，就是步数超过1000我就直接判定为找不到，然后就AC了囧~。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;

int N, K, M, S, T, d = INT_MAX, c[maxn], a[maxn][maxn], u, v, w;

bool vis[maxn];

vector< pair<int, int> > g[maxn];

void dfs(int u, int tmp) {

    if (tmp >= 1000) return;	// 没想到这样就AC了~~~

    if (tmp >= d) return;

    if (u == T) {

        d = tmp;

        return;

    }

    vis[ c[u] ] = true;

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

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

        int v = g[u][i].first;

        int w = g[u][i].second;

        if (vis[ c[v] ] ) continue;

        bool flag = true;

        for (int i = 1; i <= K; i ++) {

            if (vis[i] && a[ c[v] ][i]) {

                flag = false;

                break;

            }

        }

        if (flag) {

            dfs(v, tmp+w);

        }

    }

    vis[ c[u] ] = false;

}

int main() {

    cin >> N >> K >> M >> S >> T;

    for (int i = 1; i <= N; i ++) cin >> c[i];

    for (int i = 1; i <= K; i ++)

        for (int j = 1; j <= K; j ++)

            cin >> a[i][j];

    while (M --) {

        cin >> u >> v >> w;

        g[u].push_back( make_pair(v, w) );

        g[v].push_back( make_pair(u, w) );

    }

    dfs(S, 0);

    if (d == INT_MAX) d = -1;

    cout << d << endl;

    return 0;

}