专栏文章

题解：UVA12666 疯狂的谜题 Killer Puzzle

hhjy08
UVA12666题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minsm5tw
此快照首次捕获于
2025/12/02 07:41
3 个月前
此快照最后确认于
2025/12/02 07:41
3 个月前
查看原文
按题意模拟即可。
作为过来人，强烈建议不要过来。

0x00 鸣谢

qwen3-max-preview，gpt-5-high，deepseek-v3 for 数据生成器。
tiger2005 for WA 的旧代码和 WA+TLE+RE 的新代码。

0x01 思路

根据题面，我们需要：
  1. 枚举所有 5105^{10} 种可能答案。
  2. 判断当前答案是否正确。
相信第一步大家都会，所以我们重点讲第二步。

表达式分析

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

参数与变量

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

表达式求值

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

0x02 伪代码参考

其余部分应该都不难，这里只讲表达式求值。
声明：CalcFunc 和 CalcPred 分别处理函数和谓词。
注意！！！
调用解析表达式的函数时，一定要判表达式开头是不是函数！
比如 ("equal" 1 1) 啥都不是。

函数

基础函数

(equal a b)

CPP
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)

注意！
根据选项的不同，(option-value) 可以为函数或谓词，需要分别处理。
CPP
if(currname=="option-value"){
	return CalcFunc(cur_option);
}

(answer idx)

CPP
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)

CPP
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]);
}

统计与算术

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

(first-quertion pred)

CPP
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)

CPP
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),"");
}

谓词

略
注意！！
尽管题目说接受一个任意类型参数并返回一个布尔值，当传入错误时，谓词仍会报错。而类型不对、超出范围等情况返回 falsefalse。
注意！
(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)

略
注意！
特判 00。

(make-equal val)

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

(make-not pred)

略
注意！
这个函数返回真当且仅当传入的是 falsefalse。

(make-and pred1 pred2)

略

(make-or pred1 pred2)

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

0x03 完整代码

代码

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...