ACM刷题之路（十六）Acm程序设计竞赛自制模板（二）

1. hdu 2544 最短路贪心手法  先把除1以外的距离初始化为无穷大
2. 先从1开始 利用1可以连接到其他顶点的边 更新距离数组d[]，把1确定下来  1到1距离为0已固定
3. 在取非固定点的最小值 同样利用这个点可以连接到其他顶点的边 更新距离数组d[]...... 以此类推
4. 这样循环n次  即可求出1到n的最短路径  如果不连通  当某一个find函数返回-1  即可判断该图不连通
5. #include<iostream>
6. #include<algorithm>
7. #include<vector>
8. using namespace std;
9. int n, m;
10. bool b[102];//判断最短距离是否确定， 已确定为true 否则为假
11. int d[102];//保存1到各个节点的距离 若b数组相应值为true 则必为最短路 否则为临时最短路
12. #define inf 10000000
13. int find()//找到所有距离的最小值
14. {
15.   int i, j = -1, min = inf;
16.   for (i = 1; i <= n; i++)
17.   {
18.     if (b[i]==false && d[i] < min)
19.     {
20.       j = i;
21.       min = d[i];
22.     }
23.   }
24.   return j;
25. }
26. int main()
27. {
28.   int i, j;
29.   int q, w, e;
30.   while (cin >> n >> m)
31. //输入点数n  和 边数 m
32.   {
33.     vector<pair<int, int> >v[102];
34. //用vector + pair 模拟二维数组 即三个变量的对应关系
35.     if (n == 0 && m == 0) break;
36.     while (m--)
37.     {
38.       pair<int, int>p;//pair为辅助容器
39.       scanf("%d%d%d", &q, &w, &e);
40.       p.first = w;
41.       p.second = e;
42.       v[q].push_back(p);
43. // q 到 w 的 边长 为 e
44.       p.first = q;
45.       v[w].push_back(p);
46. // w 到 q 的 边长 为 e
47.     }
48.     fill(b, b + 102, false); 
49. //初始化函数  节点全部初始化为未访问
50.     fill(d, d + 102, inf);
51. //距离全部初始化为无穷大
52.     d[1] = 0; // 1到1的距离为0
53.     for (i = 1; i <= n; i++)
54.     {
55.       j = find();
56.       b[j] = true;
57. for (vector<pair<int, int> >::iterator it = v[j].begin(); it != v[j].end(); it++)
58. {
59. //此循环为对j到其他结点遍历  更新最短边
60. if (d[it->first] > d[j] + it->second)//如果可以通过中间点使路变的更短
61. {
62. d[it->first] = d[j] + it->second;
63. }
64.   }
65. }
66.     cout << d[n] << endl;
67. //输出1到n的最短距离 
68.   }
69.   return 0;
70. }
71. 
72. 测试数据
73. 9 15
74. 1 2 6
75. 1 3 3
76. 1 4 1
77. 2 3 2
78. 3 4 2
79. 4 5 6
80. 2 5 1
81. 4 6 10
82. 5 6 4
83. 5 7 3
84. 5 9 6
85. 5 8 2
86. 8 9 3
87. 6 7 2
88. 7 9 4
89. 答案：11

1. hdu 2544 最短路 Floyd算法 总结
2. 
3. 状态  ：Accepted  31MS  1848K
4. 基本思想：点A到点B无非是A直接到B 和 A通过若干个点再到B 这两种可能
5. 对于每一个点 都当一遍中间点 判断a[j][i] + a[i][k] < a[j][k]
6. 最后的a数组即可表示最短路径  a[i][j]代表i到j的最短路径 
7. 
8. 
9. 时间复杂度为o(n^3) 
10. 
11. 
12. #include<iostream>
13. #include<algorithm>
14. #include<vector>
15. using namespace std;
16. int n, m;
17. int a[105][105];
18. //a数组直接保存每个点之间的最短距离
19. #define inf 10000000
20. 
21. 
22. 
23. 
24. 
25. 
26. 
27. 
28. 
29. 
30. 
31. 
32. 
33. int main()
34. {
35.   int i, j, k;
36.   int q, w, e;
37.   while (cin >> n >> m)
38. //输入点数n  和 边数 m
39.   {
40.     if (n == 0 && m == 0) break;
41.     for (i = 0; i < 105; i++)
42. //全部初始化为无穷大
43.     {
44.       for (j = 0; j < 105; j++)
45.       {
46.         a[i][j] = inf;
47.       }
48.     }
49.     while (m--)
50.     {
51.       scanf("%d%d%d", &q, &w, &e);
52.       a[q][w] = e;//q到w的距离为e
53.       a[w][q] = e;//w到q的距离为e
54.     }
55. //Floyd算法 o(n^3) 暴力循环判断点i是否可以作为中间点
56.     for (i = 1; i <= n; i++)
57.     {
58.       for (j = 1; j <= n; j++)
59.       {
60.         for (k = 1; k <= n; k++)
61.         {
62. if (a[j][i] + a[i][k] < a[j][k])
63. //如果i当中间点可以缩短路径长度
64. {
65.   a[j][k] = a[j][i] + a[i][k];
66. }
67.         }
68.       }
69.     }
70.     cout << a[1][n] << endl;
71. //输出1到n的最短距离 
72.   }
73.   return 0;
74. }

1. /*
2. 算法思路：
3. 首先就是从图中的一个起点a开始，把a加入U集合，然后，寻找从与a有关联的边中，
4. 权重最小的那条边并且该边的终点b在顶点集合：（V-U）中，我们也把b加入到集合U中，
5. 并且输出边（a，b）的信息，这样我们的集合U就有：{a,b}，
6. 然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：
7. （V-U）中，我们把c加入到集合U中，并且输出对应的那条边的信息，这样我们的集合U就有：
8. {a,b,c}这三个元素了，一次类推，直到所有顶点都加入到了集合U。
9. 2018/12/6   最小生成树   Prim算法
10. */
11. #include<iostream>
12. #include<algorithm>
13. #include<cstring>
14. using namespace std;
15. const int inf = 10000000;
16. const int N = 1002;
17. int G[N][N];//G数组 保存 边长
18. int d[N];
19. //d数组  保存所有点离树的最短距离
20. int n, m;
21. bool vis[N];
22. // vis数组 保存 判断这个点是否放入树中 
23. int prim()
24. {
25.   fill(d, d + N, inf);//初始化无穷大
26.   d[1] = 0;
27.   int ans = 0;//初始化答案为0
28. 
29. 
30. 
31. 
32. 
33.   for (int i = 1; i <= n; i++)
34. //i层循环 找所有连通到的边中最短的
35.   {
36.     int u = -1;//找单次的最短边
37.     int min = inf;
38.     for (int j = 1; j <= n; j++)
39.     {
40.       if (vis[j] == false && d[j]<min)//遍历求出 没有进入树的节点 离树的最短距离
41.       {
42.         u = j;
43.         min = d[j];
44.       }
45.     }
46.     if (u == -1)//如果所有边都无穷大，说明不连通，就返回错误
47.       return -1;
48.     vis[u] = true;//该点入树
49.     ans += d[u];//距离总和加上U点离树的距离
50.     for (int v = 1; v <= n; v++)
51.     {//这里是更新没有入树的节点离树的最短距离
52.       if (vis[v] == false && G[u][v] != inf&&G[u][v]<d[v])
53.         d[v] = G[u][v];
54.     }
55.   }
56.   return ans;
57. }
58. int main()
59. {
60.   int u, v, c;
61.   cin >> n >> m;
62.   fill(G[0], G[0] + N*N, inf);
63.   for (int i = 1; i <= m; i++)
64.   {
65.     cin >> u >> v >> c;
66.     G[u][v] = G[v][u] = c;
67.   }
68.   int ans = prim();
69.   if (ans == -1)//如果不连通
70.     cout << "-1" << endl;
71.   else
72.     cout << ans << endl;
73.   return 0;
74. }

1. #include<iostream>
2. #include<cstdio>
3. #include<cstring>
4. #include<algorithm>
5. #include<cmath>
6. #define PI 3.1415926535
7. using namespace std;
8. struct node
9. {
10.   int x, y;
11. };
12. node vex[1000];//存入的所有的点
13. node stackk[1000];//凸包中所有的点
14. int xx, yy;
15. bool cmp1(node a, node b)//排序找第一个点
16. {
17.   if (a.y == b.y)
18.     return a.x<b.x;
19.   else
20.     return a.y<b.y;
21. }
22. int cross(node a, node b, node c)//计算叉积
23. {
24.   return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
25. }
26. double dis(node a, node b)//计算距离
27. {
28.   return sqrt((a.x - b.x)*(a.x - b.x)*1.0 + (a.y - b.y)*(a.y - b.y));
29. }
30. bool cmp2(node a, node b)//极角排序另一种方法，速度快
31. {
32.   if (atan2(a.y - yy, a.x - xx) != atan2(b.y - yy, b.x - xx))
33.     return (atan2(a.y - yy, a.x - xx))<(atan2(b.y - yy, b.x - xx));
34.   return a.x<b.x;
35. }
36. bool cmp(node a, node b)//极角排序
37. {
38.   int m = cross(vex[0], a, b);
39.   if (m>0)
40.     return 1;
41.   else if (m == 0 && dis(vex[0], a) - dis(vex[0], b) <= 0)
42.     return 1;
43.   else return 0;
44. }
45. int main()
46. {
47.   int t, L;
48.   while (~scanf("%d", &t), t)//总共t个点
49.   {
50.     int i;
51.     for (i = 0; i<t; i++)
52.     {
53.       scanf("%d%d", &vex[i].x, &vex[i].y);//输入每个点的x和y坐标
54.     }
55.     if (t == 1)//如果只有一个点 凸包周长为0
56.       printf("%.2f\n", 0.00);
57.     else if (t == 2)
58.       printf("%.2f\n", dis(vex[0], vex[1]));//如果只有两个点 周长是两点距离
59.     else
60.     {
61.       memset(stackk, 0, sizeof(stackk));
62.       sort(vex, vex + t, cmp1);//排序找第一个点
63.       stackk[0] = vex[0];//用数组模拟栈
64.       xx = stackk[0].x;
65.       yy = stackk[0].y;
66.       sort(vex + 1, vex + t, cmp2);//极角排序
67.       stackk[1] = vex[1];//将凸包中的第两个点存入凸包的结构体中
68.       int top = 1;//最后凸包中拥有点的个数
69.       for (i = 2; i<t; i++)
70.       {
71.         while (i >= 1 && cross(stackk[top - 1], stackk[top], vex[i])<0)
72.           //i>=1防止越界  如果在右边 把栈顶元素出栈
73.           top--;
74.         stackk[++top] = vex[i];//控制<0或<=0可以控制重点，共线的，具体视题目而定。
75.       }
76.       double s = 0;
77.       for (i = 1; i <= top; i++)   //计算凸包的周长
78.         s += dis(stackk[i - 1], stackk[i]);
79.       s += dis(stackk[top], vex[0]);//最后一个点和第一个点之间的距离
80.       printf("%.2lf\n", s);
81.     }
82.   }
83. }

1. void dfs(ll shu, int fei0, int changdu)//在搜索时需变化的量
2. {
3.  //满足条件返回
4.  //越界返回 
5.  //明显不符合条件返回 如距离奇偶性
6.  //已经找到目标  返回
7.  for (int i = 1; i <= 9; i++)
8.  {
9.    dfs(shu * 10 + i, fei0 + 1, changdu + 1);//继续深搜下去
10.   }
11. }

1. void bfs(int x)
2. {
3.  queue<int>q1;//1.先创建队列
4.  q1.push(x);//2.放入初始条件
5.  while (!q1.empty())//3.开始循环广搜
6.  {
7.    int t = q1.front();
8.    q1.pop();//4.顶部删掉
9.    for (vector<int>::iterator it = v[t].begin(); it != v[t].end(); it++)
10.     {//5.把顶部能牵连到的元素压入队列
11.       if (a[*it] == false)
12.         q1.push(*it);
13.     }
14.   }//6.全部循环结束后，如果需要返回值就返回
15. }

1. #include<iostream>
2. #include<cstring>
3. using namespace std;
4. struct node
5. {
6.  int fen, num;
7. };
8. int dp[41];
9. int main()
10. {
11.   int T;
12.   scanf("%d", &T);
13.   while (T--)
14.   {
15.     node a[10];
16.     memset(dp, 0, sizeof(dp));
17.     int n,  m;
18.     scanf("%d%d", &m, &n);
19.     int i, j, w;
20.     for (i = 0; i < n; i++)
21.       scanf("%d%d", &a[i].fen, &a[i].num);//输入每种物品的价值 和 物品数量
22.     dp[0] = 1;//初始化dp数组
23.     for (i = 0; i < n; i++)//枚举物品种类
24.     {
25.       for (j = m; j >= a[i].fen; j--)//枚举背包容量，01背包，要从大到小推，不然会重复加
26.       {
27.         for (w = 1; w <= a[i].num; w++)
28.     //枚举这个物品的个数，如果当前枚举到的价值能放入此物品的话，就加上之前的价值
29.         {
30.           if (j >= a[i].fen*w)
31.     //a[i].fen*w是w个物品能产生的价值，然后j-a[i].fen*w就是去掉a[i].fen*w的价值，加起来递推
32.           {
33.             dp[j] += dp[j - a[i].fen*w];
34.           }
35.           else break;
36.         }
37.       }
38.     }
39.     printf("%d\n", dp[m]);//m个物品的时候所能产生的价值
40.   }
41.   return 0;
42. }

1. for (i = 1; i <= n; i++)
2. {
3.  for (j = v; j >= a[i].cost; j--)
4.  {
5.    if (f[j] < f[j - a[i].cost] + a[i].val)
6.      f[j] = f[j - a[i].cost] + a[i].val;
7.  }
8. }

1. for (int i = 1; i <= n; i++)
2. {
3.  for (int j = w[i]; j <= v; j++)
4.  {
5.    dp[j] = min(dp[j], dp[j - w[i]] + p[i]);
6.  }
7. }

1. for (int i = 0; i<n; i++)
2. {      
3.  for (int k = 0; k<num[i]; k++)
4.  {            
5.    for (int j = cc; j >= v[i]; j--)
6.    {   
7.      dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
8.    }
9.  }
10. }

1. #include <iostream>
2. #include <string>
3. #include <cstring>
4. #include <stack>
5. #include <algorithm>
6. using namespace std;
7. 题意：有n门课，每门课有截止时间和完成所需的时间，如果超过规定时间完成，每超过一天就会扣1分，问怎样安排做作业的顺序才能使得所扣的分最小
8. 思路：因为最多只有15门课程，可以使用二进制来表示所有完成的状况
9. 例如5，二进制位101，代表第一门和第三门完成了，第二门没有完成，那么我们可以枚举1~1<<n便可以得出所有的状态
10. 然后对于每一门而言，其状态是t = 1<<i，我们看这门在现在的状态s下是不是完成，可以通过判断s&t是否为1来得到
11. 当得出t属于s状态的时候，我们便可以进行DP了，在DP的时候要记录路径，方便之后的输出
12. const int inf = 1 << 30;
13. struct node
14. {
15.   string name;
16.   int dead, cost;
17. } a[50];
18. struct kode
19. {
20.   int time, score, pre, now;
21. } dp[1 << 15];
22. int main()
23. {
24.   int t, i, j, s, n, end;
25.   cin >> t;
26.   while (t--)
27.   {
28.     memset(dp, 0, sizeof(dp));
29.     cin >> n;
30.     for (i = 0; i<n; i++)
31.       cin >> a[i].name >> a[i].dead >> a[i].cost;//每门课的名字、最晚完成时间、花费时间
32.     end = 1 << n;//n-1指的是每门课都完成的情况
33.     for (s = 1; s<end; s++)//暴力遍历
34.     {
35.       dp[s].score = inf;//先初始化为无穷大    是最少扣的分数
36.       for (i = n - 1; i >= 0; i--)
37.       {
38.         int tem = 1 << i;//右往左数第i+1位数
39.         if (s & tem)//如果右往左数第i+1位数为1   即i+1事件已经完成
40.         {
41.           int past = s - tem;//不可能为负 past代表当前事件发生之前的状态
42.           int st = dp[past].time + a[i].cost - a[i].dead;
43. //转移方程 要花的时间=前面要的时间+当前花的时间-最晚时间
44.           if (st<0)//如果当前不会被扣分 则等于0
45.             st = 0;
46.           if (st + dp[past].score<dp[s].score)//更新取最小值
47.           {
48.             dp[s].score = st + dp[past].score;//当前要扣的分
49.             dp[s].now = i;//当前dp最后执行的事件位置
50.             dp[s].pre = past;//执行前的二进制状态
51.             dp[s].time = dp[past].time + a[i].cost;
52.           }
53.         }
54.       }
55.     }
56.     stack<int> S;
57.     int tem = end - 1;
58.     cout << dp[tem].score << endl;//输出总的最少扣分
59.     while (tem)
60.     {
61.       S.push(dp[tem].now);//最后做的事件下表 入栈
62.       tem = dp[tem].pre;//转到前面的事件
63.     }
64.     while (!S.empty())
65.     {
66.       cout << a[S.top()].name << endl;
67.       S.pop();
68.     }
69.   }
70.   return 0;
71. }

1. #include<iostream>
2. #include<cstring>
3. using namespace std;
4. int n, p, a, b, m, x, y, ans;
5. struct node
6. {
7.  int l, r, w, f;
8. }tree[400001];
9. inline void build(int k, int ll, int rr)//建树 
10. {
11.   tree[k].l = ll, tree[k].r = rr;
12.   if (tree[k].l == tree[k].r)
13.   {
14.     scanf("%d", &tree[k].w);
15.     return;
16.   }
17.   int m = (ll + rr) / 2;
18.   build(k * 2, ll, m);
19.   build(k * 2 + 1, m + 1, rr);
20.   tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
21. }
22. inline void down(int k)//标记下传 
23. {
24.   tree[k * 2].f += tree[k].f;
25.   tree[k * 2 + 1].f += tree[k].f;
26.   tree[k * 2].w += tree[k].f*(tree[k * 2].r - tree[k * 2].l + 1);
27.   tree[k * 2 + 1].w += tree[k].f*(tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1);
28.   tree[k].f = 0;
29. }
30. inline void ask_point(int k)//单点查询
31. {
32.   if (tree[k].l == tree[k].r)
33.   {
34.     ans = tree[k].w;
35.     return;
36.   }
37.   if (tree[k].f) down(k);
38.   int m = (tree[k].l + tree[k].r) / 2;
39.   if (x <= m) ask_point(k * 2);
40.   else ask_point(k * 2 + 1);
41. }
42. inline void change_point(int k)//单点修改 
43. {
44.   if (tree[k].l == tree[k].r)
45.   {
46.     tree[k].w += y;
47.     return;
48.   }
49.   if (tree[k].f) down(k);
50.   int m = (tree[k].l + tree[k].r) / 2;
51.   if (x <= m) change_point(k * 2);
52.   else change_point(k * 2 + 1);
53.   tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
54. }
55. inline void ask_interval(int k)//区间查询 
56. {
57.   if (tree[k].l >= a&&tree[k].r <= b)
58.   {
59.     ans += tree[k].w;
60.     return;
61.   }
62.   if (tree[k].f) down(k);
63.   int m = (tree[k].l + tree[k].r) / 2;
64.   if (a <= m) ask_interval(k * 2);
65.   if (b>m) ask_interval(k * 2 + 1);
66. }
67. inline void change_interval(int k)//区间修改 
68. {
69.   if (tree[k].l >= a&&tree[k].r <= b)
70.   {
71.     tree[k].w += (tree[k].r - tree[k].l + 1)*y;
72.     tree[k].f += y;
73.     return;
74.   }
75.   if (tree[k].f) down(k);
76.   int m = (tree[k].l + tree[k].r) / 2;
77.   if (a <= m) change_interval(k * 2);
78.   if (b>m) change_interval(k * 2 + 1);
79.   tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
80. }
81. int main()
82. {
83.   printf("请输入线段树的大小n\n");
84.   scanf("%d", &n);//n个节点 
85.   printf("请输入n个数，分别是1到n的初始值\n");
86.   build(1, 1, n);//从1开始做下标 ,建立1到n的线段树
87.   printf("建树完成\n请输入操作线段树的次数m\n");
88.   scanf("%d", &m);//m种操作 
89.   printf("请输出相应指令\n1 单点查询\n2 单点修改\n3区间查询\n4区间修改\n");
90.   for (int i = 1; i <= m; i++)
91.   {
92.     scanf("%d", &p);
93.     ans = 0;
94.     if (p == 1)
95.     {
96.       printf("单点查询,输出第x个数 \n请输入x\n");
97.       scanf("%d", &x);
98.       ask_point(1);//单点查询,输出第x个数 
99.       printf("第%d个数是%d\n", x, ans);
100.    }
101.    else if (p == 2)
102.    {
103.      printf("对第x个数加上y,请输入X和Y\n");
104.      scanf("%d%d", &x, &y);
105.      change_point(1);//单点修改
106.      printf("修改完成\n");
107.    }
108.    else if (p == 3)
109.    {
110.      printf("查询[a,b]区间的和，请输入a和b\n");
111.      scanf("%d%d", &a, &b);//区间查询 
112.      ask_interval(1);
113.      printf(" %d 到 %d 的和为 %d\n", a, b, ans);
114.    }
115.    else
116.    {
117.      printf("对第[a,b]中所有数都加上y,请输入a,b和y\n");
118.      scanf("%d%d%d", &a, &b, &y);//区间修改 
119.      change_interval(1);
120.      printf("修改完成\n");
121.    }
122.  }
123. }