集训真题：
CSP-J2019NOIP普及组初赛真题
笔记补充：
二、阅读程序
- 程序大意：对于字符串中的第i位，如果i是n的约数，并且第i个字符比'a'(97)要大，就减少'a'(97)-'A'(65)。
#include <cstdio>
#include <cstring>
using namespace std;
char st[100];
int main() {
scanf("%s", st);
int n = strlen(st); // 计算字符串的长度
for (int i = 1; i <= n; ++i) { // 对字符串中的第i个字符进行循环枚举
if (n % i == 0) { // 判断i是否是n的约数
char c = st[i - 1]; // 取出字符串中的第i个字符
if (c >= 'a') // 判断字符是否大于97
st[i - 1] = c - 'a' + 'A'; // 将字符减少32
}
}
printf("%s", st); // 输出字符串
return 0;
}
1）考察程序的输入输出。
程序中没有对字符串中的字符范围进行任何要求。
2）考察表达式运算，除法和取模。
如果i = 0，那么在n对i进行取模运算时就会报错，因为除以0了。
3）考察约数判断，注意不是素数判定。
判断素数的时候通常用这种方式进行加速，是因为sqrt(n)之后的约数与之前的约数是一一对应的，这也就说明了sqrt(n)之后还有约数。
如果将循环范围缩小了，就不会处理后面的约数，导致答案不一样。
4）考察数据类型，字符型的存储与表示。
大写字母的ASCII码都要小于'a'(97)，所以不会对字符串进行修改。
5）考察数学，约数数量计算。
将要计算的数分解质因数，每个质因数的出现次数加1，再乘起来就是约数个数。
最多时每个约数的位置都可以修改，18有6个约数。
6）考察数学，约数数量计算。
10000 = 2^5 \* 5^5，一共有(5 + 1) \* (5 + 1) = 36个约数。
不会求约数个数的同学可以暴力算一下其他几个数的约数个数，用排除法也能得到这个答案。
程序大意：有ab两组元素，两组元素之间可以两两配对（0可以任意次配对）。
初始时所有元素都和另一组的0配对，每次考察a组的第x个元素和b组的第y个元素，如果这两个元素之前的配对交叉了，则把它们之前的配对元素都重新配对到0，并将这两个元素配对。
最后求有多少个元素和0配对。
#include <cstdio>
using namespace std;
int n, m;
int a[100], b[100];
int main() {
scanf("%d%d", &n, &m); // n个数与m次操作
for (int i = 1; i <= n; ++i) // 初始时所有数都跟0配对
a[i] = b[i] = 0;
for (int i = 1; i <= m; ++i) {
int x, y;
scanf("%d%d", &x, &y);
if (a[x] < y && b[y] < x) { // 对于想要配对的数，判断原先的一对配对是否交叉
if (a[x] > 0) // 将原先的配对元素重新和0配对
b[a[x]] = 0;
if (b[y] > 0)
a[b[y]] = 0;
a[x] = y; // 当前两个元素建立新的配对
a[y] = x;
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) { // 统计和0配对的元素数量
if (a[i] == 0)
++ans;
if (b[i] == 0)
++ans;
}
printf("%d\n", ans);
return 0;
}
1）考察对程序含义的理解。
m > 0时一定会有一个配对，所以和0配对的元素的数量一定小于2n。
2）考察对程序含义的理解，反例设计。
统计是按照元素编号的顺序进行的，如果有一个x < y的配对，那么统计完b中的第x个元素时ans会变成奇数。
3）考察对程序含义的理解，反例设计。
如果ab中的第i个元素进行配对，则a[i]和b[i]同时>0。
4）考察对程序含义的理解，反例设计。
x总是小于y不代表x之前没有别的配对，如果x之前有别的配对，则照样会执行清理。
可以依次对(1, 1)和(1, 2)进行配对，则第二次操作时会对1的配对进行清理。
5）考察对程序含义的理解。
x和y两两不同时，每次都会成功进行配对，m次会产生m对配对，所以和0配对的元素数量为2n - 2m。
6）考察对程序含义的理解。
x各不相同，y每次相等，那么x和y配对时每次都会清理掉之前的配对，最终只会产生一组配对，所以和0配对的元素数量为2n - 2。
3、程序大意：将一个元素序列根据a值构造成一棵二叉树，每次在序列中选择a值最小且最靠前的元素作为根，根之前的序列构建左子树，根之后的序列构建右子树。
最后求出每个节点的深度乘以b值的和。
#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) { // 计算序列中l到r这几个元素构成的根深度为depth的子树的权值
if (l > r) // 判断空子树
return 0;
int min = maxn, mink;
for (int i = l; i <= r; ++i) { // 查找a值最小的最靠左的元素
if (min > a[i]) {
min = a[i]; // 记录最小值
mink = i; // 记录位置
}
}
int lres = f(l, mink - 1, depth + 1); // 计算左子树
int rres = f(mink + 1, r, depth + 1); // 计算右子树
return lres + rres + depth * b[mink]; // 当前子树的权值为左右子树权值与根权值的和
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) // 读入每个元素的a值
cin >> a[i];
for (int i = 0; i < n; ++i) // 读入每个元素的b值
cin >> b[i];
cout << f(0, n - 1, 1) << endl; // 构建子树并计算权值
return 0;
}
1）考察循环遍历数组，也可以直接进行反例设计。
重复的a值不影响查找最小元素，所以不会出错。
2）考察对程序含义的理解。
所有元素的b值为0，则权重也全部为0，总权重就是0。
可以根据程序观察一下，所有的计算都会和b值进行相乘，没有常数，也可以猜到结果为0。
3）考察数据结构二叉树，节点分层时的特性，最劣极端情况。
每个子树中的每个节点都会进行一次比较，最坏情况下二叉树有n层（每次只划分出一个子树），所以比较次数为100 + 99 + ... + 1 = 5050，与5000最接近。
4）考察数据结构二叉树，节点分层时的特性，最优极端情况。
最少情况下二叉树有log层，100个节点约为7层，每一层的总节点数估算为n，则比较次数大约为700次，与600最接近。
5）综合考察对程序含义的理解、二叉树的结构与数学计算。
为了让输出最大，则需要让b值大的元素深度尽可能的大，一条链可以达成这个要求，则权值为1^2 + 2^2 + ... + 10^2 = 385。
6）综合考察对程序含义的理解、二叉树的结构与数学计算。
每个元素的b值均为1，则计算的是元素的深度和，所以需要让二叉树的深度尽可能小。
那么第一层可以有1个节点，第二层可以有2个，第三层可以有4个，以此类推。权值为1 \* 1 + 2 \* 2 + 4 \* 3 + 8 \* 4 + ... + 32 \* 6 + 37 \* 7 = 580，注意最后一层节点数不满。
三、完善程序 程序思路：考察分治算法，通过递归的方式来对矩阵进行填充。
从0作为元开始，每次将当前的矩阵划分成四个子矩阵，对应了一次变换，并根据变化规则分别得到四个子矩阵的元。
子矩阵用递归的方式进行填充，直到不再变换。
#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;
int res[max_size][max_size]; // 01矩阵
void recursive(int x, int y, int n, int t) { // 填充左上角为(x, y)的n阶子矩阵，且元为t
if (n == 0) { // 0阶矩阵只有一个数
res[x][y] = t; // 等于元，不再变换
return;
}
int step = 1 << (n - 1); // 分成的子矩阵之间的距离
recursive(x, y, n - 1, t); // 左上角的子矩阵，元不变
recursive(x, y + step, n - 1, t); // 右上角的子矩阵，元不变
recursive(x + step, y, n - 1, t); // 左下角哦的子矩阵，元不变
recursive(x + step, y + step, n - 1, !t); // 右下角的子矩阵，元取反
}
int main() {
scanf("%d", &n);
recursive(0, 0, n, 0); // 初始时要填充左上角为(0, 0)的n阶子矩阵，初始时元为0
int size = 1 << n; // n阶矩阵的宽度为2^n
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j)
printf("%d", res[i][j]);
puts("");
}
return 0;
}
下面讲解一下对于不能完全看懂程序的同学该如何选择。
1）如果填写一个常数，那整个矩阵就是常数矩阵了。
而且这个t在函数中传递下来就只有这里可以直接使用，其他地方都是参数。
所以除了t也没别的选择。
2）分成四个子矩阵，看不懂程序的根据另外两行都能猜出来。
另外两行中可以发现，x和y分别有加与不加两种可能，组合起来正好四种可能，所以肯定没减号。
3）同上。
4）通过函数中的参数命名可以猜出肯定是n了。
然后测一下n = 1就可以确定第二个参数填0。
5）测一下n = 1就知道肯定是1 << n。
2。程序思路：就是计数排序，和桶排序的原理有些相似。
核心思想是，先统计每个值x出现的次数，再计算出小于等于每个值x的元素数量t，这个数量t决定了排序时值为x的元素应该从第t大开始逐个往前排，这样就完成了单关键字排序。
双关键字排序时，要先排第二关键字，让元素都是根据第二关键字有序的。然后根据第一关键字重新排序时，首先可以保证结果是第一关键字有序的，同时对于第一关键字相同的元素，它们已经按照第二关键字排好序了，所以最后的结果是双关键字排序。
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;
int n;
unsigned a[maxn], b[maxn], res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d%d", &a[i], &b[i]);
memset(cnt, 0 , sizeof(cnt)); // 清0统计数组
for (int i = 0; i < n; ++i)
++cnt[b[i]]; // 先对第二关键字排序，统计每个b值的数量
for (int i = 0; i < maxs; ++i)
cnt[i + 1] += cnt[i]; // 累计小于等于每个b值的元素数量
for (int i = 0; i < n; ++i)
ord[--cnt[b[i]]] = i; // 根据第i个元素的b值，按照计算出的数量开始右后往前排列
memset(cnt, 0 , sizeof(cnt));
for (int i = 0; i < maxs; ++i)
++cnt[a[i]]; // 接下来对第一关键字排序，统计每个a值的数量
for (int i = 0; i < maxs; ++i)
cnt[i + 1] += cnt[i]; // 累计小于等于每个a值的元素数量
for (int i = n - 1; i >= 0; --i) // 因为排序中值相同的元素是从后往前放的，此时元素已经按b值排好序了，所以要从后往前来放元素才能保证a值相同的元素b值是由小到大的
res[--cnt[a[ord[i]]]] = ord[i]; // 之前排好序的元素编号在ord中，要按照第二关键字排序来放
for (int i = 0; i < n; ++i)
printf("%d %d\n", a[res[i]], b[res[i]]); // 双关键字排序的结果在res中
return 0;
}
下面讲解一下对于不能完全看懂程序的同学该如何选择。
1）先排第二关键字，肯定要选只有b[i]的选项。
2）按照第二关键字排序，答案肯定跟b[i]相关。
每个元素有ab两个值，ord中只能记录元素编号，所以肯定是保存i。
3）现在根据第一关键字排序，答案应该是跟a[i]有关。
有个与a[i]和b[i]同时有关的选项明显越界了，肯定不可能。
-
ord里面存的是元素编号，肯定不能跟a[i]配合使用，而是要跟a[ord[i]]配合使用。
同时这是根据第一关键字排序，应该是与a有关。
5）res和ord里面存的都是元素编号，肯定不能嵌套使用。
答案要按照排序输出，肯定与res或者ord有关。
0 条评论
