2002-NOIP-普及组：复赛真题及解析
说明：点击题目名称即可跳转原题链接 🙂
级数求和
思路
- 循环枚举 1/i (i: 1 ~ n)，将每一项的浮点值累加到总和变量 s 上，当 s > k 时结束，输出是第几项。
代码-1
#include <bits/stdc++.h>
using namespace std;
int main(){
int k;
scanf("%d", &k);
double s = 0;
for(int i = 1; ; i++){
s += 1.0 / i;
if(s > k){ // 当算到 s > k 时
printf("%d", i); // 最小的 n 就是第 i 项
break;
}
}
return 0;
}
代码-2
#include <bits/stdc++.h>
using namespace std;
int main(){
int k, i;
scanf("%d", &k);
double s = 0;
for(i = 1; s <= k; i++){
s += 1.0 / i;
}
printf("%d", --i); // 循环结束时的 i 是 s > k 之后，要减 1 输出
return 0;
}
选数
思路
- 一道 n 选 k 的组合枚举问题 + 质数判断，可以用 dfs 实现，搜索过程中还可以加入剪枝优化。
代码-1：dfs 组合枚举
#include <bits/stdc++.h>
using namespace std;
int n, k, a[25], ans;
bool isprime(int x){
if(x < 2) return 0;
for(int i = 2; i * i <= x; i++){
if(x % i == 0) return 0;
}
return 1;
}
void dfs(int p, int x, int sum){ // 当前到第 p 个数，已选 x 个数，总和为 sum
if(x > k) return; // 剪枝：选数多于 k 个的情况直接结束
if(n - p + 1 < k - x) return; // 剪枝：k - x(剩余要选的数个数) > n - p + 1(剩余可选数个数)
if(p == n + 1){
if(x == k && isprime(sum)){ // 满足条件的方案
ans++;
}
return;
}
dfs(p + 1, x, sum); // 不选第 p 个数
dfs(p + 1, x + 1, sum + a[p]); // 选第 p 个数
}
int main(){
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
dfs(1, 0, 0);
printf("%d", ans);
return 0;
}
代码-2：枚举 n 位二进制数，找到 1 的个数为 k 的组合
#include<bits/stdc++.h>
using namespace std;
bool isprime(int x){
for(int i = 2; i * i <= x; i++){
if(x % i == 0){
return 0;
}
}
return 1;
}
int popcnt(int x){ // 计数 x 二进制下 1 的个数
int cnt = 0;
while(x){
x &= (x - 1);
cnt++;
}
return cnt;
}
int main(){
int n, k, a[25], ans = 0;
cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> a[i];
}
int u = 1 << n; // n 位二进制取值范围：[0, u)
for(int s = 0; s < u; s++){
if(popcnt(s) == k){ // 二进制下出现 k 个 1
int sum = 0;
for(int i = 0; i < n; i++){ // 找出为 1 的位，将该位数累加
if((1 << i) & s){ // 第 i 位在 s 中为 1 (i 从 0 开始计)
sum += a[i];
}
}
if(isprime(sum)){
ans++;
}
}
}
cout << ans;
return 0;
}
产生数
思路
- 数字规则转换可以直接 x -> y，也可以间接传递转换，例如若 x -> y，且 y -> z，那么可推出 x -> z。对于间接转换方案的求解，可以采用图论中的 Floyd 算法，当 x -> y 时，我们把 a[x][y] 标记成 1，再寻找中转结点 k，a[x][k] 和 a[k][y] 都为 1 时，a[x][y] 也成立。注意每个数自己也是一种方案，a[x][x] 也要标记成 1。
- 求出每个数能表示成的方案总数，即对于 i (i:0~9) 来说，有多少个 a[i][j] (j: 0 ~ 9) 是 1。
- 遍历输入数字串（数据很大，字符串输入），求出每位对应数字表示，将每位方案数根据乘法原理相乘求出总方案数。同样，由于数据位数很大，这里需要用高精度乘低精度计算，结果存于数组中。
- 高位到低位输出高精度答案数组的值。
代码
#include<bits/stdc++.h>
using namespace std;
string n;
int k, a[15][15], b[15], c[50];
int main(){
cin >> n >> k;
while(k--){
int x, y;
cin >> x >> y;
a[x][y] = 1;
}
// Floyd 求间接转换方案数
for(int k = 1; k <= 9; k++){ // 可转换成的数：1 ~ 9
for(int i = 0; i <= 9; i++){ // 枚举规则左部的数：0 ~ 9
a[i][i] = 1; // 每个数自己是一种方案
for(int j = 1; j <= 9; j++){ // 枚举规则右部的数：1 ~ 9
if(a[i][k] && a[k][j] && !a[i][j]){
a[i][j] = 1; // 标记间接转换 1
}
}
}
}
for(int i = 0; i <= 9; i++){ // 求每个数能表示的方案数
for(int j = 0; j <= 9; j++){
if(a[i][j]){
b[i]++; // b[i]: i 的转换方案数
}
}
}
c[1] = 1; // 初始化高精度答案数组
int len = 1; // 初始化答案长度
for(int i = 0; n[i]; i++){ // 遍历原串数字
int x = n[i] - '0';
for(int j = 1; j <= len; j++){ // 高精 * 低精求方案数
c[j] *= b[x];
}
for(int j = 1; j <= len; j++){ // 处理进位
c[j + 1] += c[j] / 10;
c[j] %= 10;
}
while(c[len + 1]){ // 处理最高位进位
len++;
c[len + 1] = c[len] / 10;
c[len] %= 10;
}
}
for(int i = len; i >= 1; i--){
cout << c[i];
}
return 0;
}
过河卒
思路
- 经典的二维 DP/递推 问题。对于点 a[i][j] 来说，其状态转移方程就是 a[i-1][j] 与 a[i][j-1] 的路径数总和（前提是该点可达）。
- 需要特别注意以下几点：
- 答案数据增长会很快，需要 long long 数组存答案；
- 在标记马的控制点和判断上一步的点是否可达时，推算的坐标出现减法计算都要特判下是否越界，只有 >= 0 的坐标才是合法的；
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
/* In: 20 20 4 0 Out: 56477364570 */
int bx, by, hx, hy;
ll a[25][25]; // a[i][j]：从 A(0, 0) 到 (i, j) 的路径数
int main(){
cin >> bx >> by >> hx >> hy;
// 把马的坐标及其控制点标记为不可走 (-1)
a[hx][hy] = -1;
int d[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
{1, -2}, {1, 2}, {2, -1}, {2, 1}};
for(int i = 0; i < 8; i++){
int x = hx + d[i][0], y = hy + d[i][1];
if(x >= 0 && y >= 0){ // 避免下标越界
a[x][y] = -1;
}
}
a[0][0] = 1; // 初始化起点路径数为 1 表示可由此出发
for(int i = 0; i <= bx; i++){
for(int j = 0; j <= by; j++){
if(a[i][j] != -1){ // 若该处可达
a[i][j] += (a[i-1][j] != -1 && i >= 1 ? a[i-1][j] : 0);
a[i][j] += (a[i][j-1] != -1 && j >= 1 ? a[i][j-1] : 0);
}
}
}
cout << a[bx][by];
return 0;
}