全国站

热门城市 | 全国 北京 上海 广东

华北地区 | 北京 天津 河北 山西 内蒙古

东北地区 | 辽宁 吉林 黑龙江

华东地区 | 上海 江苏 浙江 安徽 福建 江西 山东

华中地区 | 河南 湖北 湖南

西南地区 | 重庆 四川 贵州 云南 西藏

西北地区 | 陕西 甘肃 青海 宁夏 新疆

华南地区 | 广东 广西 海南

资    源
  • 资    源
当前位置:查字典高考网>高中频道>信息学联赛知识>信息学联赛知识:Complete Search

信息学联赛知识:Complete Search

来自:查字典高考网 2009-11-12

Complete Search

The Idea

Solving a problem using complete search is based on the ``Keep It Simple, Stupid'' principle. The goal of solving contest problems is to write programs that work in the time allowed, whether or not there is a faster algorithm.

Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer. This method should almost always be the first algorithm/solution you consider. If this works within time and space constraints, then do it: it's easy to code and usually easy to debug. This means you'll have more time to work on all the hard problems, where brute force doesn't work quickly enough.

In the case of a problem with only fewer than a couple million possibilities, iterate through each one of them, and see if the answer works.

Careful, Careful

Sometimes, it's not obvious that you use this methodology.

Problem: Party Lamps [IOI 98]

You are given N lamps and four switches. The first switch toggles all lamps, the second the even lamps, the third the odd lamps, and last switch toggles lamps 1, 4, 7, 10, ... .

Given the number of lamps, N, the number of button presses made (up to 10,000), and the state of some of the lamps (e.g., lamp 7 is off), output all the possible states the lamps could be in.

Naively, for each button press, you have to try 4 possibilities, for a total of 410000 (about 106020 ), which means there's no way you could do complete search (this particular algorithm would exploit recursion).

Noticing that the order of the button presses does not matter gets this number down to about 100004 (about 1016 ), still too big to completely search (but certainly closer by a factor of over 106000 ).

However, pressing a button twice is the same as pressing the button no times, so all you really have to check is pressing each button either 0 or 1 times. That's only 24 = 16 possibilities, surely a number of iterations solvable within the time limit.

Problem 3: The Clocks [IOI 94]

A group of nine clocks inhabits a 3 x 3 grid; each is set to 12:00, 3:00, 6:00, or 9:00. Your goal is to manipulate them all to read 12:00. Unfortunately, the only way you can manipulate the clocks is by one of nine different types of move, each one of which rotates a certain subset of the clocks 90 degrees clockwise.

Find the shortest sequence of moves which returns all the clocks to 12:00.

The ``obvious'' thing to do is a recursive solution, which checks to see if there is a solution of 1 move, 2 moves, etc. until it finds a solution. This would take 9k time, where k is the number of moves. Since k might be fairly large, this is not going to run with reasonable time constraints.

Note that the order of the moves does not matter. This reduces the time down to k9 , which isn't enough of an improvement.

However, since doing each move 4 times is the same as doing it no times, you know that no move will be done more than 3 times. Thus, there are only 49 possibilities, which is only 262,072, which, given the rule of thumb for run-time of more than 10,000,000 operations in a second, should work in time. The brute-force solution, given this insight, is perfectly adequate.

Sample Problems

Milking Cows [USACO 1996 Competition Round]

Given a cow milking schedule (Farmer A milks from time 300 to time 1000, Farmer B from 700 to 1200, etc.), calculate

The longest time interval in which at least one cow was being milked

The longest time interval in which no cow is being milked

Perfect Cows Perfect Cow Cousins [USACO 1995 Final Round]

A perfect number is one in which the sum of the proper divisors add up to the number. For example, 28 = 1 + 2 + 4 + 7 + 14. A perfect pair is a pair of numbers such that the sum of the proper divisor of each one adds up to the other. There are, of course, longer perfect sets, such that the sum of the divisors of the first add up to the second, the second's divisors to the third, etc., until the sum of the last's proper divisors add up to the first number.

Each cow in Farmer John's ranch is assigned a serial number. from 1 to 32000. A perfect cow is one which has a perfect number as its serial. A group of cows is a set of perfect cow cousins if their serial numbers form a perfect set. Find all perfect cows and perfect cow cousins.

retrieved from http://ace.delos.com/usacogate

【信息学联赛知识:Complete Search】相关文章:

高中数学竞赛基本知识集锦(三)

2005年全国高中数学联赛考点诠释(一)

2007年全国高中数学联赛江西省预赛试卷

信息学联赛知识:基本程序题集

课改与高考脱节 素质教育校园很难真正践行

高分考生系列专访三:数学拿满分,要学会做“阴题”

2005年全国高中数学联赛考点诠释(二)

高中数学竞赛基本知识集锦(一)

高中数学竞赛基本知识集锦(四)

信息学联赛知识:ISBN号码

[标签:竞赛联赛,数学联赛]

网友关注视频

组合名师余老师在线讲解2019高考数学全国3卷理科16题

爆笑班主任 第一季 第220集 高考前最后一只视频,山东王老师揭秘高考的秘密

小品:马云被宋小宝调侃当年数学高考考一分!

视频|2019全国高考今日开考: 语文特级教师评析上海卷高考作文

这!就是专业 第31集 阜阳师范学院信息工程学院

沈阳音乐学院郎亦农教授的女高音高考曲目解析课程 第1集 沈阳音乐学院郎亦农为你讲解女高音高考曲目

这!就是专业 第20集 长沙理工大学—数据科学专业

武汉美术高考

美术联考用纸上海考试模拟试卷纸高考统考纸 4k水粉纸素描纸 速写纸卡纸美术模拟测试试卷纸 美术考试专用纸

印度美术高考美术联考,考前培训班

招办面对面 第2集 中国科学技术大学

高考前必听的5首励志歌曲,《Dream it possible》最能鼓舞人心!

amc传媒音乐影像 第一季 第600集 高中校长演唱《记忆花园》为高考学子助力打气

优秀!英语数学双满分,广西“最牛”高考状元730分刷新最高纪录

凤凰县高级中学高考试卷分析专题教研会

高考政治一轮:《经济生活》第九课(社会主义市场经济)练习

盘点今年最难的高考数学题

葛军大爷怒了:高考我出了个小学数学送分题,你们跟我说不会做?

创艺第二届:2019届高考录取表彰大会暨“核桃音乐节”合影——你只管努力,剩下的交给创艺

衍声高考琴行2019高本硕学生暑假音乐会 张俊瀚《陕北民歌主题变奏曲》《阿根廷舞曲》第三乐章

外国数学老师挑战中国高考题,一顿“凶猛操作”下来,被虐惨!

2019高考数学全国2卷理科第16题视频讲解及答案

2019高考·语文试题有亮点 凸显时代主题 厚植家国情怀

2019年高考试卷解析,数学套路不好用了

新闻早报 2019 高考前最后一课 合唱送给班主任

张雪峰高考志愿填报指南 第47集 高考志愿,令人头疼的数学系,才是专业万金油,毕业后机会多

知道班里的高考成绩后,山东班主任气吐血了

张雪峰高考志愿填报指南 第15集 高考填报志愿,想学电子信息类专业,推荐报这六所高校,不出错

2019全国高考志愿填报攻略 第50集 天津市高考历史三年本科录取排名

【姜浩张超画室】