2006年NOIP普及组复赛题解

题目涉及算法：

• 明明的随机数：简单模拟；
• 开心的金明：01背包；
• Jam的计数法：模拟；
• 数列：二进制。

明明的随机数

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

简单模拟：排序+去重。使用 sort + unique 实现。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, a[111];
int main() {
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
sort(a, a+n);
n = unique(a, a+n) - a;
cout << n << endl;
for (int i = 0; i < n; i ++) {
if (i) putchar(' ');
cout << a[i];
}
cout << endl;
return 0;
}


开心的金明

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

这道题目就是一道裸的01背包，每件物品的体积对应价格，价值对应价格和重要度的乘积。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 30030;
int V, n, c, p, f[maxn];
int main() {
cin >> V >> n;
while (n --) {
cin >> c >> p;
for (int i = V; i >= c; i --)
f[i] = max(f[i], f[i-c] + c * p);
}
cout << f[V] << endl;
return 0;
}


Jam的计数法

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

模拟题，找到单调递增的字符串的下一个排列。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
bool used[26];
char ch[30];
int s, t, w;bool get_next() {
memset(used, 0, sizeof(used));
for (int i = 0; i < w; i ++) used[ ch[i] - 'a' ] = true;
for (int i = w-1; i >= 0; i --) {
int st = ch[i] - 'a';
int cnt = 0;
for (int j = st+1; j <= t; j ++) if (!used[j]) cnt ++;
if (cnt >= w-i) {
int id = i;
for (int j = st+1; j <= t; j ++) {
if (!used[j]) {
ch[id++] = 'a' + j;
if (id >= w) break;
}
}
return true;
}
used[st] = false;
}
return false;
}int main() {
cin >> s >> t >> w >> ch;
s --; t --;
for (int i = 0; i < 5 && get_next(); i ++)
cout << ch << endl;
return 0;
}


数列

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

这道题目需要对二进制有一个理解。

对于 N ，如果我们将其转成二进制数是 \(a_ma_{m-1} \dots a_1a_0\) ，其中 \(a_i\) 为1表示结果中包含 \(k^i\) ，\(a_i\) 为0表示结果中不包含 \(k^i\) 。

那么我们可以发现：

N 对应的数 \(\gt\) N-1 对应的数 \(\gt\) N-2对应的数 …… \(\gt\) 1 对应的数 \(\gt\) 0 对应的数。

所以我们的答案就是N对应的二进制中所有为1的那些位i的 \(\sum k^i\) 。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, k;
long long ans;
long long quick_mi(long long a, int b) {
if (b == 0) return 1;
if (b == 1) return a;
long long t = quick_mi(a, b/2);
t *= t;
if (b % 2) t *= a;
return t;
}
int main() {
cin >> k >> n;
for (int i = 0; i <= 10; i ++)
if ( n & (1<<i) )
ans += quick_mi(k, i);
cout << ans << endl;
return 0;
}


作者：zifeiy