分类目录归档:BFS

[codeforces 734E] Anton and Tree

Description

Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph.

There are n vertices in the tree, each of them is painted black or white. Anton doesn't like multicolored trees, so he wants to change the tree such that all vertices have the same color (black or white).

To change the colors Anton can use only operations of one type. We denote it as paint(v), where v is some vertex of the tree. This operation changes the color of all vertices u such that all vertices on the shortest path from v to u have the same color (including v andu). For example, consider the tree

and apply operation paint(3) to get the following:

Anton is interested in the minimum number of operation he needs to perform in order to make the colors of all vertices equal.

继续阅读

bzoj-USACO除草计划A

我已经做了30/30


继续阅读

[bzoj 1066][SCOI2007] 蜥蜴

Description

  在一个r行c列的网格地图中有一些高度不同的石柱,一些石柱上站着一些蜥蜴,你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为1,蜥蜴的跳跃距离是d,即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定,每次当蜥蜴跳跃时,所离开的石柱高度减1(如果仍然落在地图内部,则到达的石柱高度不变),如果该石柱原来高度为1,则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。

继续阅读

[bzoj 1054][HAOI2008] 移动玩具

Description

  在一个4*4的方框内摆放了若干个相同的玩具,某人想将这些玩具重新摆放成为他心中理想的状态,规定移动时只能将玩具向上下左右四个方向移动,并且移动的位置不能有玩具,请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。

继续阅读

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.

继续阅读

AIO2010 Solution

Ninjas

You used to like ninjas. That was before the shadowy shiro-obi ninja clan moved in next door. They're mostly decent neighbours - they keep to themselves and never throw loud parties - but every few nights they sneak into your house and raid the kitchen. With no one else to turn to, you decide to take matters into your own hands and catch them in the act.

There are N ninjas trying to get inside, one at a time. You wait and watch carefully, grabbing the first one who comes past. However, in the time it takes you to securely tie up this first ninja, K other ninjas manage to sneak past you. Nevertheless, you persevere, grabbing the next ninja. Again, while you tie them up, K more ninjas sneak past. This continues until all of the ninjas have tried to get in.

\includegraphics[width=15cm]{ninjaexample}

In the above example, K=2. That is, for each ninja you tie up, the following two ninjas will sneak past. You catch the first ninja who comes past, and then ninjas #2 and #3 sneak past you. You catch ninja #4, and then ninjas #5 and #6 sneak past you. This repeats until all N ninjas have either been caught or have snuck past you.

Your task is to write a program that reads in the values of N and K, and calculates the number of ninjas who sneak past you.

继续阅读

AIO2013 Solution(Chinese)

Archery

When you were young, you were awe-struck by the battle scene in The Lord of the Rings: The Two Towers. From then on, you were determined to become the greatest archer of all time. After years of training, you are finally at the International Archery Olympiad (IAO), in Auckland.

On each of the two days of the IAO, all contestants are given a score and ranked by that score. After the second day of competition, all contestants are given an overall score equal to the sum of their two scores and their overall rank is then calculated from this.

Katniss Legolas Link Merida Robin
Day 1 Score 50 70 20 40 0
Day 1 Rank 2 1 4 3 5
Day 2 Score 30 20 40 50 40
Day 2 Rank 4 5 2 1 2
Overall Score 80 90 60 90 40
Overall Rank 3 1 4 1 5

A contestant's rank is equal to the number of competitors with strictly greater scores than theirs, plus one. In the above example, there are two overall scores strictly greater than Katniss's, so her overall rank is (2+1)=3. There are no overall scores strictly greater than Legolas's, so his overall rank is (0+1)=1. (Notice that Legolas and Merida are both ranked 1, as no one has a strictly greater score than either of them.)

Sick with anticipation of the results, you sneak a look at a judge's laptop. The scores aren't shown, nor is your overall rank, but you do manage to glimpse your first-day rank and your second-day rank. You want to work out what your overall rank could be.

Your task is to write a program which, given the number of contestants in the IAO and your rank on each day, determines your best and worst possible overall rank.

继续阅读

CodeForces Round#349 Div.2

A.Pouring Rain

设第x秒会喝完,每秒会增加e\;cm,减少\frac{v}{r^{2}\pi}\;cm,原来相差h\;cm,这就是个追击问题,容易得到方程

(\frac{v}{r^{2}\pi}-e)\times\;x=h

解之即可

B.Coat of Anticubism

考虑题目给出的性质:“初始数据保证一定不能组成凸多边形”

结论:先对原数组排序,然后答案为

a[n]-\sum_{i=1}^{n-1}a[i]\;+1

继续阅读