posted @
2012-10-04 12:27 某科学的魂魄妖梦 阅读(172) |
评论 (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 某科学的魂魄妖梦 阅读(210) |
评论 (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(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
posted @
2012-10-04 11:37 某科学的魂魄妖梦 阅读(187) |
评论 (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 某科学的魂魄妖梦 阅读(735) |
评论 (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, 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
posted @
2012-10-04 11:29 某科学的魂魄妖梦 阅读(258) |
评论 (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 某科学的魂魄妖梦 阅读(278) |
评论 (0) |
编辑 收藏