M.J的blog

TOJ 3499. Network(并查集)

今天简单看了下并查集，关于优化什么的还没有看。做了两个简单的题，先熟悉一下~
并查集用来表示若干互不相交的集合，是一种树状的结构。
并查集有三个操作：初始化，合并，查询。
其中在合并的时候，由于可能集合是一个偏的很厉害的树，如果不加分类直接合并的话，每次查询会相当浪费时间，所以
需要每次合并的时候将规模小的集合并到规模大的集合，并且随时更新集合内元素的个数。
简单的不优化的Union函数如下：

1 Union(int root1,int root2)
2 {
3      int t1,t2;
4      t1=find(root1);
5      t2=find(root2);
6      if(t1!=t2)
7          t1.father=t2;
8      return ;
9 }

优化后的Union函数如下：

 1 void Union(int root1,int root2)
 2 {
 3     int t1,t2;
 4     t1=find(root1);
 5     t2=find(root2);
 6     if(t1==t2) return ;                      //只有当两个根节点的祖先不同才合并
 7     if(t1!=t2){                              
 8         if(a[t1].v<a[t2].v){                 //将规模小的集合并到规模大的集合，同时集合元素个数增加
 9             a[t1].father=t2;
10             a[t2].v+=a[t1].v;
11         }
12         else{
13             a[t2].father=t1;
14                 a[t1].v+=a[t2].v;
15         }
16         
17     }
18 }

先看一下最简单的并查集的模板：

 1 #include<stdio.h>
 2 #define MAX 10002
 3 int m,n;
 4 struct type
 5 {
 6     int father,v;                           //father 表示根节点，v表示集合内元素个数
 7 }a[MAX];
 8 void initial(int n)
 9 {
10     int i;
11     for(i=0;i<n;i++){
12         a[i].father=i;                      //初始化将集合节点标记为自己，元素个数为1
13         a[i].v=1;
14     }
15 }
16 int find(int n)
17 {    
18     if(a[n].father!=n)
19         return find(a[n].father);            //此处也可以写为  while(a[n].father!=n) n=a[n].father;
20     return n;
21 }
22 void Union(int root1,int root2)
23 {
24     int t1,t2;
25     t1=find(root1);
26     t2=find(root2);
27     if(t1==t2) return ;                      //只有当两个根节点的祖先不同才合并
28     if(t1!=t2){                              
29         if(a[t1].v<a[t2].v){                 //将规模小的集合并到规模大的集合，同时集合元素个数增加
30             a[t1].father=t2;
31             a[t2].v+=a[t1].v;
32         }
33         else{
34             a[t2].father=t1;
35             a[t1].v+=a[t2].v;
36         }
37     }
38 }
39 int main()
40 {}

运用上边的模板，就可以将TOJ 3499 AC掉了
题意大概是N个数，从0到N-1，有M个关系，最后问P和Q之间是否是关系。
Code：

 1 #include<stdio.h>
 2 #define MAX 10002
 3 int m,n;
 4 struct type
 5 {
 6     int father,v;
 7 }a[MAX];
 8 void initial(int n)
 9 {
10     int i;
11     for(i=0;i<n;i++){
12         a[i].father=i;
13         a[i].v=1;
14     }
15 }
16 int find(int n)
17 {
18     if(a[n].father!=n)
19         return find(a[n].father);
20     return n;
21 }
22 void Union(int root1,int root2)
23 {
24     int t1,t2;
25     t1=find(root1);
26     t2=find(root2);
27     if(t1==t2) return ;
28     if(t1!=t2){
29         if(a[t1].v<a[t2].v){
30             a[t1].father=t2;
31             a[t2].v+=a[t1].v;
32         }
33         else{
34             a[t2].father=t1;
35             a[t1].v+=a[t2].v;
36         }
37     }
38 }
39 int main()
40 {
41     int cas,i,j,k,p,q,N,M;
42     while(scanf("%d%d%d",&N,&M,&k)!=EOF){
43         initial(N);
44         for(i=0;i<M;i++){
45             scanf("%d%d",&p,&q);
46             Union(p,q);
47         }
48         for(i=1;i<=k;i++){
49             scanf("%d%d",&p,&q);
50             if(find(p)==find(q))
51                 printf("YES\n");
52         else printf("NO\n");
53     }
54     }
55 }

posted @ 2010-04-24 14:55 M.J 阅读(184) | 评论 (0) | 编辑收藏

TOJ 2812. Travel

简单的DP,很好想。但是我第一次又给做成了贪心···相当无奈，不知道什么时候才能分清贪心和DP的区别。

初始化很重要，让我WA了N次。

dp[i][j]表示第 i天在 city j 所能得到的最大income。

所以有转移方程：

dp[i][j] = max{ dp[i-1][j]-pay[j][j]+income[i-1][j] ,dp[i-1][k]-pay[k][j]+income[i-1][j]};

其中1<k<=n (dp[1][i]单独初始化)

Code:

 1 #include<iostream>
 2 #define MAX 120
 3 using namespace std;
 4 int m,n,dp[MAX][MAX];
 5 int pay[MAX][MAX],income[MAX][MAX];
 6 int main()
 7 {
 8     int i,j,k,temp,mm;
 9     while(cin>>n>>m){
10         if(m==0&&n==0) break;
11         mm=-1000000;
12         for(i=1;i<=n;i++)
13              for(j=1;j<=n;j++)
14                    cin>>pay[i][j];
15         for(i=1;i<=m;i++)
16              for(j=1;j<=n;j++)
17                    cin>>income[i][j];
18         dp[0][1]=0;
19         for(i=1;i<=n;i++)
20              dp[1][i]=income[1][i]-pay[1][i];
21         for(i=2;i<=m;i++)
22              for(j=1;j<=n;j++){
23                    temp=dp[i][j]=dp[i-1][j]-pay[j][j]+income[i][j];
24                    for(k=1;k<=n;k++)
25                           if(temp<dp[i-1][k]-pay[k][j]+income[i][j]){
26                                 dp[i][j]=dp[i-1][k]-pay[k][j]+income[i][j];
27                                 temp=dp[i][j];
28                           }
29              }
30             
31         for(i=1;i<=n;i++)
32              if(dp[m][i]>mm)
33                  mm=dp[m][i];
34         cout<<mm<<endl;
35     }
36 
37 }

posted @ 2010-04-24 08:52 M.J 阅读(86) | 评论 (0) | 编辑收藏

POJ 1131 Octal Fractions

高精度除法和加法。Code：

 1 #include<iostream>

 2 #include<cstring>

 3 using namespace std;

 4 int main()

 5 {

 6     int a[20][60];

 7     int i,j,k,m,n;

 8     for(i=0;i<60;i++)

 9         a[0][i]=0;
10     a[0][0]=1;                       //初始化a[0]=1000000000000000000000

11     k=0;

12     for(i=1;i<20;i++)

13         for(j=0;j<60;j++)

14         {

15             a[i][j]=(a[i-1][j]+10*k)/8;

16             k=(a[i-1][j]+10*k)%8;                 //k是上一位的进位，其中a[i-1][j]+10*k是i-1的数

17         }

18     char p[20];

19     int len,key,di[20],re[60];

20     while(cin>>p)

21     {

22         if(strlen(p)==1&&p[0]=='0')  

23             cout<<p<<" [8] = 0  [10]"<<endl; 

24         else if(strlen(p)==1&&p[0]=='1') 

25             cout<<p<<" [8] = 1  [10]"<<endl; 

26         else{

27             memset(re,0,sizeof(re));

28             memset(di,0,sizeof(di));

29             len=strlen(p);

30             for(i=0;i<len;i++)

31                 if(p[i]=='.')

32                 {

33                     key=i+1;

34                     break;

35                 }

36             j=1;

37             for(i=key;i<len;i++)    

38                 di[j++]=p[i]-'0';

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

40             {

41                 for(k=0;k<60;k++)

42                     re[k]+=di[i]*a[i][k];

43             }

44             for(i=59;i>=0;i--)

45                 if(re[i]>=10)

46                 {

47                     re[i-1]+=(re[i]/10);

48                     re[i]%=10;

49                 }

50             cout<<p<<" [8] = "<<"0.";

51             for(i=59;i>0;i--)

52                 if(re[i]!=0)

53             {

54                 for(k=i+1;k<60;k++)

55                     re[k]=-1;

56                    break;

57             }                                       //把末尾的'0'标记为-1

58             for(i=1;i<60;i++)

59             {

60                 if(re[i]==-1) break;

61                 cout<<re[i];

62             }

63             cout<<" [10]"<<endl;

64         }

65     }

66 }
67

posted @ 2010-04-23 20:05 M.J 阅读(633) | 评论 (0) | 编辑收藏

TOJ 1007 Joseph

别人的思路，有点递归的意思。程序本身超时，但可以利用它来打表。

这个题目其实就是要求前k次踢掉的都是坏人，假设第i次踢掉的人是i，则i>k。根据题意，可以得到如下关系：
设 ai 是第i次踢掉的人在第i-1次踢掉后剩下的人中是第几个。那么

a(n) = [a(n-1)+m-1]mod(2k-n+1)
要求a(n) > k；n = 1,2,3,...,k
其中2k-n+1是第i-1次踢人后剩下的人数

 1 bool Joseph(int k, int m) // 这个算法确定对于给定的k,m是否满足上面的要求

 2 {
 3     int n=0,a=1;
 4     for(n=1;n<=k;n++)
 5     {
 6         a = (a+m-1)%(k*2-n+1);
 7         if(a == 0)  a = k*2-n+1;
 8         if(a<=k && a>=1)  return false;
 9     }
10     return true;
11 }

Code:

 1#include<iostream>
 2using namespace std;
 3bool judge(int k,int m)
 4{
 5   int i,j=1;         
 6   for(i=1;i<=k;i++)
 7   {
 8        j=(j+m-1)%(k*2+1-i);
 9        if(j==0)  j=k*2+1-i;
10        if((j<=k)&&(j>=1)) 
11            return false;
12   }
13   return true;
14}
15int main()
16{
17    int k,m,i,j,n;
18    while(cin>>k)
19    {
20        if(k==0)  break;
21        for(m=k+1;;m++)
22        {
23            if(judge(k,m))
24            {
25                cout<<m<<endl;
26                break;
27            }
28        }
29    }
30}

posted @ 2010-04-23 19:59 M.J 阅读(158) | 评论 (0) | 编辑收藏

HDU 1231 最大连续子序列

 1 #include<iostream>

 2 using namespace std;

 3 int main()

 4 {

 5    int i;

 6    while(scanf("%d",&i)!=EOF)

 7    {

 8         int j,k,m,n,temp,begin_new,begin,end,max=-100000,sum=0;

 9         bool judge=true;

10         if(i==0) break;

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

12         {

13             scanf("%d",&k);

14             if(k>=0) judge=false;

15             sum+=k;

16             if(k>sum)

17             {

18                 begin_new=k;

19                 sum=k;

20             }

21             if(sum>max)

22             {   

23                 begin=begin_new;

24                 max=sum;

25                 end=k;

26                 if(j==1){begin=k;begin_new=k;}

27                 begin=begin_new;

28             }

29       }

30       if(judge)printf("%c %d %d\n",'0',begin,k);

31       else     printf("%d %d %d\n",max,begin,end);

32    }

33 }
34

posted @ 2010-04-23 19:56 M.J 阅读(215) | 评论 (0) | 编辑收藏

POJ 1163 The Triangle

有人用递归做，有人用DP做，我是参考了一个人的思路写的代码AC的。

大意是从后往前推，因为从前往后是不能得到全局最优解的，而从后就可以。

Code：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 int a[102][102];
 6 
 7 int main()
 8 
 9 {
10 
11         int i,j,k;
12 
13         cin>>i;
14 
15         for(j=1;j<=i;j++)
16 
17                 for(k=1;k<=j;k++)
18 
19                        cin>>a[j][k];
20 
21         for(j=i-1;j>=1;j--)
22 
23                 for(k=1;k<=j;k++)
24 
25                 {
26 
27                              if(a[j+1][k]>a[j+1][k+1])
28 
29                                      a[j][k]+=a[j+1][k];
30 
31                             else
32 
33                                       a[j][k]+=a[j+1][k+1];
34 
35                 }
36 
37          cout<<a[1][1]<<endl;
38 
39 }
40

posted @ 2010-04-23 19:53 M.J 阅读(176) | 评论 (0) | 编辑收藏

求N的阶乘约数的个数

先说一个定理：

        若正整数n可分解为p1^a1*p1^a2*...*pk^ak
       其中pi为两两不同的素数,ai为对应指数
       n的约数个数为(1+a1)*(1+a2)*....*(1+ak)
       如180=2*2*3*3*5=2^2*3^2*5
       180的约数个数为(1+2)*(1+2)*(1+1)=18个。

若求A/B的约数个数，A可分解为p1^a1*p2^a2*...*pk^ak，B可分解为q1^b1*q1^b2*...*qk^bk,则A/B的约数个数为(a1-b1+1)*(a2-b2+1)*(a3-b3+1)...*(ak-bk+1).

然后说N的阶乘：

例如:20!
1.先求出20以内的素数,(2,3,5,7,11,13,17,19)
2.再求各个素数的阶数
e(2)=[20/2]+[20/4]+[20/8]+[20/16]=18;
e(3)=[20/3]+[20/9]=8;
e(5)=[20/5]=4;
...
e(19)=[20/19]=1;
所以
20!=2^18*3^8*5^4*...*19^1

解释：
2、4、6、8、10、12、14、16、18、20能被2整除
4、8、12、16、20能被4整除（即被2除一次后还能被2整除）
8、16能被8整除（即被2除两次后还能被2整除）
16能被16整除（即被2除三次后还能被2整除）
这样就得到了2的阶。其它可以依次递推。

所以在求N的阶乘质数因数个数时，从最小的质数开始，

1 int cal(int n, int p) {

2 if(n < p) return 0;

3 else return n / p + cal(n / p, p);

4 }

其中P是质数，则该函数返回的就是N的阶乘中可以表达成质数P的指数的最大值。原理如上。
TOJ 2308的AC代码：

 1 #include<iostream>
 2 
 3 #include<cmath>
 4 
 5 #define N 90
 6 
 7 #define M 450  
 8 
 9 using namespace std;
10 
11 int p[M+2]={0};
12 
13 int prime[N+2],l,q,t=1;  //求前90个素数
14 
15 void getprime(int n)
16 
17 {
18     
19     for(l=2;l<n;l++)
20         
21     {
22         
23         if(!p[l])
24             
25         {
26             
27             for(q=l+l;q<n;q+=l)
28                 
29             {
30                 
31                 p[q]=1;
32                 
33             }
34             
35             prime[t]=l;t++;
36             
37         }
38         
39       }
40     
41 }
42 
43 int cal(int n,int m)      //求N的阶乘含质因数M的次数
44 
45 {
46     if(m>n)
47         
48         return 0;
49     
50     else
51         
52         return n/m+cal(n/m,m);
53     
54 }
55 int main()
56 {
57     int i,j,k,n;
58     
59     long long m;
60     
61     getprime(M);
62     
63     while(cin>>n>>k)
64         
65     {
66         if(2*k>n)  k=n-k;
67         
68         for(i=1,m=1;prime[i]<=n,i<t;i++)
69             
70             m*=(cal(n,prime[i])-cal(k,prime[i])-cal(n-k,prime[i])+1);  
71         
72         cout<<m<<endl;
73    
74     }
75 }

posted @ 2010-04-23 19:49 M.J 阅读(516) | 评论 (0) | 编辑收藏

TOJ 2219. A famous math puzzle

是个关于拓展欧几里得的问题，但是很难想到。这题也是看了结题报告的~~

关于拓展欧几里得的算法http://mj-zhang.blogbus.com/tag/拓展欧几里得/

大意是给N个瓶子，每个瓶子有个容量C，给定一个容量W，每次只能（1）灌满一个，（2）倒空一个，（3）把一个的水倒给另一个，直到一个满了或者一个空了。通过三种操作，有没有可能最后达到某个瓶子里有W的水。可以这样考虑：

1）当所有C都小于W，肯定不行；

2）如果有N个瓶子，N个瓶子的容量C1, C2, C3 ... Cn必然有个最大公约数P。

证明：假设n个水壶的容量分别为C1,C2,C3…..Cn.
必要性：不管执行三种操作的那一种，壶中所含的水一定是Ｐ的整数倍．
充分性：由欧几里德算法扩展可知，必然存在整数A1,A2,A3…..An,使得
　A1*C1+A2*C2+A3*C3+…+An*Cn=W.
如果Ai是正数，我们就用第i个壶从水源中取Ai次水；如果Ai为负数，我们就把第i个壶倒空Ai次，这样最后必会剩下Ｗ升水

 1 #include<stdio.h>

 2 int gcd(int a,int b){

 3     int temp;

 4     if(a<b) {temp=b;b=a;a=temp;}

 5     if(a%b==0) return b;

 6     else  return gcd(b,a%b);

 7 }
 8 int main()
 9 {
10     int i,j,k,n,w,flag,tep,a[102];

11     while(scanf("%d%d",&n,&w)!=EOF){

12         if(n==0&&w==0) break;

13         flag=0;a[n+1]=0;

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

15             scanf("%d",&a[i]);

16             if(a[i]>=w) flag=1;

17         }

18         if(flag&&n!=1){

19             tep=gcd(a[1],a[2]);

20             for(i=3;i<=n;i++)

21                 tep=gcd(tep,a[i]);

22                 if(w%tep!=0)

23                     flag=0;

24         }

25         if(n==1&&a[1]!=w) flag=0;

26         else if(n==1&&a[1]==w) flag=1;

27         if(flag) printf("YES\n");

28         else  printf("NO\n");

29     }
30 
31 }