色综合久久中文字幕综合网,久久精品国产乱子伦,亚洲а∨天堂久久精品9966

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�q�ACM-ICPC亚洲区预选赛��p��十五个赛区如�?按现��日期排序)

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

1、Harbin 哈尔滨赛区（哈尔滨工业大学）
�|�络选拔赛日期：2009�q?�?3�?14:00-17:00
现场赛日期：2009�q?�?6日～27�?br>http://acm.hit.edu.cn/

2、Dhaka 辑֍�赛区�Q�孟加拉�?Northsouth University�Q?br>现场赛日期：2009�q?0�?�?br>http://www.northsouth.edu/acm/

3、Gwalior-Kanpur 瓜廖��?坎普��赛区（印度 IIITM Gwalior and Indian Institute of Technology, India�Q?br>现场赛日期：2009�q?0�?日～4�?br>http://www.cse.iitk.ac.in/users/acm/

4、Hefei 合肥赛区�Q�中国科学技术大学）
�|�络选拔赛日期：2009�q?�?�?14:00-17:00
现场赛日期：2009�q?0�?0日～11�?br>http://acm.ustc.edu.cn/

5、Ningbo 宁�L赛区�Q�浙江大学宁波理工学院）
�|�络选拔赛日期：2009�q?�?2�?br>现场赛日期：2009�q?0�?7日～18�?br>http://acmasia09.nit.net.cn/

6、Jakarta 雅加达赛区（印尼 Binus University�Q?br>现场赛日期：2009�q?0�?1�?br>http://icpc.ewubd.edu/

7、Manila 马尼拉赛区（菲律�?Ateneo de Manila University�Q?br>现场赛日期：2009�q?0�?2日～23�?br>http://www.math.admu.edu.ph/acm/

8、Shanghai 上�v赛区�Q�东华大学）
�|�络选拔赛日期：2009�q?�?0�?12:00-17:00)
现场赛日期：2009�q?0�?4日～25�?br>http://acm.dhu.edu.cn

9、Hsinchu 新竹赛区�Q�交通大学）
报名截止日期�Q?009�q?�?9�?br>现场赛日期：2009�q?0�?0日～31�?br>http://icpc2009.nctu.edu.tw/

10、Wuhan 武汉赛区�Q�武汉大学）
�|�络选拔赛日期：2009�q?0�?
现场赛日期：2009�q?0�?1日～11�?�?br>http://acm.whu.edu.cn/

11、Amritapuri 阿姆里塔普里赛区�Q�印�?Amrita Vishwa Vidyapeetham, Amritapuri Campus�Q?br>现场赛日期：2009�q?1�?�?br>http://icpc.amrita.ac.in/

12、Phuket 普吉岛赛区（泰国 Prince of Songkla University, Phuket Campus�Q?br>报名截止日期�Q?009�q?�?0�?br>现场赛日期：2009�q?1�?日～4�?br>http://www.acmicpc-thailand.org/

13、Seoul 首尔赛区�Q�韩�?Korea Advanced Institute of Science and Technology�Q?br>报名截止日期�Q?009�q?�?1�?br>现场赛日期：2009�q?1�?日～6�?br>http://acm.kaist.ac.kr/

14、Tehran 德黑兰赛区（伊朗 Sharif University of Technology�Q?br>现场赛日期：2009�q?1�?�?br>http://sharif.edu/~acmicpc

15、Tokyo 东京赛区�Q�日本早�Eȝ��大学�Q?br>现场赛日期：2009�q?1�?日～8�?br>http://www.waseda.jp/assoc-icpc2009/en/index.html

参赛报名�|�址

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

亚洲高校可组队参加全部十五个赛区的预选赛�Q�但每位参赛选手最多只能注册参�?strong>两个赛区的预选赛�?/p>

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

acmer必看�?6个对acm态度

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

Attempt

Keep on attempting!

��试�Q?/font>��试�Q�再��试�Q?/font>

Bravery

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

勇敢地跨�q?font face="Batang, 바탕, serif">�?/font>�?font face="Batang, 바탕, serif">�Q�成功就在前斏V�?/font>

Cooperation

It is teamwork, you are not alone.

我们是作��Z��个团队一起努力的�?/font>

Diligence

Working hard, and bear abundant fruit.

一份耕耘，一份收��P��

Enjoy

Enjoy the work.

态度军_��一切，ACM-ICPC是快乐的�Q?/font>

Facility

Facility in programming promise the champion.

扎实的编�E�能力是夺冠的有力支柱�?/font>

Galaxy

ACM-ICPC is just a galaxy.

��英聚会�Ҏ(gu��)��王者本艌Ӏ?/font>

Honor

It is great honor to try the contest.

ACM�Q�一�ơ无�(zh��n)�的��试�Q�一�D늲�彩的人生�?/font>

Intelligence

Who is the cleverest?

一场智慧的较量�?/font>

Judger

Judge in the contest as God in the world.

裁判�?/font>ACM�Q�就如同上帝于世界�?

Knotty

The way to champion is knotty.

冠军之�\铺满荆棘�?/font>

Lucky

Luck permits!

ACM�Q�一切皆有可能�?/font>

Magic

Magic ideas work wonder.

灵光一闪的瞬间�Q�我们知�?/font>ACM原来是一场神话的挑战�?/font>

Naturally

It’s naturally for us to win the ACM.

用我们的胜利来诠释曾�l�的努力�Q�艰辛和坚信�Q?/font>

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!

我爱你们�Q�亲��q��爸爸妈妈~

Quality

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

��L��更闪亮的星耀��g��深邃的夜�I?#8230;

Schedule

There always exists something out of schedule.

从时间表上我们看见催促看见赛�E�还有气球、还有未�?#8230;

Team

The honor belongs to our team! Come on!

一切来�?/font>ACM的契机，感激他让我们相识�?/font>

University

Shang hai Jiaotong University records my growing.

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

Victory

Two for victory~

永远记得对着镜头我们的笑那么灿烂�?/font>

Wing

We came to the fore, flew without wings.

是天使赋予了我飞��的��膀�Q�我用它举�v�?/font>ACM的奖杯�?/font>

We fight against the x!

面对未知�Q�是我们睁大好奇的双��|��也是我们无畏的向前，奔�ʎ�q�方�?/font>

Yesterday

Yesterday once more.

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

Zero

All begin with zero…

我们站在新的��L��上，整装待发�Q?/font>

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 发表评论