[平衡樹]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 能表示成的連續素數和的種數。

漢詩(かんし) 日本語對照 kanshi-nihongo

 

各種OI

USACO: USA Computing Olympiad 美國信息學競賽
CEOI: Central-European Olympiad in Informatics  中歐信息學競賽
SOI: Syrian Olympiad on Informatics 敘利亞信息學競賽
NOI:National Olympiad in Informatics 全國青少年信息學奧林匹克競賽
NOIP: National Olympiad in Informatics in Province 全國青少年信息學奧林匹克聯賽
BOI: Balkan Olympiad in Informatics 巴爾幹信息學競賽
BOI: Baltic Olympiad in Informatics 波羅的信息學競賽
ACM/ICPC: The ACM-ICPC International Collegiate Programming Contest 美國計算機協會世界大學生程序設計大賽
CTSE: Chinese Team Selection Contest IOI中國代表隊選拔賽暨全國信息學精英賽
IOI: International Olympiad in Informatics 國際青少年信息學奧林匹克競賽
POI: Polish Olympiad in Informatics 波蘭信息學競賽
HAOI: Henan Olympiad in Informatics NOI河南省代表隊選拔賽
GDOI: Guangdong Olympiad in Informatics NOI廣東省代表隊選拔賽
GZOI: Guangzhou Olympiad in Informatics 廣州市信息學尖子生選拔賽
BJOI: Beijing Olympiad in Informatics NOI北京市代表隊選拔賽
SDOI: Shandong Olympiad in Informatics NOI山東省代表隊選拔賽
WC: Winter Camp NOI冬令營

[記憶化搜索]USACO Jan09 Silver Laserphones 激光電話

**********************************************************************

Problem 8: Laserphones [Rob Kolstad, 2008]

The cows have a new laser-based system so they can have casual
conversations while out in the pasture which is modeled as a W x H
grid of points (1 <= W <= 100; 1 <= H <= 100).

The system requires a sort of line-of-sight connectivity in order
to sustain communication. The pasture, of course, has rocks and
trees that disrupt the communication but the cows have purchased
diagonal mirrors ('/' and '\' below) that deflect the laser beam
through a 90 degree turn. Below is a map that illustrates the
problem.

【轉載】Linux病毒分類以及防範方法

Linux的用戶也許聽說甚至遇到過一些Linux病毒，這些Linux病毒的原理和發作症狀各不相同，所以採取的防範方法也各不相同。

為了更好地防範Linux病毒，我們先對已知的一些Linux病毒進行分類。從目前出現的Linux病毒來看，可以歸納到以下幾個病毒類型中去：

一段被Kaspersky報毒的Python代碼

看到一段被Kaspersky報病毒"Backdoor.Python.Small.b"的Python代碼，留著以後使用，同時分享給大家研究。請勿用於非法用途！！

裸代碼RawCode

[數學方法]NOIP模擬題：倒水 water 解題報告

【題目描述】

一天， CC 買了 N 個容量可以認為是無限大的瓶子，開始時每個瓶子裡有 1 升水。接著 CC

發現瓶子實在太多了，於是他決定保留不超過 K 個瓶子。每次他選擇兩個當前含水量相同的瓶子，把一個瓶子的水全部倒進另一個裡，然後把空瓶丟棄。（不能丟棄有水的瓶子）

顯然在某些情況下 CC 無法達到目標，比如 N=3,K=1 。此時 CC 會重新買一些新的瓶子（新瓶子容量無限，開始時有 1 升水），以達到目標。

現在 CC 想知道，最少需要買多少新瓶子才能達到目標呢？

[轉載] Linux 的病毒發展史及分類

1996年的Staog是Linux系統下的第一個病毒，它出自澳大利亞一個叫VLAD的組織（Windows 95下的第一個病毒程序Boza也系該組織所為）。Staog病毒是用彙編語言編寫，專門感染二進位制文件，並通過三種方式去嘗試得到root許可權。 Staog病毒並不會對系統有什麼實質性的損壞。它應該算是一個演示版。它向世人揭示了Linux可能被病毒感染的潛在危險。Linux系統上第二個被發現的病毒是Bliss病毒，它是一個不小心被釋放出來的實驗性病毒。與其它病毒不同的是，Bliss本身帶有免疫程序，只要在運行該程序時加上 “disinfect-files-please”選項，即可恢復系統。

　　

[搜索]USACO Open05 疾病管理 disease 解題報告

Title: 疾病管理

Input: disease.in

Output: disease.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

【問題描述】

天啊，真是不幸！最近在農夫 John 的農場上有 D(1<=D<=15) 種疾病 ( 疾病的編號為 1..D) 在奶牛當中流行。 John 想要給他的 N(1<=N<=1000) 頭奶牛擠牛奶。擠出來的牛奶都被放在一個罐子裡面。如果這些牛奶中包含了超過 K(1<=K<=D) 種的疾病，那麼這些牛奶就要全部被丟棄掉了（浪費啊 -_-! ）。 John 應該給這 N 頭奶牛當中的哪些奶牛擠奶，才能使得牛奶不被丟棄，並且擠牛奶的數量最多呢？

USACO Dec07 泥潭 mud 解題報告

Title: 泥潭

Input: mud.in

Output: mud.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

譯 by CmYkRgB123

描述

Farmer John在早晨6點準時去給貝茜擠奶，然而昨天晚上下了大雨，他的牧場變得泥濘不堪了。Farmer John的家在座標平面的 (0,0) 處，貝茜在 (X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500)。他看見了所有的 N (1 ≤ N ≤ 10,000) 個泥潭，分別在 (Ai, Bi) (-500 ≤ Ai ≤ 500; -500 ≤ Bi ≤ 500) 。每個泥潭只佔一個點的位置。

Farmer John 剛剛買了新的靴子，他絕對不想把靴子踩進泥潭弄髒，而他又想儘快的找到貝茜。他已經快晚了，因爲他花了大量的時間來找到所有的泥潭的位置。 Farmer John 只能平行於座標軸移動，每次移動一個單位。請你幫助 Farmer John 找到一條路，使得 Farmer John 能夠最快的找到貝茜，而且不會弄髒靴子。我們約定一定存在一條路使 Farmer John 找到貝茜。

WC2012的神牛們.....

由於報名時運氣不好，沒有報上在常州舉辦的NOI WC2012，所以只好在網路圖片上膜拜神牛了～

 

NOI WC2012開幕式時，我看到滿眼神牛～

其中有CheePok、KingFree、TBK、Michstar

唉～嘆息啊

USACO Oct07 Silver 障礙訓練場 obstacle 解題報告

Title: 障礙訓練場

Input: obstacle.in

Output: obstacle.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

譯 By CmYkRgB123

考慮一個 N x N (1 <= N <= 100)的有1個個方格組成的正方形牧場。有些方格是奶牛們不能踏上的，它們被標記爲了'x'。例如下圖：

        . . B x .
        . x x A .
        . . . x .
        . x . . .
        . . x . .

貝茜發現自己恰好在點A出，她想去B處的鹽塊添鹽。緩慢而且笨拙的動物，比如奶牛，十分討厭轉彎。儘管如此，當然在必要的時候她們還是會轉彎的。對於一個給定的牧場，請你計算從A到B最少的轉彎次數。開始的時候，貝茜可以使面對任意一個方向。貝茜知道她一定可以到達。

[數學方法]OI練習題：硬幣遊戲 coins 解題報告

 硬幣遊戲  coins.cpp/c/pas

【問題描述】

Alice 和 Bob 決定要玩一個有趣的硬幣遊戲。遊戲的一開始他們把 n (1<=n<=10^6 ) 個硬幣放成一個圓圈，如下圖所示。一次操作是指拿走一個硬幣或者拿走兩個相鄰的硬幣，而其他的硬幣留在原來的位置不動。每次操作至少要拿走一個硬幣。從 Alice 開始，遊戲雙方輪流進行操作。拿到最後一個硬幣的人獲勝。

注意：當 n>3 時，我們沿順時針方向用 C1 ， C2 ， ….. Cn 來表示這 n 個硬幣。如果 Alice 拿走了 C2 ，那麼 C1 和 C3 就不相鄰了！（因為它們中間有一個空位置）

假設 Alice 和 Bob 都很聰明，並且兩個人都用最好的策略來比賽。現在請你來寫一個程序判斷誰將會贏得這個比賽？

USACO 2009 9th 熱浪 heatwv 解題報告

USACO/heatwv

第九題: 熱浪 [300分] [Rob Kolstad (傳統題目), 2009]
德克薩斯純樸的民眾們這個夏天正在遭受巨大的熱浪！！！他們的德克薩斯長角牛吃起來不錯， 可是他們並不是很擅長生產富含奶油的乳製品。Farmer John此時以先天下之憂而憂，後天下 之樂而樂的精神，身先士卒地承擔起向德克薩斯運送大量的營養冰涼的牛奶的重任，以減輕德 克薩斯人忍受酷暑的痛苦。
FJ已經研究過可以把牛奶從威斯康星運送到德克薩斯州的路線。這些路線包括起始點和終點先 一共經過T (1 <= T <= 2,500)個城鎮，方便地標號為1到T。除了起點和終點外地每個城鎮 由兩條雙向道路連向至少兩個其它地城鎮。每條道路有一個通過費用（包括油費，過路費等等）。 考慮這個有7個城鎮的地圖。城鎮5是奶源，城鎮4是終點（括號內的數字是道路的通過費用）。