题目涉及算法:
- 明明的随机数:简单模拟;
- 开心的金明: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