[計算幾何]USACO Feb08 USACO Silver Game of Lines 連線遊戲

Title: 連線遊戲

Input: lines.in

Output: lines.out

Time Limit: 1000 ms

Memory Limit: 16 MB

Level: ★☆

Farmer John最近發明瞭一個遊戲，來考驗自命不凡的貝茜。遊戲開始的時候，FJ會給貝茜一塊畫著N (2 <= N <= 200)個不重合的點的木板，其中第i個點的橫、縱座標分別為X_i和Y_i (-1,000 <= X_i <=1,000；-1,000 <= Y_i <= 1,000)。

貝茜可以選兩個點畫一條過它們的直線，當且僅當平面上不存在與畫出直線平行的直線。遊戲結束時貝茜的得分，就是她畫出的直線的總條數。為了在遊戲中勝出，貝茜找到了你，希望你幫她計算一下最大可能得分。

程序名: lines

[多源最短路]USACO 奶牛聚會 spart

譯: zqzas

N(1 ≤ N ≤ 1000)個農場中的每個農場都有一隻奶牛去參加位於第X個農場的聚會.共有M (1 ≤ M ≤ 100,000)條單向的道路,每條道路連接一對農場.通過道路i會花費Ti (1 ≤ Ti ≤ 100)的時間.

作爲參加聚會的奶牛必須走到聚會的所在地(農場X).當聚會結束時,還要返回各自的農場.奶牛都是很懶的,她們想找出花費時間最少的路線.由於道路都是單向的,所有她們前往農場X的路線可能會不同於返程的路線.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back? 對於所有參加聚會的奶牛,找出前往聚會和返程花費總時間最多的奶牛,輸出這隻奶牛花費的總時間.

[次短路徑]HAOI2005 路由選擇問題 route 解題報告

路由選擇問題

【問題描述】

    X城有一個含有N個節點的通信網絡，在通信中，我們往往關心資訊從一個節點I傳輸到節點J的最短路徑。遺憾的是，由於種種原因，線路中總有一些節點會出故障，因此在傳輸中要避開故障節點。

任務一：在己知故障節點的情況下，求避開這些故障節點，從節點I到節點J的最短路徑S0。

任務二：在不考慮故障節點的情況下，求從節點I到節點J的最短路徑S1、第二最短路徑S2。

【輸入文件】

第1行： N I J (節點個數 起始節點 目標節點)

第2—N+1行： Sk1 Sk2…SkN (節點K到節點J的距離爲SkJ K=1，2，……，N)

最後一行： P T1 T2……Tp (故障節點的個數及編號)

【輸出文件】

S0 S1 S2 (S1<=S2 從節點I到節點J至少有兩條不同路徑)

[平衡樹]HNOI2004 寵物收養所 pet

題目描述

最近，阿Q開了一間寵物收養所。收養所提供兩種服務：收養被主人遺棄的寵物和讓新的主人領養這些寵物。每個領養者都希望領養到自己滿意的寵物，阿Q根據領養者的要求通過他自己發明的一個特殊的公式，得出該領養者希望領養的寵物的特點值a（a是一個正整數，a<2^31），而他也給每個處在收養所的寵物一個特點值。這樣他就能夠很方便的處理整個領養寵物的過程了，寵物收養所總是會有兩種情況發生：被遺棄的寵物過多或者是想要收養寵物的人太多，而寵物太少。

1．被遺棄的寵物過多時，假若到來一個領養者，這個領養者希望領養的寵物的特點值爲a，那麼它將會領養一隻目前未被領養的寵物中特點值最接近a的一隻寵物。（任何兩隻寵物的特點值都不可能是相同的，任何兩個領養者的希望領養寵物的特點值也不可能是一樣的）如果有兩隻滿足要求的寵物，即存在兩隻寵物他們的特點值分別爲a-b和a+b，那麼領養者將會領養特點值爲a-b的那隻寵物。
2．收養寵物的人過多，假若到來一只被收養的寵物，那麼哪個領養者能夠領養它呢？能夠領養它的領養者，是那個希望被領養寵物的特點值最接近該寵物特點值的領養者，如果該寵物的特點值爲a，存在兩個領養者他們希望領養寵物的特點值分別爲a-b和a+b，那麼特點值爲a-b的那個領養者將成功領養該寵物。

一個領養者領養了一個特點值爲a的寵物，而它本身希望領養的寵物的特點值爲b，那麼這個領養者的不滿意程度爲abs(a-b)。

USACO Contest Feb2012 Bronze Moo 翻譯+題解

翻譯（質量不高，將就看吧）：
USACO Contest Feb2012 Bronze
Problem 3. Moo
奶牛們迷上了一個名為“Moo”的新的單詞遊戲。
在玩該遊戲時，奶牛們站成長長的一排，在隊列中的每一頭
奶牛都有責任盡可能快的大聲說出一個特定的字母。

在Moo遊戲中，這個單詞序列嚴格上說是無窮的，它是這樣開始的：
m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o

這一串最好由遞歸表示：令S(0)為三個字符的序列“moo”
那麼更長的字符串S(k)由三部分組成，第一部分是S(k-1)，第二部分是"m o...o"(k+2個'o')，第三部分又是S(k-1)。例如：
S(0)="m o o"
S(1)="m o o m o o o m o o"
S(2)="m o o m o o o m o o m o o o o m o o m o o o m o o"

正如你所看到的，這個過程最終將會產生一個無窮的長字符串，並且
這個長字符串正是被玩Moo遊戲的奶牛一個一個說出。

Bessie這頭奶牛，自我感覺很聰明，他想要預測第N頭奶牛將會說出m還是o。請你幫助他！

POJ2739(Japan2005) 連續素數和 conprime 解題報告

 連續素數和   題目來源：Japan 2005 （POJ2739）


連結：http://poj.org/problem?id=2739


【問題描述】

一些正整數可以表示成一個或多個連續素數和的形式。那麼一個正整數可以表示成多少種連續素數和的形式呢？例如： 53 有 2 種連續素數和的形式分別是 5+7+11+13+17 和 53. 正整數 41 有 3 種連續素數和的形式： 2+3+5+7+11+13,11+13+17 和 41. 整數 3 只有一種連續素數和的形式就是 3 。 20 就不能表示成連續素數的和。

你的任務就是找出整數 N 能表示成的連續素數和的種數。