随笔 - 6  文章 - 1  trackbacks - 0
<2019年2月>
272829303112
3456789
10111213141516
17181920212223
242526272812
3456789

常用链接

留言簿

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜












posted @ 2012-10-04 12:27 某科学的魂魄妖梦 阅读(40) | 评论 (0)编辑 收藏
     摘要: (讲义是老师从哪里转来的,不是我们老师写的……)第一题path是水题,注意100 100要用long long存 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 #include <...  阅读全文
posted @ 2012-10-04 12:12 某科学的魂魄妖梦 阅读(49) | 评论 (0)编辑 收藏
老师讲过的……但是忘了好多唉,重新写了一遍
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #define MAX 200000000
 5 using namespace std;
 6 FILE * fin  = fopen("file.in",  "r");
 7 FILE * fout = fopen("file.out""w");
 8 struct point
 9 {
10     double x, y;
11 };
12 point vert[101];
13 double res[101][101];
14 double dis(int i, int j)
15 {
16     return sqrt((vert[i].x - vert[j].x) * (vert[i].x - vert[j].x) + (vert[i].y - vert[j].y) * (vert[i].y - vert[j].y));
17 }
18 double min(double a, double b)
19 {
20     return a < b ? a : b;
21 }
22 double work(int n)
23 {
24     double s, Min = MAX;
25     res[2][1= dis(21);
26     for (int i = 2; i <= n; i++)
27         for (int j = 1; j < i; j++)
28         {
29             res[i][j] = min(res[i][j], res[i - 1][j] + dis(i - 1, i));
30             res[i][i - 1= min(res[i][i - 1], res[i - 1][j] + dis(j, i));
31         }
32     for (int i = 1; i < n; i++)
33     {
34         s = dis(i, n);
35         if (Min > res[n][i] + s)
36             Min = res[n][i] + s;
37     }
38     return Min;
39 }
40 int main()
41 {
42     int n;
43     fscanf(fin, "%d"&n);
44     for (int i = 1; i <= n; i++)
45         fscanf(fin, "%lf%lf"&vert[i].x, &vert[i].y);
46     for (int i = 1; i <= n; i++)
47         for (int j = 1; j <= n; j++)
48             res[i][j] = MAX;
49     fprintf(fout, "%.4lf\n", work(n));
50     return 0;
51 }
52 

posted @ 2012-10-04 11:37 某科学的魂魄妖梦 阅读(64) | 评论 (0)编辑 收藏
当年的一道很讨厌的题,其实就是道数学题。
(P.s.那时候我代码风格很坏,不要看)
 1 #include <stdio.h>
 2 int hashbiao[30001];
 3 int main()
 4 {
 5     int n , m , t , i , j , js = 0 , maxz = 0 , max = 0 , min = 100000;
 6     scanf("%d%d%d"&n, &m, &t);
 7     long long shuju[n + 1]; //其实这么写不太好 不过当时是这么写的,现在懒得改了 
 8     for (i = 0 ; i < n ; i++)
 9         scanf("%lld"&shuju[i]);
10     if (m == 1)
11         printf("0\n");
12     else
13     {
14          i = 2;
15          while (m != 1)
16          {
17               while (m % i == 0)
18               {
19                    m /= i;
20                    hashbiao[i]++;
21               }
22               if (i > maxz)
23                    maxz = i;
24               hashbiao[i++*= t;
25          }
26          int ans = 0;
27          for (i = 0 ; i < n ; i++)
28          {
29               max = 0;
30               for (j = 2 ; j <= maxz ; j++)
31               {
32                    if (hashbiao[j] == 0)
33                         continue;
34                    js = 0;
35                    while (shuju[i] % j == 0)
36                    {
37                         shuju[i] /= j;
38                         js++;
39                    }
40                    if (!js)
41                    {
42                         max = 100000;
43                         break;
44                    }
45                    if ((hashbiao[j] - 1/ js > max)
46                         max = (hashbiao[j] - 1/ js;
47               }
48               if (max < min)
49               {
50                    min = max;
51                    ans = max;
52               }
53          }
54          if (ans == 0)
55              printf("-1\n");
56          else
57              printf("%d\n", ans + 1);
58     }
59     return 0;
60 }
61 
posted @ 2012-10-04 11:34 某科学的魂魄妖梦 阅读(224) | 评论 (0)编辑 收藏
Marcool四个国王解法
题目大意是:
在一个M×N的棋盘上,放置K个国王(注意!不是王后),有多少种互相不攻击的方法。
测试数据里面有:70%,1<=M<=5,1<=N<=5,1<=K<=10。这个数据量用广搜就能AC,麻烦的是剩下的是1<=M<=100,1<=N<=50,1<=K<=M*N,这就需要一些数学方法进行判断了。
 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MAX 2147483648
 4 using namespace std;
 5 int n, m, king_number;
 6 long long dp[100][1000], dp_tmp[100][1000], ans = 0;
 7 bool flag[10];
 8 void READY(int x)
 9 {
10     memset(flag, falsesizeof(flag));
11     int cnt = n;
12     while (x != 0)
13     {
14         if (x % 2 == 0)
15             flag[cnt] = true;
16         x /= 2;
17         cnt--;
18     }
19 }
20 void Deep_Fisrt_Search(int x, int y, int z, long long std_dp, bool left)
21 {
22     if (z > king_number)
23         return ;
24     if (x == n + 1)
25     {
26         dp_tmp[y][z] += std_dp;
27         if (dp_tmp[y][z] > 2147483647)
28             dp_tmp[y][z] = MAX;
29         return ;
30     }
31     Deep_Fisrt_Search(x + 1, y * 2, z, std_dp, false); 
32     if(! left && ! flag[x] && !(x - 1 >= 1 && flag[x - 1]) && ! (x + 1 <= n && flag[x + 1])) 
33         Deep_Fisrt_Search(x + 1, y * 2 + 1, z + 1, std_dp, true); 
34     return ;
35 }
36 int main()
37 {
38     scanf("%d %d %d"&n, &m, &king_number);
39     memset(dp, 0sizeof(dp));
40     dp[0][0= 1;
41     int end = 1;
42     for (int i = 1; i <= n; i++)
43         end *= 2;
44     end --;
45     for (int i = 1; i <= m; i++)
46     {
47         memset(dp_tmp, 0sizeof(dp_tmp));
48         for (int j = 0; j <= end; j++)
49         {
50             READY(j);
51             for (int k = 0; k <= king_number; k++)
52             {
53                 if (dp[j][k] == 0)
54                     continue;
55                 Deep_Fisrt_Search(10, k, dp[j][k], false);
56             }
57         }
58         memcpy(dp, dp_tmp, sizeof(dp)); 
59     }
60     for (int i = 0; i <= end; i++)
61     {
62         ans += dp[i][king_number];
63         if (ans > 2147483647)
64         {
65             printf("2147483648\n");
66             return 0;
67         }
68     }
69     printf("%lld\n", ans);
70     return 0;
71 }
72 
posted @ 2012-10-04 11:29 某科学的魂魄妖梦 阅读(95) | 评论 (1)编辑 收藏
序列
难度级别: E; 运行时间限制: 3000 ms; 运行空间限制: 65536 KB;代码长度限制: 2000000 B
试题描述
给定M(M<=100)个序列,每个序列N(N<=2000)个非负整数,现在我们要从每个序列选出一个数,一共有N^M种选法,然后我们对从每个序列选出的数求和,得到了N^M个不同的值,我们需要求这当中前N小的值。
输入
第一行M,N
然后M行,每行N个数,代表一个序列
输出
排好序的前N小的数
输入示例
2 3
1 2 3
2 2 3
输出示例
3 3 4

首先DFS有一个顺序性,这个顺序的好坏决定了剪枝的优劣。我们可以注意到此题要求求前N小的组合方案,所以应该基本上选择的都是每个序列中非常靠前的几个数。所以如果说从大的数开始搜索显然效率不好,所以应该把所有序列从小到大排序,这个是剪枝1)。再思考以后发现搜索到第i小的方案后找第i+1小的方案时,有很大可能是把某序列的数向后推了一个,并且这两个数一定是最接近的。所以如果说这种情况发生在搜索的最后一层效率会搞很多。所以我们应该把数与数之间相差最小的排在后面,所以我们可以把所有序列按方差从大到小排序,此为剪枝2)。还有一个剪枝非常明显,如果说此时我们已经搜到的前n小的和中的最大值,比我们现在搜索到位置的和要小,那么如果继续搜索下去不可能找到更小的值,所以直接回溯到上一层,此为简直3)。最后一个剪枝也比较关键,就是如何维护搜到的前n小的数,这时就需要利用堆了,此为剪枝4)。

综上所述,此题可以使用4个剪枝:

1)把所有序列从小到大排序

2)序列之间按方差从大到小排序

3)搜索到某一位置时的和已大于等于已有和的最大值,直接回溯

4)用堆维护前n小的和

1)、3)、4)的剪枝非常重要,用了这些剪枝就可以非常轻松并快速的解决此题。

posted @ 2012-10-04 11:20 某科学的魂魄妖梦 阅读(98) | 评论 (0)编辑 收藏
仅列出标题