[codeforces 740D] Alyona and a tree

Description

Alyona has a tree with n vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex i she wrote ai. Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges).

Let's define dist(v, u) as the sum of the integers written on the edges of the simple path from v to u.

The vertex v controls the vertex u (v ≠ u) if and only if u is in the subtree of v and dist(v, u) ≤ au.

Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex v what is the number of vertices u such that vcontrols u.

继续阅读

[hdu 3018] Ant Trip

Problem Description

Ant Country consist of N towns.There are M roads connecting the towns.

Ant Tony,together with his friends,wants to go through every part of the country.

They intend to visit every road , and every road must be visited for exact one time.However,it may be a mission impossible for only one group of people.So they are trying to divide all the people into several groups,and each may start at different town.Now tony wants to know what is the least groups of ants that needs to form to achieve their goal.

继续阅读

[UER #7] 短路

Description

“第七套广播体操,原地踏步——走!”

众所周知,跳蚤们最喜欢每天早起做早操,经常天还没亮就齐刷刷地站在操场做着反复纵跳热热身。跳晚国在研制三星 note7 的时候注意到了这点,于是他们打算让炸弹更快地引爆,这样就可以消灭更多早起的跳蚤。

三星 note7 的主板可以看作是由 (2n+1)×(2n+1)个中继器构成的,某些中继器会有导线连在一起,左上角和右下角的中继器分别连着电源的正负极。

电流流过一根导线的时间可忽略不计,但当电流经过中继器时,会延缓一段时间再从中继器流出。这个时间只跟该中继器本身有关,我们把这段时间的长度称为中继器的延时值。

这些中继器由导线连接围成一个一个的层,同个层的中继器的种类都一样,而不同层的种类都不一样,可以发现总共有 n+1 层。当 n=4时,主板大概长这样:

图1

跳晚们打算再加几根导线将某些中继器连接起来.凭借发达的重工业,他们能生产出无数条导线。但由于主板的限制,他们的导线只能和主板四周的边平行,且其长度只够连接相邻两个中继器。

现在他们想知道,他们改造的三星 note7 的电源正极流出的电流能在多短的时间到达电源负极从而造成短路,这样电池就会释放出巨大的能量摧毁跳蚤国的有生力量了。

请参考输入格式和样例配图来更好地理解题意。

继续阅读

[codeforces 359C] Prime Number

Description

Simon has a prime number x and an array of non-negative integers a1, a2, ..., an.

Simon loves fractions very much. Today he wrote out number on a piece of paper. After Simon led all fractions to a common denominator and summed them up, he got a fraction: , where number t equals xa1 + a2 + ... + an. Now Simon wants to reduce the resulting fraction.

Help him, find the greatest common divisor of numbers s and t. As GCD can be rather large, print it as a remainder after dividing it by number 1000000007 (109 + 7).

继续阅读

贪心算法小结

写在前面

在信息学竞赛中有一类常用的算法,叫做贪心算法。所谓贪心,即对于当前的每一步决策都考虑选择最优的分支,从而使得整体最优,而对于一个问题划分成N个决策,在每次决策中选择最优的分支所需要的时间可以采用堆、左偏树、优先队列等实现(也有根据决策无需修改,在开始进行一次排序即可),进而将问题的时间复杂度大大缩减为O(NlogN)以内。贪心算法无疑是解决问题比较完美的方法,但他的局限在于无法顾及到全局,由于每次只考虑最优决策的局限性,贪心算法容易走入较差解乃至最差解的深坑中,所以在使用贪心算法前需要有对于算法正确性的严(bao)格(li)证(dui)明(pai)。笔者因为贪心学得不好,所以来补这篇文章,用于给自己做总结,希望高手能够指正文中的错误,不胜感激。

继续阅读

[Codeforces 718C] Sasha and Array

Problem Description

Sasha has an array of integers a1, a2, ..., an. You have to perform m queries. There might be queries of two types:

  1. 1 l r x — increase all integers on the segment from l to r by values x;
  2. 2 l r — find , where f(x) is the x-th Fibonacci number. As this number may be large, you only have to find it modulo 109 + 7.

In this problem we define Fibonacci numbers as follows: f(1) = 1, f(2) = 1, f(x) = f(x - 1) + f(x - 2) for all x > 2.

Sasha is a very talented boy and he managed to perform all queries in five seconds. Will you be able to write the program that performs as well as Sasha?

继续阅读

bzoj-USACO除草计划A

我已经做了30/30


继续阅读