Yeefan's Blog

Dijkstra with STL priority_queue 優先隊列

2012-03-16T13:30:00.000+08:00

Dijkstra算法是一個經典的求單源最短路的算法，經過堆優化的Dijkstra算法有着良好的性能，雖然Heap的代碼複雜度並不算很高，但是至少也會爲程序的調試帶來一些麻煩。現在C++ STL開放了，所以可以用STL中的PQ容器（優先級隊列）來實現堆。

例題：

【題目描述】

在某個遙遠的國家裏，有n個城市。編號爲1，2，3，……，n。

這個國家的政府修建了m條雙向的公路。每條公路連接着兩個城市。沿着某條公路，開車從一個城市到另一個城市，需要花費一定的汽油。

開車每經過一個城市，都會被收取一定的費用（包括起點和終點城市）。所有的收費站都在城市中，在城市間的公路上沒有任何的收費站。

小紅現在要開車從城市u到城市v(1<=u，v<=n)。她的車最多可以裝下s升的汽油。在出發的時候，車的油箱是滿的，並且她在路上不想加油。

在路上，每經過一個城市，她要交一定的費用。如果她某次交的費用比較多，她的心情就會變得很糟。所以她想知道，在她能到達目的地的前提下，她交的費用中最多的一次最少是多少。這個問題對於她來說太難了，於是她找到了聰明的你，你能幫幫她嗎？

【輸入格式】

第一行5個正整數，n，m，u，v，s。分別表示有n個城市，m條公路，從城市u到城市v，車的油箱的容量爲s升。

接下來有n行，每行1個正整數，fi。表示經過城市i，需要交費fi元。

再接下來有m行，每行3個正整數，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之間有一條公路，如果從城市ai到城市bi，或者從城市bi到城市ai，需要用ci升汽油。

【輸出格式】

僅一個整數，表示小紅交費最多的一次的最小值。

如果她無法到達城市v，輸出-1。

【輸入樣例1】

4 4 2 3 8

8

5

6

10

2 1 2

2 4 1

1 3 4

3 4 3

【輸出樣例1】

8

【輸入樣例2】

4 4 2 3 3

8

5

6

10

2 1 2

2 4 1

1 3 4

3 4 3

【輸出樣例2】

-1

【數據規模】

對於60%的數據，滿足n<=200，m<=10000，s<=200

對於100%的數據，滿足n<=10000，m<=50000，s<=1000000000

對於100%的數據，滿足ci<=1000000000，fi<=1000000000，可能有兩條邊連接着相同的城市。

[分析]

這道題是道判定類題目，算法是二分答案+單源最短路。

由於數據很大，二分N+SPFA會超時1組，所以考慮Dijkstra+Heap。

[我的代碼]

C++语言: Codee#25838

/*

*Problem: NOIP模擬題 收費站

*Author: YeefanZhu

*Website: www.yeefanblog.tk

*GTalk: zyfworks@gmail.com

*/

#include <cstdio>

#include <vector>

#include <cstdlib>

#include <algorithm>

#include <queue>

using namespace std;

const int MAXN=10001;

const int INF=1100000000;

int Cost[MAXN],BS[MAXN];

int N,M,S,B,E;

vector<int> Map[MAXN];

vector<int>Val[MAXN];



inline void init()

{

    scanf("%d %d %d %d %d\n",&N,&M,&B,&E,&S);

    for(int i=1;i<=N;i++)

    {

        scanf("%d\n",&Cost[i]);

        BS[i]=Cost[i];

    }

    sort(BS+1,BS+N+1);

    int a,b,v;

    for(int i=1;i<=M;i++)

    {

        scanf("%d %d %d\n",&a,&b,&v);

        Map[a].push_back(b);

        Map[b].push_back(a);

        Val[a].push_back(v);

        Val[b].push_back(v);

    }

}



priority_queue<pair<int,int> > PQ;

int Used[MAXN];

int Dist[MAXN];



inline bool SP(int x)

045

{

    if(Cost[B]>x) return false;

    for(int i=1;i<=N;i++) {Used[i]=0,Dist[i]=INF;}

    Dist[B]=0;

    PQ.push(make_pair(0,B));

    int u,v,cost;

    while(!PQ.empty())

    {

        u=PQ.top().second;

        PQ.pop();

        if(!Used[u])

        {

            Used[u]=1;

            for(unsigned int i=0;i<Map[u].size();i++)

            {

                v=Map[u][i];

                cost=Val[u][i];

                if(Cost[v]>x) continue;

                if(!Used[v]&&Dist[v]-Dist[u]>cost)

                {

                    Dist[v]=Dist[u]+cost;

                    PQ.push(make_pair(-Dist[v],v));

                }

            }

        }

    }

    if(Dist[E]>S) return false;

    return true;

}



inline void solve()

{

    int L=1,R=N;

    int Mid;

    if(!SP(BS[N])) {printf("-1\n");return;}

    int Ans;

    bool flag;

    while(L<=R)

    {

        Mid=(L+R)>>1;

        flag=SP(BS[Mid]);

        if(flag)

        {

            Ans=BS[Mid];

            R=Mid-1;

        }

        else L=Mid+1;

    }

    printf("%d\n",Ans);

}



int main()

{

    freopen("cost.in","r",stdin);

    freopen("cost.out","w",stdout);

    init();

    solve();

    return 0;

}

【轉載】淺談2—SAT問題

2012-03-06T11:18:00.000+08:00

2-SAT：http://www.cppblog.com/ACflying/archive/2009/06/06/86912.html

1 2 - SAT就是2判定性問題，是一種特殊的邏輯判定問題。
2 2 - SAT問題有何特殊性？該如何求解？
3 我們從一道例題來認識2 - SAT問題，並提出對一類2 - SAT問題通用的解法。

Poi 0106 Peaceful Commission [和平委員會]：

某國有n個黨派，每個黨派在議會中恰有2個代表。
現在要成立和平委員會，該會滿足：
每個黨派在和平委員會中有且只有一個代表
如果某兩個代表不和，則他們不能都屬於委員會
代表的編號從1到2n，編號為2a - 1 、2a的代表屬於第a個黨派

輸入n（黨派數），m（不友好對數）及m對兩兩不和的代表編號
其中1≤n≤ 8000 ， 0 ≤m ≤ 20000

求和平委員會是否能創立。若能，求一種構成方式。
輸入：輸出：3 2 1 1 3 4 2 4 5

原題可描述為：

有n個組，第i個組裡有兩個節點Ai, Ai ' 。需要從每個組中選出一個。而某些點不可以同時選出（稱之為不相容）。任務是保證選出的n個點都能兩兩相容。
（在這裡把Ai, Ai ' 的定義稍稍放寬一些，它們同時表示屬於同一個組的兩個節點。也就是說，如果我們描述Ai，那麼描述這個組的另一個節點就可以用Ai ' ）

初步構圖
如果Ai與Aj不相容，那麼如果選擇了Ai，必須選擇Aj‘ ；同樣，如果選擇了Aj，就必須選擇Ai’ 。 Ai Aj '
Aj Ai‘
這樣的兩條邊對稱

我們從一個例子來看：
假設4個組，不和的代表為：1和4，2和3，7和3，那麼構圖：
假設：首先選1 3必須選，2不可選 8必須選， 4 、7不可選 5 、6可以任選一個

矛盾的情況為：
存在Ai，使得Ai既必須被選又不可選。

得到演算法1：
枚舉每一對尚未確定的Ai, Ai‘ ，任選1個，推導出相關的組，若不矛盾，則可選擇；否則選另1個，同樣推導。若矛盾，問題必定無解。
此演算法正確性簡要說明：
由於Ai,Ai ' 都是尚未確定的，它們不與之前的組相關聯，前面的選擇不會影響Ai, Ai ' 。
演算法的時間複雜度在最壞的情況下為O(nm)。
在這個演算法中，並沒有很好的利用圖中邊的對稱性

更一般的說：
在每個一個環裡，任意一個點的選擇代表將要選擇此環裡的每一個點。不妨把環收縮成一個子節點（規定這樣的環是極大強連通子圖）。新節點的選擇表示選擇這個節點所對應的環中的每一個節點.對於原圖中的每條邊Ai -> Aj（設Ai屬於環Si，Aj屬於環Sj）如果Si≠Sj，則在新圖中連邊:Si -> Sj

這樣構造出一個新的有向無環圖。此圖與原圖等價。

通過求強連通分量，可以把圖轉換成新的有向無環圖，在這個基礎上，介紹一個新的演算法。

新演算法中，如果存在一對Ai, Ai ' 屬於同一個環，則判無解，否則將採用拓撲排序，以自底向上的順序進行推導，一定能找到可行解。

至於這個演算法的得來及正確性，將在下一段文字中進行詳細分析。
回憶構圖的過程：
對於兩個不相容的點 Ai, Aj，構圖方式為：Ai -> Aj ' ,Aj->Ai ' ,前面提到過，這樣的兩條邊對稱，也就是說：
如果存在Ai -> Aj，必定存在Aj ' ->Ai ' 。
等價於：Ai -> Ak,Ak ' ->Ai ' 方便起見，之後“ -> ”代表這樣一種傳遞關係.

猜測1：圖中的環分別對稱
如果存在Ai,Aj，Ai,Aj屬於同一個環(記作Si),那麼Ai ' , Aj ' 也必定屬於一個環(記作Si ' ).
再根據前面的引理，不難推斷出每個環分別對稱。

證明方式與引理相類似
一個稍稍複雜點的結構,其中紅、藍色部分分別為兩組對稱的鏈結構
推廣2：對於任意一對Si, Si ' ，Si的後代節點與Si ' 的前代節點相互對稱。
繼而提出:
猜測2：若問題無解，則必然存在Ai, Ai ' ，使得Ai,Ai ' 屬於同一個環。也就是，如果每一對Ai,Ai ' 都不屬於同一個環，問題必定有解。下面給出簡略證明：

先提出一個跟演算法1相似的步驟：
如果選擇Si，那麼對於所有Si -> Sj，Sj都必須被選擇。
而Si ' 必定不可選，這樣Si’的所有前代節點也必定不可選（將這一過程稱之為刪除）。
由推廣2可以得到，這樣的刪除不會導致矛盾。

假設選擇S3 '
?選擇S3 ' 的後代節點, S1 '
?刪除S3
?刪除S3的前代節點S1
S1與S1 ' 是對稱的

每次找到一個未被確定的Si，使得不存在Si -> Si ' 選擇Si及其後代節點而刪除Si’及Si‘的前代節點。一定可以構造出一組可行解。
因此猜測2成立。

另外，若每次盲目的去找一個未被確定的Si，時間複雜度相當高。
以自底向上的順序進行選擇、刪除，這樣還可以免去“選擇Si的後代節點”這一步。
用拓撲排序實現自底向上的順序。

一組可能的拓撲序列(自底向上）:S1 ' ,S2,S2 ' ,S3 ' ,S3,S1

演算法2的流程：
1 ．構圖 2 ．求圖的極大強連通子圖 3 ．把每個子圖收縮成單個節點，根據原圖關係構造一個有向無環圖 4 ．判斷是否有解，無解則輸出（退出） 5 ．對新圖進行拓撲排序 6 ．自底向上進行選擇、刪除 7 ．輸出

小結：
整個演算法的時間複雜度大概是O(m)，解決此問題可以說是相當有效了。
在整個演算法的構造、證明中反覆提到了一個詞：對稱。發現、利用了這個圖的特殊性質，我們才能夠很好的解決問題。
並且，由2 - SAT問題模型變換出的類似的題目都可以用上述方法解決。

全文總結：
充分挖掘圖的性質，能夠更好的解決問題。
不僅僅是對於圖論，這種思想可以在很多問題中得到很好的應用。
希望我們能掌握此種解題的思想，在熟練基礎演算法的同時深入分析、靈活運用、大膽創新，從而解決更多更新的難題。

USACO Feb12 Bronze Rope Folding 折繩子題解

2012-03-03T11:12:00.003+08:00

USACO 2012 February Contest, Bronze Division

Problem 1. Rope Folding

Problem 1: Rope Folding [Brian Dean, 2012]
Farmer John has a long rope of length L (1 <= L <= 10,000) that he uses for various tasks around his farm. The rope has N knots tied into it at various distinct locations (1 <= N <= 100), including one knot at each of its two endpoints.

FJ notices that there are certain locations at which he can fold the rope back on itself such that the knots on opposite strands all line up exactly with each-other:

Please help FJ count the number of folding points having this property. Folding exactly at a knot is allowed, except folding at one of the endpoints is not allowed, and extra knots on the longer side of a fold are not a problem (that is, knots only need to line up in the areas where there are two strands opposite each-other). FJ only considers making a single fold at a time; he fortunately never makes multiple folds.

PROBLEM NAME: folding
INPUT FORMAT:
* Line 1: Two space-separated integers, N and L.
* Lines 2..1+N: Each line contains an integer in the range 0...L specifying the location of a single knot. Two of these lines will always be 0 and L.

SAMPLE INPUT (file folding.in):
5
10
0
10
6
2
4
INPUT DETAILS:
The rope has length L=10, and there are 5 knots at positions 0, 2, 4, 6, and 10.

OUTPUT FORMAT:
* Line 1: The number of valid folding positions.

SAMPLE OUTPUT (file folding.out):
4
OUTPUT DETAILS:
The valid folding positions are 1, 2, 3, and 8.

【分析】
由題意可知，滿足要求的點只能在一個節上或者在兩個節的正中間，所以依次枚舉即可。

【我的代碼】
裸代碼RawCode

C++语言: Codee#25718

/*

*PROB: folding

*LANG: C++

*ID: yeefan

*/

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

using namespace std;



int N,L;

int Rope[101];



int Abs(int x)

{

    return x>=0?x:-x;

}



void init()

{

    scanf("%d %d\n",&N,&L);

    for(int i=1;i<=N;i++)

        scanf("%d\n",&Rope[i]);

    sort(Rope+1,Rope+N+1);

}



void solve()

{

    int Ans=0;

    for(int i=2;i<=N-1;i++)

    {

        int head=i-1,tail=i+1;

        bool flag=true;

        while(head>=1 && tail<=N)

        {

            if(Rope[head]+Rope[tail]!=2*Rope[i])

            {

                flag=false;

                break;

            }

            head--;

            tail++;

        }

        if(flag)

            Ans++; 

    }

    

    for(int i=1;i<=N-1;i++)

    {

        int ca=Rope[i],cb=Rope[i+1];

        

        int head=i,tail=i+1;

        bool flag=true;

        while(head>=1 && tail<=N)

        {

            if(Rope[head]+Rope[tail]!=ca+cb)

            {

                flag=false;

                break;

            }

            head--;

            tail++;

        }

        if(flag)

                Ans++;

    }

    printf("%d\n",Ans);

}



int main()

{

    freopen("folding.in","r",stdin);

    freopen("folding.out","w",stdout);

    init();

    solve();

    return 0;

}

並查集練習題島國 jx 題解

2012-02-28T00:52:00.001+08:00

【題目描述】
很久很久很久很久很久很久以前......

有一個島國。

這個國家的領地是一塊座標從(1,1)到(K,K)的正方形（包括領海和領陸，座標(x,y)是指(x,y)這塊土地，並非一個點）

衛星資訊會告訴你這個國家的土地情況，希望你能根據給出的資訊計算出這個國家有多少個島。

衛星給出的資訊形如x1 y1 x2 y2，表示左下角座標為x1,y1,右上角座標為x2,y2的這一個矩形區域是陸地

輸入格式：

第一行一個整數n，表示衛星會傳送給你n條資訊

下面n行每行有4個整數，x1,y1,x2,y2，含義如上

輸出格式：

第一行，一個整數Sum，表示這個國家的島的數量

注，只有一個公共點的兩塊陸地不算是一塊區域，具體如樣例

樣例輸入：

1 1 2 2

1 3 1 3

3 3 4 5

樣例輸出：

樣例解釋：

0 0 1 1 0

1 0 1 1 0

1 1 0 0 0

（1是陸地，0是海）

資料規模：

對於30%的資料，K<=1000，n<=100

對於100%的資料，K<=20000，n<=5000，x1<=x2，y1<=y2，1<=x1,x2,y1,y2<=K

by pom

【分析】

先緩存每個矩形的兩個點的坐標，然後弄個O(N^2)的枚舉，枚舉任意兩個矩形是否同屬一個島嶼，如果是，則Merge Them，這就用到並查集了。

最後，判斷有幾個獨立的集合集合。

PS。我差點把這題寫成“矩形分割”一類的了～ORZ～

【我的代碼】

裸代碼RawCode

C++语言: Codee#25690

/*

*Problem: 島國

*Author: Yee-fan Zhu

*Thanks: KingFree

*Website: zhuyf.tk

*/

#include <cstdio>

#include <cstdlib>

using namespace std;

const int MAXN=5002;

int UFS[MAXN];

int N;

int Flag[MAXN];

class Point

{public: int x1,x2,y1,y2;}P[MAXN];



int UFS_Find(int x)

{

    int t,p; p=x;

    while(UFS[p]!=p) p=UFS[p];

    while(UFS[x]!=x)

    {t=UFS[x]; UFS[x]=p;x=t;}

    return p;

}



bool UFS_Check(int a,int b)

{ return (UFS_Find(a)==UFS_Find(b)); }



void UFS_Merge(int a,int b)

{ UFS[UFS_Find(b)]=UFS_Find(a); }



void init()

{

    scanf("%d\n",&N);

    for(int i=1;i<=N;i++)

        scanf("%d %d %d %d\n",&P[i].x1,&P[i].y1,&P[i].x2,&P[i].y2);

    for(int i=1;i<=N;i++)

        UFS[i]=i,Flag[i]=0;

}



void solve()

{

    for(int i=1;i<=N;i++)

    {

        for(int j=i+1;j<=N;j++)

        {

            if(UFS_Check(i,j)) continue;

            /*四邊相離*/

            if(P[i].x1>P[j].x2+1) continue;

            if(P[i].x2<P[j].x1-1) continue;

            if(P[i].y1>P[j].y2+1) continue;

            if(P[i].y2<P[j].y1-1) continue;

            /*四角相接*/

            if(P[i].x1==P[j].x2+1 && P[i].y2+1==P[j].y1) continue;

            if(P[i].x1==P[j].x2+1 && P[i].y1-1==P[j].y2) continue; 

            if(P[i].x2+1==P[j].x1 && P[i].y2+1==P[j].y1) continue;

            if(P[i].x2+1==P[j].x1 && P[i].y1-1==P[j].y2) continue;

            UFS_Merge(i,j);

        }

    }

    int Ans=0;

    for(int i=1;i<=N;i++)

    {

        if(Flag[UFS_Find(i)]==0)

        {

            Ans++;

            Flag[UFS_Find(i)]=1;

        }

    }

    printf("%d\n",Ans);

}



int main()

{

    freopen("jx.in","r",stdin);

    freopen("jx.out","w",stdout);

    init();

    solve();

    return 0;

}

OI練習題式子 recursion

2012-02-27T16:24:00.000+08:00

【問題描述】

動態規劃 DP 的實現形式之一是遞推，因此遞推在 oi 中十分重要。在某資訊學的分支學科中， LC 學會瞭如何求一階線性遞推數列。由於他現在正在學習主幹學科，因此希望知道求出 N 階線性遞推數列。為此，他瞭解到了以下的內容：

一個 N 階線性遞推式是這樣的式子：

也就是說，這個數列的每一項都是由他之前連續 N 項加權相加所得。其中還包括一個常數 an 。

例如，當 N=2 ， a0=a1=1 ， a2=0 時，這個式子就是我們熟悉的斐波那契數列。當然，作為這界條件， f0 、 f1…f n-1 都是已知的。

LC 對這如何去求這個式子一籌莫展，因此請你來幫助他。你的任務就是對於一個給定的 N 階線性遞推式，求出它的第 K 項是多少。

【輸入文件】

第一行兩個整數： N ， K ，其中 N 表示這個式子是 N 階線性遞推式， K 表示你需要求得那一項。

第二行有 N+1 個整數： A0,A1,… ， An ，表示這個遞推式的係數。

第三行有 N 個整數： F0 ， F1 ， …. ， Fn-1 ，表示數列的初始值。

【輸出文件】

只有一行，其中只有一個整數，表示這個數列第 K 項的值。由於資料較大，你只需輸出結果 mod 9973 的值。

【樣例輸入】

2 10

1 1 0

0 1

【樣例輸出】

【資料範圍】

對於 50% 的資料： N<=K<=10^6

對於 100% 的資料：

1<N<10

N<=K<=101^8

1<=Ai ， Fi<=10^4

【提示】

矩陣(Matrix)是一個n*m（n行m列）的數組。例如[0 1]就是一個1*2的矩陣。

矩陣乘法這樣定義：

如果A是n*m的矩陣，B是m*t的矩陣，設矩陣C=A*B，則Cij=∑Aik*Bkj，其中C是一個n*t的矩陣。

例如，對於斐波那契數可以列出這個遞推公式：

矩陣乘法滿足結合率，但不滿足交換率

【分析】

矩陣乘法。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25687

#include <cstdio>

#include <cstdlib>

#include <iostream>

using namespace std;

const int MOD=9973;

const int MAXN=12;

class Matrix

{

public:

    int m[MAXN][MAXN];

};

Matrix A,B;



unsigned long long  N,K;

void init()

{

    scanf("%d",&N);

    cin>>K;

    for(int i=2;i<=N;i++) A.m[i][i-1]=1;

    int x;

    for(int i=1;i<=N+1;i++)

    {

        scanf("%d",&x);

        A.m[i][N]=x;

    }

    A.m[N+1][N+1]=1;

}



Matrix multiply(Matrix M,Matrix P)

{

    Matrix T;

    for(int i=1;i<=N+1;i++)

        for(int j=1;j<=N+1;j++)

                T.m[i][j]=0;

    for(int i=1;i<=N+1;i++)

        for(int j=1;j<=N+1;j++)

            for(int k=1;k<=N+1;k++)

                T.m[i][j]=(T.m[i][j]+M.m[i][k]*P.m[k][j])%MOD;

    return T;

}



Matrix pow(unsigned long long k)

{

    Matrix T;

    if(k==1) {return A;}

    T=pow(k/2);

    T=multiply(T,T);

    if(k%2==1) {T=multiply(T,A);}

    return T;

}



int main()

{

    freopen("recursion.in","r",stdin);

    freopen("recursion.out","w",stdout);

    init();

    B=pow(K);

    int Ans=B.m[N+1][1];

    int x;

    for(int i=1;i<=N;i++)

    {

        scanf("%d\n",&x);

        Ans=(Ans+B.m[i][1]*x)%MOD;

    }

    printf("%d\n",Ans%MOD);

    return 0;

}

ACM/ICPC 小球鐘——時間與運動

2012-02-27T16:21:00.003+08:00

問題描述

時間是運動的一種方式，所以常常用運動來度量時間。如圖所示的小球鍾就是一個通過不斷在軌道上移動小球來度量時間的簡單設備。

每分鐘，一個轉動臂將一個小球從小球隊列的底部擠走，將它上升到鐘的頂部並安置在一個表示分鐘， 5 分鐘和小時的軌道上。這裡可以顯示從 1:00 到 12:59 範圍內的時間，但無法表示 “a.m.” 和 “p.m.” 。若有 2 個球在分鐘軌道， 6 個球在 5 分鐘軌道及 5 個球在小時軌道上，就顯示時間 5:32 。

不幸的是，大多數市場上提供的小球鍾無法顯示日期，儘管只需要簡單地加上一些軌道就可以了。當小球通過鐘的機械裝置被移動後，它們就會改變其初始次序。仔細研究它們隨著時間的流逝發生的次序的改變，可以發現相同的次序會不斷出現。由於小球的初始次序最後遲早會被重複，所以這段時間的長短是可以被度量的，這完全取決於所提供小球的總數。

每分鐘，最近最少使用的那個小球從位於球鍾底部的小球隊列被移走，並將上升安置於顯示分鐘的軌道上，這裡可以放置 4 個小球。當第 5 個小球滾入該軌道，它們的重量使得軌道傾斜，原先在軌道上的 4 個小球按照與它們原先滾入軌道相反加入到鍾底部的小球隊列。引起傾斜的第 5 個小球滾入顯示 5 分鐘的軌道，該軌道可以放置 11 個球。當第 12 個小球滾入該軌道，它們的重量使得軌道傾斜，原先 11 個小球同樣以相反的次序加入鍾底部的小球隊列。而這第 12 個小球滾入了顯示小時的軌道。該軌道同樣可以放置 11 個球，但這裡有一個外加的固定不能被移動的小球，這樣小時的值域就變為 1 到 12 。從 5 分鐘軌道滾入的第 12 個小球將使小時軌道傾斜，這 11 個球同樣以相反的次序加入鍾底部的小球隊列，然後第 12 個小球同樣加入鍾底部的小球隊列。

輸入小球的個數，輸出該時鐘在經過多少天的運行可以回到它的初始小球序列。例如有 45 個小球的鐘經過 378 天會回到初始狀態。

【輸入格式】

輸入文件只有一行,有一個整數n,表示小球的個數.

【輸出格式】

輸出文件也只有一行,有一個整數m,表示小球鍾回到初始狀態的天數.

【輸入輸出樣例】

輸入文件名： xqz.in

輸出文件名： xqz.out

378

【分析】

詳見劉汝佳的黑書。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25686

#include <cstdio>

#include <cstdlib>

#include <deque> 

using namespace std;

const int MAXN=720;

typedef deque<int> Deque;

Deque Minute;

Deque Five;

Deque Hour;

Deque Bot;

int N;

int M=0;



bool check()

{

    for(int i=0;i<N;i++)

    {

        if(Bot[i]!=i+1)

            return false;

    }

    return true;    

}



void Into3()

{

    int tmp;

    int tmp2;

    tmp2=Hour.back();

    Hour.pop_back();

    for(int i=1;i<=11;i++) 

    {

        tmp=Hour.back();

        Hour.pop_back();

        Bot.push_back(tmp);

    }

    Bot.push_back(tmp2); 

}



void Into2()

{

    int tmp;

    tmp=Five.back();

    Five.pop_back();

    Hour.push_back(tmp);

    for(int i=1;i<=11;i++)

    {

        tmp=Five.back();

        Five.pop_back();

        Bot.push_back(tmp);

    }

}



void Into1()

{

    int tmp;

    tmp=Minute.back();

    Minute.pop_back();

    Five.push_back(tmp);

    for(int i=1;i<=4;i++)

    {

        tmp=Minute.back();

        Minute.pop_back();

        Bot.push_back(tmp);

    }

}



void work()

{

    bool flag=false;

    while(!flag)

    {

        M++; 

        int tmp;

        for(int a=1;a<=12;a++)

        {

            for(int b=1;b<=12;b++)

            {

                for(int c=1;c<=5;c++)

                {

                    tmp=Bot.front(); 

                    Bot.pop_front();

                    Minute.push_back(tmp);

                }

                Into1();

            }

            Into2();

        } 

        Into3();

        flag=check();

    }

    printf("%d\n",(M+1)/2);

}



int main()

{

    freopen("xqz.in","r",stdin);

    freopen("xqz.out","w",stdout);

    scanf("%d\n",&N);

    for(int i=1;i<=N;i++) Bot.push_back(i);    

    work();

    return 0;

}

圖論練習題備用交換機 gd 題解

2012-02-27T16:19:00.002+08:00

問題描述

n個城市之間有通訊網絡，每個城市都有通訊交換機，直接或間接與其它城市連接。因電子設備容易損壞，需給通訊點配備備用交換機。但備用交換機數量有限，不能全部配備，只能給部分重要城市配置。於是規定：如果某個城市由於交換機損壞，不僅本城市通訊中斷，還造成其它城市通訊中斷，則配備備用交換機。請你根據城市線路情況，計算需配備備用交換機的城市個數，及需配備備用交換機城市的編號。

【輸入格式】

輸入文件有若干行

第一行，一個整數n，表示共有n個城市(2<=n<=100)

下面有若干行,每行2個數a、b，a、b是城市編號，表示a與b之間有直接通訊線路。

【輸出格式】

輸出文件有若干行

第一行，1個整數m，表示需m個備用交換機，下面有m行，每行有一個整數，表示需配備交換機的城市編號，輸出順序按編號由小到大。如果沒有城市需配備備用交換機則輸出0。

【輸入輸出樣例】

輸入文件名： gd.in

1 2

2 3

2 4

3 4

4 5

4 6

4 7

5 6

6 7

輸出文件名：gd.out

【分析】

裸求割頂。DFS。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25685

/*

*Problem: 備用交換機

*Author: Yee-fan Zhu

*GTalk: zyfworks@gmail.com

*/

#include <cstdlib>

#include <cstdio>

#include <set>

#include <vector>

#include <algorithm>

using namespace std;

const int MAXN=101;

typedef vector<int> Vec;

int N;

Vec Map[MAXN];

int Ancestor[MAXN];

int Deep[MAXN];

int Parent[MAXN];

int total=0;

void init()

{

    scanf("%d\n",&N);

    int a,b;

    while(scanf("%d %d\n",&a,&b)==2)

    {

        Map[a].push_back(b);

        Map[b].push_back(a);

    }

}



int Min(int a,int b)

{

    return a<b?a:b;

}



void dfs(int now,int pnt)

{

    int tot=0;

    Parent[now]=pnt;

    Deep[now]=Ancestor[now]=++total;

    int nxt;

    for(unsigned int i=0;i<Map[now].size();i++)

    {

        nxt=Map[now][i];

        if(Deep[nxt]==0)

        {

            tot++;

            dfs(nxt,now);

            Ancestor[now]=Min(Ancestor[now],Ancestor[nxt]);

        }

        else

        {

            if(nxt!=pnt)

            {

                Ancestor[now]=Min(Ancestor[now],Deep[nxt]);

            }

        }

    }

}



int main()

{

    freopen("gd.in","r",stdin);

    freopen("gd.out","w",stdout);

    init();

    /*

    * 将刘汝佳黑书上的Root节点设为1号节点

    *详见《算法艺术与信息学竞赛》第285页

    */

    dfs(1,0);

    int tmp;

    set<int> Res;

    int Tmp=0;

    for(int i=2;i<=N;i++)

    {

        tmp=Parent[i];

        if(tmp==1)

            Tmp++;  

        else if(Ancestor[i]>=Deep[tmp] && tmp!=0)

            Res.insert(tmp);

    }

    if(Tmp>1)

    {

        /*

        *当根有数量>1的儿子时，根是图的割顶

        *详见 《算法艺术与信息学竞赛》第286页

        */

        Res.insert(1);

    }

    printf("%d\n",Res.size());

    for(set<int>::iterator iter=Res.begin();iter!=Res.end();iter++)

        printf("%d\n",*iter);

    return 0;

}

OI練習題溶液模擬器 simulator

2012-02-27T16:16:00.003+08:00

小 Y 太失敗了，他雖然在化學實驗課上拿來了很多溶液，但是還是沒有辦法配成想要的溶液，萬一倒錯了就沒有辦法挽回了，小 Y 遲遲不敢下手。

於是小 Y 到網上下載了一個溶液配置模擬器。溶液配置模擬器是這樣的程序：模擬器在電腦中構造一種虛擬溶液，然後你可以虛擬地向當前虛擬溶液中加入一定濃度一定質量的這種溶液，模擬器會快速地算出倒入後虛擬溶液的濃度和質量。當然，計算機最可愛的地方就是當你倒錯了可以撤銷。

模擬器的使用步驟是這樣的：

1. 為模擬器設置一個初始質量和濃度 V0 ， C0% （ 0 ≤ C0≤100 ）。

2. 進行一系列操作，模擬器支持兩種操作：

P(v,c) 操作：表示向當前的虛擬溶液中加入質量為 v 濃度為 c 的溶液；

Z 操作：撤銷上一步 P 操作。

但是，小 Y 不小心把模擬器弄丟了……，眼看考試迫在眉睫，小 Y 只能依靠你了。

輸入格式：

第一行，兩個整數 V0 ， C0 。

第二行，一個整數 n ，表示操作數（ n ≤ 10000 ）。

接下來 n 行，每行一條操作，格式為：

P v c 或 Z 。

之間用一個空格隔開，當只剩初始溶液的時候，再撤銷就沒有用了。

任意時刻質量不會超過 2 31 -1 。

輸出格式：

n 行，每行兩個數 V i ， C i , 其中 V i 為整數， C i 為實數（保留 5 位小數），之間用一個空格隔開。其中，第 i 行表示第 i 次操作以後的溶液質量和濃度。

輸入樣例：

100 100

P 100 0

輸出樣例：

200 50.00000

100 100.00000

【分析】

純模擬。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25684

#include <cstdio>

#include <cstdlib>

using namespace std;

const int MAXN=10002; 

double V[MAXN],C[MAXN];

int Top=0;



void init() 

{

    double v,c;

    scanf("%lf %lf\n",&v,&c);  

    Top++;

    V[Top]=v;

    C[Top]=c;

    return;

}



void Dis()

{

    if(Top==1)

    {

        printf("%.0lf %.5lf\n",V[1],C[1]);

        return;

    }

    Top--;

    printf("%.0lf %.5lf\n",V[Top],C[Top]);

    return;

}



void Add(double v,double c)

{

    Top++;

    V[Top]=V[Top-1]+v;

    C[Top]=(V[Top-1]*C[Top-1]+v*c)/V[Top];

    printf("%.0lf %.5lf\n",V[Top],C[Top]);

    return;

}



int main()

{

    freopen("simulator.in","r",stdin);

    freopen("simulator.out","w",stdout);

    init();

    int N;

    scanf("%d\n",&N);

    char ch; 

    double v,c;

    

    for(int i=1;i<=N;i++)

    {

        scanf("%c",&ch);

        while(ch==10 || ch==13)

            scanf("%c",&ch);

        if(ch=='Z')

        {

            Dis();

            continue;

        }    

        scanf("%lf %lf\n",&v,&c);

        Add(v,c);    

    }

    return 0;

}

圖論練習題圖的平方 ljb

2012-02-27T14:05:00.000+08:00

【問題描述】

有向圖G=(V,E)的平方是圖G^2=(V,E^2)，該圖滿足下列條件：(u,w)∈E^2當且僅當對v∈V，有(u, v)∈E，且(v,w)∈E。亦即，如果圖G中頂點u和w之間存在著一條恰包含兩條邊的路徑時，則G^2必包含該邊(u,w)。

請編程序對於給定的有向圖G，查詢邊(u,w)是否存在於平方圖G^2中。

【輸入文件】

第一行有兩個整數，v(1<=v<=100000)，m(1<=m<=1000)，其中v表示圖G的頂點個數，（頂點按1~v編號）；

接下來有m行，每行包含4個整數u1,u2,v1,v2，表示在圖G中，頂點區間[u1,u2]中的每一個頂點至頂點區間[v1,v2]中的每一個頂點都有邊相連；

接下來有一行，一個整數n（1<=n<=1000），表示查詢的個數；

接下來有n行，每一行有4個整數，x1,x2,y1,y2，表示一個詢問，即詢問在平方圖G^2中，其頂點區間[x1,x2]中的每一個頂點至頂點區間[y1,y2]中的每一個頂點是否都有邊。

【輸出文件】

對於每一個查詢，如果結果為“是”則輸出"Yes"，否則輸出"No"，如果有多個查詢，每個結果單獨佔一行。

【樣例輸入】

ljb.in

6 2

1 3 5 6

4 5 2 3

2 3 4 6

【樣例輸出】

ljb.out

注：圖G與G^2中的邊數均不會超過2000000.

【我的代碼】

裸代碼RawCode

C++语言: Codee#25683

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAXN=100001;

typedef vector<int> Vec;

Vec Map[MAXN];



int N,M;

void init()

{

    scanf("%d %d\n",&N,&M);

    int a,b,c,d;

    for(int i=1;i<=M;i++)

    {

        scanf("%d %d %d %d\n",&a,&b,&c,&d);

        for(int j=a;j<=b;j++)

        {

            for(int k=c;k<=d;k++)

            {

                Map[j].push_back(k);

            }

        }

    }

}



void solve()

{

    int V;

    scanf("%d\n",&V);

    int a,b,c,d;

    int flg[MAXN];

    for(int i=1;i<=V;i++)

    {

        scanf("%d %d %d %d\n",&a,&b,&c,&d);

        bool flag=true;

        int num;

        int nxt;

        for(int j=a;j<=b;j++)

        { 

            num=d-c+1;

            memset(flg,0,sizeof(flg));

            for(unsigned int k=0;num>0&&k<Map[j].size();k++)

            {

                nxt=Map[j][k];

                for(unsigned int l=0;num>0&&l<Map[nxt].size();l++)

                {

                    if(Map[nxt][l]>=c && Map[nxt][l]<=d)

                    {

                        if(!flg[Map[nxt][l]])

                        {

                            num--;

                            flg[Map[nxt][l]]=1;

                        }

                    }

                }

            }

            if(num!=0)

            {

                flag=0;

                break;

            }

        }

        if(flag)

            printf("Yes\n");

        if(!flag)

            printf("No\n");

    }

}



int main() 

{

    freopen("ljb.in","r",stdin);

    freopen("ljb.out","w",stdout);

    init();

    solve();

    return 0;

}

圖論練習題摔跤 rassle 題解

2012-02-27T14:02:00.001+08:00

【問題描述】

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

【輸入格式】

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

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

【輸出格式】

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

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

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

【輸入輸出樣例】

rassle.in

4 4

1 2

1 4

2 3

3 4

rassle.out

1 3

2 4

【資料範圍】

n<=10000, r<=10000

【分析】

連通分量，判環。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25682

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

const int MAXN=10001;

typedef vector<int> Vec; 

Vec Suki;

Vec Kowa;

Vec Map[MAXN];

int Visited[MAXN];

int Dist[MAXN];

int Num[MAXN];



Vec temp,tmp1,tmp2;



int N,M;



void init()

{

    scanf("%d %d\n",&N,&M);

    int a,b;

    for(int i=1;i<=M;i++)

    {

        scanf("%d %d\n",&a,&b);

        Map[a].push_back(b);

        Map[b].push_back(a);

    }

}



int abs(int a)

{

    return a>0?a:-a;

}



queue<int>Q;

bool bfs(int s)

{

    Num[s]=1;

    Dist[s]=0;

    Visited[s]=true;

    

    Q.push(s);

    int tmp,nxt;

    

    temp.clear();

    tmp1.clear();

    tmp2.clear();

    

    while(!Q.empty())

    {

        tmp=Q.front();

        Q.pop();

        

        temp.push_back(tmp);

        

        for(unsigned int i=0;i<Map[tmp].size();i++)

        {

            nxt=Map[tmp][i];

            if(Visited[nxt]==1)

            {

                if(abs(Dist[tmp]-Dist[nxt])%2==0)

                {

                    return false;

                }

                continue;

            }

            if(Visited[nxt]==0)

            {

                Num[nxt]=!Num[tmp];

                Visited[nxt]=1;

                Dist[nxt]=Dist[tmp]+1;

                Q.push(nxt);

            }

        }

    }

    Vec::iterator iter;

    int x;

    for(iter=temp.begin();iter!=temp.end();iter++)

    {

        x=*iter;

        if(Num[x]==1)

            tmp1.push_back(x); 

        if(Num[x]==0)

            tmp2.push_back(x);

    }

    if(tmp1.size()>=tmp2.size())

    {

        for(iter=tmp1.begin();iter!=tmp1.end();iter++)

        {

            x=*iter;

            Suki.push_back(x);

        }

        for(iter=tmp2.begin();iter!=tmp2.end();iter++)

        {

            x=*iter;

            Kowa.push_back(x);

        }

    }

    else

    {

        for(iter=tmp1.begin();iter!=tmp1.end();iter++)

        {

            x=*iter;

            Kowa.push_back(x);

        }

        for(iter=tmp2.begin();iter!=tmp2.end();iter++)

        {

            x=*iter;

            Suki.push_back(x);

        }

    }

    return true;

}



void solve()

{

    bool flag;

    init();

    

    for(int i=1;i<=N;i++)

        Visited[i]=0,Num[i]=0,Dist[i]=10000000;

    

    for(int i=1;i<=N;i++)

    {

        if(Visited[i])

            continue;

        flag=bfs(i);

        if(!flag)

        {

            printf("No\n");

            return;

        }

    }

    

    Vec *Big;

    Vec *Small;

    if((Suki.size())>=Kowa.size()) {Big=&Suki,Small=&Kowa;}

    if((Suki.size())<Kowa.size()) {Big=&Kowa,Small=&Suki;}

    

    sort(Suki.begin(),Suki.end());

    sort(Kowa.begin(),Kowa.end());

    

    for(Vec::iterator iter=Big->begin();iter!=Big->end();iter++)

        printf("%d ",*iter);

    printf("\n");

    for(Vec::iterator iter=Small->begin();iter!=Small->end();iter++)

        printf("%d ",*iter);

}



int main()

{

    freopen("rassle.in","r",stdin);

    freopen("rassle.out","w",stdout);

    solve();

    return 0;

}

動態規劃練習題相似基因 gene 題解

2012-02-27T13:58:00.001+08:00

問題描述

大家都知道，基因可以看作一個鹼基對序列。它包含了 4 種核苷酸，簡記作 A,C,G,T 。生物學家正致力於尋找人類基因的功能，以利用於診斷疾病和發明藥物。

在一個人類基因工作組的任務中，生物學家研究的是：兩個基因的相似程度。因為這個研究對疾病的治療有著非同尋常的作用。兩個基因的相似度的計算方法如下：

對於兩個已知基因，例如 AGTGATG 和 GTTAG ，將它們的鹼基互相對應。當然，中間可以加入一些空鹼基 - ，例如：

A	G	T	G	A	T	-	G
-	G	T	-	-	T	A	G

這樣 , 兩個基因之間的相似度就可以用鹼基之間相似度的總和來描述，鹼基之間的相似度如下表所示：

那麼相似度就是： (-3)+5+5+(-2)+(-3)+5+(-3)+5=9 。因為兩個基因的對應方法不唯一，例如又有：

A	G	T	G	A	T	G
-	G	T	T	A	-	G

相似度為： (-3)+5+5+(-2)+5+(-1)+5=14 。規定兩個基因的相似度為所有對應方法中，相似度最大的那個。

輸入

共兩行。每行首先是一個整數，表示基因的長度；隔一個空格後是一個基因序列，序列中只含 A,C,G,T 四個字母。 1<= 序列的長度 <=100 。

輸出

僅一行，即輸入基因的相似度。

樣例

gene.in

7 AGTGATG

5 GTTAG

gene.out

【分析】

簡單的動態規劃。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25681

/*

*Problem: 相似基因 gene

*Author: Yee-fan Zhu

*Method: Dynamic Programming

*Email: zyfworks@gmail.com

*/

#include <cstdio>

#include <cstdlib>

#include <cstring>

#define openfile(str) freopen(str".in","r",stdin),freopen(str".out","w",stdout)

using namespace std;

const int MAXN=101;

/*

*A:1 C:2 G:3 T:4 -:5

*/

int Sml[6][6]={

{0,0,0,0,0},

{0,5,-1,-2,-1,-3},

{0,-1,5,-3,-2,-4},

{0,-2,-3,5,-2,-2},

{0,-1,-2,-2,5,-1},

{0,-3,-4,-2,-1,-100000},

};



int GetNum(char c)

{

    if(c=='A') return 1;

    if(c=='C') return 2;

    if(c=='G') return 3;

    if(c=='T') return 4;

    return 5;

}



char str1[MAXN],str2[MAXN];

int F[MAXN][MAXN];

int len1,len2;

void init()

{

    scanf("%d %s\n%d %s\n",&len1,&str1,&len2,&str2);

    for(int i=len1;i>=1;i--) str1[i]=str1[i-1];

    for(int i=len2;i>=1;i--) str2[i]=str2[i-1];

    str1[0]='0',str2[0]='0';

    for(int i=1;i<=len1;i++)

        for(int j=1;j<=len2;j++)

            F[i][j]=0;

    for(int i=1;i<=len1;i++) F[i][0]=F[i-1][0]+Sml[GetNum(str1[i])][5];

    for(int i=1;i<=len2;i++) F[0][i]=F[0][i-1]+Sml[5][GetNum(str2[i])];

}



int MAX(int a,int b)

{

    return a>b?a:b;  

}



int main()

{

    openfile("gene");

    init();

    for(int i=1;i<=len1;i++)

    {

        for(int j=1;j<=len2;j++) 

        { 

            F[i][j]=F[i-1][j-1]+Sml[GetNum(str1[i])][GetNum(str2[j])];

            F[i][j]=MAX(F[i][j],F[i-1][j]+Sml[GetNum(str1[i])][5]);

            F[i][j]=MAX(F[i][j],F[i][j-1]+Sml[5][GetNum(str2[j])]);    

        }

    }

    printf("%d\n",F[len1][len2]);

    return 0;    

}

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

2012-02-27T13:44:00.002+08:00

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

【問題描述】

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

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

【輸入格式】

輸入文件包含多組資料。第一行為K，表示資料的總數。

每組資料的第一行是N(3≤N≤7)，

第二行是2N個盒子的初始狀態。金球用a表示，銀球用b表示，空盒用空格表示。每兩組相鄰資料用空行隔開。

【輸出格式】

對於每一組資料，若無解則輸出一行NO SOLUTION，若有解，輸出一組狀態來表示移動的序列，每個狀態佔一行。每行輸出到此狀態的移動的步數，緊接著是一個空格，然後是此時的狀態。初始狀態為第0步，每組資料都要先輸出初始狀態。如有多種最少移動次數的方案，輸出“空格靠前靠左”的一種，如下兩種方案，需輸出第二種。

0 bbbb aaaa

1 bbbbaa aa

2 bbaabbaa

3 aabbaabb

4 aa aabbbb

0 bbbb aaaa

1 bbbbaaaa

2 aabbbb aa

3 aa bbbbaa

4 aaaabbbb

相鄰的兩組資料用一個空行隔開。

【輸入輸出樣例】

樣例輸入（balls.in）:

abab

abba abab

a babbababa

樣例輸出（balls.out）：

NO SOLUTION

0 abba abab

1 abbabaa b

2 a abaabbb

3 aaaab bbb

0 a babbababa

1 aabbabb aba

2 aabbabbbaa

3 aa abbbaabb

4 aaaaabbb bb

【分析】

簡單的廣度優先搜索～

（我現在才知道這種題目叫做『隱式圖』的廣度優先搜索）

由於暴力判重時間複雜度很大，所以可以使用哈希（Hash）判重。

由於每個格子只能有3種狀態，所以可以用『3進制數』來構造哈希。

因為3^14<5x10^6，不會開爆內存。

這道題困難的地方是空格的讀入，因為C++讀取文件中開頭的空格不能使用scanf("%c",&c)，也不能使用cin.get()，getline也不用，只能使用fstream的fin.get()。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25680

/*

*Problem: 分球

*Author: Yee-fan Zhu

*Website: www.yeefanblog.tk

*/

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <fstream>

using namespace std;



ifstream fin("balls.in");

ofstream fout("balls.out");



typedef unsigned short int usint;



const int INF=100000000;

const int MAXN=16;

usint Ball[MAXN];

usint hash[5000001]={0};

int N;

int M;

int Head=0;

int Tail=0;



bool check(usint *str)

{

    int s=0;

    for(int i=1;i<=2*N;i++)

    {

        if(str[i]==2) break;

        if(str[i]==1)

            s++;

    }

    if(s==N-1)

        return true;

    return false;

}



void Print(usint *str)

{

    int tmp;

    for(int i=1;i<=2*N;i++)

    {

        tmp=str[i];

        if(tmp==1) fout<<"a";

        if(tmp==0) fout<<" ";

        if(tmp==2) fout<<"b";

    }

    fout<<endl;

}



int Hash(usint *str)

{

    int s=0;

    int j=1;

    for(int i=2*N;i>=1;i--)

    {

        if(str[i]==2)

            s+=j;

        else if(str[i]==0)

            s+=2*j;

        j*=3;

    }

    return s;

}



class QUEUE

{

public:

    usint ball[16];

    usint father;

    usint pos;

    usint step;

    void clear()

    {

        for(int i=0;i<=15;i++)

            ball[i]=0;

    }

};  

QUEUE Q[2000000]; 



usint Index[500000];

void Output(QUEUE x)

{

    

    usint top=0;

    usint p=x.father;

    while(p!=0)

    {

        top++;

        Index[top]=p;

        p=Q[p].father;

    }

    for(int i=top;i>=1;i--) 

    {

        fout<<Q[Index[i]].step<<" ";

        Print(Q[Index[i]].ball);

    }

    fout<<x.step<<" ";

    Print(x.ball);

}



void Push(QUEUE x)

{

    Tail++;

    Q[Tail]=x;

    hash[Hash(x.ball)]=1;

}



QUEUE Pop()

{

    Head++;

    return Q[Head];

}



void bfs()

{

    QUEUE tmp,nxt;

    tmp.clear();

    for(int i=1;i<=2*N;i++)

        tmp.ball[i]=Ball[i];

    tmp.father=0;

    tmp.step=0;

    for(int i=1;i<=2*N;i++)

    {

        if(Ball[i]==0)

        {

            tmp.pos=i;

            break;

        }

    }

    Push(tmp);

    

    bool flag=true;

    

    usint tp;

    while(Head!=Tail && flag)

    {

        tmp=Pop();

        tp=tmp.pos;

        for(int i=1;i<=2*N;i++)

        {

            if(tmp.ball[i]==0 || tmp.ball[i+1]==0)

                continue;

            nxt=tmp;

            nxt.father=Head;

            nxt.pos=i;

            nxt.ball[tp]=nxt.ball[i];

            nxt.ball[tp+1]=nxt.ball[i+1];

            nxt.ball[i]=0;

            nxt.ball[i+1]=0;

            nxt.step=tmp.step+1;

            if(check(nxt.ball))

            {

                Output(nxt);

                flag=false;

                return;

            }

            else

                if(hash[Hash(nxt.ball)]==0)

                    Push(nxt);

        }

    }

    fout<<"NO SOLUTION"<<endl;

}



void init()

{

    fin>>M;

    for(int i=1;i<=M;i++)

    {

        Head=0;

        Tail=0;

        fin>>N;

        usint top=0;

        char c;

        while(top<2*N)

        {

            c=fin.get();

            if(c!='a' && c!='b' && c!=' ')

                continue;

            if(c=='a') Ball[++top]=1;

            if(c=='b') Ball[++top]=2;

            if(c==' ') Ball[++top]=0;

        }

        if(check(Ball))  {fout<<"0 ";Print(Ball);continue;}

        

        for(int i=0;i<=5000000;i++)

            hash[i]=0;

        bfs();

        if(i<M)

            fout<<endl;

    }

}



int main()

{

    init();

    return 0;

}

【拓撲排序練習題】課程安排問題 curriculum

2012-02-27T13:33:00.000+08:00

【問題描述】

一個軟體專業的學生必須學習一系列基本課程，其中有些課程是基礎課，它獨立於其它課程，如《高等數學》、《計算引論》；而另一些課程必須在學完作為它的基礎的先修課程才能開始。如，在《程序設計基礎》和《離散數學》學完之前就不能開始學習《資料結構》。這些先決條件定義了課程之間的領先（優先）關係。請你在符合上述領先（優先）條件的前提下，給出所有課程的一個有序序列，以方便學校排課。

【輸入格式】

輸入文件有若干行

第一行，一個整數n，表示共有n(0<n<=100)門課程

第2--n+1行分別表示第1--n門課程的先修課程資訊，每行有若干個整數m,s1,s2,...,sm

m表示該門課程有m門先修課程，s1,s2,...,sm分別表示m門先修課的編號，如果該門課沒有先修課程，則m為0。

【輸出格式】

一行，n個整數，表示n門課程編號的有序序列(如果這樣的序列不存在，則輸出no;如果有多個這樣的序列，輸出字典序最小的)

【輸入輸出樣例】

輸入文件名： curriculum.in

1 1

2 2 3

輸出文件名：curriculum.out

1 2 3 4

【分析】

裸代碼RawCode

C++语言: Codee#25679

/*

*Problem: 拓撲排序練習題 課程安排問題 curriculum

*Author: Yee-fan Zhu

*Website: http://zhuyf.tk/

*/

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <algorithm>

using namespace std;

typedef vector<int> Vec;

typedef unsigned int usint;

int N;

const int MAXN=101;

Vec Map[MAXN];

int Zero[MAXN];

int Flag[MAXN];

Vec Res;



void init()

{

    scanf("%d\n",&N);

    int s;

    int x;

    for(int i=1;i<=N;i++)

    {

        scanf("%d",&s);

        Zero[i]=s;

        Flag[i]=0;

        for(int j=1;j<=s;j++)

        {

            scanf("%d",&x);

            Map[i].push_back(x);

        }

    }

    for(int i=1;i<=N;i++)

    {

        sort(Map[i].begin(),Map[i].end());

        //for(int j=0;j<Map[i].size();j++)

    //        printf("%d ",Map[i][j]);

        //printf("\n");

    }

}



void solve()

{

    int X;

    int Out=0;

    while(Out<N)

    {

        X=0;

        for(int i=1;i<=N;i++)

        {

            if(Flag[i]==0 && Zero[i]==0)

            {

                X=i;

                break;

            }

        }

        if(X==0 && Out<N)

        {

            printf("no\n");

            exit(0);

        }

        

        /*Delete Edge*/

        Vec::iterator iter;

        for(int i=1;i<=N;i++)

        {

            iter=find(Map[i].begin(),Map[i].end(),X);

            if(iter==Map[i].end())

                continue;

            Map[i].erase(iter);

            Zero[i]--;

        }

        //printf("%d ",X);

        Res.push_back(X);

        Flag[X]=1;

        Out++;

    }

}



int main()

{

    freopen("curriculum.in","r",stdin);

    freopen("curriculum.out","w",stdout);

    init();

    solve();

    for(Vec::iterator iter=Res.begin();iter!=Res.end();iter++)

        printf("%d ",*iter);

    return 0;

}

【強連通分量】四面楚歌 virus 解題報告

2012-02-27T13:17:00.001+08:00

【題目描述】

公元2008年10月31日星期五，篤志者所在的整個機房由於猖獗的病毒一片恐慌。經查證，病毒是由A1機器散播開來的。。這要追溯到29日，篤志者由於病毒被迫從A1機器撤離。

一想到病毒是從自己的機器傳開的，篤志者就心神不寧。他決定搞清楚病毒是怎麼散播開來的。事實上，機房內的機器並不是全部都能夠互相感染的。篤志者（ceeji）好不容易經過測試得到了機房中各機器間是否連通的圖表，就在他馬上就要得出結果的時候，大腦突然亂了！問題的嚴重性在於：如果他不在1s內搞清楚這個問題，機房就會整體癱瘓。現在篤志者求助於你，他需要知道病毒從未感染機房開始，最少入侵幾臺機器之後，機房就會整體感染。

【輸入格式】

文件的第一行為一個整數n，第二行至第n+1行為n*n的矩陣（若第i行第j列為1，則機器i能對機器j進行ARP攻擊（即感染機器j），若第i行第j列為0，則機器i不能感染機器j）。

文件名為“2.in”。

【輸出格式】

輸出文件只有一行，為篤志者想知道的最少感染機器數。

文件名為“2.out”。

【輸入樣例】

0 0 1 0 0 0 0 0

1 0 0 1 0 0 0 0

0 1 0 1 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 1 0 0 0 0

0 0 0 1 0 0 0 1

0 0 0 0 0 0 1 0

【輸出樣例】

【資料範圍】

對於 100% 的資料，n<=1000

【分析】

經典的圖論，求所有強連通分量並縮點進行拓撲排序，入度為0的點即為所求。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25678

/*

*Problem:“一家人杯”模擬賽比賽環境適應賽 四面楚歌 virus

*Author: Yee-fan Zhu

*Website: http://www.yeefanblog.tk/

*/

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <stack>

using namespace std;

typedef vector<int> Vec;

const int MAXN=1001;

Vec Map[MAXN];

int Flag[MAXN][MAXN];

int N;

int Dfn[MAXN];

int Low[MAXN];

int InStack[MAXN];

int Belong[MAXN];

int Scc[MAXN];

int Index=0;

int SCC=0;

stack<int> S; 



/*

*學習資料：http://www.byvoid.com/blog/scc-tarjan/

*/



void init()

{

    scanf("%d\n",&N);

    int x;

    for(int i=1;i<=N;i++)

    {

        Dfn[i]=0,Low[i]=0;

        Belong[i]=0,InStack[i]=0;

        Scc[i]=0;

        for(int j=1;j<=N;j++)

        {

            scanf("%d",&x);

            if(x==1)

            {

                Map[i].push_back(j);Flag[i][j]=1;

            }

        }

    }

}



int Min(int a,int b)

{return a<b?a:b;}



void Targan(int u)

{

    Dfn[u]=Low[u]=++Index;

    S.push(u);

    InStack[u]=1;

    int v;

    for(unsigned int i=0;i<Map[u].size();i++)

    {

        v=Map[u][i];

        if(Dfn[v]==0)

        {

            Targan(v);

            Low[u]=Min(Low[u],Low[v]);

        }

        else if(InStack[v]==1)

        {

            Low[u]=Min(Low[u],Dfn[v]);

        }

    }

    int tmp;

    if(Dfn[u]==Low[u])

    {

        SCC++;

        do

        {

            tmp=S.top();

            S.pop();

            Belong[tmp]=SCC;

            InStack[tmp]=0;

        }while(u!=tmp);

    }

}



int main()

{

    freopen("virus.in","r",stdin);

    freopen("virus.out","w",stdout);

    init();

    for(int i=1;i<=N;i++) { if(Dfn[i]==0) Targan(i);}

    int Ans=0;

    for(int i=1;i<=N;i++)

    {

        for(int j=1;j<=N;j++)

        {

            if(Flag[i][j]==1 && Belong[i]!=Belong[j])

                Scc[Belong[j]]=1;

        }

    }

    for(int i=1;i<=SCC;i++)

        if(Scc[i]==0) Ans++;            

    printf("%d\n",Ans);

    return 0;

}

NOIP1995 普及組編碼問題 code

2012-02-20T22:26:00.001+08:00

【問題描述】

設有一個數組 A ： ARRAY[0..N-1] OF INTEGER ；數組中存儲的元素為 0-N-1 之間的整數，且 A[I] ≠ A[J] ( 當 I ≠ J) 時。

例如： N=6 時，有：（ 4 ， 3 ， 0 ， 5 ， 1 ， 2 ）

此時，數組 A 的編碼定義如下：

A[0] 的編碼為 0 ：

A[I] 的編碼為：在 A[0] ， A[1] ，…… A[I-1] 中比 A[I] 的值小的元素的個數（ I=1 ， 2 ，…… N-1 ）

所以上面數組 A 的編碼為 :B=(0,0,0,3,1,2)

程序要求解決以下問題

① 給出數組 A 後，求出其編碼；

② 給出數組 A 的編碼後，求出 A 的原資料。

【輸入格式】

輸入由若干行組成：

第一行有兩個整數，m，n（1≤n,m≤100）；n表示數組長度，m表示問題個數。

下面有2*m行,每兩行是一個問題,每個問題的第一行是一個數字s,s=1時表示根據資料求編碼,s=2時表示根據編碼求資料,第二行是n個數，中間用空格隔開。

【輸出格式】

輸出資料有m行，每行表示一個問題的答案。

【輸入輸出樣例】

輸入文件名：code.in

2 6

4 3 0 5 1 2

0 0 0 3 1 2

輸出文件名：code.out

0 0 0 3 1 2

4 3 0 5 1 2

【分析】

常老師竟然拿一道十幾年前NOIP普及組的題當我們省選的模擬賽題～

雖說是當年普及組的最後一題，但是還是蠻簡單的，那個筆在紙上畫畫找找規律就行了。

對於由數據求編碼，從前往後模擬即可。

對於由編碼求數據，從後往前遞推即可，看看我的代碼吧。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25588

/*

*Problem: NOIP1995 普及組 

*Author: Yee-fan Zhu

*Email: zyfworks@gmail.com

*/

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

using namespace std;

int N,M;

const int MAXN=111;



int Num[MAXN];

int Ans[MAXN];



void Work1()

{

    Ans[1]=0;

    for(int i=2;i<=N;i++)

    {

        int Res=0;

        for(int j=1;j<i;j++)

        {

            if(Num[j]<Num[i])

                Res++;

        }

        Ans[i]=Res;

    }

    for(int i=1;i<=N-1;i++)

        printf("%d ",Ans[i]);

    printf("%d\n",Ans[N]);

}



void Work2()

{

    bool flag[MAXN];

    

    for(int i=0;i<=100;i++)

        flag[i]=false;

    

    Ans[N]=Num[N];

    flag[Ans[N]]=true;

    

    for(int i=N-1;i>=1;i--)

    {

        int tmp1=Num[i];

        for(int j=0;j<=N-1;j++)

        {

            if(flag[j])

                continue;

            int tmp2=0;

            for(int k=i+1;k<=N;k++)

            {

                if(Ans[k]<j)

                    tmp2++;

            }

            int tmp3=tmp1+tmp2;

            if(tmp3==j)

            {

                Ans[i]=j;

                flag[j]=true;

                break;

            }

        }

    }

    for(int i=1;i<=N-1;i++)

        printf("%d ",Ans[i]);

    printf("%d\n",Ans[N]);

}



void solve()

{

    scanf("%d %d\n",&M,&N);

    int P;

    for(int i=1;i<=M;i++)

    {

        scanf("%d\n",&P);

        for(int j=1;j<=N;j++)

            scanf("%d",&Num[j]);

        if(P==1)

            Work1();

        else if(P==2)

            Work2();

    }

}



int main()

{

    freopen("code.in","r",stdin);

    freopen("code.out","w",stdout);

    solve();

    return 0;

}

[動態規劃]Ural 1031 rail 火車票解題報告

2012-02-20T22:13:00.000+08:00

【題目描述】
現在有一條“葉卡特琳堡－斯維爾德洛夫斯克”鐵路線。它有若干個火車站。這個鐵路線可以用一條線段來表示，而火車站就是線段上的點。鐵路起始於葉卡特琳堡(Eakterinburg)，終止於斯維爾德洛夫斯克(Sverlovsk)，且各站從葉卡特琳堡(它的編號是1)至斯維爾德洛夫斯克(終點)編號。

兩個站之間的票價僅跟兩站間的距離有關係。票價規定如下表。

兩站間距離 - X	票價
0<X<=L₁	C₁
L₁<X<=L₂	C₂
L₂<X<=L₃	C₃

當且僅當兩站間距離不大於L3時才能購買這兩站之間的直達車票。所以有時須要購買若干張票來完成整個旅行。

例如，在上圖，整條鐵路有七個站。從第2站不能直達第6站(因為距離大於L3)，但有另外幾種方法購票。其中一種是買兩張票：一張是從第2站至第3 站(票價為C2)，另一張是從第3站至第6站(票價為C3)，注意，雖然從第2站至第6站的距離為2×L2，但不可以買兩張價值C2的票，因為一張票只可以用一次且起點和終點必須在車站上。

你的任務時計算給出的兩站之間的最小花費。

輸入

輸入的第一行包含六個由空格隔開的整數L1，L2，L3，C1，C2，C3(1<=L1<L2<L3<=10^9，1& lt;=C1<C2<C3<=10^9)。第二行為車站數N(2<=N<=10000)。第三行有兩個由空格隔開的不等的整數，表示旅行起點和終點。接下來的N-1行為起點(葉卡特琳堡)至其它站的距離。這些距離為互不相等的正整數而且呈上升序列。從葉卡特琳堡至斯維爾德洛夫斯克的距離不超過10^9。任意兩相鄰站之間的距離不超過L3。旅行最小花費不超過10^9。

輸出

一個整數------最小花費。

樣例輸入

3 6 8 20 30 40
7
2 6
3
7
8
13
15
23

樣例輸出

【我的代碼】
裸代碼RawCode

C++语言: Codee#25587

/*

*Problem: Ural 1031 rail

*Author: Yee-fan Zhu

*Email: zyfworks@gmail.com

*Method: Dynamic Programming

*/

#include <cstdio>

#include <cstdlib>

using namespace std;

const int MAXN=10001;

typedef unsigned long long ull;

ull L[4];

ull Cost[4];

ull dist[MAXN];

ull F[MAXN];

int S,T;

int N;



void init()

{

    for(int i=1;i<=3;i++) scanf("%d",&L[i]);

    for(int i=1;i<=3;i++) scanf("%d",&Cost[i]);

    scanf("%d\n",&N);

    scanf("%d %d\n",&S,&T);

    if(S>T){int t=S;S=T;T=t;}

    if(S==T) {printf("0\n");exit(0);}

    dist[1]=0;

    for(int i=2;i<=N;i++) scanf("%d\n",&dist[i]);

}



ull Min(ull a,ull b)

{

    return a<b?a:b;

}



void dp()

{

    F[S]=0;

    for(int i=S+1;i<=T;i++)

    {

        F[i]=2000000000;

        int k=i-1;

        ull delta;

        for(;k>=S;k--)

        {

            delta=dist[i]-dist[k];

            if(delta>L[3])

                break;

            if(delta<=L[1])

            {

                F[i]=Min(F[i],F[k]+Cost[1]);

                continue;

            }

            if(delta<=L[2])

            {

                F[i]=Min(F[i],F[k]+Cost[2]);

                continue;

            }

            F[i]=Min(F[i],F[k]+Cost[3]);

        }

    }

    printf("%d\n",F[T]);

}



int main()

{

    freopen("rail.in","r",stdin);

    freopen("rail.out","w",stdout);

    init();

    dp();

    return 0;

}

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

2012-02-20T21:33:00.000+08:00

週年紀念聚會

Background

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

Problem

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

Input

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

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

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

<L> <K>

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

輸入以0 0表示結束

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

Sample Input

1 3

2 3

6 4

7 4

4 5

3 5

0 0

Sample Output

【分析】

樹形動態規劃。

由於邊界條件是葉子節點，所以需要遞歸每個節點來尋找葉子節點。

F[i][0] :不選第i個節點的最大歡樂度。

F[i][1] :選第i個節點的最大歡樂度。

狀態轉移方程：

F[i][0]+=max{ F[x][0] , F[x][1] } (i與x鄰接)

F[i][1]+=Happy[i]+F[x][0] (x與i鄰接)

目標結果：
Max{F[Root][1],F[Root][0]}

Root為根節點，即題目中的公司老闆。可以統計每個點的入度，0入度的點
即為根節點。

【我的代碼】
裸代碼RawCode

C++语言: Codee#25586

/*

*Problem: 週年紀念聚會 aniv

*Author: Yee-fan Zhu

*Email: zyfworks@gmail.com

*Method: DFS/DP

*/

#include <cstdio>

#include <cstdlib>

#include <vector>

using namespace std;  

const int MAXN=6001;

int F[MAXN][2];

int Happy[MAXN];

int N;

int visited[MAXN];

vector<int> Map[MAXN];

int  root=1;

bool flag[MAXN];



void init()

{

    scanf("%d\n",&N);

    for(int i=1;i<=N;i++)

    { 

        scanf("%d\n",&F[i][1]);

        visited[i]=0;

    }

    int x,y;

    scanf("%d %d\n",&x,&y);

    while(x!=0)

    {

        Map[y].push_back(x);

        flag[x]=1;

        scanf("%d %d\n",&x,&y);

    }

    for(int i=1;i<=N;i++)

    {

        if(!flag[i])

        {

            root=i;

            return;

        }

    }

}



int Max(int a,int b)

{

    return a>b?a:b;

}



void dp(int x)

{

    visited[x]=1;

    for(unsigned int i=0;i<Map[x].size();i++)

    {

        if(visited[Map[x][i]])

            continue;

        dp(Map[x][i]);

        F[x][0]+=Max(F[Map[x][i]][0],F[Map[x][i]][1]);

        F[x][1]+=F[Map[x][i]][0];

    }

}



int main()

{

    freopen("aniv.in","r",stdin);

    freopen("aniv.out","w",stdout);

    init();

    dp(root);

    printf("%d\n",Max(F[root][0],F[root][1]));

    return 0;

}

[動態規劃]OI練習題最後的利益 9cwy 解題報告

2012-02-20T21:08:00.000+08:00

【問題描述】
最近9C馬上就要和WY交收WOW的運營權了，9C為了最後的利益決定讓GM控制玩家上線時間。因為9C的小霸王伺服器總是容易爆滿，所以某伺服器中只剩一個玩家的位子，GM為了讓玩家在線時間總和最長。他將選擇一些上線時間不重複的玩家讓他們上線。我們假設某玩家下線以後，另一個玩家可以立即登入。但是GM又笨又懶，他希望你能幫他幫他寫一個程序來完成這個任務。

【輸入文件】

輸入文件第一行是一個正整數n，n<=10000，為玩家數量

一下n行每行含有兩個數t1、t2表示某玩家上線時段

【輸出文件】

輸出最長遊戲總時間

【輸入樣例】

9cwy.in

1 2

3 5

0 4

6 8

7 13

4 6

9 10

9 12

11 14

15 19

14 16

18 20

9cwy.out

【分析】

動態規劃。

先以每個玩家的t1、t2為關鍵字進行雙關鍵字排序。數據量不小，需要使用快速排序函數或者STL內建排序函數以及STL內建的鏈表合併函數以實現O(N*LogN)時間複雜度的排序。

狀態設定：F[i] 如果讓排序後的第i個玩家上線獲得的最大在線時間。

初始狀態：F[0]=0,F[1]=T[i];

狀態轉移方程：F[i]=Max{F[j]+T[i] (End[j]<=Begin[i]) } (1<=j<=i-1)

目標結果：Max{F[i]} (1<=i<=N)

【我的代碼】

裸代碼RawCode

C++语言: Codee#25585

/*

*Problem: 最後的利益 9cwy

*Author: Yee-fan Zhu

*GTalk: zyfworks@gmail.com

*/

#include <cstdlib>

#include <cstdio>

using namespace std;

const int MAXN=10001;

class WOW

{

public:

    int s,e;

    int v;

}T[MAXN];

int N;



int cmp(const void *a,const void *b)

{

    class WOW *c=(class WOW *)a;

    class WOW *d=(class WOW *)b;

    if(c->s!=d->s)

        return c->s-d->s;

    return c->e-d->e;

}



void init()

{

    scanf("%d\n",&N);

    for(int i=1;i<=N;i++) 

    {

        scanf("%d %d\n",&T[i].s,&T[i].e);

        T[i].v=T[i].e-T[i].s;

    }

    qsort(T+1,N,sizeof(T[0]),cmp);

}



int F[MAXN];



int max(int a,int b)

{

    return a>b?a:b;

}



int Max=0;

void dp()

{

    F[0]=0;

    for(int i=1;i<=N;i++)

    {

        F[i]=T[i].v;

        for(int j=1;j<i;j++)

        {

            if(T[j].e>T[i].s)

                continue;

            F[i]=max(F[i],F[j]+T[i].v);

        }

        if(F[i]>Max)

            Max=F[i];

    }

    printf("%d\n",Max);

}



int  main()

{

    freopen("9cwy.in","r",stdin);

    freopen("9cwy.out","w",stdout);

    init();

    dp();

    return 0;

}

[動態規劃]POI 1998 ple 潛水員問題解題報告

2012-02-20T20:52:00.000+08:00

【問題描述】
一個潛水員在潛水時使用一種特殊的裝置：一個有兩個容器的氣筒。一個容器中裝的是氧氣，另一個容器中裝氮氣。潛水員需要攜帶的氧氣和氮氣量依賴於潛水的時間和深度。潛水員有一系列的氣筒，用來在不同的情況下攜帶。每個氣筒可以用這樣幾個量來描述：氣筒的質量，氣筒中所能容納的氧氣量，以及可以容納的氮氣量。為了能完成最近的一個任務，潛水員需要一定量的氧氣和氮氣。潛水員有一系列準備好的氣筒。他希望能攜帶總質量儘可能小的氣筒下水。現在請你幫他計算一下至少要攜帶多少質量的氣筒下水才能完成這個任務。

【示例說明】
潛水員有以下 5 個氣筒。每個氣筒用三個整數來描述：氣筒所能容納的氧氣的量，氮氣的量和氣筒的質量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果這次任務中潛水員需要攜帶 5 升氧氣， 60 升氮氣。那麼他至少要攜帶總質量為 249 的氣筒下水（樣例中的第一個和第二個氣筒或者第四個和第五個氣筒）。

【任務】
寫一個程序：
• 從輸入文件中讀入完成任務所需要的氧氣和氮氣量以及氣筒的個數和對每個氣筒的描述。
• 計算潛水員完成任務至少需要攜帶的多少質量的氣筒。
• 將結果寫入輸出文件中。
注意：題目中給出的氣筒總是能夠容納足夠多的氣體使得潛水員能完成任務。

【輸入格式】
在文件的第一行中有兩個整數 t 和 a ，分別描述完成任務所需的氧氣和氮氣量。（ 1 ≤ t ≤ 21 ， 1 ≤ a ≤ 79 ）。第二行中有一個整數 n ，表示氣筒的個數。（ 1 ≤ n ≤ 1000 ）。以後 n 行中，每行有三個整數 t i ， a i ， w i ， t i 表示第 i 個氣筒所能容納的氧氣量， a i 表示第 i 個氣筒所能容納的氮氣量， w i 表示氣筒 i 的質量。（ 1 ≤ a i ≤ 21 ， 1 ≤ t i ≤ 79 ， 1 ≤ w i ≤ 800 ）。

【輸出格式】
輸出文件只有一行，這行中包含一個整數，表示最少需要攜帶的多少質量的氣筒來完成改任務）。

【樣例輸入】
ple.in
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

【樣例輸出】
ple.out
249

【分析】
二維背包～具體方法請看dd的《背包九講》。

【我的代碼】
裸代碼RawCode

C++语言: Codee#25584

/*

*Problem: POI 1998  ple

*Author: Yee-fan Zhu

*GTalk: zyfworks@gmail.com

*Method: Dynamic Programming

*/

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;

int N;

class PLE

{

public:

    int O;//Oxygen  酸素

    int N;//Netrogen 窒素

    int W;//Weight

}P[1001];

int T,A;

int F[1001][50][160];/*對於前i個氧氣瓶,O2=j,N2=k時的最小質量*/



const int INF=1000000000;

int MIN(int a,int b)

{

    return (a>b?b:a);

}



int MAX(int a,int b)

{

    return (a>b?a:b);

}



int MaxO=0,MaxN=0;



void init()

{

    scanf("%d %d\n%d\n",&T,&A,&N);

    for (int i=1;i<=N;i++)

    {

        scanf("%d %d %d\n",&P[i].O,&P[i].N,&P[i].W);

        MaxO=MAX(MaxO,P[i].O);

        MaxN=MAX(MaxN,P[i].N);

    }

    for (int i=1;i<=N;i++)

    {

        for(int j=0;j<=T+MaxO;j++)

            for(int k=0;k<=A+MaxN;k++)

                F[i][j][k]=INF;    

        F[i][0][0]=0;    

    }

    return;

}



void dynamic()

{

    for(int k=1;k<=N;k++)

    {

        for (int i=1;i<=P[k].O;i++)

            for (int j=1;j<=P[k].N;j++)

                F[k][i][j]=P[k].W; 

    }

    

    for(int k=1;k<=N;k++)

    {

        for(int i=1;i<=P[k].O;i++)

            F[k][i][0]=P[k].W;

        for(int i=1;i<=P[k].N;i++)

            F[k][0][i]=P[k].W;

    }

    

    int i=2;    

    for (;i<=N;i++) 

    {

        for (int j=0;j<=T+MaxO;j++)

        {

            for(int k=0;k<=A+MaxN;k++)

            {

                int Min=F[i-1][j][k];

                if(j-P[i].O>=0 && k-P[i].N>=0)

                    Min=MIN(Min,F[i-1][j-P[i].O][k-P[i].N]+P[i].W);

                if(j-P[i].O<=0 && k-P[i].N<=0)

                    Min=MIN(Min,P[i].W);

                if(j-P[i].O>=0 && k-P[i].N<=0)

                    Min=MIN(Min,F[i-1][j-P[i].O][k]+P[i].W);

                if(j-P[i].O<=0 && k-P[i].N>=0)

                    Min=MIN(Min,F[i-1][j][k-P[i].N]+P[i].W);

                F[i][j][k]=Min;

            }

        }

    }

    

    int Ans=INF;

    for (int i=T;i<=T+MaxO;i++)

        for (int j=A;j<=A+MaxN;j++)

            Ans=MIN(Ans,F[N][i][j]);

    printf("%d\n",Ans);

}



int main()

{

    freopen("ple.in","r",stdin);

    freopen("ple.out","w",stdout);

    init();

    dynamic();

    return 0;

}

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

2012-02-18T22:49:00.001+08:00

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

輸入格式:

第1行: 輸入1個正整數：N

第2..N+1行: 第i+1行用2個用空格隔開的整數X_i、Y_i，描述了點i的座標

輸入樣例 (lines.in):

-1 1

-2 0

0 0

1 1

輸出格式:

第1行: 輸出1個整數，表示貝茜的最大得分，即她能畫出的互不平行的直線數

輸出樣例 (lines.out):

輸出說明:

貝茜能畫出以下4種斜率的直線：-1，0，1/3以及1。

【分析】

這是一道簡單的計算幾何的題目。雖然題目很簡單，就是讓你求斜率不同的直線的個數。

首先要單獨考慮斜率不存在的情況，也就是與Y軸平行的直線，因為它的斜率是無窮大，

導致在計算過程中會出現除數為0的情況，所以要單獨考慮。

本題關鍵是在於斜率的判重。

我一開始是直接掛上set容器，由於set是『集合』，不會出現重複的元素，所以可以利用這一點來判重。這樣插入的時間複雜度為O(N*LogN)，不會超時。但是，我這樣寫僅僅能在Windows下AC、在Ubuntu 11.10下AC，在NOI Linux（Ubuntu 9.04）下會出現WA 6組的情況～可能是由於實數的精度問題吧。

後來，我打算不直接存儲斜率了，由於每條斜率的直線可以化為兩個正整數之比，所以我直接存儲斜率的分子和分母。開2000個平衡樹（就是set容器了），如果斜率為負，就把負號移到分子上，保證分母是正數，然後…… set[分母].insert(分子)，就這樣，利用set容器的特性來幫你判重。最後統計每個set容器的size()即可，注意不要忘記考慮斜率無窮大的情況。

我在昨晚這題後，為了向神牛學習，參看了BYVoid神牛的解題報告，他是用的向量共線來判重。只不過時間複雜度有點高，他的程序在COGS上的運行時間為1.6秒，我的程序是0.16秒。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25575

/*

*Problem: USACO Feb08 Silver lines

*Author: Yee-fan Zhu

*Email: zyfworks@gmail.com

*Method: Computer Aided Geometric Design

*/

#include <cstdio>

#include <cstdlib>

#include <set>

#include <algorithm>

using namespace std;

const int MAXN=201;

bool NoTangent=false;

bool TanZero=false;

class Point

{

public:

    int x,y;

}P[MAXN];



int N;

set<int>tan[2001];



void init()

{

    scanf("%d\n",&N);

    for(int i=1;i<=N;i++)

        scanf("%d %d\n",&P[i].x,&P[i].y);

}



int Min(int a,int b)

{

    return a>b?b:a;

}



int Abs(int a)

{

    return a>=0?a:-a;

}



void check(int m,int n)

{    

    int x=P[n].x-P[m].x;

    int y=P[n].y-P[m].y;

    if(x==0)

    {

        NoTangent=true;

        return;

    }

    if(y==0)

    {

        TanZero=true;

        return;

    }

    bool fu=( (x<0 && y>0) || (x>0 && y<0) );

    x=Abs(x),y=Abs(y);

    int tmp=Min(x,y);

    for(int i=2;i<=tmp;i++)

    {

        while(x%i==0 && y%i==0)

        {

            x/=i,y/=i;

        }

    }

    if(fu)

        x=-x;

    tan[y].insert(x);

}



void solve()

{

    for(int i=1;i<=N;i++)

        for(int j=i+1;j<=N;j++)

            check(i,j);

    int Ans=0;

    for(int i=1;i<=2000;i++)

        Ans+=(tan[i].size());

    printf("%d\n",Ans+NoTangent+TanZero);    

}



int main()

{

    freopen("lines.in","r",stdin);

    freopen("lines.out","w",stdout);

    init();

    solve();

    return 0;

}

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

2012-02-16T21:01:00.000+08:00

譯: 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? 對於所有參加聚會的奶牛,找出前往聚會和返程花費總時間最多的奶牛,輸出這隻奶牛花費的總時間.

輸入格式:

第1行:三個用空格隔開的整數.

第2行到第M+1行,每行三個用空格隔開的整數:Ai, Bi,以及Ti.表示一條道路的起點,終點和需要花費的時間.

輸出格式:

唯一一行:一個整數: 所有參加聚會的奶牛中,需要花費總時間的最大值.

样例输出:

样例输入:

样例说明:
共有4只奶牛參加聚會,有8條路,聚會位於第2個農場.

第4只奶牛可以直接到聚會所在地(花費3時間),然後返程路線經過第1和第3個農場(花費7時間),總共10時間.

【分析】

裸SPFA………我沒寫優化，結果10組一共0.3秒～

我一同學，Floyd也過了！！！！

http://paulinsider.at.ua/news/sparty/2011-11-07-7

【我的代碼】

裸代碼RawCode

C++语言: Codee#25525

/*

*Problem: USACO sparty

*Author: Yee-fan Zhu

*Email: zyfworks@gmail.com

*Method: SPFA

*/

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <queue>

#define min(a,b) (a>b?b:a)

using namespace std;

const int MAXN=1001;

const int INF=100000; 

typedef vector<int>Vec;

Vec Map[MAXN];

Vec Val[MAXN];

int Mat[MAXN][MAXN];



int N,M,X;



void init()

{

    scanf("%d %d %d\n",&N,&M,&X);

    for(int i=1;i<=N;i++)

        for(int j=1;j<=N;j++)

            Mat[i][j]=INF;

    int s,e,v;    

    for(int i=1;i<=M;i++)

    {

        scanf("%d %d %d\n",&s,&e,&v);

        Mat[s][e]=min(Mat[s][e],v);

    }        

    for(int i=1;i<=N;i++)

    {

        for(int j=1;j<=N;j++)

        {

            if(Mat[i][j]==INF)

                continue;

            Map[i].push_back(j);

            Val[i].push_back(Mat[i][j]);

        }

    }

}



queue<int> Q;

unsigned short int dist[MAXN];

unsigned short int flag[MAXN];

int spfa(int S,int E)

{

    for(int i=1;i<=N;i++)

        dist[i]=INF,flag[i]=0;

    dist[S]=0;

    flag[S]=1;

    Q.push(S);

    int tmp,nxt,ndist;

    while(!Q.empty())

    {

        tmp=Q.front();

        Q.pop();

        flag[tmp]=0;

        for(unsigned int i=0;i<Map[tmp].size();i++)

        {

            ndist=dist[tmp]+Val[tmp][i];

            nxt=Map[tmp][i];

            if(ndist<dist[nxt])

            {

                dist[nxt]=ndist;

                if(!flag[nxt])

                {

                    Q.push(nxt);

                    flag[nxt]=1;

                }

            }

        }

    }

    return dist[E];

}



void solve()

{

    int sp1,sp2,sp;

    int Max=0;

    for(int i=1;i<=N;i++)

    {

        if(i==X)

            continue;

        sp1=spfa(i,X);

        sp2=spfa(X,i);

        sp=sp1+sp2;

        if(sp>Max)

            Max=sp;

    }

    printf("%d\n",Max);

    //printf("%d\n",clock());

}



int main()

{

    freopen("sparty.in","r",stdin);

    freopen("sparty.out","w",stdout);

    init();

    solve();

    return 0;

}

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

2012-02-12T18:11:00.001+08:00

路由選擇問題

【問題描述】

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至少有兩條不同路徑)

【輸入輸出樣例】

route.in

5 1 5

0 10 5 0 0

10 0 0 6 20

5 0 0 30 35

0 6 30 0 6

0 20 35 6 0

1 2

route.out

40 22 30

【約束條件】

(1)N<=50 N個節點的編號爲1，2，…，N

(2)Skj爲整數，Skj<=100，(K，J=1，2…，N 若Skj=0表示節點K到節點J沒線路)

(3)P<=5 　

【分析】

這題很沒意思啊～想要求次短路就直接問唄，還弄幾個壞節點～

數據規模很小，N<=50，這麼小的數據規模很不符合『省選』的風格啊，這哪怕時亂搞一個O(N^4)的算法也能過～雖然我的是次短路時O(N^2*M)的～

這道題目需要存爲有向圖。

第一問求最短路（需要排除幾個故障節點），把壞掉的節點標記一下，

在單源最短路算法中擴展時跳過就行了～我寫了Dijkstra。

第二問也是求最短路，只不過不考慮故障的頂點，只需要把剛纔標記的節點再去掉標記然後再Dijkstra一下就行了。

第三問是次短路徑，雖然可以用求K短路徑的Yen算法，但是這畢竟時『次』短啊，只需要枚舉最短路徑的每條邊，將它刪去然後求最短路，找出他們的最小的最短路即爲次短路。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25474

/*

* Problem: HAOI2005 路由選擇問題

* Author: Yee-fan Zhu

* Website: http://zhuyf.tk/

* Method: (2nd) Shortest-Path

* Algorithm: Dijkstra

* Cost: 0.000s

* Memory: 472KB

*/

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

const int INF=100000000;

const int MAXN=51;

int  Wasu[MAXN];//壞掉的節點

int N;//總節點數

int P;//壞掉的節點數

int S,T;//起訖點



class Graph

{

public:

    int Map[MAXN][MAXN];//臨接矩陣存圖

    int dist[MAXN];

    int prev[MAXN];

    int flag[MAXN];

    int Node[MAXN];

    int Top;

    int ShortestPath()

    {

        int ans;

        for(int i=1;i<=N;i++)

        {

            dist[i]=INF;

            flag[i]=0;

            prev[i]=0;

        }

        

        for(int i=1;i<=N;i++)

        {

            if(Map[S][i]==0 || Wasu[i]==0)

                continue;

            dist[i]=Map[S][i];

            prev[i]=S;

        }

        

        dist[S]=0;

        flag[S]=1;

        

        for(int i=2;i<=N;i++)

        {

            int tmp=INF;

            int u=S;

            for(int j=1;j<=N;j++)

            {

                if((!flag[j]) && dist[j]<tmp && Wasu[j]==1)

                {

                    u=j;

                    tmp=dist[j];

                }

            }

            flag[u]=1;

            for(int j=1;j<=N;j++)

            {

                if(flag[j]==1)

                    continue;

                if(Map[u][j]==0)

                    continue;

                if(Wasu[j]==0)

                    continue;

                int newdist=dist[u]+Map[u][j];

                if(newdist<dist[j])

                {

                    dist[j]=newdist;

                    prev[j]=u;

                }

            }

        }

        ans=dist[T];

        return ans;

    }

    

    void GetPath()

    {

        Top=1;

        int p=T;

        for(int i=1;i<=N;i++)

            Node[i]=0;

        while(p!=S)

        {

            Node[Top]=p;

            p=prev[Node[Top]];

            Top++;

        }

        Node[Top]=S;     

        

        int tt[MAXN];

        for(int i=1;i<=Top;i++)

            tt[i]=Node[Top-i+1];

        for(int i=1;i<=Top;i++)

            Node[i]=tt[i];

    }

    

    void NewGraph(Graph *New,int x)

    {

        for(int i=1;i<=N;i++)

            for(int j=1;j<=N;j++)

                New->Map[i][j]=Map[i][j];

        New->Map[Node[x]][Node[x+1]]=0;        

    }

}G,Sec;



void init()

{

    scanf("%d %d %d\n",&N,&S,&T);

    for(int i=1;i<=N;i++)

    {

        Wasu[i]=1;

        for(int j=1;j<=N;j++)

            scanf("%d",&G.Map[i][j]);

    }

    scanf("%d",&P);

    int tmp;

    for(int i=1;i<=P;i++)

    {

        scanf("%d",&tmp);

        Wasu[tmp]=0;

    }

    return;

}



void Solve()

{

    int Ans1=G.ShortestPath();

    for(int i=1;i<=N;i++) Wasu[i]=1;

    int Ans2=G.ShortestPath();

    printf("%d %d ",Ans1,Ans2);

    

    G.GetPath();

    

    int top=G.Top;

    /*printf("%d\n",top);*/

    int Min=INF;

    int res;

    for(int i=1;i<top;i++)

    {

        G.NewGraph(&Sec,i);

        res=Sec.ShortestPath();

        if(res<Min)

            Min=res;

    }

    printf("%d\n",Min);

}



int main()

{

    freopen("route.in","r",stdin);

    freopen("route.out","w",stdout);

    init();    

    Solve();

    return 0;    

}

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

2012-02-11T17:15:00.000+08:00

題目描述

最近，阿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)。

【任務描述】
你得到了一年當中，領養者和被收養寵物到來收養所的情況，希望你計算所有收養了寵物的領養者的不滿意程度的總和。這一年初始時，收養所裏面既沒有寵物，也沒有領養者。
【輸入格式】
你將從文件當中讀入資料。文件的第一行爲一個正整數n，n<=80000，表示一年當中來到收養所的寵物和領養者的總數。接下來的n行，按到來時間的先後順序描述了一年當中來到收養所的寵物和領養者的情況。每行有兩個正整數a, b，其中a=0表示寵物，a=1表示領養者，b表示寵物的特點值或是領養者希望領養寵物的特點值。（同一時間呆在收養所中的，要麼全是寵物，要麼全是領養者，這些寵物和領養者的個數不會超過10000個）
【輸入樣例】
5
0 2
0 4
1 3
1 2
1 5
【輸出格式】
輸出文件中僅有一個正整數，表示一年當中所有收養了寵物的領養者的不滿意程度的總和mod 1000000以後的結果。
【輸出樣例】
3
(abs(3-2) + abs(2-4)=3，最後一個領養者沒有寵物可以領養)
【運行限制】
運行時限：1秒鐘
【評分方法】
本題目一共有十個測試點，每個測試點的分數爲總分數的10%。對於每個測試點來說，如果你給出的答案正確，那麼你將得到該測試點全部的分數，否則得0分。

【分析】

平衡樹的基礎練習題，哦不，STL Set的基礎練習題！

直接使用C++ STL Set容器，建立兩個容器，分別是領養人和寵物，然後按照題目要求去『模擬』即可。

用到的Set函數：

1. 插入函數

void insert(type x)

2. 查找函數

set::iterator lower_bound(type x) 返回第一個>=x的元素的迭代器

3. 刪除函數 void erase(set::iterator iter)

=============================================

爲了防止意外，我使用了『同餘原理』，防止ans超過2^31。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25467

/*

*Problem: 寵物收養所 pet

*Author: Yee-fan Zhu

*Website: http://zhuyf.tk/

*Method: Balanced Tree 

         C++ Standard Templates Library: Set Container

*Cost: Total 310ms

*Memory: 499KB

*/

#include <cstdio>

#include <cstdlib>

#include <set>

#include <iterator>

using namespace std;

typedef set<int>  Set;



const int MOD=1000000;

int N;

Set Pet,Owner;



int abs(int x)

{return x>0?x:-x;}



int Maintenance(Set& A,Set& B,int m)

{

    int res=0;

    if(A.size()==0)

    {

        B.insert(m);

        return 0;

    }

    Set::iterator iter;

    iter=A.lower_bound(m);

    if(iter==A.end())

    {

        iter--;

        res=abs(*iter-m);

        A.erase(iter);

        return res;

    }

    if(*iter==m)

    {

        A.erase(iter);

        return 0;

    }

    if(iter==A.begin())

    {

        res=abs(*iter-m);

        A.erase(iter);

        return res;

    }

    Set::iterator tmp;

    res=abs(*iter-m);

    tmp=iter;

    

    iter--;

    if(abs(*iter-m)<=res)

    {

        res=abs(*iter-m);

        tmp=iter;

    }

    A.erase(tmp);

    return res;

}



void init()

{

    int Ans=0;

    scanf("%d\n",&N);

    int x,m;

    for(int i=1;i<=N;i++)

    {

        scanf("%d %d\n",&x,&m);

        if(!x)

            Ans+=Maintenance(Owner,Pet,m);

        else

            Ans+=Maintenance(Pet,Owner,m);

        Ans%=MOD;

    }    

    printf("%d\n",Ans);

}

 

int main()

{

    freopen("pet.in","r",stdin);

    freopen("pet.out","w",stdout);

    init();

    return 0;

}

USACO Contest Feb2012 Bronze Moo 翻譯+題解

2012-02-11T13:34:00.002+08:00

翻譯（質量不高，將就看吧）：
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。請你幫助他！

輸入：
11
輸出 :
m

【分析】
拿道這題，我首先想到了比這個題更難的『產生01串』
不要去考慮模擬，O(n)都已經到了10^9的境界......
=========為了敘述方便，以下把S(1)當作"moo"，以此類推。==========
由於S(k)=2*S(k-1)+k+2，所以logN是一個可行的時間複雜度。

1 3
2 10
3 25
4 56
5 119
6 246
7 501
8 1012
9 2035
10 4082
11 8177
12 16368
13 32751
14 65518
15 131053
16 262124
17 524267
18 1048554
19 2097129
20 4194280
21 8388583
22 16777190
23 33554405
24 67108836
25 134217699
26 268435426
27 536870881
28 1073741792

可以看出，只用開30個整型變量就能存下了。
然後就是找到N所在的位置，看N是介於在哪兩個串長度之間，然後把那個串分成三部分，如果處於兩邊，則遞歸下去，如果在中間直接輸出就可以了，就這樣，循環往復……

【我的代碼】
下載的測試數據自評滿分
裸代碼RawCode

C++语言: Codee#25478

/*

*Problem: USACO Feb12 Bronze Moo

*Author: Yee-fan Zhu

*Email: zyfworks@gmail.com

*/

#include <cstdio>

#include <cstdlib>

using namespace std;

int S[1000];

int N;

void CreateSequence()

{

    S[1]=3;

    for(int i=2;S[i-1]<=1000000000;i++)

    {

        S[i]=S[i-1]*2+i+2;

        //printf("%d %d\n",i,S[i]);

    }

}



void end()

{

    exit(0);

    return;

}



int GetPos(int x)

{

    int pos=0;

    for(;S[pos]<x;pos++);

    if(S[pos]==x)

    {

        printf("o\n");

        end();

    }

    return pos-1;

}



void work()

{

    int pos=GetPos(N)+1;

    int now;

    int mid;

    while(pos>1)

    {

        //pos=GetPos(N);

        now=N-S[pos-1];

        if(now==0)

        {

            printf("o\n");

            end();

        }

        if(now<0)

        {

            pos--;

            continue;

        }

        mid=pos+2;

        if(now==1)

        {

            printf("m\n");

            end();

        }

        if(now<=mid)

        {

            printf("o\n");

            end();

        }

        N=now-mid;

        pos--;

    }

    if(N==1)

        printf("m\n");

    if(N>1)

        printf("o\n");

    end();

}



int main()

{

    freopen("moo.in","r",stdin);

    freopen("moo.out","w",stdout);

    scanf("%d\n",&N);

    CreateSequence();

      work();

    return 0;

}

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

2012-02-11T12:49:00.000+08:00

連續素數和 題目來源：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 能表示成的連續素數和的種數。

【輸入格式】

* 每行一個正整數 N(2<=N<=10000) ，表示你要處理的數。當 N=0 時輸入結束。

【輸出格式】

* 對於每一個整數 N ，你要輸出它能表示成連續素數和的種數。

【輸入輸出樣例】

輸入

666

輸出

【分析】

COGS上寫的是貪心策略，但是我想了半天也不知道該如何貪，最後只好寫枚舉了。最後竟然還過了，只不過有點慢。

由於N<=10000，所以程序應先初始化出2～10000之間的素數表。

（我第一次提交時WA了，50分，原因是我只初始化了2～5003之間的素數表，畢竟題目中說“連續”嘛，至少應該有兩個加數～其實，在測試數據中，1個數也叫做『連續』）

然後暴力枚舉，你懂的～

【我的代碼】

裸代碼RawCode

C++语言: Codee#25466

/*

*Problem: POJ2739 conprime

*Author: Yee-fan Zhu

*GTalk: zyfworks@gmail.com

*Source: Japan2005

*/

#include <cstdio>

#include <cstdlib>

using namespace std;

const int MAXN=1500; 

const int MAXP=10000;

int P[MAXN+100];

int prime=0;

void Prime()

{

    P[++prime]=2;

    for(int i=3;i<=MAXP;i+=2)

    {

        bool flag=true;

        for(int j=2;j<=i/2;j++)

        {

            if(i%j==0)

            {

                flag=false;

                break;

            }

        }

        if(flag)

        {

            P[++prime]=i;

        }

    }

    /*

    for(int i=1;i<=prime;i++)

        printf("%d\n",P[i]);

    Test if the Primes are Correct

    */

}



int main()

{

    freopen("conprime.in","r",stdin);

    freopen("conprime.out","w",stdout);

    Prime();

    int N;

    scanf("%d\n",&N);

    int Res,ans;

    while(N)

    {

        Res=0;

        for(int i=1;i<=prime;i++)

        {

            ans=0;

            for(int j=i;j<=prime;j++)

            {

                ans+=P[j];

                if(ans>N)

                    break;

                if(ans==N)

                {

                    Res++;

                    break;

                }

            }

        }

        printf("%d\n",Res);

        scanf("%d\n",&N);

    }

    return 0;

}

Yeefan's Blog

Dijkstra with STL priority_queue 優先隊列

【轉載】淺談2—SAT問題

USACO Feb12 Bronze Rope Folding 折繩子 題解

USACO 2012 February Contest, Bronze Division

Problem 1. Rope Folding

並查集練習題 島國 jx 題解

OI練習題 式子 recursion

ACM/ICPC 小球鐘——時間與運動

圖論練習題 備用交換機 gd 題解

OI練習題 溶液模擬器 simulator

圖論練習題 圖的平方 ljb

圖論練習題 摔跤 rassle 題解

動態規劃練習題 相似基因 gene 題解

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

【拓撲排序練習題】課程安排問題 curriculum

【強連通分量】四面楚歌 virus 解題報告

NOIP1995 普及組 編碼問題 code

[動態規劃]Ural 1031 rail 火車票 解題報告

輸入

輸出

樣例輸入

樣例輸出

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

[動態規劃]OI練習題 最後的利益 9cwy 解題報告

[動態規劃]POI 1998 ple 潛水員問題 解題報告

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

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

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

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

USACO Contest Feb2012 Bronze Moo 翻譯+題解

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

USACO Feb12 Bronze Rope Folding 折繩子題解

並查集練習題島國 jx 題解

OI練習題式子 recursion

圖論練習題備用交換機 gd 題解

OI練習題溶液模擬器 simulator

圖論練習題圖的平方 ljb

圖論練習題摔跤 rassle 題解

動態規劃練習題相似基因 gene 題解

NOIP1995 普及組編碼問題 code

[動態規劃]Ural 1031 rail 火車票解題報告

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

[動態規劃]OI練習題最後的利益 9cwy 解題報告

[動態規劃]POI 1998 ple 潛水員問題解題報告