1 条题解

  • 0
    @ 2025-4-10 0:38:56

    解题思路:

    本题要求判断一个序列是否存在“有趣的跳跃”,即相邻元素的差值的绝对值排序后恰好构成11n1n-1的连续序列。解决此问题的关键在于验证差值是否满足特定条件。

    关键步骤:

    计算相邻差值:遍历序列,计算每两个相邻元素的绝对差值。
    记录差值唯一性:使用数组标记已出现的差值,若发现重复差值,立即判定不满足条件。
    验证覆盖范围:检查所有11n1n-1的整数是否均被差值覆盖,确保连续。

    实现细节:

    数组标记:用数组subssubs记录差值的出现情况,索引对应差值,值为11表示存在。
    重复判断:在计算差值时,若发现重复值,直接标记为不满足条件。
    范围检查:遍历11n1n-1,若存在未被标记的数值,则判定不满足条件。

    特殊情况处理:

    • 当序列长度为11时,直接满足条件。
    • 差值超出11n1n-1范围或包含00时,自动判定为不满足条件。

    C++实现:

    #include <cstdio>
    #include <cstring>
    #include <cmath>
    
    int subs[3100]; // 标记数组,记录差值的出现情况
    int num[3100];  // 存储输入序列
    
    int main() {
        int n;
        while (scanf("%d", &n) != EOF) {
            memset(subs, 0, sizeof(subs)); // 初始化标记数组
            int flag = 1; // 初始标记为满足条件
            
            for (int i = 0; i < n; i++) {
                scanf("%d", &num[i]); // 读入序列元素
                if (i > 0) {
                    int diff = abs(num[i] - num[i-1]); // 计算相邻差值绝对值
                    if (diff >= 1 && diff < n) { // 差值需在有效范围内
                        if (subs[diff] == 0) {
                            subs[diff] = 1; // 标记该差值已出现
                        } else {
                            flag = 0; // 重复差值,不满足条件
                        }
                    } else {
                        flag = 0; // 差值超出范围,不满足条件
                    }
                }
            }
            
            // 检查1到n-1是否全部被覆盖
            if (n > 1) {
                for (int i = 1; i <= n-1; i++) {
                    if (subs[i] != 1) {
                        flag = 0;
                        break;
                    }
                }
            }
            
            printf(flag ? "Jolly\n" : "Not jolly\n");
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1576
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    9
    已通过
    1
    上传者