题解：UVA12666 疯狂的谜题 Killer Puzzle

hjy08 · 2025-09-25 18:00:06 · 题解

~~按题意模拟即可。~~

作为过来人，强烈建议不要过来。

0x00 鸣谢

qwen3-max-preview，gpt-5-high，deepseek-v3 for 数据生成器。

tiger2005 for WA 的旧代码和 WA+TLE+RE 的新代码。

0x01 思路

根据题面，我们需要：

枚举所有 5^{10} 种可能答案。
判断当前答案是否正确。

相信第一步大家都会，所以我们重点讲第二步。

表达式分析

我们需要把题目及选项的表达式拆分成方便处理的形式。
我们将输入的字符串按类型划分成若干 Token，并匹配对应的括号。
类似于这题的弱化。

参数与变量

依题意，我们需要维护每个变量的类型和值。开个结构体维护即可。

表达式求值

因为在 Lisp 下函数的写法为 (name [options])，我们考虑传入左右括号的下标递归求值。
首先，我们需要一种方式来区分函数、谓词和生成器。函数和谓词都是 (name [options]) 的形式，需要特判 name。而谓词生成器比较特别，它是 ((generator [options]) [options]) 的形式，判断第一位的左括号有没有匹配到右端点即可。
这里就遇到了一个问题：谓词生成器的返回值可能很复杂，怎么办？
直接处理需要每次建表达式树，显然不现实，所以我们考虑先计算这个生成器返回的谓词接收的参数，把它带入生成器中递归求值。
比如 ((make-or prime-p square-p) 5) 就将 5 带入，在 prime-p 和 square-p 分别得到 true 和 false，递归到 make-or 合并，最终返回 true。

0x02 伪代码参考

其余部分应该都不难，这里只讲表达式求值。

声明：CalcFunc 和 CalcPred 分别处理函数和谓词。 :::error[注意！！！] 调用解析表达式的函数时，一定要判表达式开头是不是函数！
比如 ("equal" 1 1) 啥都不是。 :::

函数

基础函数

(equal a b)

if(currname=="equal"){
    val tmp1=CalcFunc(cur,arg[1].L,arg[1].R);
    val tmp2=CalcFunc(cur,arg[2].L,arg[2].R);
    if(tmp1==ERROR||tmp2==ERROR) return ERROR;
    return val(Bool,tmp1==tmp2,"");
}

(option-value)

:::info[注意！] 根据选项的不同，(option-value) 可以为函数或谓词，需要分别处理。 :::

if(currname=="option-value"){
    return CalcFunc(cur_option);
}

(answer idx)

if(currname=="answer"){
    val index=CalcFunc(cur,arg[1].L,arg[1].R);
    if(type(index)!=int||invalid(index)) return ERROR;
    return problem[index].answer;
}

(answer-value idx)

if(currname=="answer-value"){
    val index=CalcFunc(cur,arg[1].L,arg[1].R);
    if(type(index)!=int||invalid(index)) return ERROR;
    return CalcFunc(problem[index].option[problem[index].answer]);
}

统计与算术

:::info[注意！] 所有此类别下的函数处理的均是题目编号。 :::

(first-quertion pred)

if(currname=="first-question"){
    for(int i=1;i<=N;i++){
        if(CalcPred(arg[1].L,arg[1].R,i)) return val(Int,i,"");
    }
    return ERROR;
}

(last-quertion pred)

同上

(only-quertion pred)

同上

(count-quertion pred)

同上

(diff-answer pred)

if(currname=="diff-answer"){
    val index1=CalcFunc(cur,arg[1].L,arg[1].R);
    val index2=CalcFunc(cur,arg[2].L,arg[2].R);
    if(type(index1)!=int||invalid(index1)||type(index2)!=int||invalid(index2)) return ERROR;
    return val(Int,abs(problem[index1].answer-problem[index2].answer),"");
}

谓词

略 :::warning[注意！！] 尽管题目说接受一个任意类型参数并返回一个布尔值，当传入错误时，谓词仍会报错。而类型不对、超出范围等情况返回 false。 ::: :::info[注意！] (cubic-p) 判负数 :::

谓词生成器

(make-answer-diff-next-equal num)

略

(make-answer-equal a)

略

(make-answer-is pred)

略

(make-answer-value-equal a)

略

(make-answer-value-is pred)

略

(make-is-multiple num)

略 :::info[注意！] 特判 0。 :::

(make-equal val)

略 :::warning[注意！！] (make-equal a) 只能传入整数和字符串，布尔值会报错，而 (equal a b) 不会。 :::

(make-not pred)

略 :::info[注意！] 这个函数返回真当且仅当传入的是 false。 :::

(make-and pred1 pred2)

略

(make-or pred1 pred2)

:::warning[注意！！] 当任意参数为错误时，该函数报错。
当有一个参数为 true 时，返回 true。（另一个参数的类型和值都无所谓，除非是错误） :::

0x03 完整代码

代码