AIO2007 Solution

Wetlands

The Friends of Wetlands have dammed a creek to provide water for the nearby wetlands. During each month some rainwater flows into the dam, and then at the end of each month precisely 10 megalitres of water are released into the wetlands. If the dam contains less than 10 megalitres at the end of the month, the entire contents of the dam are released.

The local firefighters view the dam as a potential source of water to fight bushfires, and would like to know how much water there is likely to be in the dam in the height of the bushfire season in eight months' time. Your task is to use predicted rainfall figures to answer this question.

For example, suppose the predicted amounts of rainwater flowing into the dam for each of the eight months are 12, 9, 10, 7, 10, 13, 9 and 15 megalitres respectively. Assuming these figures are correct, after the first month the dam fills with 12 megalitres, and then 10 megalitres are taken (leaving 2). After the second month the dam fills to 2+9=11 megalitres, which is then reduced to 1. After the third month the dam fills to 11 megalitres and is again reduced to 1.

The fourth month is more interesting--here the dam only fills to 1+7=8 megalitres. Since the usual 10 megalitres cannot be taken, the dam is emptied completely. After the fifth month it fills to 10 and is again emptied, then it fills to 13 and reduces to 3, then fills to 12 and reduces to 2, and finally after the eighth month it fills to 17 and reduces to 7. Therefore your final answer for the firefighters is 7 megalitres.

Solution

辣鸡模拟题


Superphone

It is almost time. After months of waiting and media hype, the new all-in-one mobile phone, music player and electric toothbrush is about to be released. You have been waiting outside the tall store for the last twelve hours hoping to be the first to get your hands on one of these new phones. In just a few minutes, the store is going to open.

Unfortunately, a large number of other people have also been milling about outside the store, they too wanting to be the first to purchase one of these new phones. To ensure that they don't beat you to it, you will not only have to sprint to the sales desk of the store, but you will need to ensure that you take the absolute fastest route to get there.

The store is a large building consisting of several floors. Each floor has a pair of escalators that connect to the floor above, as shown in the figure below. The left-hand side of the building has an escalator to the right-hand side of the floor above, and the right-hand side of the building has an escalator to the left-hand side of the floor above. All of these escalators move up. Also, on each floor you are able to (if you wish) sprint to the other side of the building to get to the escalator on the other side.

The doors of the store, where you are currently waiting, are located to the left of bottom floor. The sales desk, where you must purchase your phone, is located on the right of the top floor.

\includegraphics[scale=0.6]{escalator.eps}

From your research, you know that different escalators move at different speeds, and some floors are more difficult to run through than others. Fortunately, you have carefully recorded precisely how many seconds it takes you to run up each individual escalator, as well as how many seconds it takes you to run from one side of each individual floor to the other.

Your task is to determine the minimum amount of time required to reach the sales desk of the building from the doors of the building.

Solution

无智商选手并不会你们那么简单的算法,于是写了一发堆优化的dij就水过了。。。


Mansion

It has been five years since you founded your highly successful online restaurant Bytes and Nybbles, and you have amassed a small fortune. In need of something to do with all this money, you decide to build an extremely large and luxurious mansion.

Of course you could never live in such a mansion--you would get lost trying to find your way from one end to the other. The only purpose of this mansion would be for people to look at it and admire it. You therefore need to choose a location for your mansion so as many people can see it as possible.

Your mansion will be built on a long road, as illustrated below. One side of the road is filled with houses, each of the same size. You have done your homework, and you have a complete listing of how many people live in each house. Your mansion will cover the width of w houses combined, and will be built on the other side of this road. Your aim is to choose a location so that as many people as possible live opposite your mansion.

\includegraphics[scale=0.7]{mansionroad.eps}

For instance, consider the road above and suppose that w=4. There are four possible locations for your mansion, each illustrated below. In the first location you would have 3+2+5+1=11 people living opposite. In the second location you would have 2+5+1+4=12 people opposite, and in the third and fourth locations you would have 11 and 9 people respectively. The best you can do is 12 people, and so you build your mansion in the second location (to the envy of your neighbours).

\includegraphics[scale=0.7]{mansionpos.eps}

Of course this is just an example--in reality the road might be much longer, and your mansion might be much larger. Your task is to write a computer program that can choose the best location for you.

Solution

暴力枚举,维护前缀和即可


Invasion

As a highly-trained and razor-sharp military strategist, you have decided that it is time to establish your own empire. Unfortunately you do not have an army with which to do this: since the hushed-up incident with the pet hamster and the nuclear power plant, you were exiled from your former nation and nowadays you are on your own.

Your grand plan requires you to find a new nation to join forces with. You will then immediately invade all of its neighbours, taking them completely by surprise. Of course your empire will probably end there, since your forces will be so stretched at this point that you will not be able to expand any further.

The first decision for you to make is which nation to join forces with. You have acquired a map that shows the boundaries of the nations in your region. You wish to invade as many countries as possible, which means you must choose a nation with as many neighbours as possible.

Military maps are of course highly structured, and this map is no exception. It consists of a large grid of square cells, where each nation is formed from some group of cells. An example map on a 3  x  6 grid of cells is shown below, describing the nine nations a, b, ..., i.

\includegraphics[scale=0.8]{invasion.eps}

Two nations are considered neighbours if they own land that is vertically or horizontally adjacent (for instance, a and d are neighbours in the example above, but a and e are not since they only touch at a corner).

Your task is to find the largest number of countries that you can invade, that is, the largest number of neighbours that any single nation has.

Solution

枚举一个点,加入相邻不同色到该色点集中,直接统计即可

时间复杂度O(n\times m+26\times nlogn)


Restaurants

You are the organiser for the Youth United Nations Conference which is being held this year in Le Nourse, Switzerland. It is the first night and you need to find somewhere for everybody to eat, but having forgotten to book, the local restaurants are nearly full and only have limited seating left.

Due to the important political nature of the Youth UN, it is crucial that no two delegates from the same country eat at the same restaurant. This will force them to meet the delegates from other countries and get to work on solving the world's problems.

However, because of the limited seating, this arrangement may not be possible--in particular, some delegates may not be able to eat at a restaurant. You would like to minimise the number of delegates that miss out so as not to cause an international incident.

Knowing that the fate of the world's future political leaders rests solely on your shoulders, you whip out your trusty laptop and set about determining the fewest number of delegates that will be forced to go hungry.

Solution

xjb暴力一下就好了


Air Drop

Election time is looming, and the battle for votes will be fierce. To win over the public's hearts and minds, the major parties are always looking for new and unusual methods of advertising, and this year they have hit upon a winner: the air drop.

In an air drop, the leader of the party flies over a city in an aeroplane and drops glossy leaflets onto the ground below. These leaflets fall in a straight line across the city, with the leaflets equally spaced along this line.

You are employed as the Grand Auditor, and it is your job to estimate just how much of the taxpayers' money is being spent on this exercise. Your first investigation takes you to the main street of the city, where you find eight leaflets littered along the street. These leaflets are found at positions 1, 3, 4, 7, 9, 10, 11 and 14 metres along the street as illustrated below.

\includegraphics[scale=1.0]{drop.eps}

Your task is to determine the largest number of leaflets that could have been dropped in a single flight. For instance, in the illustration above, a single flight could have dropped leaflets at positions 7, 9 and 11 metres along the street (since these three leaflets are equally spaced). Likewise, a single flight could have dropped leaflets at positions 3, 7 and 11 metres. However, the largest number of leaflets that could be dropped in a single flight is four, landing at positions 1, 4, 7 and 10 metres along the street.

With a frown you write a note in your little black book and move to the next street where there are even more leaflets to consider. As you watch the propaganda planes zooming overhead you realise you will be here for a long time yet; you therefore decide to write a computer program to help you with your task.

Solution

dp[i,j]表示以i为结尾,公差为j的最长子序列的长度

根据决策值单调,很容易推出

dp[i,j]=dp[las,j]+1\;\;\;\;(a[i]-a[las]==j)

但是暴力枚举公差实在是太慢了,时间复杂度为O(N^{3})

考虑修改状态描述

dp[i,j]表示以i为结尾,公差为a[i]-a[j]的最长子序列长度

易推出

dp[i,j]=dp[j,las]+1\;\;\;\;(a[i]-a[j]==a[j]-a[las])

怎么求las呢?我们做个变换,

a[i]-a[j]==a[j]-a[las]\Leftrightarrow a[las]==2\times a[j]-a[i]

于是直接二分就好了

注意特判n=1的情况,时间复杂度为O(n^{2}\times\log n)

 

发表评论