[搜索]OI練習題：求圖形面積 area

題一 求圖形面積

【問題描述】

具有不同顏色的 N 個小的矩形的紙被疊放在一張白紙上， 紙的尺寸是寬(左右)為A， 長(上下)為B，擺放矩形時使矩形的邊與紙的邊平行，並且每個矩形必須整個放在紙的邊界之內。因此，不同顏色的各種不同圖形可在紙上出現，同一顏色的兩個區域中如果至少有一個公共點，則認為它們是同一圖形的一部分，否則認為是不同的圖形。

題目要求計算每一圖形的面積。 A ， B 是正的偶數，且均不大於30 。座標系統的定義為：座標原點在紙的中心，兩個軸分別平行於紙的兩邊。

[轉載]次短路径与次小生成树问题的简单解法

轉載自http://www.byvoid.com/blog/2-sp-mst/ ，轉載請註明！

  次短路径与次小生成树问题的简单解法

 

[次短路径]

次短路径可以看作是k短路径问题的一种特殊情况，求k短路径有Yen算法等较为复杂的方法，对于次短路径，可以有更为简易的方法。下面介绍一种求两个顶点之间次短路径的解法。

美國各大網站抗議SOPA

這兩天正值美國國會審議SOPA法案的日子。為了抗議美國對網絡進行審查，美國各大互聯網公司都在自己網站的醒目位置放置抗議標語，有點網站甚至全站關停。
以下就是我對一些參加抗議的網站的截圖。
（什麼時候中國互聯網公司也能聯合起來反抗G.F.W.就好了）

推薦一個在線Ping的網站！

今天發現了一個可以在線Ping的網站，網址是http://just-ping.com。
你輸入一個地址後，該網站會返回世界各地幾十個城市Ping的結果，很不錯。
當然，Ping www.twitter.com等會觸發關鍵詞遭到屏蔽。

下面是我博客的Ping結果。

[動態規劃]OI練習題：打鼴鼠 mouse 解題報告

【問題背景】
鼴鼠是一種很喜歡挖洞的動物，但每過一定的時間，它還是喜歡把頭探出到地面上來透透氣的。

根據這個特點阿Q編寫了一個打鼴鼠的遊戲：在一個n*n的網格中，在某些時刻鼴鼠會在某一個網格探出頭來透透氣。你可以控制一個機器人來打鼴鼠，如果i時刻鼴鼠在某個網格中出現，而機器人也處於同一網格的話，那麼這個鼴鼠就會被機器人打死。而機器人每一時刻只能夠移動一格或停留在原地不動。機器人的移動是指從當前所處的網格移向相鄰的網格，即從座標為（i,j）的網格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四個網格，機器人不能走出整個n*n的網格。遊戲開始時，你可以自由選定機器人的初始位置。

【任務描述】

現在你知道在一段時間內，鼴鼠出現的時間和地點，希望你編寫一個程序使機器人在這一段時間內打死儘可能多的鼴鼠。

筆記本鍵盤字母變數字 解決方案

有時我們可能會遇到這樣的情況，筆記本鍵盤上的字母按鍵點擊後出現的是數字，而不是我們想要的字母。這種問題該怎樣解決呢？


    其實，筆記本鍵盤字母變數字是因爲打開了筆記本鍵盤的數字鍵盤鎖。解決筆記本鍵盤字母變數字的方法很簡單，我們只需關閉數字鍵盤鎖即可。關閉方法如下：


    在鍵盤上尋找NumLk鍵（一般爲藍色，位於鍵盤右上角，在F12上或其周圍）。找到以後，按住左下角的Fn按鍵，再按一下NumLk鍵就可以了。這樣，筆記本鍵盤字母變數字的問題就解決了。


    但是，有些筆記本的Fn鍵只有在電腦安裝了相應的電源管理軟件之後才能使用，這種情況下按下Fn+NumLk並不能解決筆記本鍵盤字母變數字的問題。這時候，我們需要到筆記本廠商官網下載或從筆記本附贈的光盤中安裝電源管理軟件，然後再使用Fn+NumLk關閉數字鍵盤鎖。


    對筆記本鍵盤來說，數字鍵盤鎖可以使數字的輸入變得非常方便，是一個實用的功能，大家在使用筆記本的時候可以對此多加留意。


    類似的按鍵還有Scr Lk，此鍵在Excel中用於鎖屏。

[搜索]POI1997 阿里巴巴 ali 解題報告

【問題描述】
想要“芝麻開門”，必須擁有一定數量的錢幣，其中包括至少z枚金幣，s枚銀幣和m枚銅幣。 最初，阿里巴巴擁有三種錢幣若干枚。他可以按照一定規則和芝麻之門的守護者進行交易。 每一種規則用以下形式表示：

z1, s1, m1 -> z2, s2, m2 (zi, si, mis屬於集合{0,1,2,3,4})。

這樣一種規則表示阿里巴巴可以將z1枚金幣, s1枚銀幣, m1枚銅幣換成z2枚金幣, s2枚銀幣, m2枚銅幣。 一次交易而得的錢幣可以繼續參加下一次的交易。

任務

從文件中讀入幾組資料；對於每一組資料：

阿里巴巴最初擁有的金銀銅三種錢幣數目

“芝麻開門”所需的金銀銅三種錢幣數目

所有交易規則

對每一組資料，判斷是否存在有限次的交易，使阿里巴巴能開啟芝麻之門。如果是，則將最少交易次數輸出，否則在輸出NIE(波蘭文NO)

把結果寫進文件中

[網絡最大流]POI1999 洞穴探險 gro 解題報告

問題描述

古老的Byte山上有一處神祕的連環洞穴。考古學家們爲了對這個洞穴進行研究，組織了一次探險活動。他們花了幾天的時間仔細地翻閱了前人留下的資料，對該連環洞穴有了大致的瞭解。

這是一個有許多不同的小溶洞組成的連環洞穴，每個小溶洞都分佈在不同的地層中，並且可能通過洞穴隧道與其他小溶洞相通。

考古學家們已經發現了作爲連環洞穴的入口的一個小溶洞，並且根據前人的資料，繪製出了洞穴的地圖，標明瞭哪些小溶洞之間是有洞穴隧道相連的。

富有冒險和激情的考古學家們都期望自己能夠獨自進行探險活動。於是，他們又提出了這樣的要求：從入口的溶洞出發時，每個人都選擇一條不同的 洞穴隧道前進；探險結束時，每個人都是通過不同的洞穴隧道抵達最底層的小溶洞。當然了，這些考古學家也達成了妥協：在探險的過程中，可以有不止一名的考古 學家通過同一條洞穴隧道。 爲了體現這次探險活動的一往直前的精神，考古學家們還決定，要從小溶洞入口進入，一直抵達最底層的溶洞！每個考古學家探險路線上通過的小溶洞所在的地層必 須比該路線上前一個溶洞的地層低。

考古學家提出來如此多的要求使得本次探險活動的組織者犯了愁，他究竟最多能邀請多少位考古學家來參加這項活動呢？

[數論]OI練習題：最優分解方案 best 解題報告

[問題描述]

經過第一輪的遊戲，不少同學將會獲得聖誕特別禮物，但這時細心的數學課代表發現了一個問題：留下來的人太多而使禮物數量可能不夠，為此，加試了一道數學題：將一個正整數 n 分解成若干個互不相等的正整數的和，使得這些數的乘積最大，當主持人報出一個 n 後，請你立即將這個最大值報出來，現請你幫你的好友編一個程序來解決這個問題。

網絡流 練習題：流量有下限的最大流

Title: 運輸問題2
Input: maxflowb.in
Output: maxflowb.out
Time Limit: 1000 ms
Memory Limit: 128 MB
Level: ★★★
運輸問題
【問題描述】
一個工廠每天生產若干商品，需運輸到銷售部門進行銷售。從產地到銷地要經過某些城鎮，有不同的路線可以行走，每條兩城鎮間的公路都有一定的流量限制。爲了 保證公路的運營效率，每條公路都有一個容量下界，也就是至少應有多少車輛通過。每條公路還有一個容量上界，也就是最多應有多少車輛通過。請你計算，在不考 慮其它車輛使用公路的前提下，如何充分利用所有的公路，使產地運輸到銷地的商品最多，最多能運輸多少商品。