全国站

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

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

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

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

华中地区 | 河南 湖北 湖南

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

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

华南地区 | 广东 广西 海南

资    源
  • 资    源
当前位置:查字典高考网>高中频道>信息学联赛知识>信息学联赛知识: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】相关文章:

06年与07年高考化学考纲对比

高中数学联赛培训讲义(二)

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

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

高考制度改革突破口:多元化评价与多元化入学

全国高中数学联合竞赛简介

信息学联赛知识:ISBN号码

九成人赞同高考改革 近六成人认为需要动大手术

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

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

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

网友关注

海南:高考评卷工作7月14日启动 预计7月20日结束

2020年高校第二学士学位专业备案结果公布

西藏:2020年高考成绩查询入口(官网) —查字典高考网

河南:2020年高报名总人数115.8万人,25日零时起可查成绩

2020年高考全国II卷政治评析

2020浙江高考语文真题及答案公布 —查字典高考网

2020高考文综评析

科教司关于个别机构收集考生信息,误导、欺骗考生的紧急公告

2020年高考语文北京卷:变中求稳正面导向发挥育人功能

2020年全国Ⅰ卷化学试卷评析

北京高考语文卷:今年语文题难度稳定不刁钻

名师解析2020高考数学真题:注重综合能力考查

云南:7月23日左右可查成绩

2020年全国Ⅲ卷高考数学(理科)评析

新高考语文卷首次亮相出现新应用写作形式

专家:语文题难度略降 新高考地区现代文阅读有调整

2020年高考全国Ⅱ卷数学试卷评析

江苏:高考卷原来是这样改出来的

关于四川美术学院在江苏省设点组织艺术类专业校考考生须知

北京高考语文试卷考虑考生实际 注重基础

2020年全国普通高考北京卷语文试题作文题详解及同题作文

甘肃:7月25日起进行第一次高考志愿填报 —查字典高考网

2020年山东新高考政治:产业聚集难倒众考生

2020年高考全国I卷生物试卷评析

云南省、贵州省、西藏自治区2020年度空军招飞定选检测安排

2020年高考江苏数学(理科)试卷评析

2020高考结束要知道的考后信息

广东:预计25日左右公布高考成绩

四川省、重庆市2020年度空军招飞定选检测安排

疫情与改革叠加2020年高考语文有哪些亮点

网友关注视频

这!就是专业 第43集 河北经贸大学—计算机科学与技术专业

良心推荐:2019高考数学全国3卷理科12题讲解,附答案

高考体育四项生的日常训练——深蹲移动跳:发展膝关节,踝关节力量。

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

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

他高考作文仅得6分,总分428分,被985高校录取,却被导师拒绝!

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

高考英语作文分析2

励志歌曲《阳光总在风雨后》送给高考的莘莘学子,祝金榜题名!

广州早晨 2019 山西一高中班主任带学生骑行1800公里去上海

2019高考语文试卷解析

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

最新高考数学全国2卷第12题视频解读

高中数学必修5 高考数列选填真题技巧秒杀讲解

加油吧考生:2019高考咨询大直播 第43集 科学填报志愿 规划精彩人生

这四首励志歌曲,送给为梦起航的高考学子们,听完心潮澎湃!

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

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

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

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

高级中学高考试卷分析专题教研评比活动

北京新闻 2019 5.9万余北京考生今日高考 语文试题鼓励创造性阅读与表达

【姜浩张超画室】

老师好:这大概是高考前所有班主任都会干的事,取消一切副课!

高中信息技术

初二辍学,3次高考落榜,如今却成为最成功的音乐人之一

这!就是专业 第18集 中国科学技术大学

1000张学生用草稿纸考研专用免邮空白便宜薄演草演算纸白纸本书写纸批发打草a4大张实惠装18k高考数学草稿本

2019年高考数学全国2卷理科第4题讲解及答案

体育大杂烩 第2217集 太厉害!马龙登上全国高考作文题