The Fourth Dimension Space

discovery(探索發(fā)現(xiàn))下載地址

posted @ 2009-08-26 11:18 abilitytao 閱讀(1500) | 評論 (0) | 編輯 收藏

差分約束系統(tǒng)(System Of Difference Constraints)

（本文假設(shè)讀者已經(jīng)有以下知識：最短路徑的基本性質(zhì)、Bellman-Ford算法。）
    比如有這樣一組不等式：
   

X1 - X2 <= 0 X1 - X5 <= -1 X2 - X5 <= 1 X3 - X1 <= 5 X4 - X1 <= 4 X4 - X3 <= -1 X5 - X3 <= -3 X5 - X4 <= -3

不等式組(1)

    全都是兩個(gè)未知數(shù)的差小于等于某個(gè)常數(shù)（大于等于也可以，因?yàn)樽笥页艘?1就可以化成小于等于）。這樣的不等式組就稱作差分約束系統(tǒng)。
    這個(gè)不等式組要么無解，要么就有無數(shù)組解。因?yàn)槿绻幸唤M解{X1, X2, ..., Xn}的話，那么對于任何一個(gè)常數(shù)k，{X1 + k, X2 + k, ..., Xn + k}肯定也是一組解，因?yàn)槿魏蝺蓚€(gè)數(shù)同時(shí)加一個(gè)數(shù)之后，它們的差是不變的，那么這個(gè)差分約束系統(tǒng)中的所有不等式都不會被破壞。
   
    差分約束系統(tǒng)的解法利用到了單源最短路徑問題中的三角形不等式。即對于任何一條邊u -> v，都有：

d(v) <= d(u) + w(u, v)

    其中d(u)和d(v)是從源點(diǎn)分別到點(diǎn)u和點(diǎn)v的最短路徑的權(quán)值，w(u, v)是邊u -> v的權(quán)值。
    顯然以上不等式就是d(v) - d(u) <= w(u, v)。這個(gè)形式正好和差分約束系統(tǒng)中的不等式形式相同。于是我們就可以把一個(gè)差分約束系統(tǒng)轉(zhuǎn)化成一張圖，每個(gè)未知數(shù)Xi對應(yīng)圖中的一個(gè)頂點(diǎn)Vi，把所有不等式都化成圖中的一條邊。對于不等式Xi - Xj <= c，把它化成三角形不等式：Xi <= Xj + c，就可以化成邊Vj -> Vi，權(quán)值為c。最后，我們在這張圖上求一次單源最短路徑，這些三角形不等式就會全部都滿足了，因?yàn)樗亲疃搪窂絾栴}的基本性質(zhì)嘛。
    話說回來，所謂單源最短路徑，當(dāng)然要有一個(gè)源點(diǎn)，然后再求這個(gè)源點(diǎn)到其他所有點(diǎn)的最短路徑。那么源點(diǎn)在哪呢？我們不妨自已造一個(gè)。以上面的不等式組為例，我們就再新加一個(gè)未知數(shù)X0。然后對原來的每個(gè)未知數(shù)都對X0隨便加一個(gè)不等式（這個(gè)不等式當(dāng)然也要和其它不等式形式相同，即兩個(gè)未知數(shù)的差小于等于某個(gè)常數(shù)）。我們索性就全都寫成Xn - X0 <= 0，于是這個(gè)差分約束系統(tǒng)中就多出了下列不等式：
   

X1 - X0 <= 0 X2 - X0 <= 0 X3 - X0 <= 0 X4 - X0 <= 0 X5 - X0 <= 0

不等式組(2)

    對于這5個(gè)不等式，也在圖中建出相應(yīng)的邊。最后形成的圖如下：

圖1

    圖中的每一條邊都代表差分約束系統(tǒng)中的一個(gè)不等式。現(xiàn)在以V0為源點(diǎn)，求單源最短路徑。最終得到的V0到Vn的最短路徑長度就是Xn的一個(gè)解啦。從圖1中可以看到，這組解是{-5, -3, 0, -1, -4}。當(dāng)然把每個(gè)數(shù)都加上10也是一組解：{5, 7, 10, 9, 6}。但是這組解只滿足不等式組(1)，也就是原先的差分約束系統(tǒng)；而不滿足不等式組(2)，也就是我們后來加上去的那些不等式。當(dāng)然這是無關(guān)緊要的，因?yàn)閄0本來就是個(gè)局外人，是我們后來加上去的，滿不滿足與X0有關(guān)的不等式我們并不在乎。
    也有可能出現(xiàn)無解的情況，也就是從源點(diǎn)到某一個(gè)頂點(diǎn)不存在最短路徑。也說是圖中存在負(fù)權(quán)的圈。這一點(diǎn)我就不展開了，請自已參看最短路徑問題的一些基本定理。

    其實(shí)，對于圖1來說，它代表的一組解其實(shí)是{0, -5, -3, 0, -1, -4}，也就是說X0的值也在這組解當(dāng)中。但是X0的值是無可爭議的，既然是以它作為源點(diǎn)求的最短路徑，那么源點(diǎn)到它的最短路徑長度當(dāng)然是0了。因此，實(shí)際上我們解的這個(gè)差分約束系統(tǒng)無形中又存在一個(gè)條件：

X0 = 0

    也就是說在不等式組(1)、(2)組成的差分約束系統(tǒng)的前提下，再把其中的一個(gè)未知數(shù)的值定死。這樣的情況在實(shí)際問題中是很常見的。比如一個(gè)問題表面上給出了一些不等式，但還隱藏著一些不等式，比如所有未知數(shù)都大于等于0或者都不能超過某個(gè)上限之類的。比如上面的不等式組(2)就規(guī)定了所有未知數(shù)都小于等于0。
   
    對于這種有一個(gè)未知數(shù)定死的差分約束系統(tǒng)，還有一個(gè)有趣的性質(zhì)，那就是通過最短路徑算法求出來的一組解當(dāng)中，所有未知數(shù)都達(dá)到最大值。下面我來粗略地證明一下，這個(gè)證明過程要結(jié)合Bellman-Ford算法的過程來說明。
    假設(shè)X0是定死的；X1到Xn在滿足所有約束的情況下可以取到的最大值分別為M1、M2、……、Mn（當(dāng)然我們不知道它們的值是多少）；解出的源點(diǎn)到每個(gè)點(diǎn)的最短路徑長度為D1、D2、……、Dn。
    基本的Bellman-Ford算法是一開始初始化D1到Dn都是無窮大。然后檢查所有的邊對應(yīng)的三角形不等式，一但發(fā)現(xiàn)有不滿足三角形不等式的情況，則更新對應(yīng)的D值。最后求出來的D1到Dn就是源點(diǎn)到每個(gè)點(diǎn)的最短路徑長度。
    如果我們一開始初始化D1、D2、……、Dn的值分別為M1、M2、……、Mn，則由于它們?nèi)紳M足三角形不等式（我們剛才已經(jīng)假設(shè)M1到Mn是一組合法的解），則Bellman-Ford算法不會再更新任合D值，則最后得出的解就是M1、M2、……、Mn。
    好了，現(xiàn)在知道了，初始值無窮大時(shí)，算出來的是D1、D2、……、Dn；初始值比較小的時(shí)候算出來的則是M1、M2、……、Mn。大家用的是同樣的算法，同樣的計(jì)算過程，總不可能初始值大的算出來的結(jié)果反而小吧。所以D1、D2、……、Dn就是M1、M2、……、Mn。
   
    那么如果在一個(gè)未知數(shù)定死的情況下，要求其它所有未知數(shù)的最小值怎么辦？只要反過來求最長路徑就可以了。最長路徑中的三角不等式與最短路徑中相反：

d(v) >= d(u) + w(u, v) 也就是 d(v) - d(u) >= w(u, v)

    所以建圖的時(shí)候要先把所有不等式化成大于等于號的。其它各種過程，包括證明為什么解出的是最小值的證法，都完全類似。
    
    用到差分約束系統(tǒng)的題目有ZJU 2770，祝好運(yùn)。

轉(zhuǎn)自：http://imlazy.ycool.com/post.1702305.html

posted @ 2009-08-21 23:34 abilitytao 閱讀(2328) | 評論 (6) | 編輯 收藏

POJ 3322 Bloxorz I(BFS, 改編自同名游戲，很不錯(cuò)的一題)

posted @ 2009-08-16 22:25 abilitytao 閱讀(1849) | 評論 (4) | 編輯 收藏

POJ 1631 Bridging signals——最長上升子序列 DP(nlogn)

#include<iostream>
#include<cstdio>
using namespace std;


const int N =  40000;

int a[N], C[N], f[N]; // f[i]用于記錄a[0i]的最大長度

int bsearch(const int *C, int size, const int &a) 

{
    
    int l=0, r=size-1;
    
    while( l <= r ) 
        
    {
        
        int mid = (l+r)/2;
        
        if( a > C[mid-1] && a <= C[mid] ) return mid; // >&&<= 換為: >= && <
        
        else if( a < C[mid] ) r = mid-1;
        
        else l = mid+1;
        
    }
    
}

int LIS(const int *a, const int &n){
    
    int i, j, size = 1;
    
    C[0] = a[0]; f[0] = 1;
    
    for( i=1; i < n; ++i ){
        
        if( a[i] <= C[0] ) j = 0;                 // <= 換為: <
        
        else if( a[i] >C[size-1] ) j = size++;   // > 換為: >= 
        
        else j = bsearch(C, size, a[i]);
        
        C[j] = a[i]; f[i] = j+1;
        
    }
    
    return size;
    
}



int main()
{
    int testcase;
    int n;
    scanf("%d",&testcase);
    int i,j;
    for(i=1;i<=testcase;i++)
    {
        scanf("%d",&n);
        for(j=0;j<n;j++)
            scanf("%d",&a[j]);
        printf("%d\n",LIS(a,n));
    }
    return 0;
}

posted @ 2009-08-12 19:14 abilitytao 閱讀(1855) | 評論 (1) | 編輯 收藏

最長不降子序列的nlogn算法 (轉(zhuǎn))

所謂“最長不降子序列問題”，就是在一個(gè)給定的序列中尋找一個(gè)子序列{ai}滿足:

                       a1<=a2<=...<an

這個(gè)問題在一般教材上，往往會作為動態(tài)規(guī)劃的引例。

即使用如下的狀態(tài)轉(zhuǎn)移方程進(jìn)行計(jì)算：

                   F[i]=max{F[j]}+1     aj<=ai

但是它的復(fù)雜度是O(n^2)的，對于稍大的規(guī)模便無法承受。

那么有沒有改進(jìn)的方法呢？答案是肯定的。

----------------------------------------------------------------分割線------------------------------------------------------------------------------------------

我們維護(hù)一個(gè)數(shù)組C[i]，這里C[i]表示F值為i的最小數(shù)。

不難發(fā)現(xiàn)   C[1]<=C[2]<=...<=C[n]

因此我們可以利用C[]通過二分查找確定F[j]的值。

----------------------------------------------------------------分割線------------------------------------------------------------------------------------------

實(shí)現(xiàn)如下：

const int N = 1001;

int a[N], C[N], f[N]; // f[i]用于記錄a[0...i]的最大長度

int bsearch(const int *C, int size, const int &a)

{

    int l=0, r=size-1;

    while( l <= r )

    {

        int mid = (l+r)/2;

        if( a > C[mid-1] && a <= C[mid] ) return mid; // >&&<= 換為: >= && <

        else if( a < C[mid] ) r = mid-1;

        else l = mid+1;

    }

}

int LIS(const int *a, const int &n){

     int i, j, size = 1;

     C[0] = a[0]; f[0] = 1;

     for( i=1; i < n; ++i ){

          if( a[i] <= C[0] ) j = 0;                 // <= 換為: <

         else if( a[i] >C[size-1] ) j = size++;   // > 換為: >=

         else j = bsearch(C, size, a[i]);

         C[j] = a[i]; f[i] = j+1;

     }

     return size;

}

------------------------------------------------------------------分割線------------------------------------------------------------------------------------------

至此，我們了解了O(nlogn)的算法，它主要是利用了二分查找的方法對樸素的動態(tài)規(guī)劃進(jìn)行加速、優(yōu)化，從而達(dá)到理想的效率。

posted @ 2009-08-12 18:27 abilitytao 閱讀(413) | 評論 (0) | 編輯 收藏

POJ 計(jì)算幾何入門題目推薦（轉(zhuǎn)）

posted @ 2009-08-07 01:15 abilitytao 閱讀(1776) | 評論 (0) | 編輯 收藏

POJ 1066——Treasure Hunt解題報(bào)告

我剛開始被這道題目的名字吸引了，因?yàn)樗蛯毑赜嘘P(guān)，呵呵^_^不過把題目讀完以后才發(fā)現(xiàn)這道題是個(gè)無聊的計(jì)算幾何題 ，說實(shí)話有點(diǎn)失望。。。

題目的大意是這樣的：尋寶者在一個(gè)被分割成很多房間的正方形迷宮里尋寶，這個(gè)迷宮是100*100的正方形而且四個(gè)頂點(diǎn)坐標(biāo)一定。尋寶者具有把墻鑿穿通過的能力，若尋寶者可以從正方形的任意一個(gè)邊界進(jìn)入，問到達(dá)藏寶地點(diǎn)最少要穿過幾道墻？

這個(gè)題的解法是：枚舉每一個(gè)入口。然后在所有的情況中取穿墻數(shù)最少的輸出即可。
考察每一個(gè)入口的時(shí)候，枚舉每條邊，如果起點(diǎn)和終點(diǎn)在這條直線的兩側(cè)，那么尋寶者一定要穿過一道墻。于是此題轉(zhuǎn)化成了判斷2點(diǎn)是否在一條直線的異側(cè)的問題。模板解決~

由于自己寫的有點(diǎn)冗長，于是參考了下網(wǎng)上的代碼，發(fā)現(xiàn)將所有邊界上的點(diǎn)按照角度排序的確是個(gè)很巧妙的方法，學(xué)習(xí)了^_^

//coded by abilitytao
//Time:2009年8月5日17:50:19

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
double const EPS = 1e-8;
const int INF = 0xf777777;
#define zero(x) (((x)>0?(x):-(x))<eps) 



struct Point
{
    double x,y;
    Point(){}
       Point(double a, double b):x(a), y(b){}
       bool operator<(Point a){return atan2(y - 50, x - 50) < atan2(a.y - 50, a.x - 50); }
}; 

struct Line// 定義一條線段，用起點(diǎn)和終點(diǎn)來表示 
{               
    Point a, b; 
    Line() {} 
    Line(Point p10, Point p20): a(p10), b(p20) {} //Line a(p1,p2);
}; 


Point mypoint[64], s, t;
Line myline[30];
int n, countnum, minnum;

double xmult(Point p1, Point p2 , Point p0)
{
    return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
}
int same_side(Point p1,Point p2,Line l)
{ 
    return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>EPS; 
}

int main()
{
    int i, j, ans;
    minnum = INF; countnum = 0;
    mypoint[countnum++] = Point(0, 0);
    mypoint[countnum++] = Point(100, 0);
    mypoint[countnum++] = Point(0, 100);
    mypoint[countnum++] = Point(100, 100);
    
    cin >> n;
    for(i = 0; i < n; i++)
    {
        scanf("%lf%lf%lf%lf",&myline[i].a.x ,&myline[i].a.y ,&myline[i].b.x ,&myline[i].b.y);
        mypoint[countnum++] = myline[i].a;
        mypoint[countnum++] = myline[i].b;
    }
    scanf("%lf%lf",&s.x,&s.y);
    
       sort(mypoint, mypoint+countnum);
       
       for(i=0;i<countnum;i++ )
       {
           ans = 0;
           t = Point( (mypoint[i].x + mypoint[(i+1)%countnum].x)/2, (mypoint[i].y + mypoint[(i+1)%countnum].y)/2 );
           for(j = 0; j < n; j++)          
               if(!same_side(s, t, myline[j]))
                   ans++;
            if(ans <minnum) minnum = ans;
       }
       
       printf("Number of doors = %d\n", minnum+1);
       return 0;
}

posted @ 2009-08-05 23:58 abilitytao 閱讀(1563) | 評論 (0) | 編輯 收藏

2009年ACM-ICPC亞洲區(qū)預(yù)選賽共設(shè)十五個(gè)賽區(qū)如下(按現(xiàn)場賽日期排序):

1、Harbin 哈爾濱賽區(qū)（哈爾濱工業(yè)大學(xué)）
網(wǎng)絡(luò)選拔賽日期：2009年9月13日 14:00-17:00
現(xiàn)場賽日期：2009年9月26日～27日
http://acm.hit.edu.cn/

2、Dhaka 達(dá)卡賽區(qū)（孟加拉國 Northsouth University）
現(xiàn)場賽日期：2009年10月3日
http://www.northsouth.edu/acm/

3、Gwalior-Kanpur 瓜廖爾-坎普爾賽區(qū)（印度 IIITM Gwalior and Indian Institute of Technology, India）
現(xiàn)場賽日期：2009年10月3日～4日
http://www.cse.iitk.ac.in/users/acm/

4、Hefei 合肥賽區(qū)（中國科學(xué)技術(shù)大學(xué)）
網(wǎng)絡(luò)選拔賽日期：2009年9月6日 14:00-17:00
現(xiàn)場賽日期：2009年10月10日～11日
http://acm.ustc.edu.cn/

5、Ningbo 寧波賽區(qū)（浙江大學(xué)寧波理工學(xué)院）
網(wǎng)絡(luò)選拔賽日期：2009年9月12日
現(xiàn)場賽日期：2009年10月17日～18日
http://acmasia09.nit.net.cn/

6、Jakarta 雅加達(dá)賽區(qū)（印尼 Binus University）
現(xiàn)場賽日期：2009年10月21日
http://icpc.ewubd.edu/

7、Manila 馬尼拉賽區(qū)（菲律賓 Ateneo de Manila University）
現(xiàn)場賽日期：2009年10月22日～23日
http://www.math.admu.edu.ph/acm/

8、Shanghai 上海賽區(qū)（東華大學(xué)）
網(wǎng)絡(luò)選拔賽日期：2009年9月20日(12:00-17:00)
現(xiàn)場賽日期：2009年10月24日～25日
http://acm.dhu.edu.cn

9、Hsinchu 新竹賽區(qū)（交通大學(xué)）
報(bào)名截止日期：2009年8月19日
現(xiàn)場賽日期：2009年10月30日～31日
http://icpc2009.nctu.edu.tw/

10、Wuhan 武漢賽區(qū)（武漢大學(xué)）
網(wǎng)絡(luò)選拔賽日期：2009年10月3
現(xiàn)場賽日期：2009年10月31日～11月1日
http://acm.whu.edu.cn/

11、Amritapuri 阿姆里塔普里賽區(qū)（印度 Amrita Vishwa Vidyapeetham, Amritapuri Campus）
現(xiàn)場賽日期：2009年11月1日
http://icpc.amrita.ac.in/

12、Phuket 普吉島賽區(qū)（泰國 Prince of Songkla University, Phuket Campus）
報(bào)名截止日期：2009年9月30日
現(xiàn)場賽日期：2009年11月3日～4日
http://www.acmicpc-thailand.org/

13、Seoul 首爾賽區(qū)（韓國 Korea Advanced Institute of Science and Technology）
報(bào)名截止日期：2009年9月11日
現(xiàn)場賽日期：2009年11月5日～6日
http://acm.kaist.ac.kr/

14、Tehran 德黑蘭賽區(qū)（伊朗 Sharif University of Technology）
現(xiàn)場賽日期：2009年11月6日
http://sharif.edu/~acmicpc

15、Tokyo 東京賽區(qū)（日本早稻田大學(xué)）
現(xiàn)場賽日期：2009年11月7日～8日
http://www.waseda.jp/assoc-icpc2009/en/index.html

參賽報(bào)名網(wǎng)址

http://cm.baylor.edu/welcome.icpc

亞洲高校可組隊(duì)參加全部十五個(gè)賽區(qū)的預(yù)選賽，但每位參賽選手最多只能注冊參加兩個(gè)賽區(qū)的預(yù)選賽。

posted @ 2009-08-04 17:08 abilitytao 閱讀(1726) | 評論 (0) | 編輯 收藏

計(jì)算幾何模板整理

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

struct Point // 定義一個(gè)點(diǎn)
{              
    double x, y;  
    Point() {} 
    Point(double x0, double y0): x(x0), y(y0) {} //Point a(1.0,2.0);
}; 

struct Line// 定義一條線段，用起點(diǎn)和終點(diǎn)來表示 
{               
    Point p1, p2; 
    Line() {} 
    Line(Point p10, Point p20): p1(p10), p2(p20) {} //Line a(p1,p2);
}; 

//定義叉積：
//1.如果返回值為正數(shù)，表明sp在op->ep（op指向ep)這條射線的順時(shí)針方向；
//2.如果返回值為負(fù)數(shù)，表明sp在op->ep（op指向ep)這條射線的逆時(shí)針方向；
//3.如果返回值為0，表明三點(diǎn)共線
double multiply(Point sp,Point ep,Point op)
{
    return((sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y));
}

posted @ 2009-08-04 16:35 abilitytao 閱讀(226) | 評論 (0) | 編輯 收藏

POJ 2318 toys 叉積的簡單運(yùn)用

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

struct Point 
{              // 二維點(diǎn)或矢量 
    double x, y;  
    Point() {} 
    Point(double x0, double y0): x(x0), y(y0) {} 
}; 

struct Line
 {               // 二維的直線或線段 
    Point p1, p2; 
    Line() {} 
    Line(Point p10, Point p20): p1(p10), p2(p20) {} 
}; 


double multiply(Point sp,Point ep,Point op)
{
    return((sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y));
}



Line myline[5100];
int record[5100];


int main()
{

    int n,m,i;
    Point left;
    Point right;
    while(scanf("%d",&n))
    {

        if(n==0)
            break;
        memset(record,0,sizeof(record));
        scanf("%d%lf%lf%lf%lf",&m,&left.x,&left.y,&right.x,&right.y);
        myline[0].p1.x=left.x;
        myline[0].p1.y=right.y;
        myline[0].p2.x=left.x;
        myline[0].p2.y=left.y;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf",&myline[i].p2.x,&myline[i].p1.x);
            myline[i].p1.y=right.y;
            myline[i].p2.y=left.y;

        }
        myline[n+1].p1.x=right.x;
        myline[n+1].p1.y=right.y;
        myline[n+1].p2.x=right.x;
        myline[n+1].p2.y=left.y;
        
        Point toy;
        for(i=1;i<=m;i++)
        {
            scanf("%lf%lf",&toy.x,&toy.y);
            int front=0;
            int rear=n+1;
            while(front<=rear)
            {

                int mid=(front+rear)>>1;
                if(multiply(toy,myline[front].p2,myline[front].p1)>0&&multiply(toy,myline[mid].p2,myline[mid].p1)<0)
                {

                    if(mid==front+1)
                    {
                        record[front]++;
                        break;
                    }
                    rear=mid;
                    continue;
                }
                else
                {

                    if(mid+1==rear)
                    {
                        record[mid]++;
                        break;
                    }
                    front=mid;
                    continue;
                }

            }
        }

        for(i=0;i<=n;i++)
        {
            printf("%d: %d\n",i,record[i]);
        }
        printf("\n");
    }
    return 0;
}

posted @ 2009-08-04 16:26 abilitytao 閱讀(946) | 評論 (1) | 編輯 收藏