标签归档:POJ

poj 3191 The Moronic Cowmpouter(负进制数转换)

Description

Inexperienced in the digital arts, the cows tried to build a calculating engine (yes, it’s a cowmpouter) using binary numbers (base 2) but instead built one based on base negative 2! They were quite pleased since numbers expressed in base −2 do not have a sign bit.

You know number bases have place values that start at 1 (base to the 0 power) and proceed right-to-left to base^1, base^2, and so on. In base −2, the place values are 1, −2, 4, −8, 16, −32, … (reading from right to left). Thus, counting from 1 goes like this: 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, and so on.

Eerily, negative numbers are also represented with 1’s and 0’s but no sign. Consider counting from −1 downward: 11, 10, 1101, 1100, 1111, and so on.

Please help the cows convert ordinary decimal integers (range -2,000,000,000..2,000,000,000) to their counterpart representation in base −2.

Input

Line 1: A single integer to be converted to base −2

Output

Line 1: A single integer with no leading zeroes that is the input integer converted to base −2. The value 0 is expressed as 0, with exactly one 0.

Sample Input

Sample Output

Hint

Explanation of the sample:

Reading from right-to-left:

负进制数转换,因为不管是正进制数还是负进制数他每一位都必须是正数。

所以如果出现余数为负数的情况下,需要调整为正数。另外需要特判0的情况。

 

poj 3268 Silver Cow Party(spfa)

Language:
Silver Cow Party
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 20287 Accepted: 9289

Description

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ XN). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow’s return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

Input

Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.

Output

Line 1: One integer: the maximum of time any one cow must walk.

Sample Input

Sample Output

Hint

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

题意:求出x到各个点的最短路加上各个点到x的最短路的最大值。

如果每个点都跑一遍spfa的话,复杂度就有点大了。因为是单向边,所以可以开两个邻接表,一个是正向,一个是反向。那么各自从x跑一遍spfa就可以了。因为反向跑的话,就相当于是从各个点到x的最短路。

 

 

OpenJudge C15H:Lucky Draw(单调队列维护次小值)

描述

In the Lucky village, people are crazy on a game called Lucky Draw. In this game, N players stand in a line, and each one is assigned an integer number. Then, the village master would randomly choose K continuous players. Among these K players, the one who has the largest number will win the first prize of A dollars. Also, the one with the second smallest number will win the second prize of B dollars. Different players may have same numbers. As an agreement, only the rightmost player who has the largest number owns the first prize, and the leftmost player who has the second smallest number owns the second prize. Note that the second smallest number should be greater than the smallest number. Therefore, if all of these K players have the same number, no one will win the second prize.

A big problem in this game is about fairness. Some players may have much more chance to win prizes than others. So, the village master wants to know how fair the game is. You should tell the village master how many players have the opportunity to win the prize. In addition, you need to calculate the variance of the expected prize moneys of these potential prize winners.

输入The first line contains four integers, N, K, A, B, as described before. (1 ≤ K ≤ N ≤ 1000000, 1 ≤ A, B ≤ 1000).

The second line contains N integers, indicate the numbers assigned to those players, listed from left to right. The numbers are guaranteed to fit in 32-bit signed integers.输出Output only one line containing an integer M and a real number V, separated by a single space. M is the number of players who have any chance to win the prize money. V is the variance of the expected prize money of these M players, rounded to four digits after the decimal point.样例输入

样例输出

提示In the sample case, assuming players are represented by P1, P2, …, P6 from left to right.

If players P1, P2, P3 are chosen, whose assigned numbers are 1 2 1, P2 wins 3 dollars.

If players P2, P3, P4 are chosen, whose assigned numbers are 2 1 3, P4 wins 1 dollar and P2 wins 2 dollars.

If players P3, P4, P5 are chosen, whose assigned numbers are 1 3 3, P5 wins 1 dollar and P4 wins 2 dollars.

If players P4, P5, P6 are chosen, whose assigned numbers are 3 3 3, only P6 wins 1 dollar.

P2, P4, P5 and P6 have a chance to win, and the expected prize moneys are 1.25, 0.75, 0.25 and 0.25 respectively.

The average expected prize money of these four players is 0.625 and the variance is 0.1719.

 

题目大意:给出一个长度为n的序列,每次找出连续的k个人,给拥有最大值的人A块钱,给拥有次小值的人B块钱,问可以有多少个人有机会有钱,以及求出收益的期望的方差。

假如是最大值和最小值的话,就是个单调队列裸题了。

我们先考虑子问题最大值的话,这个之前说了就是个单调队列了,那这个可以O(n)计算完。

考虑另一个子问题次小值的话,我们用两个队列来处理。一个队列维护最小值,之前当我们处理到加入一个数时,队尾那个数比加入数大的时候,要移动队尾指针(出队)。现在我们需要把出队的元素加入到第二个队列。这个队列维护的是在最小值队尾之前加入的次小值。所以说在计算真正的次小值的时候,还需要考虑队首的后一个元素,两相比较。这个比较非常重要,因为条件没写清楚WA了无数发。至于维护的过程和一般的一样。

需要注意的是,求最小值的时候,如果两个数相同越靠左越优,所以最好是从右往左加入。

被学弟教育啦,然后被韩司机教育了半天,改了半天大概应该没什么问题了呢。。。

之前的想法其实是错的,因为之前我们在当最小值的序列的末尾因为被删除的时候其实这个删除的顺序是乱序的,而不是我们从右向左的顺序了。自己想一想这个过程就发现了,这样的话,单调队列的时效性就不对了。我们考虑两种情况,一种就是新加入的值一直在最小值队列从后往前走,但是没有走到队头。也就是新加入的值最多是一个次小值,那么我们不去管那些被删除的数。因为次小值只会出现在最小值队列的第二个位置或者次小值队列的第一个值。第二种是新加入的值成为了当前的最小值,这时候我们需要把从原来的最小值队列头部的位置的数到当前的头部之前的数都加入进去次小值队列里面。因为考虑我们维护的过程,头部的数字肯定是比后面的数字在更靠右的位置,那么这样子做才是按照顺序加入。

但是需要注意,如果我们新加入的是一个和原头部相同的值,虽说新的值代替了头部的值,但是我们不能把原头部的值加进去,因为它们仍是这个时候的最小值,而不是次小值。而当将来成为次小值的时候,次小值的位置也应该是现在的头部而不是原来的。

嘤嘤嘤~终于搞完啦,希望没啥问题了。。。