P1663. 数字台阶 题解

题目分析

题目要求根据平面上点的坐标 $(x, y)$，判断该点是否写有数字，若有则输出对应的数字，否则输出 $No Number$。根据题目描述，数字的分布遵循以下规律：

• 数字从 $(0,0)$ 开始按特定模式排列。
• 有效坐标需满足两种模式之一：
  1. 点在直线 $y = x$ 上（称为“上对角线”）；
  2. 点在直线 $y = x - 2$ 上（称为“下对角线”）。

规律总结

通过观察示例和推导，可得出以下结论：

• 有效坐标条件：$(x, y)$ 必须满足 $y = x$ 或 $y = x - 2$，且 $x, y \geq 0$。
• 数字计算规则：
  • 若 $y = x$（上对角线）：
    • 当 $x$ 为偶数时，数字为 $2x$；
    • 当 $x$ 为奇数时，数字为 $2x - 1$。
  • 若 $y = x - 2$（下对角线）：
    • 当 $x$ 为偶数时，数字为 $2x - 2$；
    • 当 $x$ 为奇数时，数字为 $2x - 3$。

算法思路

1. 输入处理：读取测试用例数 $T$，逐个处理每个坐标 $(x, y)$。
2. 有效性判断：检查 $(x, y)$ 是否满足 $y = x$ 或 $y = x - 2$，且 $x, y \geq 0$。不满足则输出 $No Number$。
3. 数字计算：根据坐标所属的对角线类型（上或下）及 $x$ 的奇偶性，计算对应的数字并输出。

代码解释

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int T;
    scanf("%d", &T);  // 读取测试用例数
    int x, y;
    bool isAbove, isLower;  // 判断是否属于上/下对角线
    for (int t = 0; t < T; ++t) {
        scanf("%d%d", &x, &y);  // 读取坐标 (x, y)
        isAbove = (y == x);        // 是否属于上对角线（y = x）
        isLower = (y == x - 2);    // 是否属于下对角线（y = x - 2）
        
        // 无效情况：不满足上/下对角线，或坐标为负数
        if ((!isAbove && !isLower) || x < 0 || y < 0) {
            printf("No Number\n");
            continue;
        }
        
        // 根据对角线类型和x的奇偶性计算数字
        if (isAbove) {  // 上对角线（y = x）
            if (x % 2 == 0) {
                printf("%d\n", x * 2);  // x为偶数：2x
            } else {
                printf("%d\n", x * 2 - 1);  // x为奇数：2x - 1
            }
        } else {  // 下对角线（y = x - 2）
            if (x % 2 == 0) {
                printf("%d\n", x * 2 - 2);  // x为偶数：2x - 2
            } else {
                printf("%d\n", x * 2 - 3);  // x为奇数：2x - 3
            }
        }
    }
    return 0;
}

示例验证

以题目示例输入为例：

3
4 2   // 属于下对角线（y = 4-2=2），x=4（偶数），数字为 4*2-2=6 → 输出6  
6 6   // 属于上对角线（y=6），x=6（偶数），数字为6*2=12 → 输出12  
3 4   // 不满足y=3（3≠4）且不满足y=3-2=1（1≠4）→ 输出No Number  

输出结果与示例完全一致，验证了代码的正确性。

复杂度分析

• 时间复杂度：$O(T)$，其中 $T$ 为测试用例数。每个测试用例的处理仅需常数时间。
• 空间复杂度：$O(1)$，仅使用固定额外空间。