质数方阵题小结 24宴会上的彩灯☆ ◆算法效率分析 续址是全共物#2 在的方法需要枚举多少次? 置:姦券福廷堑爹灯巯绕 关灯游戏 Turnofflight swf 质数判断的两种优化方法各最多需要几次判断? 小试牛刀 http:/acm.pku.edu.cn/judgeOnline/showproblem?problemid 彩灯状态转换示意图 观察得到的结论 ◆每个开关最多被操作一次,因为操作两次 的结果相当于没有操作。 第i的灯的状态只能由第i-1,i计+1行的开 ◆如果第i-1,i开关状态已经确定,为了要 关上第i的灯,第i+1行开关的状态也就 被唯一确定 关灯策略:局部枚举 一个例子 枚举对第一行开关的操作 ·桔色:灯亮 蓝色:灯 ·按动第二行的开关,把第一行的 ·按忸:开关 灯都关 按动第三行的开关,把第二行的 的灯关上 输出结果是 100111 按动第五行的开关,看是否可以 ll0000 恰好第四行和第五行的灯的灯 000100 Il0101 1011014 质数方阵题小结 Š 算法效率分析： http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=11 65 Š 小试牛刀 Š减少枚举次数 Š减少判断每种情况的时间 Š现在的方法需要枚举多少次？还能不能更快？ Š 质数判断的两种优化方法各最多需要几次判断？ 2.4 宴会上的彩灯 Š 在举行宴会的房间的一面墙上，30盏 彩灯排成5行6列，每盏灯带有1个开 关。按动某盏灯的开关，它和它上下 左右的灯都会转变状态。 Š 宴会之后，这些彩灯有开有关，愁煞 了管理员。如何才能将这些彩灯统统 关上呢？ Š 关灯游戏 TurnoffLight.swf 开关的状态 有230种可能 彩灯状态转换示意图 观察得到的结论 Š 每个开关最多被操作一次，因为操作两次 的结果相当于没有操作。 Š 第i行的灯的状态只能由第i-1, i, i+1行的开 关控制。 Š 如果第i-1, i行开关状态已经确定，为了要 关上第i行的灯，第i+1行开关的状态也就 被唯一确定。 关灯策略：局部枚举 Š 枚举对第一行开关的操作。 Š 按动第二行的开关，把第一行的 灯都关。 Š 按动第三行的开关，把第二行的 的灯关上。 Š …… Š 按动第五行的开关，看是否可以 恰好第四行和第五行的灯的灯。 一个例子 Š 桔色：灯亮 Š 蓝色：灯灭 Š 按钮：开关 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 输出结果是：