ABC225C 日历验证器
ABC225C 日历验证器
【算法】 模拟、数学
【C++】 二维数组、取模运算
一、题目简述
有一个巨大的矩阵 ,大小为 ,其中第 行第 列的元素为:
换句话说, 就是一个无限大的"日历",每行 7 个数,按行优先依次填入 :
第1行: 1 2 3 4 5 6 7
第2行: 8 9 10 11 12 13 14
第3行: 15 16 17 18 19 20 21
...现在给定一个 的矩阵 ,判断 是否是 的某个不旋转的矩形子区域。
数据范围:
二、解题思路
1. 数据规模分析
最大 , 最大 ,矩阵 最多约 个元素。 的枚举完全可以接受。
2. 核心想法
矩阵 的结构非常规整。给定一个值 ,它在 中的位置可以唯一确定:
- 所在行:
- 所在列:
由于 必须是 的一个"矩形切片",我们可以先根据 算出它在 中的起始位置,然后推出 中每个位置应该的值,逐个验证。
具体来说,设 start = B[1][1],起始列 col = (start - 1) % 7 + 1。
第一步:检查是否越界—— 个列不能跨行。如果 col + M - 1 > 7,说明这个矩形会"折行",直接输出 No。
第二步:逐个验证。对于 (行列编号从 1 开始),它的期望值是:
因为每往下走一行加 7,每往右走一列加 1。
如果所有位置都匹配,输出 Yes,否则输出 No。
3. 手动模拟样例
样例 1:
2 3
1 2 3
8 9 10start = 1,col = (1-1) % 7 + 1 = 1,M = 3,col + M - 1 = 3 ≤ 7 ✓
- :期望 = ✓
- :期望 = ✓
- :期望 = ✓
- :期望 = ✓
- :期望 = ✓
- :期望 = ✓
全部匹配 → Yes
样例 2:
2 1
1
2start = 1,col = 1,M = 1,col + 0 = 1 ≤ 7 ✓
- :期望 = ≠ ✗ →
No
注意,虽然这个矩阵旋转 90° 后可以匹配,但题目要求不能旋转。
⚠️ 易错点:题目明确要求不能旋转!只看原样是否匹配。4. 另一种思路(更直观)
也可以直接对每个元素计算它在 中的位置,然后检查:
- 同一行内,列号是否连续(差为 1)、行号是否相同(不能换行)
- 同一列内,行号是否连续(差为 1)、列号是否相同
两种思路本质相同,第一种用期望值验证更简洁。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// 读第一行,确定起始信息
int first;
cin >> first;
int col = (first - 1) % 7 + 1; // B[1][1] 在 A 中的列号
// 检查:从该列开始能否放下 M 列
if (col + m - 1 > 7) {
cout << "No" << endl;
return 0;
}
// 读第一行剩余元素并验证
for (int j = 2; j <= m; j++) {
int x;
cin >> x;
if (x != first + (j - 1)) {
cout << "No" << endl;
return 0;
}
}
// 逐行读入并验证
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int x;
cin >> x;
int expected = first + (i - 1) * 7 + (j - 1);
if (x != expected) {
cout << "No" << endl;
return 0;
}
}
}
cout << "Yes" << endl;
return 0;
}四、复杂度分析
时间复杂度:。每个元素读入一次、验证一次。,非常快。
空间复杂度:。边读边验证,不需要存储整个矩阵。
五、知识扩展
本题的核心是坐标映射——利用公式将一维数值映射到二维矩阵位置。这在很多问题中都会用到,比如:
- 将二维数组用一维数组存储时,下标转换公式:
index = (i-1) * cols + j - 反过来:
i = (index - 1) / cols + 1,j = (index - 1) % cols + 1
理解了这个双向映射,本题就迎刃而解了。
💡 提示:本题代码无需开二维数组存储所有数据,边读边验证即可,节省内存。