AIO2009 Solution

Travelling Salesperson

Even in uncertain economic times, no home can be without electrical appliances. Realising that there is still a sales opportunity, you have recently taken up a part-time job selling electrical appliances the old fashioned way--travelling door to door. However, your hometown of Perth is full of electrical salespeople who have cornered the market, and so you must travel across Australia to find customers.

You will start in your hometown, Perth, drive across Australia to Sydney, and then back again to Perth. There are three routes between Perth and Sydney. In your market research, you have counted the number of customers living along each route. You wish to plan your trip to Sydney and back so that you visit the greatest number of customers possible. You must take a different route on the return journey, otherwise you would simply end up visiting the same satisfied customers twice.

Your task is to write a program which, given the number of customers along each of the three routes between Perth and Sydney, determines the greatest number of customers you can visit by travelling from Perth to Sydney and back.

Solution

这就是个阅读理解题吧。。。


Nomnomnom

The hippopotami of North Yorkshire are busy creatures indeed. They wake at dawn for some light aerobics, followed by a quick galumph to the shops where they scare the tourists, dance ballet and wallow contentedly in the area's famous natural mud pits. Of course, all of this is quite strenuous work and by the end of the day they are hungry, hungry hippos.

At dinner time these majestic native animals begin their trek back home. Each evening, the respectful locals place dishes of food along the main road. Different dishes weigh different amounts: for example, a plate of cabbage might weigh just one kilogram, a pot of fish soup might weigh ten, while a colossal wedding cake may weigh upwards of nine thousand.

The hippos are not very good with knives and forks, so they must eat these food dishes whole. This makes it difficult for them to share their food evenly. Instead, they have devised the following system:

  • When the hippos reach the first dish on the road, the eldest hippo will eat it and be satisfied;
  • The next-eldest hippo will eat every dish he passes until he has eaten at least as much as the previous hippo, at which point he is satisfied;
  • This pattern continues, with each hippo in turn eating everything they pass until they have eaten at least as much as the hippo before them, at which point they are satisfied.

However, there is never enough food to feed all the hippos. Eventually one of the hippos will find that there is not enough food left for them to be satisfied. Your task is to write a program that reads in a list of dishes and calculates the number of hippos who are satisfied.

Solution

绝世傻题,按照顺序模拟下就好了


Safe Cracking

Over the centuries many wars have been won, not through a battle of strength but a battle of wits. Your sources have recently informed you that your mother has purchased a pre-release copy of the latest computer game, WheeZork, and is hiding it in the safe at home. To open the safe, one must enter a long sequence of numbers by rotating the circular dial to each number in the correct order.

If the correct sequence of numbers is entered into the safe, the safe opens and you can sneak your Christmas present out early. If you get the sequence wrong the alarm system is activated and you will be grounded for life! Luckily, you know that your mother has written the code down on a sheet of paper in her bedside drawer, which she likes to call the "code sheet".

She often boasts about how clever she is and explains to you that the numbers on the sheet are indeed the code to the safe, however each number in the sequence has been increased by a constant non-negative integer, k, which only she knows. Without this value the sheet is useless, and thus only she can open the safe ... or so she thinks!

In order to determine the correct code, you have spied on your mother when she unlocks the safe and you have managed to remember part of the code that she entered. You are not sure which part of the code this corresponds to, but it is definitely a consecutive sequence of numbers in the code. Armed with this knowledge, you set out to determine the full code to the safe.

Your task is, given the full list of numbers your mother has written down on her code sheet, and the shorter sequence that you know appears in the actual code, determine the entire sequence to unlock the safe.

For example, if the code to the safe was 7, 9, 4, 6, 8, 12, and your mother had incremented all numbers by 4, her code sheet would read 11, 13, 8, 10, 12, 16. This is because 7 + 4 = 11, giving the first number 11. The second number is obtained by adding 9 + 4 = 13. The third number is obtained by adding 4 + 4 = 8, and so forth. You may have caught a glimpse of her entering the numbers 4, 6, 8, in order. With this knowledge, you can determine the entire code.

Solution

发现B的大小才30,所以暴力怎么都能过。。。但我怎么莫名其妙的wa了3个点

现在让我们来讲一讲O(a+b)的做法,感谢晴川姥爷的指导

首先对题意我们可以总结出一个很有用的东西,即一定存在一段a_{i}满足a_{i...i+m-1}-b_{1...m}=k

考虑m=2的情况,为了方便我们用矩阵表示

\begin{bmatrix}a&b\\c&d\end{bmatrix}

我们所关心的是a-c=b-d

那么两边交换一下,就是b-a=d-c,雷同差分形式

所以我们只需要对原数组进行差分,再跑一次KMP即可,注意到k\geq0,要特殊处理小于的情况


Carmen Sanfrancisco

After a mysterious ten year absence, notorious international landmark thief Carmen Sanfrancisco is back and burgling like never before. On Wednesday 2 September, under the cover of night, the villainess stole the Eiffel Tower. But while Carmen Sanfrancisco can run, she can't hide.

The ACME Detective Agency has requested your services as an elite detective in tracking down the stolen Eiffel Tower. You have fellow agents scattered throughout the world--lurking in bus companies, train companies, taxi ranks and airlines. While your agents are numerous they are somewhat ineffective, incapable of ever actually determining where in the world Carmen is at any point in time. Instead, they can merely tell youwhich mode of transport (such as bus, train, taxi and so on) Carmen uses each time she moves between two cities.

Carmen is only able to move between two cities if there is a transport link between them. Transport links are always bi-directional; for instance, if Carmen can catch a plane from Paris to Prague, she could also catch a plane back from Prague to Paris. Additionally, a pair of cities may have more than one mode of transport connecting them; Prague and Paris could be connected by both plane and train, for example.

You have obtained a map of all the cities in which Carmen Sanfrancisco could potentially be hiding. The map contains a list of transport links connecting pairs of cities by modes of transport. While you have no idea which city Carmen is currently in, each time she moves to a different city you will be informed of the mode of transport she used. Your task is, given this list of movements, to determine all the cities she could possibly be in after she has finished moving.

Solution

一眼看上去是神题其实是思博题,我们只需要按照k来模拟就行了。

对于当前阶段这个点是否可行取决且仅取决于与他相连的边符合条件,且边的另一端在上一阶段没有被BAN,那么这样算下复杂度大概是O(k\times(n+2\times M))。卡着时间过了2333,有老司机会更快的话求指导


Treasure Hunt

For generations stories have been told of hidden treasures deep in the caves of Rodrom. The stories are unclear as to precisely where or what the treasure is--everything from lost gold to magical elixirs have been rumoured to lie forgotten in the depths of Rodrom.

Despite the promise of wealth, not even the bravest treasure hunter has attempted to enter the crumbling caves, as renowned for their instability as for their treasures. The slightest movements in the caves cause the ceilings to come crashing down, trapping hopeful treasure hunters with no hope of rescue.

Where humans have failed, however, robots will conquer (or at least that is what you tell yourself as you put the finishing touches on your four-legged robotic cave-crawlers). Your plan is to send the courageous robots on a one-way mission into the caves to discover once and for all whether the treasure truly exists.

The caves of Rodrom can be mapped as a grid consisting of passages (shown in white) and walls (shown in gray), as follows:

\includegraphics[scale=0.33]{grid_blank}

Your robots enter the cave from the top-left, and can move up, down, left or right from one passage to another. Your robots are unable to squeeze through passages diagonally. Because the caves are so unstable, each time one or more of your robots leaves a passage, the ceiling of that cell collapses in preventing anything from entering that cell again.

Any single robot sent into the cave would quickly hit a dead-end and become trapped. In a moment of inspiration, you determine that if you sendseveral robots into the cave simultaneously (spreading out as they go deeper) you will be able to explore the entire cave. For example, the cave shown above could be fully explored with four robots, as follows:

\includegraphics[scale=0.33]{grid}

Simplifying your task, after careful study of the maps of Rodrom you have determined that the caves have no paths that loop back to themselves. Such structures would have already collapsed centuries ago. For example, neither of the following two cave systems could exist:

\includegraphics[scale=0.33]{grids_bad}

While the robots are expendable, they are expensive. Your task is, given a map of the caves of Rodrom, determine the smallest number of robots needed to start off in the top left cell so that all parts of the cave can be explored.

Solution

(1,1)开始BFS,遇到没有决策点就意味着一条路结束,对答案贡献加1

时间复杂度O(nm)


No (One) Left

It is the distant year of 2012, and the doomsayers were right. Natural disasters have squashed cities and cleaved continents, massive solar flares have destroyed the ozone layer, and chemical pollution has turned the animals feral. Coda City, once a thriving metropolis, is now a wasteland. Besides you, there is no one left.

With the sun's merciless ultraviolet rays beating down during the day, and foul creatures roaming the streets at night, you have taken refuge in the sewers underneath the city. Fortunately, the sewers are very modern and have heating, lighting, and power outlets for your laptop. Unfortunately, you have no food with you, and so you must leave the sewer to stock up on supplies. The only time it is safe to surface is at sunset, when the sun is at its least harmful and the feral hamsters are still afraid to emerge.

Coda City consists of streets running north-south and east-west, forming a grid. Every street intersection has a manhole. The intersections are given coordinates as follows:

\includegraphics[height=6.5cm,trim=55 60 0 60,clip=true]{noleft-grid}

Some street intersections contain abandoned shopping trolleys, cast aside by panicking civilians during the flash floods and volcanic eruptions. If you collect all the food from all the trolleys, it should last you long enough for help to arrive. Since being outside at all is a massive risk, you decide to visit all the shopping trolleys in one fell swoop.

Your plan is as follows: You will emerge from any manhole. You will then run along the streets, emptying trolleys as you go. While you are doing this you must be wary of the sun's glare. If you try to head west, its powerful rays will blind you and you will trip, break your ankle and be eaten alive by feral hamsters. Once you have been to all the trolleys, you will climb down any manhole.

The longer you stay outside, the more vulnerable you are, so you must find the shortest route possible. Your task is, given the locations of abandoned trolleys within the city, to determine the shortest distance that you must travel above ground in order to collect food from all the abandoned trolleys.

Solution

问题的突破点在于不会左拐,而我们又知道开始点和结束点选关键点最优,所以我们只需要逐列进行DP即可,设f(i,0/1)表示前i列进行选择,上一列是选择最后停留在顶部或者底部时的最小花费,O(1)转移即可

 

发表评论