C++博客-某科学的魂魄妖梦的笔记

2010暑假讲义_提高版讲义【转自他人】

某科学的魂魄妖梦 — Thu, 04 Oct 2012 04:27:00 GMT

某科学的魂魄妖梦 2012-10-04 12:27 发表评论

2010年暑假集训讲义+程序

某科学的魂魄妖梦 — Thu, 04 Oct 2012 04:12:00 GMT

摘要: （讲义是老师从哪里转来的，不是我们老师写的……）第一题path是水题，注意100 100要用long long存 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 #include <... 阅读全文

某科学的魂魄妖梦 2012-10-04 12:12 发表评论

双调欧几里德旅行商问题

某科学的魂魄妖梦 — Thu, 04 Oct 2012 03:37:00 GMT

老师讲过的……但是忘了好多唉，重新写了一遍

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(2, 1);
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

某科学的魂魄妖梦 2012-10-04 11:37 发表评论

NOIP2009细胞分裂

某科学的魂魄妖梦 — Thu, 04 Oct 2012 03:34:00 GMT

当年的一道很讨厌的题，其实就是道数学题。
（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

某科学的魂魄妖梦 2012-10-04 11:34 发表评论

Marcool 海淀区区赛试题四个国王

某科学的魂魄妖梦 — Thu, 04 Oct 2012 03:29:00 GMT

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, false, sizeof(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, 0, sizeof(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, 0, sizeof(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(1, 0, 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 

某科学的魂魄妖梦 2012-10-04 11:29 发表评论

Marcool304剪枝dfs方法

某科学的魂魄妖梦 — Thu, 04 Oct 2012 03:20:00 GMT

序列

难度级别： 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)的剪枝非常重要，用了这些剪枝就可以非常轻松并快速的解决此题。

某科学的魂魄妖梦 2012-10-04 11:20 发表评论