CCF CSP 第30次（2023.05）（1_重复局面_C++）
- 题目背景：
- 题目描述：
- 输入格式：
- 输出格式：
- 样例输入
- 样例输出：
- 样例解释：
- 子任务：
- 提示：
- 解题思路：
- 思路一（哈希集合）：
- 代码实现
- 代码实现（思路一（哈希集合））：
- 部分代码解读
时间限制： 1.0 秒
空间限制： 512 MiB
题目背景：
国际象棋在对局时，同一局面连续或间断出现3次或3次以上，可由任意一方提出和棋。
题目描述：
国际象棋每一个局面可以用大小为 8×8 的字符数组来表示，其中每一位对应棋盘上的一个格子。六种棋子王、后、车、象、马、兵分别用字母 k、q、r、b、n、p 表示，其中大写字母对应白方、小写字母对应黑方。棋盘上无棋子处用字符 * 表示。两个字符数组的每一位均相同则说明对应同一局面。
现已按上述方式整理好了每步棋后的局面，试统计每个局面分别是第几次出现。
输入格式：
从标准输入读入数据。
输入的第一行包含一个正整数 n，表示这盘棋总共有 n 步。
接下来 8×n 行，依次输入第 1 到第 n 步棋后的局面。具体来说每行包含一个长度为 8 的字符串，每 8 行字符串共 64 个字符对应一个局面。
输出格式：
输出到标准输出。
输出共 n 行，每行一个整数，表示该局面是第几次出现。
样例输入
8
********
******pk
*****r*p
p*pQ****
********
**b*B*PP
****qP**
**R***K*
********
******pk
*****r*p
p*pQ****
*b******
****B*PP
****qP**
**R***K*
********
******pk
*****r*p
p*p*****
*b**Q***
****B*PP
****qP**
**R***K*
******k*
******p*
*****r*p
p*p*****
*b**Q***
****B*PP
****qP**
**R***K*
******k*
******p*
*****r*p
p*pQ****
*b******
****B*PP
****qP**
**R***K*
********
******pk
*****r*p
p*pQ****
*b******
****B*PP
****qP**
**R***K*
********
******pk
*****r*p
p*p*****
*b**Q***
****B*PP
****qP**
**R***K*
********
******pk
******rp
p*p*****
*b**Q***
****B*PP
****qP**
**R***K*
样例输出：
1
1
1
1
1
2
2
1
样例解释：
第6、7 步后的局面分别与第 2、3 步后的局面相同。第8 步后的局面与上图相对应。
子任务：
输入数据满足 n≤100。
提示：
判断重复局面仅涉及字符串比较，无需考虑国际象棋实际行棋规则。
解题思路：
思路一（哈希集合）：
1、结题步骤拆分：
① 数据输入：第一行输入一个整数n，其后面输入n*8行，每八行是一个棋盘（双重循环n为外层循环次数，8为内层循环次数）。
② 数据处理：将八行数据合并成一个字符串，判断其重复次数.重复次数使用哈希表来存储（key代表连接的字符串，value代表此棋盘至今为止出现的次数）。每输入一个棋盘就统计棋盘至今为止出现的次数。
③ 答案输出：将统计棋盘出现次数依次输出。
代码实现
代码实现（思路一（哈希集合））：
#include<iostream>
#include<unordered_map>
#include <vector>
using namespace std;int main(int argc, char const *argv[])
{// 声明一个整数n，用于存储棋盘的数量int n;// 使用unordered_map来存储每个棋盘字符串及其出现的次数，map的key是棋盘的字符串，value是出现次数unordered_map<string, int> mp;// 用于存储每个棋盘的字符串string str = "", nstr = "";// 用一个vector<int>来记录每个棋盘的重复次数，最后输出vector<int> ans;// 输入棋盘的数量ncin >> n;// 遍历每个棋盘for (int i = 0; i < n; i++){// 每次开始处理一个新的棋盘，初始化nstr为空nstr = "";// 读取棋盘的8行，每一行是一个8个字符的字符串for (int j = 0; j < 8; j++){// 读取每一行的字符串cin >> str;// 将读取到的每一行字符串连接到nstr中，形成一个完整的棋盘字符串nstr += str;}// 更新哈希表中的该棋盘字符串的出现次数mp[nstr]++;// 将当前棋盘的重复次数添加到结果数组中ans.push_back(mp[nstr]);}// 输出每个棋盘的重复次数for (auto &i : ans){// 依次输出存储在ans中的每个重复次数cout << i << endl;}// 程序结束return 0;
}
部分代码解读
unordered_map和unordered_set对比
unordered_map:存储键值对（key-value pairs）。 每个元素由一个唯一的键和一个与该键关联的值组成。示例：#include<unordered_map> unordered_map<int, std::string> myMap;myMap[1] = "one";myMap[2] = "two";
unordered_set（可以进行降重）:只存储唯一的键，没有值（即只存储键）。 用于存储不重复的元素。示例： #include<unordered_set> unordered_set<int> mySet;mySet.insert(1);mySet.insert(2);
元素的访问 unordered_map：myMap[key] 可以获得与 key 相关的值unordered_set：通过 mySet.find(value) 来检查某个值是否存在 unordered_map的用法
1. 包含头文件#include <unordered_map>
2. 定义和初始化unordered_map<int, int> hashtable;
3. 插入元素hashtable[1] = 100; // 插入键值对 (1, 100) hashtable.insert({4, 400}); // 插入键值对 (4, 400)
4. 查找元素auto it=hashtable.find(2);if (it!=hashtable.end()) {//找到了键为 2 的元素cout<<"Key:"<<it->first<<", Value:"<<it->second<<endl;}else{cout<<"Key not found."<<endl;}5. 访问元素int value = hashtable[1]; // 获取键为 1 的值
6. 删除元素hashtable.erase(2); // 删除键为 2 的元素
7. 遍历元素for(const auto& pair:hashtable) {cout<<"Key:"<<pair.first<<",Value:"<<pair.second<<endl;}// 或使用迭代器for(auto it=hashtable.begin();it!=hashtable.end();++it) {cout<<"Key:"<<it->first<<",Value:"<<it->second<<endl;}
8. 检查元素是否存在:可以通过 find() 或 count() 方法来检查特定的键是否存在if(hashtable.count(3)>0) {cout<<"Key 3 exists."<<endl;}
9. 清空哈希表hashtable.clear(); // 清空所有元素
10. 获取大小size_t count = hashtable.size(); // 获取当前元素个数
欢迎大家和我沟通交流(✿◠‿◠)
