圖論練習題 摔跤 rassle 題解

【問題描述】

有兩種類型的職業摔跤手：一種是“好選手”，另一種是“差選手”。對於任何一對職業摔跤手來說，他們中可能有、也可能沒有比賽。假定有 n 位職業摔跤手，並且有一份清單，上面列出了 r 對參加比賽的摔跤手。寫一個程序,它能夠確定是否可能指定某些摔跤手為好選手，而將餘下的摔跤手指定為壞選手，從而使得每一場比賽都是在一個好選手與一個差選手之間進行。如果有可能做出這樣的指定，你的程序就應該將它產生出來，否則輸出無解“No”。

【輸入格式】

第1行有三個整數n，r。n是職業摔跤手的數量，r是比賽場數，它們之間用一個空格隔開。

接下來的r行，每行用兩個數V1，V2表示V1號摔跤手與V2號摔跤手比賽，選手從1開始編號。

【輸出格式】

輸出有兩行，第一行“好選手”的編號，第二行為“差選手”的編號，編號之間用一個空格隔開。

注意：為了鼓勵選手，使輸出答案唯一，請儘量多的將選手設為“好選手”，並且在可行條件下選擇編號小的選手為“好選手”。

如果無解，則輸出一行“No”。

[搜索]ACM練習題：分球 ball 解題報告

題目來源：
1. 浙江理工大學 OnlineJudge 2584
2. 山東理工大學 OnlineJudge 1406

【問題描述】

在一個裝滿財寶的屋子裡，有2N個盒子排成一排。除了兩個相鄰的空盒外，其餘的每個盒子裡都裝有一個金球或者一個銀球，總共有N-1個金球和N-1個銀球。用圖6．3所示為一個N=5時的例子，G表示金球，S表示銀球。

G

S

S

G

G

S

G

S

任意兩個相鄰的非空的盒子裡的球可以移動到兩個相鄰的空盒中，移動不能改變這兩個球的排列順序。寫一個程序，用最少的移動次數把所有的金球都移到所有的銀球的左邊。

[動態規劃]OI練習題 週年紀念聚會 aniv 解題報告

週年紀念聚會

Background

校長正在籌備學校的80週年紀念聚會。由於學校的職員有不同的職務級別，可以構成一棵以校長為根的人事關係樹。每個職員都有一個唯一的整數編號（範圍在1到N之間），並且對應一個參加聚會所獲得的歡樂度。為了使每個參加聚會者都感到歡樂，校長想設法使每個職員和他（她）的直接上司不會同時參加聚會。

Problem

你的任務是設計一份參加聚會者的名單，使總的歡樂度最高。

Input

輸入的第一行是一個整數N，1<= N <= 6000

以下的N行是對應的N個職員的歡樂度（歡樂度是一個從-128到127之間的整數）

接著是學校的人事關係樹，樹的每一行格式如下：

<L> <K>

表示第K個職員是第L個職員的直接上司。

輸入以0 0表示結束

輸出：參加聚會者獲得的最大總歡樂度

[記憶化搜索]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.

[搜索]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 找到貝茜。

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最少的轉彎次數。開始的時候，貝茜可以使面對任意一個方向。貝茜知道她一定可以到達。

【搜索】單詞遊戲 words 解題報告

Title: 單詞遊戲

Input: words.in

Output: words.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

【問題描述】

慧慧和南南在玩一個單詞遊戲。

他們輪流說出一個僅包含母音字母的單詞，並且後一個單詞的第一個字母必須與前一個單詞的最後一個字母一致。

遊戲可以從任何一個單詞開始。

任何單詞禁止說兩遍，遊戲中只能使用給定詞典中含有的單詞。

遊戲的複雜度定義為遊戲中所使用的單詞長度總和。

編寫程序，求出使用一本給定的詞典來玩這個遊戲所能達到的遊戲最大可能複雜度。

[BFS]POI2007 山峰和山谷 grz 解題報告

Ridges and Valleys

Memory limit: 32 MB

Byteasar loves trekking in the hills. During the hikes he explores all the ridges and valleys in vicinity. Therefore, in order to plan the journey and know how long it will last, he must know the number of ridges and valleys in the area he is going to visit. And you are to help Byteasar.
Byteasar has provided you with a map of the area of his very next expedition. The map is in the shape of a square. For each field belonging to the square (for ), its height is given.
We say two fields are adjacent if they have a common side or a common vertex (i.e. the field is adjacent to the fields , , , , , , , , provided that these fields are on the map).
We say a set of fields forms a ridge (valley) if:

• all the fields in have the same height,
• the set forms a connected part of the map (i.e. from any field in it is possible to reach any other field in while moving only between adjacent fields and without leaving the set ),
• if and the field is adjacent to , then (for a ridge) or (for a valley).

In particular, if all the fields on the map have the same height, they form both a ridge and a valley.
Your task is to determine the number of ridges and valleys for the landscape described by the map.

[搜索]USACO Feb08 Silver 流星雨 meteor 解題報告

題目連結：http://cogs.yeefanblog.tk/t/138

Title: 流星雨

Input: meteor.in

Output: meteor.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

貝茜聽說了一個駭人聽聞的消息：一場流星雨即將襲擊整個農場，由於流星體積過大它們無法在撞擊到地面前燃燒殆盡，屆時將會對它撞到的一切東西造成毀 滅性的打擊。很自然地，貝茜開始擔心自己的安全問題。以FJ牧場中最聰明的奶牛的名譽起誓，她一定要在被流星砸到前，到達一個安全的地方（也就是說，一塊 不會被任何流星砸到的土地）。如果將牧場放入一個直角座標系中，貝茜現在的位置是原點，並且，貝茜不能踏上一塊被流星砸過的土地。

根據預報，一共有M顆流星(1 <= M <= 50,000)會墜落在農場上，其中第i顆流星會在時刻T_i (0 <= T_i <= 1,000)砸在座標為(X_i, Y_i) (0 <= X_i <= 300；0 <= Y_i <= 300)的格子裡。流星的力量會將它所在的格子，以及周圍4個相鄰的格子都化為焦土，當然貝茜也無法再在這些格子上行走。

貝茜在時刻0開始行動，它只能在第一象限中，平行於座標軸行動，每1個時刻中，她能移動到相鄰的（一般是4個）格子中的任意一個，當然目標格子要沒有被燒焦才行。如果一個格子在時刻t被流星撞擊或燒焦，那麼貝茜只能在t之前的時刻在這個格子裡出現。

請你計算一下，貝茜最少需要多少時間才能到達一個安全的格子。

程序名: meteor

GZOI2011 Rail 解題報告

第四題（40分）

提交文件：Rail.exe

輸入文件：Rail.in

輸出文件：Rail.out

題目描述：

你所在的省剛獲得國家撥款興建高鐵，高鐵的起止城市是國家選定的，中途可能經過若干城市。根據國家撥款的政策，國家將負擔費用最大的兩個區間，其餘的必須由省負擔。假如高鐵線路中途只經過一個城市，國家只負擔費用較大的區間。假如是直達的，國家將不負擔任何費用。

你被省裡選定作為這個項目的總工程師，你必須規劃出一條高鐵線路，使得省負擔的費用最少。當然，路線上每個城市最多只經過一次。

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

題一 求圖形面積

【問題描述】

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

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

[搜索]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)

把結果寫進文件中

USACO Dec2011 Bronze: Escaping the Farm 翻譯+題解

Problem 3: Escaping the Farm [Brian Dean and Kalki Seksaria, 2011]
【英文原題】
The cows have decided on a daring plan to escape from the clutches of
Farmer John. They have managed to procure a small inflatable raft, and
during the cover of night, a group of cows will board the raft and row
across the river bordering the farm. The plan seems perfect, until the
cows realize that their small inflatable raft may not be able to hold
much weight!
The N cows (1 group of cows is light enough to avoid sinking the raft, the cows add up
all of the weights in the group. Unfortunately, cows are notoriously bad at
arithmetic, and if the addition of the weights of the cows in a group
causes any carries to occur (using standard base 10 addition), then the
cows give up and conclude that group must weigh too much to use the raft.
Any group whose weights can be added without any carries is assumed to be
light enough to fit on the raft.
Please help the cows determine the size of the largest group that they
believe can fit on the raft (that is, the largest group whose weights can
be added together with no carries).
PROBLEM NAME: escape
INPUT FORMAT:
* Line 1: The number of cows, N (1
* Lines 2..N+1: Each line contains the weight of one cow, an integer
in the range 1…100,000,000.
SAMPLE INPUT (file escape.in):
5
522
6
84
7311
19
INPUT DETAILS:
There are 5 cows, with weights 522, 6, 84, 7311, and 19.
OUTPUT FORMAT:
* Line 1: The number of cows in the largest group whose weights can be
added together with no carries.
SAMPLE OUTPUT (file escape.out):
3
OUTPUT DETAILS:
The three weights 522, 6, and 7311, can be added together with no carries:
522
6
+ 7311
——
7839

【中文翻譯】

Problem 3:逃離農場
譯by Freddy
【題目描述】
奶牛們做了一個魯莽的計劃：那就是逃離農場主Farmer John。她們已經獲得了一個可充氣的小型木筏，計劃在某天夜晚中，一群奶牛通過使用木筏渡而過位於農場邊界的河流。這個計劃似乎很完美，直到奶牛們意識到她們的小木筏可能不能承受住她們的體重。

這N頭奶牛(1<=N<=20)的體重w_1…w_N。為了計算出一群奶牛的體重能否避免木筏沉沒的悲劇，一群奶牛把她們的體重加在一起。
不幸的是，奶牛們在算術方面臭名遠揚，並且一群奶牛內的各奶牛體重相加的過程中如果出現了進位（標準的10進制），那麼這群奶牛只好放棄因為她們知道她們的體重對於小木筏來說太重了。

所有 那些群內奶牛體重相加不出現進位的奶牛群都被認為可以乘坐那個木筏而不發生沉沒。

請幫奶牛們找出能乘坐木筏而不沉沒的奶牛群的最大奶牛數。（也就是說，找出最多的奶牛使她們的體重相加而不出現進位。）

程序名：escape
輸入格式：
▪第1行：奶牛的數量，N(1<=N<=20)
▪第2…N+1行：每行包含一頭奶牛的體重，一個整數(1…100,000,000)。
輸入樣例(file escape.in)：
5
522
6
84
7311
19
輸入解釋：
有5只奶牛，她們的體重分別為522，6，84，7311和19。
輸出格式：
只有一行，表示一群使她們的體重相加而不出現進位的奶牛的最大奶牛數量。
輸出樣例（file escape.out）：
3
輸出解釋：



這三個奶牛的體重分別為：522，6，7311，它們相加不會出現進位：
    522
       6
+7311
 ——–
  7839

【分析】
搜索題目，可以用DFS。遞歸每頭牛的兩種狀態：要或者不要，每次遞歸判斷一下是否符合要求（沒有進位），然後更新最優值即可。
時間複雜度:
DFS遞歸：O(2^N)
判斷：O(KN) 『K是讀入的數字的平均長度，根據題意，可取5～6』

【我的代碼】

/*
ID:yeefan
LANG:C++
PROB:escape
website:http://yeefan.tk/
*/
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
int N;
int W[21];
int A=0;
int Q[21];
int Best=0;
void init()
{
 scanf("%d\n",&N);
 for (int i=1;i<=N;i++)
  scanf("%d\n",&W[i]);
 return;
}
void check()
{
 int T[11];
 memset(T,0,sizeof(T));
 for(int i=1;i<=A;i++)
 {
  int K=1;
  int tmp=W[Q[i]];
  while(tmp!=0)
  {
   T[K]+=tmp%10;
   tmp/=10;
   K++;
  }
 }
 for(int i=1;i<=10;i++)
 {
  if(T[i]>=10)
   return;
 }
 if(A>Best)
  Best=A;
}
void dfs(int num)
{
 if(num==N+1)
 {
  check();
  return;
 }
 Q[++A]=num;
 dfs(num+1);
 A--;
 dfs(num+1);
}
int main()
{
 freopen("escape.in","r",stdin);
 freopen("escape.out","w",stdout);
 init();
 dfs(1);
 printf("%d\n",Best);
 //printf("%d\n",clock());
 return 0;
}

【BFS】GZOI2011廣州2011選拔賽：理財年代 money 解題報告

【問題描述】

最近通貨膨脹很厲害，CPI跑得比銀行利息要快，要抗通脹，又要避風險，其中一種很好的方式，就是購買銀行發行的理財產品。雖然理財產品的利息比銀行定期要高，而且沒有風險，但是，購買理財產品需要一定的資金門檻，而且還要保證吧錢存入一定時間不能取出來，因此也是有一定的限制的。

小郭很喜歡研究銀行的理財產品，她計劃在2011年拿10萬元進行理財產品的投資，為了簡單方便，她在2011年每次投資理財產品時，都是把這筆資金和之前購買理財產品產生的所有利息投入進去，希望在年底獲取最高的利潤。

【理財產品】

一個理財產品有如下要素：

資金門檻：至少要投入多少資金；

發行時間：該理財產品的購買時間；

投資天數：資金存放的天數，

年利息：該理財產品如果存放一年365天能獲取的利息。

由於郭小姐選擇的所有理財產品的門檻都是10萬以內，因此理財產品就剩下的3個要素。

例如，A1理財產品，發行時間是3月1日，投資天數為30天，年利息為 3.5%，那麼，如果10萬元購買該產品，那麼在30天后，也就是3月30日收市後，她可以獲得的資金為：

`100000*(1+0.035*30/365)=100287.67元 （四捨五入，保留2位小數）

然後，她就可以吧100287.67元這筆資金，購買3月31日或之後發行的任何理財產品。

郭小姐在這一年內不斷把本金和利息一起全額地購買理財產品，希望在2012年到來之前獲得最高的收益。如果購買的兩個理財產品之間有時間間隔，那麼這筆錢就不能產生利潤（銀行活期利息太低，利潤可以忽略）。請問她這年內，能通過購買理財產品，最多獲取多少錢呢？

【輸入格式】

第一行是整數N(1<=N<=15)，代表理財產品的數目

下面N行為3個由空格隔開的字元串 A B C

A代表發行時間，格式為MMDD（兩位月兩位日），例如4月1日則為0401，10月2日則為1002

B (整數)，代表投資天數，範圍是[10,300]

C (最多2位的小數)，代表百分之幾的年利息，範圍是[3,30]

輸入資料保證 發行時間+投資天數不會超過2012年。

【輸出格式】

輸出只有一行，為年底最多可獲得的連本帶利的資金數目，保留2位小數

【輸入樣例】

3

0101 100 4.5

0201 30 5

0402 50 7.8

【例子分析】

例子中的3個理財產品，只能購買1號產品，或者連續購買2號、3號理財產品。

購買1號理財產品的收益為 100000*(1+0.045*100/365)=101232.88

購買2/3號理財產品的收益為：

購買2號產品後總資金： 100000*(1+0.05*30/365)=100410.96

再購買3號產品後總資金： 100410.96*(1+0.078*50/365)=101483.84

因此最高收益為 101483.84

【輸出樣例】

101483.84

【分析】

本題是廣州NOI選拔賽中比較簡單的一道，可以用BFS廣度優先搜索做。由於N很小、而且減枝十分有效，所以隊列會很小。

本題易錯地方有：

1) 日期的轉換和判斷

2) 利息的計算

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int N;
class Money
{
public:
    int Mon;
    int Days;
    int Day1;
    int Day2;
    int Time;
    double Rate;
}M[30];

int days(int b,int c) 
{ 
    int d=0; 
    if(b==1) d=c; 
    if(b==2) d=31+c; 
    if(b==3) d=60+c; 
    if(b==4) d=91+c; 
    if(b==5) d=121+c; 
    if(b==6) d=152+c; 
    if(b==7) d=182+c; 
    if(b==8) d=213+c; 
    if(b==9) d=244+c; 
    if(b==10) d=274+c; 
    if(b==11) d=305+c; 
    if(b==12) d=335+c; 
    return d; 
} 

int cmp(const void *a,const void *b)
{
    class Money *c=(class Money *)a;
    class Money *d=(class Money *)b;
    if(c->Day1!=d->Day1)
        return c->Day1-d->Day1;
    return c->Day2-d->Day2;
}

void init()
{
    scanf("%d\n",&N);
    int tmp1,tmp2;
    char ch1,ch2;
    for (int i=1;i<=N;i++)
    {
        scanf("%c%c",&ch1,&ch2);
        tmp1=(ch1-'0')*10+ch2-'0';
        scanf("%c%c",&ch1,&ch2);
        tmp2=(ch1-'0')*10+ch2-'0';
        M[i].Mon=tmp1;
        M[i].Days=tmp2;
        M[i].Day1=days(tmp1,tmp2);
        scanf("%d %lf\n",&M[i].Time,&M[i].Rate);
        M[i].Day2=M[i].Day1+M[i].Time-1;
    }
    qsort(M+1,N,sizeof(M[0]),cmp);
}

class QUEUE
{
public:
    double money;
    int pos;
    int day;
}Q[100000];

double GetMoney(double ben,int num)
{
    double res=ben;
    double rate=double(1)+M[num].Rate*(double(M[num].Time)/double(365))/(double(100));
    res=res*rate;
    return res;
}

void bfs()
{
    double S=0;
    int head=N;
    int rear=0;
    for (int i=1;i<=N;i++)
    {
        Q[i-1].pos=i;
        Q[i-1].money=GetMoney(double(100000),i);
        Q[i-1].day=M[i].Day2+1;
    }
   
    double tm;
    int td;
    int tp;
    while(rear<head)
    {
        tm=Q[rear].money;
       
        if(tm>S)
            S=tm;
       
        td=Q[rear].day;
        tp=Q[rear].pos;
        for(int i=tp+1;i<=N;i++)
        {
            if(M[i].Day1>=td)
            {
                Q[head].money=GetMoney(tm,i);
                Q[head].pos=i;
                Q[head].day=M[i].Day2+1;
                head++;
            }
        }
        rear++;
    }
    printf("%.2lf\n",S);
}


int main()
{
    freopen("money.in","r",stdin);
    freopen("money.out","w",stdout);
    init();
    bfs();
    return 0;
}

NOIP2011_Day1 mayan:用程序解決mayan puzzle遊戲

NOIP2011一試的第三題給我介紹了一個好玩的智力遊戲——Mayan Puzzle。聯賽過後，我從網上下載了這個一夜間變得巨火的遊戲。

在遊戲中，第9關被用來當聯賽那題的說明，第14關就是輸入輸出樣例。

遊戲下載：英文原版、漢化版

首先先誇讚一下遊戲的開發人員，動畫效果做的不錯啊！

我在第8關就碰到了難題，一直過不了關，於是就用聯賽時寫的程序試了一下，結果很棒，程序總能找到正確的解決方案！於是從第8關到第45關都是我用程序解出來的～～

先貼上程序吧：

C++语言: Codee#24246

//NOIP2011-Senior-mayan
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct aaa
{
    int t[6];
    int c[6][8];
    aaa()
    {
        memset(t,0,sizeof(t));
        memset(c,0,sizeof(c));
    }
};

int n,ans[6][3];

bool flag,b[6][8];

aaa solve(aaa g)
{
    aaa h;
    int i,j;
    for(i=1;i<=5;i++)
    {
        for(j=1;j<=g.t[i];j++)
        {
            if(g.c[i][j]&&!b[i][j])
            {
                h.t[i]++;
                h.c[i][h.t[i]]=g.c[i][j];
            }
        }
    }
    return h;
}

aaa clear(aaa g)
{
    int i,j;
    aaa h;
    flag=false;
    memset(b,0,sizeof(b));
    for(i=1;i<=5;i++)
    {
        for(j=1;j<=g.t[i];j++)
        {
            if(i<=3)
            {
                if(g.c[i][j]==g.c[i+1][j]&&g.c[i][j]==g.c[i+2][j])
                {
                    b[i][j]=b[i+1][j]=b[i+2][j]=true;
                    flag=true;
                }
            }
            if(j<=g.t[i]-2)
            {
                if(g.c[i][j]==g.c[i][j+1]&&g.c[i][j]==g.c[i][j+2])
                {
                    b[i][j]=b[i][j+1]=b[i][j+2]=true;
                    flag=true;
                }
            }
        }
    }
    if(flag)
    {
        h=solve(g);
        return clear(h);
    }
    else
    {
        return g;
    }
}

void output()
{
    freopen("mayan.out","w",stdout);
    int i;
    for(i=1;i<=n;i++)
    {
        printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
    }
    exit(0);
}

void dfs(aaa g,int k)
{
    int i,j,l;
    aaa h;
    flag=true;
    for(i=1;i<=5;i++)
    {
        if(g.t[i])
        {
            flag=false;
            break;
        }
    }
    if(flag)
    {
        if(k>n)
        {
            output();
        }
        else
        {
            return;
        }
    }
    if(k>n)
    {
        return;
    }
    for(i=1;i<=5;i++)
    {
        for(j=1;j<=g.t[i];j++)
        {
            if(i<5)
            {
                if(j>g.t[i+1])
                {
                    h=g;
                    h.t[i+1]++;
                    h.c[i+1][h.t[i+1]]=h.c[i][j];
                    h.c[i][j]=0;
                    h.t[i]--;
                    for(l=j;l<=h.t[i];l++)
                    {
                        h.c[i][l]=h.c[i][l+1];
                    }
                    h=clear(h);
                    ans[k][0]=i-1;
                    ans[k][1]=j-1;
                    ans[k][2]=1;
                    dfs(h,k+1);
                }
                else
                {
                    h=g;
                    l=h.c[i][j];
                    h.c[i][j]=h.c[i+1][j];
                    h.c[i+1][j]=l;
                    h=clear(h);
                    ans[k][0]=i-1;
                    ans[k][1]=j-1;
                    ans[k][2]=1;
                    dfs(h,k+1);
                }
            }
            if(i>1)
            {
                if(j>g.t[i-1])
                {
                    h=g;
                    h.t[i-1]++;
                    h.c[i-1][h.t[i-1]]=h.c[i][j];
                    h.c[i][j]=0;
                    h.t[i]--;
                    for(l=j;l<=h.t[i];l++)
                    {
                        h.c[i][l]=h.c[i][l+1];
                    }
                    h=clear(h);
                    ans[k][0]=i-1;
                    ans[k][1]=j-1;
                    ans[k][2]=-1;
                    dfs(h,k+1);
                }
            }
        }
    }
}

int main()
{
    freopen("mayan.in","r",stdin);
    freopen("mayan.out","w",stdout);
    int i,j;
    aaa g;
    scanf("%d",&n);
    for(i=1;i<=5;i++)
    {
        scanf("%d",&j);
        while(j)
        {
            g.t[i]++;
            g.c[i][g.t[i]]=j;
            scanf("%d",&j);
        }
    }
    dfs(g,1);
    printf("-1\n");
    return 0;
}

比如第10關，把它轉換為程序的輸入文件就是這樣：
mayan.in
3
1 2 2 0
2 0
1 0
3 1 3 0
1 3 1 0

運行程序，輸出文件是：
mayan.out
0 0 1
3 2 1
3 0 1

於是我按照程序的“指示”移動方塊，沒想到果然過關了！

[搜索]AHOI2009：飛行棋 fly 解題報告

Description

給出圓週上的若干個點，已知點與點之間的弧長，其值均爲正整數，並依圓周順序排列。

請找出這些點中有沒有可以圍成矩形的，並希望在最短時間內找出所有不重複矩形。

Input

第一行爲正整數N，表示點的個數，接下來N行分別爲這N個點所分割的各個圓弧長度

Output

所構成不重複矩形的個數

Sample Input

8 1 2 2 3 1 1 3 3

Sample Output

3

Hint

N<= 20

Source 

HAOI2009-2    2009年安徽NOI省選 第二試 第一題

【分析】 

省選中的水題，直接爆搜即可。

根據平面幾何的知識，構成矩形的充分條件是對邊相等。

由於數據量不大，深度優先搜索、廣度優先搜索均可，連開四層循環暴力枚舉都可以。

【我的代碼】
#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
int N;
int Q[5];
int S[21]={0};
int C[21];
int ans=0;

void init()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>C[i];
        S[i]=S[i-1]+C[i];
    }
}

void dfs(int deep,int num)
{
    if(deep==5)
    {
        if((S[N]-Q[2]-Q[3]-Q[4])==Q[3] && Q[2]==Q[4])
            ans++;
        return;
    }
    for (int i=num+1;i<=N;i++)
    {
        Q[deep]=S[i]-S[num];
        dfs(deep+1,i);
    }
}

int main()
{
    freopen("fly.in","r",stdin);
    freopen("fly.out","w",stdout);
    init();
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}

[搜索][最短路徑]BYVoid魔獸世界模擬題Stage.1 埃雷薩拉斯的尋寶 eldrethalas 解題報告

【問題描述】

一萬兩千年前，精靈還是在艾薩拉女王的統治下，辛德拉是女王手 下一名很有地位的法師。他受任建造了一座城市，來保存女王的法師們進行魔法研究的成果和法術物品。這個城市就是埃雷薩拉斯。永恆之井的爆炸，使這裏的精靈 和總部聯繫中斷，並失去了永恆之井的水做爲能量的來源。辛德拉的後人爲了滿足魔法的慾望，捕獵了一個惡魔，伊莫塔爾，並以水晶塔建造了一個帶有能量平衡係 統的結界監獄，水晶塔從惡魔身上吸取能量，一部分維持結界監獄，一部分可以讓精靈狂熱者吸收。近萬年平安無事。但是現在，惡魔的能量被消耗得越來越多，最 終變得不穩定，已經難以維持結界監獄的消耗。統治這裏的托爾塞林王子開始下令屠殺。只有少數狂熱者之外的其他人都要死，以減少魔法能量的消耗。

終於，強大的戈多克食人魔入侵了埃雷薩拉斯，並殺死了大量的精靈。他們把這裏當作他們的領地，叫做厄運之槌。面臨滅頂之災的精靈們把他們祖先留下的寶藏用魔法結界藏了起來，以防戈多克食人魔搶走。

作爲一名勇敢的探險者，你悄悄來到了埃雷薩拉斯，來尋找傳說中的寶藏。終於，你看到了寶藏，他就在你的前方不遠處。但是你不能貿然前進，因爲路上有着強大的魔法結界。這些結界根據能量的不同分爲P種，踏入每種結界，你都會受到一定的傷害。爲了拿到寶藏，這些傷害算不了什麼。但是你要儘可能地減少傷害，請你設計一條路綫，使你穿越結界獲取寶藏受到的傷害最少。

下面是一個魔法結界能量示意圖，結界是一個正方形，內部有P種不同的能量，每種字母表示一種能量。你從最上端開始走，每次能走到與你所在的位置鄰接的一個單元格，或者在同種能量結界中任意傳送。重複進入同一種能量結界不會再次受到傷害。

|AAABBC|

|ABCCCC|

|AABBDD|

|EEEEEF|

|EGGEFF|

|GGFFFF|

你有H點生命值，請你在貿然行動之前先判斷是否能夠活着（生命值大於0）穿越結界拿到寶藏，如果能夠，請求出最大的生命值。

輸入格式

第1行 三個非負整數 N P H。N爲結界的邊長，P爲不同的能量結界的數量，H爲你的生命值。

第2-P+1行 每行一個非負整數，表示走到該種能量結界受到的傷害值。

第P+2至第P+2+N行 每行N個正整數，爲地圖上該單元格的能量種類的編號，編號爲1..P。

輸出格式

如果你能夠穿越結界到達對岸的寶藏，輸出最多剩餘的生命值。如果不能穿越，輸出NO。

樣例輸入

6 7 10

3

1

2

2

1

1

3

1 1 1 2 2 3

1 2 3 3 3 3

1 1 2 2 4 4

5 5 5 5 5 6

5 7 7 5 6 6

7 7 6 6 6 6

樣例輸出

7

樣例說明

路綫爲

起始-2-5-6-目標

1 1 1 2 2 3

1 2 3 3 3 3

1 1 2 2 4 4

5 5 5 5 5 6

5 7 7 5 6 6

7 7 6 6 6 6

數據規模

對於40%數據

4<=N<=10

對於100%數據

4<=N<=50

1<=P<=N*N

0<=H<=200000000

【分析】
搜索+最短路，把每個結界縮成一個點，通過搜索找出與每個結界相鄰接的結界，就這樣構圖就行了。然後用Dijkstra等O(N^2)算法求最短路即可。
【我的代碼】
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN=2505;
const int MAX=0x7fffffff;
int Mat[MAXN][MAXN];
int Val[MAXN][MAXN];
int Abut[MAXN]={0};
bool used[MAXN][MAXN];
bool flag[MAXN]={false};
int dist[MAXN];
int Map[62][62];
int step[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

int N,P,H,E;
int Magic[62];

void init()
{
    scanf("%d %d %d",&N,&P,&H);
   
    E=P+1;
   
    for (int i=1;i<=P;i++)
        scanf("%d",&Magic[i]);
   
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            scanf("%d",&Map[i][j]);
   
    for (int i=1;i<=P;i++)
        for(int j=1;j<=P;j++)
            used[i][j]=false;
       
    bool used[MAXN];
    memset(used,false,sizeof(used));
    for (int i=1;i<=N;i++)
        used[Map[1][i]]=true;
   
    for (int i=1;i<=P;i++)
    {
        if(used[i])
        {
            Abut[0]++;
            Mat[0][Abut[0]]=i;
            Val[0][Abut[0]]=Magic[i];
        }
    }
   
    memset(used,false,sizeof(used));
    for (int i=1;i<=N;i++)
        used[Map[N][i]]=true;
   
    for (int i=1;i<=P;i++)
    {
        if(used[i])
        {
            Abut[i]++;
            Mat[i][Abut[i]]=E;
            Val[i][Abut[i]]=0;
        }
    }
   
    return;
}

void CreatGraph()
{
    int nx,ny;
    int nc;
    for (int k=1;k<=P;k++)
    {
        for (int i=1;i<=N;i++)
        {
            for (int j=1;j<=N;j++)
            {
                if(Map[i][j]!=k)
                    continue;
                for (int m=0;m<4;m++)
                {
                    nx=i+step[m][0];
                    ny=j+step[m][1];
                    if(nx<1 || nx>N || ny<1 || ny>N)
                        continue;
                    nc=Map[nx][ny];
                    if(nc!=k && !used[k][nc] && nc!=-1)
                    {
                        Abut[k]++;
                        Mat[k][Abut[k]]=nc;
                        Val[k][Abut[k]]=Magic[nc];
                        used[k][nc]=true;
                       
                        Abut[nc]++;
                        Mat[nc][Abut[nc]]=k;
                        Val[nc][Abut[nc]]=Magic[k];
                        used[nc][k]=true;
                    }
                }
                Map[i][j]=-1;
            }
        }
    }
}

void Dijkstra(int S)
{
    for (int i=0;i<=E;i++)
    {
        dist[i]=MAX;
        flag[i]=false;
    }
    for(int i=1;i<=Abut[S];i++)
    {
        dist[Mat[S][i]]=Val[S][i];
    }
    dist[S]=0;
    flag[S]=1;
   
    for(int i=0;i<=E;i++)
    {
        int tmp=MAX;
        int u=S;
        for (int j=0;j<=E;j++)
        {
            if(!flag[j] && dist[j]<tmp)
            {
                u=j;
                tmp=dist[j];
            }
        }
        flag[u]=1;
       
        for (int j=0;j<=Abut[u];j++)
        {
            if(!flag[Mat[u][j]])
            {
                int newdist=dist[u]+Val[u][j];
                if(newdist<dist[Mat[u][j]])
                {
                    dist[Mat[u][j]]=newdist;
                }
            }
        }
    }
}

int main()
{
    freopen("eldrethalas.in","r",stdin);
    freopen("eldrethalas.out","w",stdout);
    init();
    CreatGraph();
    Dijkstra(0);
    int res=dist[E];
    if(res<H)
    {
        res=H-res;
        printf("%d\n",res);
    }
    else
        printf("NO\n");
    return 0;
}

【評測結果】
正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	55463 KB	0
2	正确	10	0.091 s	55463 KB	0
3	正确	10	0.000 s	55463 KB	0
4	正确	10	0.000 s	55463 KB	0
5	正确	10	0.001 s	55463 KB	0
6	正确	10	0.001 s	55463 KB	0
7	正确	10	0.019 s	55463 KB	0
8	正确	10	0.065 s	55463 KB	0
9	正确	10	0.080 s	55463 KB	0
10	正确	10	0.080 s	55463 KB	0

运行完成
运行时间 0.338 s
平均内存使用 55463 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!