第30次csp认证——前三题个人题解思路与反思

2023.5.28 ccf-csp 认证

• 202305-1 重复局面
• 202305-2 矩阵运算
• 202305-3 解压缩

202305-1 重复局面

题目大意：给你n个棋盘的状态，输出这个状态是第几次出现

反思：很简单的一道题，暴力比较每个棋盘的每个格子也能过（考试的时候没想到什么好方法，就试了试发现可以过），也可以用字符串保存每个棋盘的状态，这样比较起来更方便。

思路：把输入的每个棋盘的棋子保存到字符数组中，然后判断这个字符串在map中是否出现过，若出现过，则出现次数加一，否则把这个字符串的出现次数设置为1。

#include 
using namespace std;
int n;
char pieces[64];
map<string, int> status_map;
int main()
{cin >> n;for (int i = 0; i < n; i ++){for (int j = 0; j < 64; j ++) cin >> pieces[j];if (status_map.count(pieces)) status_map[pieces] ++;else status_map[pieces] = 1;cout << status_map[pieces] << endl;}return 0;
}

202305-2 矩阵运算

题目大意：计算三个矩阵的点乘，分别为 $n\ast d$ 矩阵， $d\ast n$ 矩阵， $n\ast d$ 矩阵，其中 $n$ 的范围为 1 0 4 10^4 104，$d$ 的范围为 $20$

反思：这道题也不难，再纸上推一下规律就能找到循环去计算的规律。这道题的重点在于时间复杂度，如果先算QK矩阵相乘，会得到n * n的矩阵，时间复杂度是 O ( n 2 ∗ d ) = O ( 2 ∗ 1 0 9 ) O(n^2 * d) = O(2 * 10^9) O(n2∗d)=O(2∗109) 会超时，所以要先算后面两个矩阵，时间复杂度是 O ( d 2 ∗ n ) = O ( 4 ∗ 1 0 6 ) O(d^2 * n) = O(4 * 10^6) O(d2∗n)=O(4∗106) 就可以过了。PS：考试的时候1e4写成了1000，导致Runtime Error了，烦。

思路：找规律

#include 
using namespace std;
typedef long long LL;
const int N = 10010, D = 30;
LL tmp[D][D], ans[N][N];
int n, d;
int Q[N][D], K[N][D], V[N][D], W[N];
int main()
{cin >> n >> d;for (int i = 1; i <= n; i ++)for (int j = 1; j <= d; j ++)cin >> Q[i][j];for (int i = 1; i <= n; i ++)for (int j = 1; j <= d; j ++)cin >> K[i][j];for (int i = 1; i <= n; i ++)for (int j = 1; j <= d; j ++)cin >> V[i][j];for (int i = 1; i <= n; i ++) cin >> W[i];// 计算 Q * V = tmpfor (int i = 1; i <= d; i ++)for (int j = 1; j <= d; j ++)for (int k = 1; k <= n; k ++)tmp[i][j] += K[k][i] * V[k][j];// 计算 K * tmp = ansfor (int i = 1; i <= n; i ++)for (int j = 1; j <= d; j ++){for (int k = 1; k <= d; k ++)ans[i][j] += Q[i][k] * tmp[k][j];ans[i][j] *= (LL) W[i];}for (int i = 1; i <= n; i ++){for (int j = 1; j <= d; j ++)cout << ans[i][j] << " ";cout << endl;}return 0;
}

202305-3 解压缩

题目大意：给你一段压缩过的代码，可以拆分为引导域和数据域，引导域决定了解压缩后的数据长度，数据域也是可以分段的，每一段由其第一个字节的最低两位决定，若为00，则是字面量，若为01或10，则为回溯引用。输出解压缩后的数据，8字节为一行，最后一行允许不到8个字节。

反思：这道题我在考试的时候被进制转换卡住了，用字节处理太麻烦了，后面才想到用 stoi()——有符号整型 或者 stoul——无符号整型 来进行进制转换。示例如下：

string str = "80";
// 以16进制解析该字符串
cout << stoi(str, nullptr, 16); 
// 结果为128

然后一个关键点就是整型转二进制，可以用bitset，示例如下：

string str = "80";
// 转换为8位二进制
cout << bitset<8>(stoi(str, nullptr, 16)).to_string();
// 结果为10000000

思路：由于要多次读取字节，所以最好封装一个函数来 读取字节 ，记录当前读到的位置。由于要进行小端序调整字符串，可以考虑封装一个函数来 按小端序调整字符串 。由于01和10结尾都要回溯引用，也可以封装一个函数来 填充字符串 。（PS：怪怪的这题，不知道算原始数据长度有啥用，题目貌似保证了待解压的数据都是合法的）

#include 
using namespace std;
const int N = 2e6 + 10;
int n, idx, p; // 当前已经解压缩了 p 字节，下一个读的是第 idx 下标的字符
string res; // 解压后的数据string readBytes(int num)
{char byte[2 * num];for (int i = 0; i < 2 * num; i ++) cin >> byte[i];idx += num * 2;return string(byte, 2 * num);
}void trackBack(int o, int l)
{int start = res.length() - o * 2;int len = o * 2;string back_track_string = res.substr(start, len);int cnt = 0;while (cnt < l * 2 - l * 2 % len){res += back_track_string;cnt += len;}res += back_track_string.substr(0, l * 2 % len);
}
int main()
{cin >> n;string bts;vector<int> c;int v_c;// 读入字节 直到最高位为0while ((bts = readBytes(1)) >= "80"){v_c = stoi(bts, nullptr, 16);v_c -= 128;c.push_back(v_c);}// 最高位为0时，直接保存到c里v_c = stoi(bts, nullptr, 16);c.push_back(v_c);// 引导区结束，计算原始数据长度int length = 0;for (int i = 0; i < c.size(); i ++) length += c[i] * pow(128, i);while (idx < n * 2){// 接下来是数据域// 读入一个字节bts = readBytes(1);string string_to_binary = bitset<8>(stoi(bts, nullptr, 16)).to_string();string lowest_two_digits = string_to_binary.substr(6, 2);if (lowest_two_digits == "00"){string high_six_digits = string_to_binary.substr(0, 6);int ll = stoi(high_six_digits, nullptr, 2);// l <= 60，高六位 ll 表示 l - 1if (ll <= 59)res += readBytes(ll + 1);else{// 第一个字节的高六位存储的值为 60、61、62 或 63 时，分别代表 l - 1 用 1、2、3 或 4 个字节表示int literal_length = ll - 59;// 按照小端序重组字符串 0x01 0x0A => 0x0A01string string1 = readBytes(literal_length);string string2;// 字符串每两位反转for (int i = string1.length() - 2; i >= 0; i -= 2)string2 += string1.substr(i, 2);int l = 1 + stoi(string2, nullptr, 16); // 字面量长度res += readBytes(l);}}else if (lowest_two_digits == "01"){// 第 2 ~ 4 位即 从下标 3 开始的三位 001 011 01string two_to_four_digits = string_to_binary.substr(3, 3);// l - 4 占 3 位，存储于首字节的 2 至 4 位中int l = stoi(two_to_four_digits, nullptr, 2) + 4;// o 占 11 位，其低 8 位存储于随后的字节中，高 3 位存储于首字节的高 3 位中string high_three_digits = string_to_binary.substr(0, 3);string next_byte_binary = bitset<8>(stoi(readBytes(1), nullptr, 16)).to_string();int o = stoi(high_three_digits + next_byte_binary, nullptr, 2);// 回溯引用trackBack(o, l);}else if (lowest_two_digits == "10"){string high_six_digits = string_to_binary.substr(0, 6);// l 占 6 位，存储于首字节的高 6 位中int l = stoi(high_six_digits, nullptr, 2) + 1;// o 占 16 位，以小端序存储于随后的两个字节中string string1 = readBytes(2);string string2;// 字符串每两位反转for (int i = string1.length() - 2; i >= 0; i -= 2)string2 += string1.substr(i, 2);int o = stoi(string2, nullptr, 16);// 回溯引用trackBack(o, l);}}for (int i = 0; i < res.length(); i ++){cout << res[i];// 输出，每16个字符加一个换行if ((i + 1) % 16 == 0) cout << endl;}// 若最后一行不能凑8个，则补一个换行if (res.length() % 16) cout << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！