AIO2015 Solution(English)

Wet Chairs

As luck would have it, it has rained on the morning of the concert. To make matters worse, the staff did a very rushed job drying the seats! Now it is up to you to decide how to seat everyone.

The seats are arranged in a single long line in front of the stage. In particular there are chairs in the line, and each seat is either wet or dry.

However, all is not lost. Out of the N friends you are bringing to the concert K of them are happy to sit on a wet chair. The other N-K of your friends insist on sitting on a dry chair.

Since this concert is best enjoyed with friends, you would also like your group to be seated as close together as possible so that the distance between the leftmost person and rightmost person is as small as possible. Output the smallest distance possible between the leftmost and rightmost friend at the concert.

Your task is to write a program that outputs this smallest possible distance.

Solution

We use binary search to get the length.Then the question is:

We have the length L,the number of bad points we can allow is K,then how to check it is okay?

Name S[i]\;= prefix sum of chairs.(0->wet,1->dry)

we enumerate i as the start of the chairs we sit.then we can use S[i] to confirm whether it will work.

So the this is an O(n\log n) algorithm.

Ruckus League

It's that time of year again! The Annual Ruckus World Championships is fast approaching and you are absolutely determined to see Australia victorious. As the name implies, the goal of the competition is to be as loud and obnoxious as possible. Players compete in teams of at least Mpeople (there is no upper limit on team sizes). To make sure teams don't mix, team members must hold hands with each other.

Of course, you've found that there is nothing more obnoxious than spoilt kindergarteners, so you've rounded up N of the loudest ones you could find. You were hoping to send as many teams as possible, but some of the children have already started holding hands with their friends. Being as stubborn as they are, you are finding it rather difficult to convince them to let go of each other, or even to hold hands with anyone else.

Now for any other person, the story would end here; you'd have to send whatever teams their 'friendships' have forged. However, being the social engineering master you are, you've brought K lollipops to use to bribe the children. You can pass a lollipop to the hand of a child, which will make them let go of the hand they are holding.

Using your K lollipops, what is the largest number of teams with at least M children you can form?

Solution

According to the problem description. It is absolutely that there are only rings and chains.

So we can use greedy algorithm.

First of all,we can suppose there are many directed-graphs.

Secondly,we can name in[i] to correct the edges which direct to it.So we can get the start of the rings and chains.

Third,we use DFS to calc the size of subgraphs.

Obviously,it is better to solve the chains first than the rings.

Before solving the rings,we need to use one lollipop to make it become a chain.So the question is,there is a S vertex chain,what is the number of the maximum contribution we can get?Definetly \frac{S}{M}-1.

By the way,it is necessary to solve from large size to small size.

In the end,it is O(n\log n)

Snap Dragons III: Binary Snap

Have you ever heard of Melodramia, my friend? It is a land of forbidden forests and boundless swamps, of sprinting heroes and dashing heroines. And it is home to two dragons, Rose and Scarlet, who, despite their competitive streak, are the best of friends.

Rose and Scarlet love playing Binary Snap, a game for two players. The game is played with a deck of cards, each with a numeric label from 1 toN. There are two cards with each possible label, making 2N cards in total. The game goes as follows:

  • Rose shuffles the cards and places them face down in front of Scarlet.
  • Scarlet then chooses either the top card, or the second-from-top card from the deck and reveals it.
  • Scarlet continues to do this until the deck is empty. If at any point the card she reveals has the same label as the previous card she revealed, the cards are a Dragon Pair, and whichever dragon shouts `Snap!' first gains a point.

After many millenia of playing, the dragons noticed that having more possible Dragon Pairs would often lead to a more exciting game. It is for this reason they have summoned you, the village computermancer, to write a program that reads in the order of cards in the shuffled deck and outputs the maximum number of Dragon Pairs that the dragons can find.

Solution

We use dp[i] to count the ans of the sequence which starts from i

Here I should orz Sam Zhang,He gave me this solution.

dp[i]\;=\;max\begin{Bmatrix}dp[i+1],dp[nex[i]-1]+1+c(i+1,nex[i]-1)\end{Bmatrix}

Array c(i,j) is the contribution of [i,j].How to get it?Just use segment tree

If we divide [i,j] into many pieces.We just need to calculate P(l),P(r),P(last_{l}\;and\;last_{r})

Segment tree can solve it in O(n\log n)

So it is O(n\log n)

 

AIO2015 Solution(English)》上有1条评论

  1. Pingback引用通告: 填坑计划一览表 | 一个沙茶的代码库

发表评论