C++博客-算法学习

换个博客，重新开始学习。。。

Darren — Thu, 29 Apr 2010 16:52:00 GMT

Darren 2010-04-30 00:52 发表评论

pku 1691 Painting A Board 状态压缩DP

Darren — Thu, 08 Oct 2009 06:54:00 GMT

#include < stdio.h >
#include < stdlib.h >
#include < string .h >

int const inf = 1 << 29 ;
int n;
struct Point {
     int Lx, Ly, Rx, Ry;
} ;

Point pnt[ 16 ];
int   need[ 16 ], dp[ 1 << 15 ][ 15 ], color[ 16 ];

void init() {
     for ( int i = 0 ; i <= n; ++ i ) need[i] = 0 ;

     for ( int i = 0 ; i < n; ++ i ) {
         for ( int j = 0 ; j < n; ++ j ) {
             if ( i == j ) continue ;

             if ( pnt[j].Ry <= pnt[i].Ly && pnt[j].Lx < pnt[i].Rx ) {
                need[i] |= ( 1 << j);
            }
        }
    }
}

void solve() {
     for ( int i = 0 ; i < ( 1 << n); ++ i )
         for ( int j = 0 ; j < n; ++ j ) dp[i][j] = inf;

    dp[ 0 ][ 0 ] = 0 ;
     for ( int i = 0 ; i < n; ++ i )
         if ( need[i] == 0 ) dp[ 1 << i][i] = 1 ;

     for ( int s = 0 ; s < ( 1 << n); ++ s ) {
         for ( int i = 0 ; i < n; ++ i ) {
             if ( ( s & ( 1 << i) ) == 0 ) continue ;

             for ( int j = 0 ; j < n; ++ j ) {
                 if ( s & ( 1 << j) ) continue ;
                 if ( (s & need[j]) != need[j] ) continue ;

                 if ( dp[s][i] + ( color[i] != color[j] ) < dp[s | ( 1 << j)][j] ) {
                    dp[s | ( 1 << j)][j] = dp[s][i] + ( color[i] != color[j] );
                }
            }
        }
    }

     int ans = inf;
     for ( int i = 0 ; i < n; ++ i )
         if ( dp[( 1 << n) - 1 ][i] < ans ) ans = dp[( 1 << n) - 1 ][i];

    printf( " %d\n " , ans );
}

int main() {
     int test;
    scanf( " %d " , & test );

     while ( test -- ) {
        scanf( " %d " , & n );

         for ( int i = 0 ; i < n; ++ i ) {
            scanf( " %d%d%d%d " , & pnt[i].Ly, & pnt[i].Lx, & pnt[i].Ry,   & pnt[i].Rx );
            scanf( " %d " , color + i );
        }

        init();
        solve();
    }

     return 0 ;
}

Darren 2009-10-08 14:54 发表评论

HDU 1255

Darren — Thu, 06 Aug 2009 01:59:00 GMT

#include < iostream >
#include < algorithm >

using namespace std;

#define N 2110

struct Tree {
     double length, len;
     int     cnt;
    Tree() { length = 0 ; cnt = 0 ; }
     void init() { length = 0 ; cnt = 0 ; len = 0 ; }
} tb[ 10100 ];

double x1[N], y1[N], x2[N], y2[N], xx[N], idx[N];
int pos, n;

struct Line {
     double y, x1, x2;
     bool type;
} line[N];

bool operator < ( Line const & a, Line const & b ) {
     return a.y < b.y; }

inline int bsearch( double value ) {
     int low = 1 , high = pos + 1 ;
     while ( low <= high ) {
         int mid = (low + high) >> 1 ;
         if ( idx[mid] > value ) high = mid - 1 ;
         else if ( idx[mid] < value ) low = mid + 1 ;
         else return mid; }
}

inline void update( int rt, int l, int r ) {
     if ( tb[rt].cnt ) tb[rt].length = idx[r] - idx[l];
     else if ( l + 1 == r ) tb[rt].length = 0 ;
     else tb[rt].length = tb[rt << 1 ].length + tb[(rt << 1 ) + 1 ].length;
}

inline void update2( int rt, int l, int r ) {
     if ( tb[rt].cnt > 1 ) tb[rt].len = idx[r] - idx[l];
     else if ( tb[rt].cnt == 1 ) tb[rt].len = tb[rt << 1 ].length + tb[(rt << 1 ) + 1 ].length;
     else tb[rt].len = tb[rt << 1 ].len + tb[(rt << 1 ) + 1 ].len; }

void deal( int rt, int l, int r, int a, int b, int t ) {
     if ( a <= l && b >= r ) {
        tb[rt].cnt += t; update( rt, l, r ); update2( rt, l, r );   return ; }

     int mid = (l + r) >> 1 ;
     if ( a < mid ) deal( rt << 1 , l, mid, a, b, t);
     if ( b > mid ) deal( (rt << 1 ) + 1 , mid, r, a, b, t );

    update( rt, l, r ); update2( rt, l, r );
}

int main() {
     int test = 1 ;
    scanf( " %d " , & test );
     while ( test -- ) {
        scanf( " %d " , & n);
         for ( int i = 0 ; i <= 10000 ; ++ i ) tb[i].init();
         for ( int i = 0 ; i < n; ++ i ) {
            scanf( " %lf%lf%lf%lf " , x1 + i, y1 + i, x2 + i, y2 + i );
            line[ 2 * i].y = y1[i];   line[ 2 * i].x1 = x1[i];
            line[ 2 * i].x2 = x2[i];  line[ 2 * i].type = 0 ;

            xx[ 2 * i] = x1[i]; xx[ 2 * i + 1 ] = x2[i];
            line[ 2 * i + 1 ].y = y2[i];  line[ 2 * i + 1 ].x1 = x1[i];
            line[ 2 * i + 1 ].x2 = x2[i]; line[ 2 * i + 1 ].type = 1 ;
        }
        sort( xx, xx + 2 * n );    sort( line, line + 2 * n );
        pos = 1 ; idx[ 1 ] = xx[ 0 ];
         for ( int i = 1 ; i < 2 * n; ++ i )
         if ( xx[i] != xx[i - 1 ] ) idx[ ++ pos] = xx[i];

         double ans = 0 ;
         for ( int i = 0 ; i < 2 * n - 1 ; ++ i ) {
             int u = bsearch( line[i].x1 ), v = bsearch( line[i].x2 );
             if ( line[i].type == 0 ) deal( 1 , 1 , pos, u, v, 1 );
             else deal( 1 , 1 , pos, u, v, - 1 );

            ans += tb[ 1 ].len * ( line[i + 1 ].y - line[i].y );
        }
        printf( " %.2lf\n " , ans );
    }

     return 0 ;
}

Darren 2009-08-06 09:59 发表评论

PKU　　1151

Darren — Wed, 05 Aug 2009 16:49:00 GMT

摘要: #include < iostream > #include < algorithm > using namespace std; ... 阅读全文

Darren 2009-08-06 00:49 发表评论

2009年ACM-ICPC亚洲区预选赛共设十五个赛区如下(按现场赛日期排序)

Darren — Tue, 04 Aug 2009 13:35:00 GMT

1、Harbin 哈尔滨赛区（哈尔滨工业大学）
网络选拔赛日期：2009年9月13日 14:00-17:00
现场赛日期：2009年9月26日～27日
http://acm.hit.edu.cn/

2、Dhaka 达卡赛区（孟加拉国 Northsouth University）
现场赛日期：2009年10月3日
http://www.northsouth.edu/acm/

3、Gwalior-Kanpur 瓜廖尔-坎普尔赛区（印度 IIITM Gwalior and Indian Institute of Technology, India）
现场赛日期：2009年10月3日～4日
http://www.cse.iitk.ac.in/users/acm/

4、Hefei 合肥赛区（中国科学技术大学）
网络选拔赛日期：2009年9月6日 14:00-17:00
现场赛日期：2009年10月10日～11日
http://acm.ustc.edu.cn/

5、Ningbo 宁波赛区（浙江大学宁波理工学院）
网络选拔赛日期：2009年9月12日
现场赛日期：2009年10月17日～18日
http://acmasia09.nit.net.cn/

6、Jakarta 雅加达赛区（印尼 Binus University）
现场赛日期：2009年10月21日
http://icpc.ewubd.edu/

7、Manila 马尼拉赛区（菲律宾 Ateneo de Manila University）
现场赛日期：2009年10月22日～23日
http://www.math.admu.edu.ph/acm/

8、Shanghai 上海赛区（东华大学）
网络选拔赛日期：2009年9月20日(12:00-17:00)
现场赛日期：2009年10月24日～25日
http://acm.dhu.edu.cn

9、Hsinchu 新竹赛区（交通大学）
报名截止日期：2009年8月19日
现场赛日期：2009年10月30日～31日
http://icpc2009.nctu.edu.tw/

10、Wuhan 武汉赛区（武汉大学）
网络选拔赛日期：2009年10月3
现场赛日期：2009年10月31日～11月1日
http://acm.whu.edu.cn/

11、Amritapuri 阿姆里塔普里赛区（印度 Amrita Vishwa Vidyapeetham, Amritapuri Campus）
现场赛日期：2009年11月1日
http://icpc.amrita.ac.in/

12、Phuket 普吉岛赛区（泰国 Prince of Songkla University, Phuket Campus）
报名截止日期：2009年9月30日
现场赛日期：2009年11月3日～4日
http://www.acmicpc-thailand.org/

13、Seoul 首尔赛区（韩国 Korea Advanced Institute of Science and Technology）
报名截止日期：2009年9月11日
现场赛日期：2009年11月5日～6日
http://acm.kaist.ac.kr/

14、Tehran 德黑兰赛区（伊朗 Sharif University of Technology）
现场赛日期：2009年11月6日
http://sharif.edu/~acmicpc

15、Tokyo 东京赛区（日本早稻田大学）
现场赛日期：2009年11月7日～8日
http://www.waseda.jp/assoc-icpc2009/en/index.html

参赛报名网址

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

亚洲高校可组队参加全部十五个赛区的预选赛，但每位参赛选手最多只能注册参加两个赛区的预选赛。

Darren 2009-08-04 21:35 发表评论

acmer必看的26个对acm态度

Darren — Mon, 03 Aug 2009 14:05:00 GMT

Attempt

Keep on attempting!

尝试，尝试，再尝试！

Bravery

Never lose heart, be sure you are brave enough to face failure!

勇敢地跨过失败，成功就在前方。

Cooperation

It is teamwork, you are not alone.

我们是作为一个团队一起努力的。

Diligence

Working hard, and bear abundant fruit.

一份耕耘，一份收获！

Enjoy

Enjoy the work.

态度决定一切，ACM-ICPC是快乐的！

Facility

Facility in programming promise the champion.

扎实的编程能力是夺冠的有力支柱。

Galaxy

ACM-ICPC is just a galaxy.

群英聚会方显王者本色。

Honor

It is great honor to try the contest.

ACM，一次无悔的尝试，一段精彩的人生。

Intelligence

Who is the cleverest?

一场智慧的较量。

Judger

Judge in the contest as God in the world.

裁判于ACM，就如同上帝于世界。

Knotty

The way to champion is knotty.

冠军之路铺满荆棘。

Lucky

Luck permits!

ACM，一切皆有可能。

Magic

Magic ideas work wonder.

灵光一闪的瞬间，我们知道ACM原来是一场神话的挑战。

Naturally

It’s naturally for us to win the ACM.

用我们的胜利来诠释曾经的努力，艰辛和坚信！

Objective

To achieve the objective is always in the next second…

或许我们更大的收获在于我们之间许下牢不可破的誓言…

Parents

On this long hard load, we wonder, we hesitate. It’s your power push me forward, my parents!

我爱你们！亲爱的爸爸妈妈~

Quality

The quality of a contest should be focus on person rather than skill.

总有更闪亮的星耀眼于深邃的夜空…

Schedule

There always exists something out of schedule.

从时间表上我们看见催促看见赛程还有气球、还有未来…

Team

The honor belongs to our team! Come on!

一切来自ACM的契机，感激他让我们相识。

University

Shang hai Jiaotong University records my growing.

也许有一天思源湖会冠上我的名字~

Victory

Two for victory~

永远记得对着镜头我们的笑那么灿烂。

Wing

We came to the fore, flew without wings.

是天使赋予了我飞翔的翅膀，我用它举起了ACM的奖杯。

We fight against the x!

面对未知，是我们睁大好奇的双眼，也是我们无畏的向前，奔赴远方。

Yesterday

Yesterday once more.

回眸那些辉煌，唯有忘却才能凯旋！

Zero

All begin with zero…

我们站在新的起点上，整装待发！

Darren 2009-08-03 22:05 发表评论

ZJU 3228 Searching the String ( AC 自动机 )

Darren — Sun, 02 Aug 2009 14:05:00 GMT

摘要: #include < iostream > #include < queue > using namespace std; #define N 100010 ... 阅读全文

Darren 2009-08-02 22:05 发表评论

Pku 3169 Layout

Darren — Mon, 20 Jul 2009 11:55:00 GMT

#include < stdio.h >
#include < stdlib.h >
#include < string .h >

#define N 1005
#define inf 1<<29

struct Edge{
     int u, v, d;
    Edge( int a = 0 , int b = 0 , int c = 0 ):
        u(a), v(b), d(c) {}
};

int n, ml, md, s = 0 ;
Edge  ege[ 20010 ];
int dist[N];

int bell_man(){
     for ( int i = 1 ; i <= n; ++ i ) dist[i] = inf;
    dist[ 1 ] = 0 ;

     int flag = 0 ;
     for ( int i = 1 ; i <= n; ++ i ){
        flag = 0 ;
         for ( int j = 0 ; j < s; ++ j ){
             int u = ege[j].u, v = ege[j].v, w = ege[j].d;
             if ( dist[u] + w < dist[v] ) dist[v] = dist[u] + w, flag = 1 ;
        }
         if ( ! flag ) break ;
    }
     if ( flag ) return - 1 ;
     else if ( dist[n] == inf ) return - 2 ;
     else return dist[n];
}

int main(){
    scanf( " %d%d%d " , & n, & ml, & md );
     int u, v, d;
     while ( ml -- ){
        scanf( " %d%d%d " , & u, & v, & d );
        ege[s ++ ] = Edge( u, v, d );
    }
     while ( md -- ){
        scanf( " %d%d%d " , & u, & v, & d );
        ege[s ++ ] = Edge( v, u, - d );
    }
    printf( " %d\n " , bell_man() );

     return 0 ;
}

Darren 2009-07-20 19:55 发表评论

Pku 1986 Distance Queries

Darren — Mon, 20 Jul 2009 02:56:00 GMT

#include < iostream >
#include < vector >

using namespace std;

#define N 40010
typedef pair < int , int > PAIR;

int m, n;
vector < PAIR > query[N], map[N];

int uset[N] = { 0 }, acs[N], flag[N] = { 0 }, dis[N] = { 0 }, ans[N], visite[N] = { 0 };

int find( int x ){
     while ( x != uset[x] ) x = uset[x];
     return x; }

void join( int x, int y ){  uset[ find(x) ] = uset[ find(y) ]; }

void dfs( int u, int d ){
    uset[u] = u; acs[u] = u; dis[u] = d; visite[u] = 1 ;
     for ( size_t i = 0 ; i < map[u].size(); ++ i ){
         int v = map[u][i].first, w = map[u][i].second;
         if ( ! visite[v] ){
            dfs( v, d + w );
            join( u, v ); acs[ find(u) ] = u;  }
    }

    flag[u] = 1 ;
     for ( size_t i = 0 ; i < query[u].size(); ++ i ){
         int v = query[u][i].first, w = query[u][i].second;

         if ( flag[v] ) ans[w] = dis[u] + dis[v] - 2 * dis[ acs[ find(v) ] ];
    }
}

int main(){
     int u, v, d;
     char s[ 10 ];

    scanf( " %d%d " , & n, & m);
     while ( m -- ){
        scanf( " %d%d%d%s " , & u, & v, & d,s );
        map[u].push_back( PAIR(v,d) );
        map[v].push_back( PAIR(u,d) );
    }

    scanf( " %d " , & m );
     for ( int i = 1 ; i <= m; ++ i ){
        scanf( " %d%d " , & u, & v );
        query[u].push_back( PAIR(v,i) );
        query[v].push_back( PAIR(u,i) );
    }
    memset( flag, 0 , sizeof (flag) );
    memset( visite, 0 , sizeof (visite) );

    dfs( 1 , 0 );
     for ( int i = 1 ; i <= m; ++ i ) printf( " %d\n " , ans[i] );

     return 0 ;
}

Darren 2009-07-20 10:56 发表评论

Pku 1276 Cash Machine

Darren — Sun, 19 Jul 2009 05:44:00 GMT

#include < iostream >

using namespace std;

#define N 100001

int nk[ 11 ], dk[ 11 ], n, m, ans[N], num[N];

int main(){
     while ( scanf( " %d%d " , & m, & n ) != EOF ){
         for ( int i = 0 ; i < n; ++ i ) scanf( " %d%d " , nk + i, dk + i );
         for ( int i = 0 ; i <= m; ++ i ) ans[i] = 0 ; ans[ 0 ] = 1 ;

         for ( int i = 0 ; i < n; ++ i ){
             for ( int j = 0 ; j <= m; ++ j ) num[j] = 0 ;

             for ( int j = dk[i]; j <= m; ++ j )
             if ( ! ans[j] && ans[j - dk[i]] && num[j - dk[i]] < nk[i] ){
                num[j] = num[j - dk[i]] + 1 ;
                ans[j] = 1 ; }
        }

         int res = m;
         while ( ans[res] == 0 && res >= 1 ) res -- ;
        printf( " %d\n " , res );
    }

     return 0 ;
}

Darren 2009-07-19 13:44 发表评论