[POJ1655] Balancing Act

描述 Description

Consider a tree T with N (1 <= N <= 20,000) nodes numbered 1…N. Deleting any node from the tree yields a forest: a collection of one or more trees. Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node from T.

For example, consider the tree:

Deleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6}, {3,7}, and {4,5}. Each of these trees has two nodes, so the balance of node 1 is two.

For each input tree, calculate the node that has the minimum balance. If multiple nodes have equal balance, output the one with the lowest number.

Read More

[2014-10-29 模拟赛] 买汽水

描述 Description

暑期集训一共 N 天,大家都辛苦了,Symbol 准备给大家买汽水,但是钱只有 M。

每天买汽水的花销都是不固定的,如果不够钱,买到的汽水不够大家一起喝,那样子不太好对不对?所以我们要买的话,就得让每个人都能喝到汽水要不我们那天就不买了。现在给出每天买汽水的花销,请问我们一共最多能够花掉 Symbol 多少钱呢?

暑假最多不超过 40 天,Symbol 给大家花的钱最多有一亿。

Read More

[FZOJ1552] 某种密码 (password.*)

描述 Description

关于某种密码有如下描述:某种密码的原文 A 是由 N 个数字组成,而密文 B 是一个长度为 N 的 01 数串,原文和密文的关联在于一个钥匙码 KEY。若 KEY=∑〖Ai*Bi〗,则密文就是原文的一组合法密码。

现在有原文和钥匙码,请编一个程序来帮助他统计到底有多少个符合条件的密文。

Read More

【BZOJ1621】[Usaco2008 Open]Roads Around The Farm 分岔路口

描述 Description

约翰的 N(1≤N≤1,000,000,000) 只奶牛要出发去探索牧场四周的土地.她们将沿着一条路走,一直走到三岔路口(可以认为所有的路口都是这样的).这时候,这一群奶牛可能会分成两群,分别沿着接下来的两条路继续走.如果她们再次走到三岔路口,那么仍有可能继续分裂成两群继续走. 奶牛的分裂方式十分古怪:如果这一群奶牛可以精确地分成两部分,这两部分的牛数恰好相差 K(1≤K≤1000),那么在三岔路口牛群就会分裂.否则,牛群不会分裂,她们都将在这里待下去,平静地吃草. 请计算,最终将会有多少群奶牛在平静地吃草.

Read More