第三次CCF-CSP认证（含C++源码）

第一道（easy）

题目链接

思路及AC代码

solution 1（模拟）

#include <bits/stdc++.h>
using namespace std;
const int N =1010;
int n;
int s[N];
//基本思路：使用数组模拟哈希表实现 本质上是编号和来访次数之间的映射
int main()
{cin>>n;while(n--){int x;cin>>x;s[x]++;//本质上就是哈希表cout<<s[x]<<" ";//控制输入输出 这里不能用endl}return 0;
}

solution 2 (哈希表)

#include <iostream>
#include <unordered_map>
#include <vector>using namespace std;int main() {int n;// 读取记录的条数cin >> n;vector<int> records(n);// 自定义的哈希表，用于存储每个读者编号出现的次数unordered_map<int, int> study_hard;// 读取每条记录中的读者编号for (int i = 0; i < n; ++i) {cin >> records[i];}// 遍历每条记录，统计每个读者编号出现的次数for (int i = 0; i < n; ++i) {int readerId = records[i];// 如果该读者编号是第一次出现，初始化为 1if (study_hard.find(readerId) == study_hard.end()) {study_hard[readerId] = 1;} else {// 否则，将该读者编号的出现次数加 1++study_hard[readerId];}// 输出该读者编号是第几次出现cout << study_hard[readerId]<<" ";}return 0;
}

第二道（easy but mid for me）

题目链接

思路及AC代码

solution 1

讲解视频
首先我们拿到这个题目不要慌，一看这个图这么复杂，又是左右上下又是斜着移动，其实我们只要找准规律，给出限制条件，就能AC，这个方法是我在B站上学习的，我们将题中的矩阵放在直角坐标系中并给他们编个号（左上角坐标），将左上角看做原点
分析：什么是限制？
对于这题而言我们需要按蛇形输出矩形的坐标 ，同时也意味着我们不能超过这个矩形的范围，我们仔细观察一下，在这个图中的运动轨迹如果只是上下左右走，边界是很好控制的，只需要不超过矩形的边长就行（条件3），但是这题是个蛇形 还特么是斜着的，所以我们要着重处理两个方向（direction）左下和右上，也就分别对应下图中绿色和蓝色的箭头。
solution：我们先处理一下右上，也就是当我们的纵坐标小于0的时候（j<0）,我们需要将这个非法的移动方向给他调整一下，具体就是让j=0，这样就变成向右移动了，然后紧接着我们需要向左下方移动（direction 1）也就是j++，i–，这样我们就给出了一个完整的限制条件 左下同理（条件 1、2）

#include <iostream>
using namespace std;int main() {int n;cin >> n;// 动态分配二维数组 一开始用静态分配内存直接爆栈了哈哈哈int** a = new int*[n];for (int i = 0; i < n; ++i) {a[i] = new int[n];}int dir = 2;int i = 0;int j = 0;// 输入矩阵for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {cin >> a[i][j];}}i = 0;j = 0;// 输出矩阵元素while (1) {// 输出当前元素cout << a[i][j] << " ";// 判断是否到达矩阵右下角元素，若是则退出循环if (i == n - 1 && j == n - 1) {break;}switch (dir) {case 1: // 左下方向i++;j--;break;case 2: // 右上方向i--;j++;break;}// 处理越界情况，调整方向和位置if (i < 0 || j >= n) {if (j >= n) {i = i + 2;j = n - 1;}else {i = 0;}dir = 1;}else if (j < 0 || i >= n) {if (i >= n) {j = j + 2;i = n - 1;}else {j = 0;}dir = 2;}}// 释放动态分配的内存for (int i = 0; i < n; ++i) {delete[] a[i];}delete[] a;return 0;
}

遇到的问题

在原来的代码里使用了 int a[N][N]; 来定义二维数组，这里的 N 是一个宏定义，数组是在栈上分配内存的。栈的空间通常是有限的，当矩阵规模（即 n 的值）比较大时，a[N][N] 所需的内存会超出栈的可用空间，从而导致栈溢出错误。
矩形比较小：

矩形比较大：

solution 2

这个方法是抓住了斜对角线的性质即横纵坐标之和正好是这条对角线的序号,通过补全这个矩形的下方和右方 就可以做到只需要按两个方向遍历输出即可

#include <bits/stdc++.h>
// 定义一个常量 N 为 510，用于表示矩阵的最大规模
const int N = 510;
// 定义变量 n 用于存储矩阵的实际规模
int n;
// 定义二维数组 q 用于存储矩阵元素，q[i][j] 表示矩阵第 i 行第 j 列的元素
int q[N][N];int main ()
{// 从标准输入读取一个整数 n，作为矩阵的行数和列数scanf("%d",&n);// 使用两层嵌套循环遍历矩阵的每一个元素for(int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)// 从标准输入读取矩阵第 i 行第 j 列的元素，并存储到 q[i][j] 中scanf("%d", &q[i][j]);// 外层循环控制遍历的对角线编号，从 2 到 2 * n// 矩阵的对角线编号从 2 开始（因为左上角元素是第 2 条对角线），最大到 2 * nfor (int i = 2; i <= n * 2; i++){// 判断当前对角线编号是否为偶数if (i % 2 == 0){// 对于偶数编号的对角线，从下往上遍历// 从对角线的最后一个可能的元素开始，逐步向上遍历for (int j = i - 1; j >= 1; j--)// 检查当前元素的行和列是否在矩阵范围内// j 表示行，i - j 表示列if (j >= 1 && j <= n && i - j >= 1 && i - j <= n)// 如果元素在矩阵范围内，输出该元素，并在后面添加一个空格printf("%d ", q[j][i - j]);}else{// 对于奇数编号的对角线，从上往下遍历// 从对角线的第一个可能的元素开始，逐步向下遍历for (int j = 1; j <= i; j++)// 检查当前元素的行和列是否在矩阵范围内// j 表示行，i - j 表示列if (j >= 1 && j <= n && i - j >= 1 && i - j <= n)// 如果元素在矩阵范围内，输出该元素，并在后面添加一个空格printf("%d ", q[j][i - j]);}}return 0;
}

第三题（mid）

题目链接

基本思路及AC代码

明天更一下 困了懒得写了

结语

估计这篇文章之后我的粉丝就到200了，还是感谢各位支持，其实一开始我写博客也只是为了记录一下，但是没想到写着写着就会发现第一遍学的时候有很多遗漏或者囫囵吞枣，这样就强迫自己学的更深入了，同时在遇到一些计算机相关问题的时候我都会优先在CSDN上搜索，收获颇丰，那么 希望看到这里的你有美好的一天！我会保持更新，请多多三连！！！最后送给大家一句话“先完成，再完美，just right now”
*********************************************************************************************signed by 曦月逸霜