http://noi.openjudge.cn/ch0201/

OpenJudge NOI 2.1 基本算法之枚举题目难度评级与知识点分类

一、难度星级评级（从易到难）

（注：难度基于枚举范围、逻辑复杂度及边界条件处理）

二、知识点分类

（一）数学枚举应用

• 基础算术问题：

  • 鸡兔同笼（1752）、两倍（1809）、和数（2722）
  • 因子问题（2723）、余数相同问题（7647）
  • 不定方程求解（7650）、质数的和与积（7827）

• 数论与组合：

  • 完美立方（1812）、确定进制（1973）
  • 最简真分数（3526）、三个三位数（8757）

• 序列与查找：

  • 找和为K的两个元素（6184）、我家的门牌号（7649）
  • Cantor表（8760）

（二）逻辑推理与模拟

• 称量与判断：

  • Counterfeit Dollar（15，假币判断）
  • 称体重（6187）、比饭量（6188）
  • 砝码称重（8755）

• 密码与组合：

  • Safecracker（250，密码组合）
  • 硬币面值组合（7621）、五户共井问题（7623）

（三）枚举与状态控制

• 二维状态枚举：

  • 数字方格（1749）、Flip Game（755，翻牌游戏）
  • 熄灯问题（1813）、画家问题（1815）

• 时钟与状态转换：

  • 拨钟问题（1816）、生理周期（1978）

（四）字符串与子串枚举

• 子串计算（2472）、谁是你的潜在朋友（2983，字符串交集）

（五）游戏与模拟场景

• 炸弹游戏（1661，Bomb Game）、垃圾炸弹（7213）
• Minecraft（7216）、火车上的人数（8759）
• 猴子吃桃（7217，逆推枚举）

三、说明

1. 难度评级依据：

   • ★ ：单变量枚举或直接算术计算（如鸡兔同笼、两数求和）。
   • ★★ ：多变量枚举或简单数论（如完美立方、最简分数）。
   • ★★★ ：枚举范围扩大或逻辑嵌套（如数字方格、生理周期）。
   • ★★★★：状态枚举与条件判断复杂（如假币判断、硬币组合）。
   • ★★★★★：多维状态枚举或最优解搜索（如熄灯问题、游戏模拟）。

2. 枚举策略差异：

   • 简单枚举：直接遍历范围（如1752、1809）。
   • 优化枚举：通过数学性质缩小范围（如7647余数问题）。
   • 状态压缩枚举：用位运算表示状态（如1813熄灯问题）。

建议先掌握基础数学枚举题，再练习逻辑推理类题目，最后挑战状态控制与游戏模拟类问题，重点理解如何通过枚举范围优化提高效率。