M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

2010年12月8日

此blog废掉啦~

       请访问http://www.orzminjie.info/

posted @ 2010-12-08 22:59 M.J 阅读(227) | 评论 (0)编辑 收藏

2010年7月8日

求树的直径

              树的直径是指树的最长简单路。求法: 两遍BFS :先任选一个起点BFS找到最长路的终点,再从终点进行BFS,则第二次BFS找到的最长路即为树的直径;
              原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点
              证明: 1) 如果u 是直径上的点,则v显然是直径的终点(因为如果v不是的话,则必定存在另一个点w使得u到w的距离更长,则于BFS找到了v矛盾)
                      2) 如果u不是直径上的点,则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了
                       所以v一定是直径的一个端点,所以从v进行BFS得到的一定是直径长度

              相关题目有TOJ1056,TOJ3517.

TOJ 1056(Labyrinth):
        大意是一个由‘#’和'.'构成的迷宫,'.'表示可行,‘#’表示不可行,问可行的最长的路的长度是多少。

#include <cstdio>
#include 
<cstring>
#include 
<queue>
#define M 1002

using namespace std;

int r,c;
char map[M][M];
bool flag[M][M];
int move[4][2]={-1,0,1,0,0,-1,0,1};                                               // 分别表示上下左右
int maxt;
struct Node{
        
int x,y,num;
};
Node ans;
bool legal(int x,int y){                                                                   //判断该点是否越界及是否可走
        if(x >=0 && x < r && y>=0 && y < c &&map[x][y]=='.'return true;
        
return false;
}
void bfs(Node start){
        memset(flag,
false,sizeof(flag));                                               //初始所有点标记为false
        flag[start.x][start.y] = true;                                                    //起点标记为true
        queue<Node>f;
        
while(!f.empty()) f.pop();                                                       //清空创建的队列
        Node m,n,tep;
        
int tx,ty,xx,yy;
        
int i,j,k,num;
        f.push(start);
        
while(!f.empty()){                                                                   //如果队列不为空
                m = f.front();                                                                   //取出队首元素
                tx = m.x; ty = m.y; num = m.num;
                
if(num > maxt){                                                              //如果该元素的长度大于maxt,更新maxt
                        maxt = num;
                        ans 
= m;
                }
                
for(i = 0;i < 4; i++){                                                       //以m为起点向4个方向BFS
                        xx = tx + move[i][0];
                        yy 
= ty + move[i][1];
                        
if(!flag[xx][yy] && legal(xx,yy)){
                                flag[xx][yy] 
= true;
                                tep.x 
= xx;
                                tep.y 
= yy;
                                tep.num 
= num + 1;
                                f.push(tep);
                                
if(num+1>maxt){                                            //如果有更大的则更新
                                        maxt = num + 1;
                                        ans 
= tep;
                                }
                        }
                }
                f.pop();                                                                              
//弹出队首元素
        } 
}
int main(){
        
int i,j,T;
        Node start,end;
        
bool mark;
        scanf(
"%d",&T);
        
while(T--){
                scanf(
"%d%d",&c,&r);
                mark 
= false; maxt = -1;
                
for(i = 0;i < r; i++)
                        scanf(
"%s",map[i]);
                
for(i = 0;i < r; i++){
                        
for(j = 0;j < c; j++){
                                
if(map[i][j]=='.'){                                                     //任选一点BFS
                                        start.x = i;
                                        start.y 
= j;
                                        start.num 
= 0;
                                        bfs(start);
                                        mark 
= true;
                                        
break;
                                }
                        }
                        
if(mark) break;
                }
                maxt 
= -1;ans.num = 0;                                                           //此时ans一定是直径的端点,将它设为起点
                bfs(ans);                                                                                    //进行第二次BFS
                printf("Maximum rope length is %d.\n",maxt);
        }
}


TOJ3517(The longest athletic track):
          题目给出了一棵生成树,问这棵生成树最长的路的长度是多少。

#include<iostream>
#include
<queue>
#define INF 999999
#define M 2002
using namespace std;
int n;
int maxx;
int map[M][M],sum[M];
bool flag[M];
int bfs(int begin){
            queue
<int>f;
           
int i,m,k,key;
            maxx
=0;
            memset(flag,
false,sizeof(flag));
            f.push(begin);
           
while(!f.empty()){
                        k
=f.front();
                        
for(i=1;i<=n;i++){
                                
if(map[k][i]!=INF&&!flag[i]){
                                            flag[i]
=true;
                                            f.push(i);
                                            sum[i]
=sum[k]+map[k][i];
                                            
if(sum[i]>maxx) { maxx=sum[i];key=i; }
                                 }
                         }
                         f.pop();
            }
           
return key;
}
int main()
{
           
int i,j,k,dis,key,cas;
            scanf(
"%d",&cas);
           
while(cas--){
                         scanf(
"%d",&n);
                        
for(i=1;i<n;i++)
                                  
for(j=i+1;j<=n;j++)
                                            map[i][j]
=map[j][i]=INF;
                        
for(i=1;i<n;i++){
                                   scanf(
"%d%d%d",&j,&k,&dis);
                                   map[j][k]
=map[k][j]=dis;
                         }
                         sum[
1]=0;
                         key
=bfs(1);
                         sum[key]
=0;
                         key
=bfs(key);
                         printf(
"%d\n",maxx);
             }
    
//system("pause");
}





posted @ 2010-07-08 01:14 M.J 阅读(2572) | 评论 (0)编辑 收藏

归并排序求逆序对

              早就想学一下归并排序求逆序对,在这之前只会用树状数组来做,有时候还需要离散化,而且效率还不如归并排序高。
              其实还是蛮简单的,知道归并排序的原理就很容易知道如何求逆序对了。设数组为A,关键是在合并的时候,用数组L 和 R 表示左右两个子数组,因为逆序对的个数f(A) = f(L) + f(R) + s(L,R);其中f(L) 和 f(R) 分别表示L 内部 和R内部的逆序对个数,s(L.R)表示大数在L,小数在R的逆序对。因为L和R是已经排好序的,故其实只需求s(L,R).这个可以在合并L和R依次进行比较的时候算出。
for(k = p;k <= r;k ++){
         
if(L[i]<=R[j])
                  a[k] 
= L[i++];
         
else{                                                //如果L最上面的数大于R的,那么L[i]及后面的数可以和R[j]构成n1-i+1个逆序对
                  a[k] 
= R[j++];
                  count 
+=(n1 -+ 1);              //累加
          }
}

归并排序的代码:

void merge(int p,int q,int r){
         
int n1 = q-p+1,n2 = r-q;
         
int i,j,k;
         
for(i = 1;i <= n1; i++)
                   L[i] 
= a[p+i-1];
         
for(j = 1;j <= n2; j++)
                   R[j] 
= a[q+j];
          L[n1
+1= INF;
          R[n2
+1= INF;
          i 
= 1;j = 1;
         
for(k = p;k <= r;k ++){
                  
if(L[i]<=R[j])
                             a[k] 
= L[i++];
                  
else{
                             a[k] 
= R[j++];
                             count 
+=(n1 -+ 1);
                   }
          }
}
void merge_sort(int p,int r){
         
if(p<r){
                  
int q = (p+r)/2;
                   merge_sort(p,q);
                   merge_sort(q
+1,r);
                   merge(p,q,r);
          }
}


posted @ 2010-07-08 00:07 M.J 阅读(2625) | 评论 (1)编辑 收藏

2010年7月7日

多重背包问题

今天看了下多重背包,理解的还不够深入,不过因为是01背包过来的,所以接受起来很容易。
主要是运用了二进制的思想将一个数量为N很大的物品分为了logN个数量小的物品,而这logN个物品可以组成数量为0到N任意数量,所以这种策略是
成立的。
多重背包问题有TOJ1034,TOJ1670.

TOJ1034 :
大意是有6种规格的石头,编号从1到6,编号为 i 的石头的价值为 i .现在给出各种石头的数量,问有没有可能得到总价值的一半。
做法:    DP, 每种石头价值为v[i],价值为 i ,数量为 num[i] ,通过多重背包看能不能恰好取得总价值的一半。
           一个优化是总价值为奇数直接不用考虑,而在DP的时候设置一个标记来记录是否已经取得总价值一半,如果取得则可以返回。
做法2:这种方法的前提是POJ  discuss里的一种做法,即给每个石头的数量mod 8。证明是用抽屉原理证的,很复杂,我没有看。但是这样以来,数量
            一下子大大减少,极大的提高了效率。
            我说的做法2事实上是我的最初做法,即DFS,搜索,在搜索过程中注意剪枝,再加上数量取模的优化,复杂度也不高。 

Code for 1034(Dividing):
import java.util.Scanner;

import java.util.
*;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
public class Main {
    
public static int f[] = new int[20001*6];                                                // f[i]表示容量为 i 的背包最多能装的物品的价值
    
public static int v[] = new int[7];
    
public static int num[] = new int[7];
    
public static int total,flag,key;                                                               //total为 6 种大理石的总价值 ,flag为标记,一旦为1表示可以取得,可以返回了
    
public static void onezeropack(int cost,int weight) {                           //  01背包函数,注意循环是从total 到 cost,不要弄反
             
int i;
             
for(i = total;i >= cost; i--) {
                        f[i] 
= Math.max(f[i],f[i-cost]+weight);
                       
if(f[i] == key) {                                                                 // 如果可以取得总价值一半,flag=1,返回
                                  flag 
= 1;
                                 
return ;
                        }
              }
    }
    
public static void finishpack(int cost,int weight) {                            
             
int i;
             
if(flag==1return ;
             
for(i = cost;i <= total; i++) {
                         f[i] 
= Math.max(f[i], f[i-cost]+weight);
                       
if(f[i] == key) {
                                flag 
= 1;
                               
return ;
                        }
              }
    }
    
public static void multipack(int cost,int weight,int amount) {
                
if(cost*amount >= total) {
                            finishpack(cost, weight);
                           
return ;
                 }
                
if(flag==1return ;
                
int k = 1;
                
while(k < amount) {                                                                                        // 该过程即为将一件物品拆分为1,2,4...2^k 件物品进行01背包过程
                            onezeropack(k
*cost, k*weight);
                            amount 
-= k;
                            k 
*= 2;
                 }
                 onezeropack(cost
*amount, weight*amount);
    }
    
public static void main(String[] args){
                 Scanner 
in = new Scanner(System.in);
                
int i,j,cas = 1;
                
while(true) {
                            Arrays.fill(f,
0);
                            total 
= 0; flag = 0;
                           
for(i = 1;i <= 6; i++) {
                                       num[i] 
= in.nextInt();
                                       v[i] 
= i;
                                       total 
+= i*num[i];
                            }
                          
if(num[1]==0&&num[2]==0&&num[3]==0&&num[4]==0&&num[5]==0&&num[6]==0)
                                     
break;
                          
if(total%2==1) flag = 0;
                          
else {
                                     key 
= total/2;
                                    
for(i = 1;i <= 6; i++
                                     multipack(i, i, num[i]);
                           }
                           System.
out.println("Collection #"+cas+":");
                          
if(flag==0) System.out.println("Can't be divided.");
                          
else System.out.println("Can be divided.");
                           System.
out.println();
                           cas
++;
                }
    }

}

TOJ 1670:
          大意是一台取款机有N中货币,每种货币面值为 V[i] ,数量为 num[i] , 给出一个价值,为在这个价值之内(包括这个价值)最大能取得多大。
分析:典型的多重背包,给出的价值即为背包容量,每种货币为一种物品,价值为v[i] , 数量为num[i],求能得到的最大价值。
          注释就不加了,参考上面的程序

Code for 1670(Cash Mechine):

#include <cstdio>
#include 
<cstring>

int f[100002],v[12],num[12],cost[12];
int total,n;
int max(int a,int b){ return a>b?a:b;}

void OneZeroPack(int cost,int value){
          
int i,j;
          
for(i = total;i >= cost; i--)
                   f[i] 
= max(f[i],f[i-cost]+value);

}
void completePack(int cost,int weight){
          
int i;
          
for(i = cost;i <= total; i++)
                   f[i] 
= max(f[i],f[i-cost]+weight);
}
void multiPack(int cost,int weight,int amount){
          
if(cost*amount >= total){
                   completePack(cost,weight);
                  
return ;
           }
          
int k = 1;
          
while(k < amount){
                   OneZeroPack(k
*cost,k*weight);
                   amount 
-= k;
                   k
*=2;
           }
           OneZeroPack(cost
*amount,amount*weight);
}
int main(){
          
int i,j,k;
          
while(scanf("%d%d",&total,&n)!= EOF){
                   memset(f,
0,sizeof(f));
          
for(i = 1;i <= n; i++){
                   scanf(
"%d%d",&num[i],&cost[i]);
                   v[i] 
= cost[i];
           }
          
for(i = 1;i <= n; i++)
                   multiPack(cost[i],v[i],num[i]);
                   printf(
"%d\n",f[total]);    
           }
}



posted @ 2010-07-07 20:18 M.J 阅读(763) | 评论 (0)编辑 收藏

2010年7月5日

TOJ 3446.Money Matters 并查集,路径压缩

        题目大意是N个人互相有债a[i](正的表示别人欠钱,否则表示自己欠别人钱,a[i]的和保证为0),但是这N个人只有朋友间才能互相算帐,现在给出N个人的债,并且给出M个关系,即谁和谁是朋友,最后问有没有可能所有人都把帐算清。


Sample Input 1:                         Sample Input 2:

5    3                                            4     2
100                                              15
-75                                               20
-25                                              -10
-42                                              -15
42                                                0  2
0 1                                               1  3
1 2
3 4

Sample Output 1:                       Sample Output  2:

POSSIBLE                                    IMPOSSILBE

 思路1:

              每输入一个关系,合并,最后从1到N,对于每一个人,找出它们的祖先,将他们的债debt加到祖先的debt

              上。通俗的讲,就是每个集合的成员都将自己的debt加到祖先上,自己归0,最后看祖先的值是否为0;

              最后在从1到N扫一遍如果有debt不为0的,输出“IMPOSSIBLE”,否则“POSSIBLE”;

              缺点:复杂度高,查询复杂度*N,最后勉强过了,时间0.63s

思路2:

              路径压缩,每输入一个关系,合并。最后从1到N,如果 i 的debt不为0,从 i 到 i 的祖先的路径不断压缩直到

              祖先,这样虽然仍然是N次操作,但由于在压缩过程中大部分成员debt归0,故实际上进行操作的次数远小于N.

              最后时间为0.11,比起上一种方法有了很大提高

Code 1:

#include <cstdio>
#include 
<cstring>
struct Node{
        
int father,v,num;
}a[
10002];
int find(int n){
        
int tep,m = n;
        
while(n != a[n].father)
                n 
= a[n].father;
        
while(m != n){
                tep 
= a[n].father;
                a[n].father 
= n;
                m 
= tep;
        }
        
return n;
}
void Union(int root1,int root2){
        
int t1,t2;
        t1 
= find(root1),t2 = find(root2);
        
if(t1 == t2) return ;
        
else{
                
if(a[t1].v > a[t2].v){
                        a[t1].v 
+= a[t2].v;
                        a[t2].father 
= t1;
                }
                
else{
                        a[t2].v 
+= a[t1].v;
                        a[t1].father 
= t2;
                }
        }
}
int main()
{
        
int n,m,i,j;
        
bool flag = false;
        scanf(
"%d%d",&n,&m);
        
for(i = 0;i < n; ++i){
                a[i].father 
= i,a[i].v = 0;
                scanf(
"%d",&a[i].num);
        }
        
while(m--){
                scanf(
"%d%d",&i,&j);
                Union(i,j);
        }
        
for(i = 0;i < n; ++i){
                
int tep = find(i);
                
int tt = a[i].num;
                a[i].num 
-= tt;
                a[tep].num 
+= tt;
        }
        
for(i = 0;i < n; i++)
                
if(a[i].num != 0){
                        flag 
= true;
                        
break;
                }
        
if(flag) printf("IMPOSSIBLE\n");
        
else     printf("POSSIBLE\n");
}

Code 2:

#include <cstdio>
#include 
<cstring>
struct Node{
        
int father,v,num;
}a[
10002];
int find(int n){
        
int m = n,tep;
        
while(n != a[n].father)
                n 
= a[n].father;
        
while(m != n){
                tep 
= a[m].father;
                
int tt = a[m].num;
                a[m].num 
-= tt;
                a[tep].num 
+= tt;
                a[m].father 
= n;
                m 
= tep;
        }
        
return n;
}
void Union(int root1,int root2){
        
int t1,t2;
        t1 
= find(root1),t2 = find(root2);
        
if(t1 == t2) return ;
        
else{
                
if(a[t1].v > a[t2].v){
                        a[t1].v 
+= a[t2].v;
                        a[t2].father 
= t1;
                }
                
else{
                        a[t2].v 
+= a[t1].v;
                        a[t1].father 
= t2;
                }
        }
}
int main()
{
        
int n,m,i,j;
        
bool flag = false;
        scanf(
"%d%d",&n,&m);
        
for(i = 0;i < n; ++i){
                a[i].father 
= i,a[i].v = 0;
                scanf(
"%d",&a[i].num);
        }
        
while(m--){
                scanf(
"%d%d",&i,&j);
                Union(i,j);
        }
        
for(i = 0;i < n; ++i)
             
if(a[i].num != 0) find(i);
        
for(i = 0;i < n; i++)
                
if(a[i].num != 0){
                        flag 
= true;
                        
break;
                }
        
if(flag) printf("IMPOSSIBLE\n");
        
else     printf("POSSIBLE\n");
}








posted @ 2010-07-05 21:08 M.J 阅读(287) | 评论 (0)编辑 收藏

TOJ 1688. Corporative Network 并查集

       这道题题意很难懂,大意是有N个公司,每个公司有一个center,最初每个公司的center都在自己公司,然后有M次操作,每次操作 A , B (A保证是一个集合的center,B不一定) 表示将A所在的集合并到B所在的集合,且B的center成为了A的center。每次操作后两个公司的线的距离增加abs(A-B)%1000;
Sample Input: (E  P表示查询P距离自己center的线的长度,I   P  Q 表示合并 P ,Q);
1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O
Sample Output:
0
2
3
5

Code:
#include <cstdio>
#include 
<iostream>
#define M 20010
using namespace std;

struct Node{
        
int father,num;
}a[M];
void initial(int n){
        
int i;
        
for(i = 1;i <= n; i++){
                a[i].father 
= i;
                a[i].num 
= 0;
        }
}
int find(int n){
        
int tep,m = n;
        
if(n == a[n].father) return n;
        find(a[n].father);               
//递归查找n的祖先
        a[n].num += a[a[n].father].num;   //n的直需要更新(加上n的父亲的值)
        a[n].father = a[a[n].father].father;
}
int main()
{
        
int T,n,i,j,k;
        
char order[3];
        scanf(
"%d",&T);
        
while(T--){
                scanf(
"%d",&n);
                initial(n);
                
while(scanf("%s",order)){
                        
if(order[0]== 'O'break;
                        
if(order[0== 'E'){
                                scanf(
"%d",&k);
                                find(k);
                                printf(
"%d\n",a[k].num);
                        }
                        
else{
                                scanf(
"%d%d",&j,&k);
                                
int dis = abs(j-k)%1000;
                                a[j].num 
= dis;           //该值dis为j的值
                                a[j].father = k;          //k成为了j的父亲
                        }
                }
        }
}





posted @ 2010-07-05 20:48 M.J 阅读(123) | 评论 (0)编辑 收藏

2010年6月23日

TOJ 2904【JAVA大数的进制问题】

题目给定一个进制b,然后给两个b进制下的大数 m 和 n ,要求求出m % n的结果,用b进制表示。
最近在学JAVA,发现做起高精度简直太爽了~ 这个题有JAVA简直就是个水题,知道一些函数就好了。
BigInteger a = in.nextBigInteger(base);       //将一个大数按照base进制输入
a.mod(b) ;                                                 //a%b,其中a和b都是大数且结果为10进制,不管a和b是什么进制
String str= a.toString(base);                      //将一个大数a转换成b进制的字符串

这个题就用到这些东西,代码就不贴了。~~

posted @ 2010-06-23 16:05 M.J 阅读(211) | 评论 (0)编辑 收藏

2010年6月12日

TOJ 1135 Matrix Chain Multiplication

很简单的题,给定N个矩阵,然后给出一系列运算式,用括号来限制运算,最后求一共进行了多少次乘法运算。
R(m,s) 和Q(s,n)相乘,要进行m*s*n次~
处理运算先后的时候,用栈实现,即后进先出就可以了。
Sample Input:
9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))
Sample Outout:
0
0
0
error
10000
error
3500
15000
40500
47500
15125
Code:
#include <iostream>
#include 
<cstdio>
#include 
<string>
#include 
<map>
using namespace std;

struct Matrx{
        
char id;
        
int x,y;
}a[
30];
Matrx stack[
100];
int main()
{
        
int i,j,k,n,ans;
        
bool flag;
        map
<char,int>mark;
        scanf(
"%d",&n);
        
for(i = 1;i <= n; i++){
                cin 
>> a[i].id;
                scanf(
"%d%d",&a[i].x,&a[i].y);
                mark[a[i].id] 
= i;
        }
        
string str;
        
while(cin>>str){
                ans 
= 0; flag = true;
                
int len = str.length();
                
int head,tail;
                head 
= tail = 0;
                
for(i = 0;i <len; i++){
                        
if(str[i] == '(')
                                
continue;
                        
else if(str[i] == ')'){     //pop
                                if(head == 1)
                                        head 
--;
                                
else if(head > 1){
                                        
int tx = stack[head-2].x;
                                        
int ty = stack[head-1].y;
                                        
if(stack[head-2].y != stack[head-1].x) flag = false;
                                        ans 
+= stack[head-2].x*stack[head-2].y*stack[head-1].y;
                                        head 
-= 2;
                                        stack[head].x 
= tx;
                                        stack[head
++].y = ty;
                                }

                        }
                        
else{        // push
                                stack[head++= a[mark[str[i]]];

                        }
                }
                
if(!flag) printf("error\n");
                
else printf("%d\n",ans);
        }
}




posted @ 2010-06-12 22:10 M.J 阅读(158) | 评论 (0)编辑 收藏

【DP】TOJ 2820 How many different ways

给定从1 到 N的 N 个数,问有多少种不同方案划分这些数。比如N = 3,则有5种方案:
{{1},{2},{3}}
{{1,2},{3}}
{{1,3},{2}}
{{2,3},{1}}
{{1,2,3}}
最后的结果只保留后四位,即mod10000;
上网查了下,集合的划分的个数叫做bell数,bell数可以递归求解:
bell[0] = 1;
bell [n + 1] = sigma(C(n,k))*(bell[k]); (0<=k<=n)

 
然而这个题却不可以这样做,因为N得范围是2000,这样做必定超时,于是想到了DP,如果用dp[i][j]表示i个数
划分成j个集合,那么便有dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1];( i > j )直观理解就是,将i个数划分成j个集合的个数,即为i-1个数划分到j个集合的数,再将多的那个依次放到j个集合中,所以乘以j,或者是i-1个数放在j-1个集合中,第j个集合为空,则正好将多的这个数放到这个集合中,于是便有上边的状态转移方程。
Code:

 

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

int map[2002][2002];
void DP(){
    memset(map,
0,sizeof(map));
    
int i,j,k;
    
for(i = 0;i <= 2000; i++){
        map[i][i] 
= 1;
        map[i][
1= 1;
    }

    
for(i = 0;i <= 2000 ;i++)
        
for(j = 0; j < i; j++)
            map[i][j] 
= (j * map[i-1][j] + map[i-1][j-1])%10000;
}

int main()
{
    
int i,j,k,n;
    DP();
    
while(scanf("%d",&n),n){
        
int ans = 0;
        
for(i = 0;i <= n; i++)
            ans 
= (ans + map[n][i])%10000;
        
string str = "0000";
        str[
3= ans%10+'0'; ans/=10;
        str[
2= ans%10+'0'; ans/=10;
        str[
1= ans%10+'0'; ans/=10;
        str[
0= ans%10+'0'; ans/=10;
        cout
<<str<<endl;
    }

}

posted @ 2010-06-12 15:05 M.J 阅读(228) | 评论 (0)编辑 收藏

2010年5月28日

Dilworth定理及相关题目

偏序集的两个定理:
定理1) 令(X,≤)是一个有限偏序集,并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理:
定理2) 令(X,≤)是一个有限偏序集,并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
 即:链的最少划分数=反链的最长长度
相关的题目有pku 1065,pku 3636,pku 1548
POJ 3636:
#include<iostream>
#include
<algorithm>
#define M 20002
using namespace std;
struct Node{
    
int h,w;
}
a[M];
int tail[M],n;
void LIS(int n){
    
int i,j,m,len,mid,low,high;
    len
=1;tail[1]=a[1].h;
    
for(i=2;i<=n;i++){
        
if(tail[len]<=a[i].h) {
            len
++;
            tail[len]
=a[i].h;
        }

        
else{
            low
=1;high=len; 
            
while(low<high){
                mid
=(low+high)/2;
                
if(a[i].h>=tail[mid]) low=mid+1;
                
else high=mid;
            }

            tail[low]
=a[i].h;
        }

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

bool cmp(Node a,Node b){
    
if(a.w!=b.w)return a.w>b.w;
    
else return a.h<b.h;
}

int main()
{
    
int i,j,k,cas;
    scanf(
"%d",&cas);    
    
while(cas--){
        scanf(
"%d",&n);
        
for(i=1;i<=n;i++)
            scanf(
"%d%d",&a[i].w,&a[i].h);
        sort(a
+1,a+1+n,cmp);
        LIS(n);
    }

    
//system("pause");
    return 0;
}
POJ  1548:
#include<iostream>
#include
<algorithm>
using namespace std;
int k,a[700],tail[800],b[860];
void LIS(){
    
int i,j,m,n,len,mid,left,right;
    n
=1;
    
for(i=k-1;i>=1;i--) b[n++]=a[i];
    n
--;
    len
=1;tail[1]=b[1];
    
for(i=2;i<=n;++i){
        
if(b[i]>tail[len]){
            len
++;
            tail[len]
=b[i];
        }

        
else{
            left
=1;right=len;
            
while(left<right){              //二分查找插入的位置 
                mid=(left+right)/2;
                
if(tail[mid]<b[i]) left=mid+1;
                    
else  right=mid;
                }

            tail[left]
=b[i];                //插入 
        }
 
    }
                    
    printf(
"%d\n",len);      
}

int main()
{
    
int i,j,m,n;
    
while(1){
        k
=1;
        scanf(
"%d%d",&i,&j);
        
if(i==-1&&j==-1break;
        a[k
++]=j;
        
while(scanf("%d%d",&i,&j)){
            
if(i==0&&j==0 ){
                LIS();
                
break;        
            }

            a[k
++]=j;
        }
    
    }

}

posted @ 2010-05-28 18:35 M.J 阅读(986) | 评论 (0)编辑 收藏