posts - 99,  comments - 8,  trackbacks - 0
 
hdu 1102
//运用prime 算法解决最小生成树问题 :这里默认从第一个顶点开始
//本题中要求输出最终的最短路径的和，所以将开始就有的路之间的边长设为 0 
//奉献了好多次的WA   结果是因为在将已有边存在的地方只设定了 edge[a][b] = 0; 出错
本题的关键运用在于辅助数组 lowcost[ ] 的使用
 1
 2#include <stdio.h>
 3#include <stdlib.h>
 4#include <string.h>
 5
 6int main ()
 7{
 8    int n, q, a, b;
 9    int lowcost[101];               //开始时储存源点到其他各顶点的边值，随后根据加进来的顶点，不断改变所存的边值 
10    int edge[101][101];             //存输入的边之间的长度 
11    int visit[101];                 //标志顶点是否已经加入 
12    
13    while ( scanf ("%d", &n)!= EOF )
14    {
15           memset (visit, 0, sizeof (visit)); 
16           memset (lowcost, 0, sizeof (lowcost));                                                                      
17           
18          //输入处理 
19          for (int i = 1; i <= n; i ++)
20          {
21              for (int j = 1; j<= n; j ++)
22              {
23                  scanf ("%d", &edge[i][j]);
24              }
25          }
26          scanf ("%d", &q);
27          if ( q )
28          {
29               for (int i = 0; i < q; i ++)  //本身存在边则该顶点被标记 
30               {
31                   scanf ("%d %d", &a, &b);
32                   edge[a][b] = edge[b][a] = 0; 
33               }
34          }
35          
36          //prime:每次都从剩下的边中选出最短的一条，标记相关的顶点，并且修改相关边的值 
37          //对lowcost 进行初始化处理
38          for (int i = 1; i <= n; i ++ )
39          {
40              lowcost[i] = edge[1][i];
41          } 
42          
43          int sum = 0;  
44          int k;        
45          for (int i = 1; i <= n; i ++)
46          {            
47              int max = 10000;
48
49              for ( int i = 1; i <= n; i ++ )
50              {
51                  if ( lowcost[i] < max && !visit[i] ) 
52                  {
53                     max = lowcost[i];
54                     k = i;
55                  }                                                                             
56              }
57              
58              if (max == 10000)  //如果没有找到最小的边一下一个顶点作为起点                       
59              break;
60              
61              visit[k] = 1;
62              sum += lowcost[k];
63              
64              //修改要加入的顶点到其他未加入顶点之间的距离
                       for (int i = 1; i <= n; i ++)
65              {
66                  if ( !visit[i] && lowcost[i] > edge[k][i])  //新引入的顶点到其他顶点的边值  是否 小于  原来的边值 
67                  {
68                       lowcost[i] = edge[k][i]; 
69                  } 
70              }
71          }          
72          printf ("%d\n", sum);
73    }
74   // system ("pause");
75    return 0;
76} 
77
posted @ 2010-08-23 14:06 雪黛依梦 阅读(347) | 评论 (0) | 编辑 收藏
hdu 2037

简单的贪心题：只需要将结束时间利用qsort进行排序后，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排，
好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。 加上一个判断条件就可以搞定了

 1#include <stdio.h>
 2#include <stdlib.h>
 3struct time
 4{
 5    int start; 
 6    int end;
 7}a[100];
 8
 9int cmp (const void *a, const void *b)
10{
11    return (*(time *)a).end - (*(time *)b).end;
12}
13
14int main ()
15{
16    int n;
17    while (scanf ("%d", &n) != EOF && n != 0)
18    {
19          for (int i = 0; i < n; i ++)
20          {
21              scanf ("%d %d", &a[i].start, &a[i].end);
22          }
23          //对结束时间进行从小到大的排序
24          qsort (a, n, sizeof (a[0]), cmp); 
25          
26          int count = 1;
27          int temp = 0;
28          for (int i = 1; i < n; i ++)
29          {
30              if (a[i].start >= a[temp].end)
31              {
32                 temp = i;
33                 count ++;                 
34              }                
35          }
36          
37          printf ("%d\n", count);
38    }
39    //system ("pause");
40    return 0;
41}
42


 

posted @ 2010-08-22 21:04 雪黛依梦 阅读(787) | 评论 (0) | 编辑 收藏
hdu 1050

//虽然说是一道贪心题，可我没见到用了贪心的知识啊
//思路：如果有某个值出现在另一个区间中则必然会使a[i] 加 1 相反如果不在任何一个界限内a[i] 都会是 1
//缩小比较的范围思想方法挺值得借鉴的

#include <cstdio>  
#include <string>  
#include <algorithm>   
using namespace std;   
  
int main()   
{   
    int NumOfTest,pair;   
    int i,Max;   
    int a[201];   
    int b,c,n1,n2;   
    scanf("%d",&NumOfTest);   
    while (NumOfTest--)   
    {   
        scanf("%d",&pair);   
        memset(a,0,sizeof(a));   
        while (pair--)   
        {   
            scanf("%d%d",&b,&c);   
            if(b>c)/**//*交换数值，让小值在前，大值在后，从而使得n1<=n2*/  
                swap(b,c);   
            /**//*求n1和n2*/  
            if(b%2==1)   
                n1 = (b-1)/2+1;   
            else  
                n1 = b/2;   
            if(c%2==1)   
                n2 = (c-1)/2+1;   
            else  
                n2 = c/2;   
            if(n1!=n2)   
                for(i=n1;i<=n2;i++)   
                    a[i]++;   
            else  
                a[n1]++;   
        }   
        Max = -1;   
        for(i=1;i<=200;i++)   
            if(Max<a[i])   
                Max = a[i];   
        printf("%d\n",10*Max);   
    }   
    return 0;   
}  
posted @ 2010-08-22 20:25 雪黛依梦 阅读(727) | 评论 (0) | 编辑 收藏
hdu 1085

 

//理解好模板后分步做 
#include <stdio.h>
#include <stdlib.h>
 
int main ()
{
    int num1[9000];              
    int num2[9000];
    int number1, number2, number3;
    
    while ( scanf ("%d%d%d", &number1, &number2, &number3) != EOF && ( number1 != 0 && number2 != 0 && number3 != 0 ) )
    {
          int max;
          max = 1 * number1 + 2 * number2 + 5 * number3;
          //总体初始化 
          for (int i =0; i <= max; i ++)
          {
              num2[i] = 0;
              num1[i] = 0;            
          }                
          
          //第一个表达式和第二个表达式相乘
          for (int i = 0; i <= number1; i ++) //第一个表达式的所有面值都有一种情况 
          {
              num1[i] = 1;
          }  
          for (int i = 0; i <= number1 * 1; i ++)
          {
              for (int j = 0; j <= number2 * 2; j += 2)
              {
                  num2[i + j] += num1[i];
              }
          } 
          for (int i = 0; i <= number1 * 1 + number2 * 2; i ++)  //扩大面值范围 
          {
              num1[i] = num2[i];
              num2[i] = 0;
          }
          //第二个表达式和第三个表达式相乘
          for (int i = 0; i <= 1 * number1 + 2 * number2; i ++)
          {
              for (int j = 0; j <= 5 * number3; j += 5)
              {
                  num2[i + j] += num1[i];
              }
          } 
          for (int i =0; i <= max; i ++)
          {
              num1[i] = num2[i];
              num2[i] = 0;
          }
          
          int i;
          for ( i = 0; i <= max; i ++)
          {
              if (num1[i] == 0)
              {
                          printf ("%d\n", i);
                          break;
              }
          } 
          
          if(i == max+1)
            printf("%d\n", i);                  
    }
    
   // system ("pause");
    return 0;
} 
posted @ 2010-08-22 11:46 雪黛依梦 阅读(627) | 评论 (2) | 编辑 收藏
hdu 1160 简单题
//解题思路：根据题意，要输出的是排序之前的序号，所以将要处理的数据都存入一个结构体中
//首先利用qsort对weight进行快排
//剩下的问题就是从已排好的数组中找到最长下降子列（speed），并且输出这个子列的长度和子列中的元素的下标

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

struct mouse
{
  int w;
  int s;
  int cn;
}node[1001];
    
int cmp (const void *a, const void *b)  //一定要注意指针的指向是结构体      mouse
{
    if ( (*(mouse *)a).w != (*(mouse *)b).w )    //体重不等时对体重进行排序 
    return  (*(mouse *)a).w - (*(mouse *)b).w;
    
    else if ( (*(mouse *)a).w == (*(mouse *)b).w )
    return  (*(mouse *)b).s - (*(mouse *)a).s;  //反之对速度进行降序排序 
}

int main ()
{
    
    //输入数据
    int levl = 1;
    while (scanf ("%d%d", &node[levl].w, &node[levl].s) != EOF)                                            
    {
          node[levl].cn = levl;
          levl ++;
    }
    
    //快排
    qsort ( node, levl, sizeof(node[0]), cmp ); 
    
    //对speed 按降序找到最长的子串:
    //用数组F[i]记录以i为起点的满足条件的子列长度，显然初始时为1;
    //用rout[i]记录搜索到最长子串的路径 ，把路径的下标存入到index[]中 
    //max记录到当前为止子列的最长长度，end 记录到当前为止最长子列的最后一个下标
    int  F[1001]; 
    for (int i = 1; i < levl; i ++)
    {
        F[i] = 1;
    } 
    int rout[1001];
    for (int i = 1; i < levl; i ++)
    {
        rout[i] = i;
    }
    
    int max = 1;  int end = 1;
    for (int i = 2; i < levl; i ++)
    {
        for (int j = 1; j < i; j ++)
        {
            if (node[j].s > node[i].s)
            {
               if (F[j] + 1 > F[i])   //现在长度增加1要 > 当前F[i] 才能产生作用 
               {
                        F[i] = F[j] + 1;
                        rout[i] = j;                    //记录找到最下降序列的路径（即下标标号） 
               }
            }
        }
       
       if ( F[i] > max )  //当前记录的长度大于 >  max时 
        {
                max = F[i];
                end = i; 
        }
    }
    
    printf ("%d\n", max);
    
    int index[1001];
    for (int i = 0; i < max; i ++)             //将路径记录到数组index[]中 
    {
        index[max - i - 1] = end;
        end = rout[end--];
    } 
    
    for ( int i = 0; i < max; i ++)
    {
        printf ("%d\n", node[index[i]].cn);
    }
   // system ("pause");
    return 0;
} 
posted @ 2010-08-22 11:24 雪黛依梦 阅读(983) | 评论 (0) | 编辑 收藏
hdu 1028
# include <stdio.h>
# include <stdlib.h>
int main ()
{
    int num1[121];
    int num2[121];
    int n;
    
    while ( scanf ("%d", &n) != EOF )
    {
          for ( int i = 0; i <= n; i ++ )  //不要初始化错了 
          {
              num2[i] = 0;
              num1[i] = 1;           //第一个表达式中的面值组合都是1，所以下面的是从第二个表达式开始 
          }
          
          for ( int i = 2; i <= n; i ++ )
          {
              for( int j = 0; j <= n; j ++ )   //注意每一个表达式都是从第 0 项开始  到 第 n 项 
              {
                   for (int k = 0; k + j <= n; k += i)
                   {
                       num2[k + j] += num1[j];
                   }
              }
              
              for (int i = 0; i <= n; i ++)
              {
                  num1[i] = num2[i];   //num2[]  只是起到一个中间保留面值的作用组合的作用，而从下一个表达式开始又要初始化为0  
                  num2[i] = 0;
              }
          }
          
          printf ("%d\n", num1[n]);
    }
   // system ("pause");
    return 0;
}
posted @ 2010-08-21 20:42 雪黛依梦 阅读(475) | 评论 (0) | 编辑 收藏
hdu 1211 数论
1#include <stdio.h>
 2#include <stdlib.h>
 3#include <math.h>
 4int main ()
 5{
 6    int p, q, e, l;
 7    __int64 n, Fn;
 8    int d;
 9    
10    while ( scanf ("%d%d%d%d", &p, &q, &e, &l) != EOF )
11    {
12          n = p * q;
13          Fn = (p -1) * (q - 1);
14          //利用枚举法求d
15          d = 1;
16          while ( (d * e) % Fn != 1)
17          d ++; 
18           
19           //破译密文:利用scanf输入空格结束处理c
20           int c, temp;
21           for (int i = 0; i < l; i++)
22           {
23               scanf("%d", &c); 
24               temp = 1;
25               for (int j = 1; j <= d; j++)  //难点：如何利用数论知识处理计算 (c 的 d 次方) %  n;
26                                             //上式等于  (c %  n) d 次方  % n; 
27               {
28                   temp *= c;
29                   temp %= n;
30               }  
31               printf ("%c",temp);                                                                                                                                                                                                                                                                                                                                      
32           } 
33           
34           printf ("\n");
35    }
36    return 0;
37}
38
posted @ 2010-08-21 11:43 雪黛依梦 阅读(572) | 评论 (2) | 编辑 收藏
数论 hdu 1215 利用筛选法求得一个数的各因子之和,然后存入到数组中直接访问输出
1/*思路：利用筛选法求得一个数的各因子之和,然后存入到数组中直接访问输出 
 2//1.经典 
 3#include <stdio.h>
 4#include <stdlib.h>
 5#define N 500000
 6
 7int factors[500001] = {0};
 8int main ()
 9{
10    factors[0] = 0; factors[1] = 0;
11    for (int i = 2; i < N + 1; i ++)
12    {
13       factors[i] = 1;
14    } 
15
16    for (int i = 2; i <= (N + 1) / 2; i ++)
17    {
18        for (int j = 2 * i; j < N + 1; j += i)
19        {
20            factors[j] += i;
21        }
22    }
23    
24    int t, n;
25    while ( scanf ("%d", &t) != EOF )
26    {
27          for (int i = 0; i < t; i ++)
28          {
29              scanf ("%d", &n);
30              printf ("%d\n", factors[n]); 
31          }
32    }
33    //system("pause");
34    return 0;
35}*/
36//2.蛮力搜索 
37#include<stdio.h>
38#include<stdio.h>
39int main ()
40{
41int t, n;
42while ( scanf ("%d", &t) != EOF )
43{
44   int i , j, m;
45   for ( i = 0; i < t; i ++)
46   {
47    scanf ("%d", &n);
48    if (n == 1 )
49     printf ("%d\n", 0);
50    else
51    {
52     int factors = 1;
53     for (j = 2; j*j <= n; j++)
54     {
55      if (n % j == 0)
56      {
57       factors += n / j + j;
58      }
59     }
60
61    if ( (j - 1) * (j - 1) == n )
62      factors = factors - ( j - 1);   例如：n = 16时
63    
64     printf ("%d\n", factors);
65    }
66   }
67}
68//system (pause);
69return 0;
70}
71
posted @ 2010-08-21 11:41 雪黛依梦 阅读(224) | 评论 (0) | 编辑 收藏
hdu 1398
理解好了模板就很简单
题目地址：
http://acm.hdu.edu.cn/showproblem.php?pid=1398     母函数 ( Generating function ) 详解
也是一道基础的 母函数题目  
现在以上面的第二种情况每种种类个数无限为例，给出模板： 

1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            21
            22
            23
            24
            25
            26
            27
            28
            29
            30
            31
            32
            33
            34
            35
            36
            37
            38
            
 #include <iostream>
            using namespace std;
            // Author: Tanky Woo
            // www.wutianqi.com
            const int _max = 10001;
            // c1是保存各项质量砝码可以组合的数目
            // c2是中间量，保存没一次的情况
            int c1[_max], c2[_max];
            int main()
            {	//int n,i,j,k;
            int nNum;   // 
            int i, j, k;
             
            while(cin >> nNum)
            {
            for(i=0; i<=nNum; ++i)   // ---- ①
            {
            c1[i] = 1;
            c2[i] = 0;
            }
            for(i=2; i<=nNum; ++i)   // ----- ②
            {
             
            for(j=0; j<=nNum; ++j)   // ----- ③
            for(k=0; k+j<=nNum; k+=i)  // ---- ④
            {
            c2[j+k] += c1[j];
            }
            for(j=0; j<=nNum; ++j)     // ---- ⑤
            {
            c1[j] = c2[j];
            c2[j] = 0;
            }
            }
            cout << c1[n] << endl;
            }
            return 0;
            }

我们来解释下上面标志的各个地方：

①  、首先对c1初始化，由第一个表达式(1+x+x2+..xn)初始化，把质量从0到n的所有砝码都初始化为1.


②  、 i从2到n遍历，这里i就是指第i个表达式，上面给出的第二种母函数关系式里，每一个括号括起来的就是一个表达式。


③、j 从0到n遍历，这里j就是只一个表达式里第j个变量，比如在第二个表达式里：(1+x2+x4….)里，第j个就是x2*j.

③  k表示的是第j个指数，所以k每次增i（因为第i个表达式的增量是i）。

④  、把c2的值赋给c1,而把c2初始化为0，因为c2每次是从一个表达式中开始的


#include <iostream>
using namespace std;
int num1[11111];
int num2[11111];
int main ()
{
    int N;
    while ( cin >> N , N )
    {
           for ( int i = 0 ; i <= N; ++ i )
           {
                 num1[i] = 1;
                 num2[i] = 0; 
           }

           for ( int i = 2; i <= 17; ++ i )       从第二个表达时开始一直到第n个表达式     
                 {
                 for ( int j = 0;j <= N; ++ j )            从这个表达式其中的第j项（0---n）分别和所有可能的面值进行指数相加运算 ，j <= 最大可能的面值

                 {
                       for ( int k = 0; k + j <= N; k += i * i ) 
                       {
                             num2[j + k] += num1[j]; 
                       }
                 } 
                 for ( int j = 0; j <= N; ++ j )
                 {
                       num1[j] = num2[j];
                       num2[j] = 0;
                 }
           }
           cout << num1[N] << endl;
    }
    return 0; 
}


posted @ 2010-08-21 11:24 雪黛依梦 阅读(306) | 评论 (0) | 编辑 收藏
//HDU 1010
//典型的搜索题，这里采用深度优先搜索
//1.本题如果不注意剪枝很容易超时，这里有两处剪枝
//2.深度搜索时主要是处理：1.具体题目中如何定深度，本题以某一个合法位置的四个方向是同一深度所以for 循环中steps + 1
//                                              2.理解回溯的思想
//HDU 1010
#include <stdio.h>
#include <stdlib.h>

int dir[4][2] = {{0, 1}, {-1, 0}, {0, -1},{1, 0}};
char block[9][9];  //迷宫数组 
int si, sj;        //入口 
int di, dj;        //出口 
int m, n, t;
int steps;
bool escape;

int DFS (int curx, int cury, int steps)
{
    //printf ("%d %d", curx, cury);
    if (curx < 0 || curx == 0 || cury < 0 || cury == 0 || curx > m || cury > n)  //该路径位置不合理，此次递归结束，但并不是整个递归结束
     return 0;
    
    if (curx == di && cury == dj && steps == t)
    escape = 1;
    
    //奇偶性剪枝
    int temp = 0;
    temp = (t - steps ) - abs (di - curx) - abs (dj - cury);   //处在该位置的深搜是否有可能到达终点 
    if (temp < 0 || temp & 1)  //当temp为奇数时 按位与是 1 ，temp为偶数时 按位是 0  
       return 0;
       
       if (escape)
       return 1;
    
    for (int i = 0; i < 4; i ++)
    {
        if (block[curx + dir[i][0]][cury + dir[i][1]] != 'X')  //因为也可以是D 
        {
           block[curx + dir[i][0]][cury + dir[i][1]] = 'X';
           DFS (curx + dir[i][0], cury + dir[i][1], steps + 1);
           block[curx + dir[i][0]][cury + dir[i][1]] = '.';
        }
    }
}

int main ()
{
     while ( scanf ("%d%d%d", &m, &n, &t) && (m != 0 && n != 0 && t != 0))
     {
           getchar ();
           int wall = 0;
           for (int i = 1; i <= m; i ++)
           {
               for (int j = 1; j <= n; j ++)
               {
                   scanf ("%c", &block[i][j]);
                   
                   if (block[i][j] == 'S')  //入口坐标 
                   {
                      si = i; 
                      sj = j;
                   }
                  
                   if (block[i][j] == 'D')  //出口坐标 
                   {
                      di = i; 
                      dj = j;
                   } 
                   if (block[i][j] == 'X')
                   {
                      wall ++;
                   }  
               }
               getchar ();    //错点 
           } 
            //printf ("%d %d", si, sj);
           /*for (int i = 1; i <= m; i ++)
           {
               for (int j = 1; j <= n; j ++)
               {  
                   printf ("%d", block[i][j]);
                   }
           }*/
         
           
           if ( m * n - wall < t)  //剪枝 
           {
                printf ("NO\n");
                continue;
           }

              escape = 0;
              steps = 0; 
              block[si][sj] = 'X'; 
              DFS (si, sj, steps);
              
              if (escape)
              printf ("YES\n");  
              else
              printf ("NO\n");
     }
     system ("pause");
     return 0;
}
posted @ 2010-08-19 11:20 雪黛依梦 阅读(485) | 评论 (0) | 编辑 收藏
仅列出标题
共10页: First 2 3 4 5 6 7 8 9 10 
Copyright ©2024 雪黛依梦 Powered By: 博客园 模板提供：沪江博客
<2024年11月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜