百度推广怎么做网站的优化,中国建设工程电子信息网,那里有帮做网站的,高性能网站建设进阶更多 CSP 认证考试题目题解可以前往#xff1a;CSP-CCF 认证考试真题题解 原题链接#xff1a; 202305-1 重复局面
时间限制#xff1a; 1.0s 内存限制#xff1a; 512.0MB
题目背景
国际象棋在对局时#xff0c;同一局面连续或间断出现3次或3次以上#xff0c;可由任… 更多 CSP 认证考试题目题解可以前往CSP-CCF 认证考试真题题解 原题链接 202305-1 重复局面
时间限制 1.0s 内存限制 512.0MB
题目背景
国际象棋在对局时同一局面连续或间断出现3次或3次以上可由任意一方提出和棋。
问题描述
国际象棋每一个局面可以用大小为 8 × 8 8 \times 8 8×8 的字符数组来表示其中每一位对应棋盘上的一个格子。六种棋子王、后、车、象、马、兵分别用字母 k、q、r、b、n、p 表示其中大写字母对应白方、小写字母对应黑方。棋盘上无棋子处用字符 * 表示。两个字符数组的每一位均相同则说明对应同一局面。
现已按上述方式整理好了每步棋后的局面试统计每个局面分别是第几次出现。 输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 n n n表示这盘棋总共有 n n n 步。
接下来 8 × n 8 \times n 8×n 行依次输入第 1 1 1 到第 n n n 步棋后的局面。具体来说每行包含一个长度为 8 8 8 的字符串每 8 8 8 行字符串共 64 64 64 个字符对应一个局面。
输出格式
输出到标准输出中。
输出共 n n 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 6 6、 7 7 7 步后的局面分别与第 2 2 2、 3 3 3 步后的局面相同。第 8 8 8 步后的局面与上图相对应。
子任务
输入数据满足 n ≤ 100 n \le 100 n≤100。
提示
判断重复局面仅涉及字符串比较无需考虑国际象棋实际行棋规则。 题解
将一个棋盘局面看成一个长度为 64 64 64 的字符串然后用 std::map 的第一维表示棋盘的局面第二维表示该局面出现的次数。每次遇到一个局面就将局面出现的次数 1 1 1 后并输出。
时间复杂度 O ( n log n ) \mathcal{O}(n\log n) O(nlogn)。
参考代码0ms2.988MB
/*Created by Pujx on 2024/3/16.
*/
#pragma GCC optimize(2, 3, Ofast, inline)
#include bits/stdc.h
using namespace std;
#define endl \n
//#define int long long
//#define double long double
using i64 long long;
using ui64 unsigned long long;
using i128 __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout (x ? yes : no) endl
#define Yn(x) cout (x ? Yes : No) endl
#define YN(x) cout (x ? YES : NO) endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i 1; i n; i) cin a[i]
#define cinstl(a) for (auto x : a) cin x;
#define coutarr(a, n) for (int i 1; i n; i) cout a[i] \n[i n]
#define coutstl(a) for (const auto x : a) cout x ; cout endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod mod) % mod)
#define ls (s 1)
#define rs (s 1 | 1)
#define ft first
#define se second
#define pii pairint, int
#ifdef DEBUG#include debug.h
#else#define dbg(...) void(0)
#endifconst int N 2e5 5;
//const int M 1e5 5;
const int mod 998244353;
//const int mod 1e9 7;
//template typename T T ksm(T a, i64 b) { T ans 1; for (; b; a 1ll * a * a, b 1) if (b 1) ans 1ll * ans * a; return ans; }
//template typename T T ksm(T a, i64 b, T m mod) { T ans 1; for (; b; a 1ll * a * a % m, b 1) if (b 1) ans 1ll * ans * a % m; return ans; }int a[N];
int n, m, t, k, q;void work() {cin n;mapstring, int mp;auto read [] () - string {string s, t;for (int i 1; i 8; i) cin t, s t;return s;};while (n--) cout mp[read()] endl;
}signed main() {
#ifdef LOCALfreopen(C:\\Users\\admin\\CLionProjects\\Practice\\data.in, r, stdin);freopen(C:\\Users\\admin\\CLionProjects\\Practice\\data.out, w, stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int Case 1;//cin Case;while (Case--) work();return 0;
}
/*_____ _ _ _ __ __| _ \ | | | | | | \ \ / /| |_| | | | | | | | \ \/ /| ___/ | | | | _ | | } {| | | |_| | | |_| | / /\ \|_| \_____/ \_____/ /_/ \_\
*/关于代码的亿点点说明 代码的主体部分位于 void work() 函数中另外会有部分变量申明、结构体定义、函数定义在上方。#pragma ... 是用来开启 O2、O3 等优化加快代码速度。中间一大堆 #define ... 是我习惯上的一些宏定义用来加快代码编写的速度。debug.h 头文件是我用于调试输出的代码没有这个头文件也可以正常运行前提是没定义 DEBUG 宏在程序中如果看到 dbg(...) 是我中途调试的输出的语句可能没删干净但是没有提交上去没有任何影响。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步加快输入 cin 输出 cout 速度这个输入输出流的速度很慢。在小数据量无所谓但是在比较大的读入时建议加这句话避免读入输出超时。如果记不下来可以换用 scanf 和 printf但使用了这句话后cin 和 scanf、cout 和 printf 不能混用。将 main 函数和 work 函数分开写纯属个人习惯主要是为了多组数据。
