试题 H: 限高杆
【问题描述】
某市有 n 个路口，有 m 段道路连接这些路口，组成了该市的公路系统。其中一段道路两端一定连接两个不同的路口。道路中间不会穿过路口。由于各种原因，在一部分道路的中间设置了一些限高杆，有限高杆的路段货车无法通过。在该市有两个重要的市场 A 和 B，分别在路口 1 和 n 附近，货车从市场 A出发，首先走到路口 1 ，然后经过公路系统走到路口 n，才能到达市场 B。
两个市场非常繁华，每天有很多货车往返于两个市场之间。市长发现，由于限高杆很多，导致货车可能需要绕行才能往返于市场之间，这使得货车在公路系统中的行驶路程变长，增加了对公路系统的损耗，增加了能源的消耗，同时还增加了环境污染。市长决定要将两段道路中的限高杆拆除，使得市场 A 和市场 B 之间的路程变短。请问最多能减少多长的距离？
【输入格式】
输入的第一行包含两个整数 n, m，分别表示路口的数量和道路的段数。
接下来 m 行，每行四个整数 a, b, c, d，表示路口 a 和路口 b 之间有一段长度为 c 的道路。如果 d 为 0，表示这段道路上没有限高杆；如果 d 为 1，表示这段道路上有限高杆。两个路口之间可能有多段道路。
输入数据保证在不拆除限高杆的情况下，货车能通过公路系统从路口 1 正常行驶到路口 n。
【输出格式】
输出一行，包含一个整数，表示拆除两段道路的限高杆后，市场 A 和市场B 之间的路程最大减少多长距离。
1. 【样例输入】 2. 5 7 3. 1 2 1 0 4. 2 3 2 1 5. 1 3 9 0 6. 5 3 8 0 7. 4 3 5 1 8. 4 3 9 0 9. 4 5 4 0 10. 【样例输出】 11. 6
【样例说明】
只有两段道路有限高杆，全部拆除后，1 到 n 的路程由原来的 17 变为了
11，减少了 6。
【评测用例规模与约定】
对于 30% 的评测样例，2 ≤ n ≤ 10，1 ≤ m ≤ 20, 1 ≤ c ≤ 100。
对于 50% 的评测样例，2 ≤ n ≤ 100，1 ≤ m ≤ 1000, 1 ≤ c ≤ 1000。
对于 70% 的评测样例，2 ≤ n ≤ 1000，1 ≤ m ≤ 10000, 1 ≤ c ≤ 10000。
对于所有评测样例，2 ≤ n ≤ 10000，2 ≤ m ≤ 100000, 1 ≤ c ≤ 10000，至少
有两段道路有限高杆。
先计算不拆限高架的情况下,即d等于1的输入数据,我们先保存起来,其中ganx保存起点,gany保存终点,ganLi保存距离
因为蓝桥杯是闭卷考试,dijkstra算法一下子想不起来了,所以使用了floyd算法,暴力三层for循环,找到每个点之间的最短路径保存在li1数组中,把1到n的最短路径保存在 qianAns 中
然后再两层for循环遍历限高的道路,使用li2临时数组复制li1的最短路数据,然后尝试把两个拆掉限高的路加进去,再求一遍最短路
多次遍历完成,计算出最短值
相减就是答案,算法非常差,但基础样例可以过
1. #include<iostream> 2. #include<string> 3. #include<cstring> 4. #include<algorithm> 5. #include<cmath> 6. #include<cstdio> 7. #include<queue> 8. using namespace std; 9. int li1[10002][10002]; // qian 10. int li2[10002][10002]; // hou 11. int ganx[10002]; 12. int gany[10002]; 13. int ganLi[10002]; 14. int main(){ 15. 16. int n,m; 17. 18. while(cin>>n>>m){ 19. memset(li1,1,sizeof(li1)); 20. int ganGe = 0; 21. for(int i = 0 ; i <= n ; i ++){ 22. li1[i][i] = 0; 23. } 24. for(int i = 0 ; i < m ; i ++){ 25. int a,b,c,d; 26. scanf("%d%d%d%d",&a,&b,&c,&d); 27. if(d == 0){ 28. if(li1[a][b] > c){ 29. li1[a][b] = c; 30. } 31. if(li1[b][a] > c){ 32. li1[b][a] = c; 33. } 34. }else{ 35. ganx[ganGe] = a; 36. gany[ganGe] = b; 37. ganLi[ganGe++] = c; 38. } 39. } 40. for(int i = 1 ; i <= n ; i ++ ){ 41. for(int j = 1 ; j <= n ; j++ ){ 42. for(int k = 1 ; k <= n ; k ++ ){ 43. if(li1[i][j] > li1[i][k] + li1[k][j] ){ 44. li1[i][j] = li1[i][k] + li1[k][j]; 45. } 46. } 47. } 48. } 49. int qianAns = li1[1][n]; 50. int houAns = 99999; 51. for(int g1 = 0 ; g1<ganGe ; g1 ++ ){ 52. for(int g2 = g1 + 1 ; g2 < ganGe ; g2++){ 53. for(int i = 1;i<=n;i++){ 54. for(int j = 1 ; j <= n ; j ++){ 55. li2[i][j] = li1[i][j]; 56. } 57. } 58. if(li2[ganx[g1]][gany[g1]] > ganLi[g1]){ 59. li2[ganx[g1]][gany[g1]] = ganLi[g1]; 60. } 61. if(li2[gany[g1]][ganx[g1]] > ganLi[g1]){ 62. li2[gany[g1]][ganx[g1]] = ganLi[g1]; 63. } 64. if(li2[ganx[g2]][gany[g2]] > ganLi[g2]){ 65. li2[ganx[g2]][gany[g2]] = ganLi[g2]; 66. } 67. if(li2[gany[g2]][ganx[g2]] > ganLi[g2]){ 68. li2[gany[g2]][ganx[g2]] = ganLi[g2]; 69. } 70. for(int i = 1 ; i <= n ; i ++ ){ 71. for(int j = 1 ; j <= n ; j++ ){ 72. for(int k = 1 ; k <= n ; k ++ ){ 73. if(li2[i][j] > li2[i][k] + li2[k][j] ){ 74. li2[i][j] = li2[i][k] + li2[k][j]; 75. } 76. } 77. } 78. } 79. if(li2[1][n] < houAns){ 80. houAns = li2[1][n]; 81. } 82. } 83. } 84. 85. // cout<<qianAns << endl; 86. // cout<<houAns<<endl; 87. cout<<qianAns - houAns<<endl; 88. } 89. return 0; 90. }
试题 I: 画中漂流
【问题描述】
在梦境中，你踏上了一只木筏，在江上漂流。根据对当地的了解，你知道在你下游 D 米处有一个峡谷，如果你向下游前
进大于等于 D 米则必死无疑。现在你打响了急救电话，T 秒后救援队会到达并将你救上岸。水流速度是1 m/s，你现在有 M 点体力。每消耗一点体力，你可以划一秒桨使船向上游前进 1m，否则会向下游前进 1m (水流)。M 点体力需在救援队赶来前花光。因为江面太宽了，凭借你自己的力量不可能上岸。请问，有多少种划桨的方案可以让你得救。
两个划桨方案不同是指：存在某一秒钟，一个方案划桨，另一个方案不划。
【输入格式】
输入一行包含三个整数 D, T, M。
【输出格式】
输出一个整数，表示可以让你得救的总方案数，答案可能很大，请输出方
案数除以 1, 000, 000, 007 的余数。
1. 【样例输入】 2. 1 6 3 3. 【样例输出】 4. 5
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ T ≤ 350。
对于所有评测用例，1 ≤ T ≤ 3000, 1 ≤ D ≤ T, 1 ≤ M ≤ 1500。
我运用了广搜,结构体的weizhi是相对于起点的位置,tili为当前还剩下的体力,time是当前剩余的时间
注意题目要求,必须在救援队来之前把体力用完,如果没用完,不计数
1. #include<iostream> 2. #include<string> 3. #include<cstring> 4. #include<algorithm> 5. #include<cmath> 6. #include<cstdio> 7. #include<queue> 8. using namespace std; 9. struct mu{ 10. int weizhi; 11. int tili; 12. int time; 13. mu(int x,int y,int z){ 14. weizhi = x; 15. tili = y; 16. time = z; 17. } 18. }; 19. void bfs(int d,int t,int m){ 20. int ans = 0; 21. d = -d; 22. queue<mu> q; 23. q.push(mu(0,m,t)); 24. while(!q.empty()){ 25. mu mm = q.front(); 26. if(mm.weizhi <= d){ // si 27. q.pop(); 28. continue; 29. } 30. if(mm.tili == 0 && mm.time == 0){ 31. ans ++; 32. } 33. if(mm.time <= 0){ 34. q.pop(); 35. continue; 36. } 37. if(mm.tili > 0){ // up 38. mu m1 = mu(mm.weizhi + 1,mm.tili -1 , mm.time - 1); 39. q.push(m1); 40. } 41. // down 42. mu m2 = mu(mm.weizhi - 1,mm.tili , mm.time - 1); 43. q.push(m2); 44. q.pop(); 45. } 46. cout<<ans<<endl; 47. } 48. int main(){ 49. int d,t,m; 50. while(cin>>d>>t>>m){ 51. bfs(d,t,m); 52. } 53. return 0; 54. }
试题 J: 旅行家
【问题描述】
从前，在海上有 n 个岛屿，编号 1 至 n。居民们深受洋流困扰，无法到达比自己当前所在岛屿编号更小的岛屿。经过数年以后，岛屿上的人数随着岛屿的编号递增（可能相等）。作为一名出色的旅行家（RP 学家），你想从 1 号岛屿出发开启一次旅程，以获得更多的 RP，因为受到海洋的洋流影响，你只能去到比当前岛屿编号更大的岛屿。因为你比较善良，你会在离开一个岛屿的时候将你的 RP 分散给岛民，具体的：你的 RP 会除以 2（用去尾法取整，或者说向零取整）（当你的 RP 小于零时，岛民也依旧要帮你分担，毕竟你们已经建立起了深厚的友谊）。第 i 号岛屿有 Ti 人, 但是你很挑剔，每次你从 j 号岛屿到达 i 号岛屿时，你只会在到达的岛屿上做 Ti × T j 件好事（一件好事可以获得 1 点 RP)。
唯一不足的是，由于你在岛上住宿，劳民伤财，你会扣除巨量 RP，第 i 号岛屿的住宿扣除 Fi 点 RP。注意：将离开一个岛屿时，先将 RP 扣除一半，再扣除住宿的 RP，最后在新到达的岛屿上做好事，增加 RP。离开 1 号岛屿时需要扣除在 1 号岛屿住宿的 RP，当到达这段旅程的最后一个岛屿上时，要做完好事，行程才能结束，也就是说不用扣除在最后到达的岛屿上住宿的 RP。你因为热爱旅行 (RP)，所以从 1 号岛屿开始旅行，初始时你有 0 点 RP。
你希望选择一些岛屿经过，最终选择一个岛屿停下来，求最大的 RP 值是多少？
【输入格式】
输入的第一行包含一个数 n , 表示岛屿的总数。
第二行包含 n 个整数 T1, T2, · · · , Tn , 表示每个岛屿的人口数。
第三行包含 n 个整数 F1, F2, · · · , Fn , 表示每个岛屿旅馆损失的 RP。
【输出格式】
输出一个数，表示最大获得的 RP 值。
1. 【样例输入】 2. 3 3. 4 4 5 4. 1 10 3 5. 【样例输出】 6. 19
【样例说明】
从一号岛屿直接走到三号岛屿最优，初始 0 点 RP，扣除一半取整变成 0点。扣除在一号节点住宿的 1 RP，在三号岛屿做好事产生 4 × 5 = 20 点 RP,最终得到 19 点 RP。
1. 【样例输入】 2. 5 3. 969 980 1013 1016 1021 4. 888423 945460 865822 896150 946615 5. 【样例输出】 6. 246172
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n ≤ 15；
对于 70% 的评测用例，1 ≤ n ≤ 5000；
对于所有评测用例，1 ≤ n ≤ 500000, 1 ≤ Ti ≤ 20000, 1 ≤ Fi ≤ 200, 000, 000。
给定的 Ti 已经按照升序排序。建议使用 64 位有符号整数进行运算。
我是完全模拟题目的思路写得代码,注意n等于1的时候需要特判
1. #include<iostream> 2. #include<string> 3. #include<cstring> 4. #include<algorithm> 5. #include<cmath> 6. #include<cstdio> 7. #include<queue> 8. using namespace std; 9. long long a[500010]; 10. long long b[500010]; 11. int n; 12. long long maxRp; 13. void dfs(long long rp,int index,long long qianRen){ 14. // ting 15. if(index +1 > n) return ; 16. if(rp + qianRen * a[index + 1] > maxRp){ 17. maxRp = rp + qianRen * a[index + 1]; 18. } 19. dfs((rp + qianRen * a[index + 1])/2 - b[index + 1],index + 1,a[index + 1]); 20. //buting 21. dfs(rp,index+1,qianRen); 22. } 23. int main(){ 24. while(cin>>n){ 25. 26. for(int i = 1 ; i <= n ; i ++){ 27. scanf("%lld",&a[i]); 28. } 29. for(int i = 1 ; i <= n ; i ++){ 30. scanf("%lld",&b[i]); 31. } 32. if(n == 1) { 33. cout<<"0"<<endl; 34. }else{ 35. maxRp = -b[1]; 36. dfs(-b[1],1,a[1]); 37. cout << maxRp << endl; 38. } 39. } 40. return 0; 41. }
