devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Robocom本科组初赛_懂的都懂robocompython

作者：IT小白 | 2024-06-29 16:22:01

赞

踩

懂的都懂robocompython

这几天主要在写robocom的题，写了个初赛就自闭了，我怎么可以这么菜啊。

7-1 懂的都懂(20分)

题意：设n个非负整数和k次询问，每一次询问中的m个数字是否都是n个非负整数中其中四个数字的平均值，是的话输出Yes，否则输出No。

题目特征：n个数中选4个数，并且要对这个结果进行处理。

思路：dfs，搜到四个数就停下来，把平均值用map存起来，记得要回溯。我写代码的时候采用的是固定一个数，然后去搜剩下的三个数，但其实搜四个数也是一样的。（第一反应居然是全排列，蓝桥杯打傻了

  1. 1.	#include<bits/stdc++.h>  
  2. 2.	using namespace std;  
  3. 3.	int n, k, a[55], vis[55];  
  4. 4.	map<int, int> mp;  
  5. 5.	void dfs(int num, int sum, int kk){  
  6. 6.	    if(num == 4){  //选够四个数
  7. 7.	        if(sum % 4 == 0)  mp[sum / 4] = 1;  //因为输进来的都是整数，所以确定模4等于0之后才能存入
  8. 8.	        return;  
  9. 9.	    }  
  10. 10.	    vis[kk] = 1;  
  11. 11.	    for(int i = 0; i < n; i++){  
  12. 12.	        if(!vis[i]){  
  13. 13.	            dfs(num + 1, sum + a[i], i);  
  14. 14.	        }
  15. 15.	    }
  16. 16.	    vis[kk] = 0;  //回溯
  17. 17.	}  
  18. 18.	int main(){  
  19. 19.	    ios::sync_with_stdio(false);  
  20. 20.	    cin.tie(0);  
  21. 21.	    cin >> n >> k;  
  22. 22.	    int kk = 0;  
  23. 23.	    for(int i = 0; i < n; i++){  
  24. 24.	        cin >> a[i];  
  25. 25.	    }  
  26. 26.	    sort(a, a + n);  
  27. 27.	    for(int i = 0; i < n; i++){  
  28. 28.	        dfs(1, a[i], i);  
  29. 29.	    }  
  30. 30.	//  for(auto it = mp.begin(); it != mp.end(); it++){  
  31. 31.	//      printf("****%d\n", (*it).first);  
  32. 32.	//  }  
  33. 33.	    for(int i = 0; i < k; i++){  
  34. 34.	        int flag = 0;  
  35. 35.	        int x;  cin >> x;  
  36. 36.	        for(int j = 0; j < x; j++){  
  37. 37.	            int g;  cin >> g;  
  38. 38.	            if(!mp[g])  flag = 1;  
  39. 39.	        }  
  40. 40.	        if(!flag)  printf("Yes\n");  
  41. 41.	        else  printf("No\n");  
  42. 42.	    }  
  43. 43.	    return 0;  
  44. 44.	}

题意：假设现在有 N 个机场，M 条航线，每天都会新增一个机场无法正常运作，每天会有 Q i对旅客从 X i机场前往 Y i机场，请计算有多少对旅客会受到影响无法完成行程。

思路：并查集+反向建图，最开始写的是dfs，只过了部分测试点，看了题解之后直呼妙啊，先把所有变量存下来，然后从后面的点开始建图，因为点是从前向后一个一个消失的，建立一个点相当于该点的前一个点消失后的状态（太妙了。在此之前还要对没有被防控的机场建图。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct node{
  4. 	int st, ed;
  5. };
  6. int fa[50005], vis[50005];
  7. int n, m, d;  
  8. vector<vector<node> > v(50005);
  9. vector<node> vn;
  10. vector<int> ans;
  11. stack<int> sta;
  12. void init(){
  13. 	for(int i = 0; i <= n; i++)  fa[i] = i;
  14. }
  15. int find(int x){
  16. 	if(x == fa[x])  return x;
  17. 	else  return fa[x] = find(fa[x]);
  18. }
  19. int main(){
  20. 	cin >> n >> m >> d;
  21. 	init();
  22. 	for(int i = 0; i < m; i++){
  23. 		int a, b;  cin >> a >> b;
  24. 		vn.push_back({a, b});
  25. 	}
  26. 	for(int i = 0; i < d; i++){
  27. 		int c, q;  cin >> c >> q;
  28. 		sta.push(c);
  29. 		vis[c] = 1;
  30. 		for(int j = 0; j < q; j++){
  31. 			int x, y;  cin >> x >> y;
  32. 			v[c].push_back({x, y});
  33. 		}
  34. 	}
  35. 	for(int i = 0; i < m; i++){
  36. 		if(vis[vn[i].st] || vis[vn[i].ed])  continue;
  37. 		int finda = find(vn[i].st);
  38. 		int findb = find(vn[i].ed);
  39. 		if(finda != findb){
  40. 			fa[finda] = findb;
  41. 		}
  42. 	}
  43. 	while(!sta.empty()){
  44. 		int qf = sta.top(), cnt = 0;
  45. 		sta.pop();
  46. 		for(int i = 1; i <= n; i++)  int ww = find(i);
  47. 		for(int i = 0; i < v[qf].size(); i++){
  48. 			if((fa[v[qf][i].st] != fa[v[qf][i].ed]) || vis[v[qf][i].st] || vis[v[qf][i].ed])  cnt++;
  49. 		}
  50. 		for(int i = 0; i < m; i++){
  51. 			if(vn[i].st != qf && vn[i].ed != qf)  continue;
  52. 			int finda = find(vn[i].st);
  53. 			int findb = find(vn[i].ed);
  54. 			if(finda != findb){
  55. 				fa[finda] = findb;
  56. 			}
  57. 		}
  58.         vis[qf] = 0;
  59.         ans.insert(ans.begin(), cnt);
  60. 	}
  61. 	for(int i = 0; i < ans.size(); i++){
  62.         printf("%d\n", ans[i]);
  63.     }
  64. }

 7-3 打怪升级

 

 

这一题没有全部过完（23/25）不知道是哪里出了问题，看好多人都是用迪杰斯特拉去路径还原，而我搜了一个弗洛伊德的路径还原板子，照着写上去了，但是没有全过。

题意：找一个点到输入的所有点耗费的能量最小，并且沿途获得的武器价值最大。

思路：典型的最短路问题，数据范围很小，考虑使用floyd，并且不仅要记录耗费的能量，还要记录获得的价值，路径能量耗费相同的情况下选择获得价值高的，还有最短路的路径还原问题。

路径还原参照博客：(36条消息) floyd——记录路径，原理详解。_小酒窝.的博客-CSDN博客_floyd算法怎么记录路径

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int inf = 0x3f3f3f3f;
  4. struct node{
  5. 	int me, wv;    //武器价值和怪兽能量
  6. };
  7. int pre[1005][1005];   //记录路径还原
  8. int n, m;
  9. node g[1005][1005];   //记录图
  10. int num[1005];    //要攻破的堡垒
  11.  
  12. void print(int i,int j)    //路径还原的输出
  13. {
  14.     if(i==j) return ;
  15.     if(pre[i][j]==0) cout << "->" << j;
  16.     else{
  17.         print(i,pre[i][j]);
  18.         print(pre[i][j],j);
  19.     }
  20. }
  21. int main(){
  22. 	cin >> n >> m;
  23. 	memset(g, inf, sizeof(g));
  24. 	memset(pre, 0, sizeof(pre));
  25. 	for(int i = 0; i < m; i++){
  26. 		int b1, b2, x, y;  cin >> b1 >> b2 >> x >> y;
  27. 		g[b1][b2] = g[b2][b1] = {x, y};
  28. 	}
  29. 	for(int k = 1; k <= n; k++){
  30. 		for(int i = 1; i <= n; i++){
  31. 			for(int j = 1; j <= n; j++){
  32. 				if(g[i][k].me + g[k][j].me < g[i][j].me)
  33. 				{
  34. 					pre[i][j]=k;
  35. 					g[i][j].me = g[i][k].me + g[k][j].me;
  36. 					g[i][j].wv = g[i][k].wv + g[k][j].wv;
  37. 				}
  38. 				else if(g[i][k].me + g[k][j].me == g[i][j].me){
  39. 					if((g[i][k].wv + g[k][j].wv > g[i][j].wv) && (g[i][k].wv + g[k][j].wv < inf ))  
  40. 					{
  41. 						pre[i][j]=k;
  42. 						g[i][j].wv = g[i][k].wv + g[k][j].wv;
  43. 					}
  44. 				}
  45. 			}
  46. 		}
  47. 	}
  48. 	int k; cin>>k;
  49. 	for(int i=0;i<k;i++) cin>>num[i];
  50. 	int ans=inf;
  51. 	int ans1;
  52. 	for(int i=1;i<=n;i++)
  53. 	{
  54. 		int maxx=-1;
  55. 		for(int j=0;j<k;j++)
  56. 		{
  57. 			int dis=g[i][num[j]].me;
  58. 			maxx=max(maxx,dis);
  59. 		}
  60. 		if(ans>maxx)
  61. 		{
  62. 			ans=maxx;
  63. 			ans1=i;
  64. 		}
  65. 		
  66. 	}
  67. 	cout<<ans1<<endl;
  68. 	for(int i = 0; i < k; i++){
  69. 		printf("%d", ans1);
  70.         print(ans1,num[i]);
  71.         printf("\n");
  72.         if(ans1 == num[i])  printf("0 0\n");
  73.         else  printf("%d %d\n", g[ans1][num[i]].me, g[ans1][num[i]].wv);
  74. 	}
  75. }

7-2芬兰木棋(25分)

芬兰木棋（Mölkky，又称芬兰木柱）是源自芬兰的一项运动。哲哲将这个运动改造成了赛博朋克单人版，现在场上一开始有 N 根立起的小木棋（上面分别标有一个非负整数），哲哲投掷一根大木棋去击倒这些小木棋以获得分数。分数规则如下：

  • 如果仅击倒 1 根木棋，则得木棋上的分数。
  • 如果击倒 2 根或以上的木棋，则只得击倒根数的分数。（例如击倒 5 根，则得 5 分。）

哲哲固定站在 (0,0) 点上，四周放着若干个小木棋 (Xi​,Yi​)，坐标均为整数。每次哲哲可以朝一个方向扔出大木棋，大木棋会打倒这个方向上离哲哲最近的 k 个小木棋。哲哲游戏水平很高超，所以这个 k 可以自由控制。

请问哲哲最多能拿多少分，在获得最多分数的情况下最少需要扔出多少次大木棋？

规则与真实规则有较大出入，真实游玩时请以国际莫尔基组织的规则为准

输入格式:

输入第一行是一个正整数 N (1 ≤ N ≤ 105)，表示场上一开始有 N 个木棋。

接下来 N 行，每行 3 个整数 Xi​,Yi​,Pi​，分别表示木棋放置在 (Xi​,Yi​)，木棋上的分数是 Pi​。坐标在 32 位整数范围内，分数为小于等于 1000 的正整数。

保证 (0,0) 点没有木棋，也没有木棋重叠放置。

输出格式:

输出一行两个数，表示最多分数以及获得最多分数最少需要投掷大木棋多少次。

输入样例:

  1. 11
  2. 1 2 2
  3. 2 4 3
  4. 3 6 4
  5. -1 2 2
  6. -2 4 3
  7. -3 6 4
  8. -1 -2 1
  9. -2 -4 1
  10. -3 -6 1
  11. -4 -8 2
  12. 2 -1 999

输出样例:

1022 9

题意：如题，这道题题意还是比较好理解的。

思路：计算斜率，对斜率相同的点存进一个容器里，然后计算有多少个连续的1，若不是1，那就直接加上去，这里要注意的是，斜率相同，有可能象限不同，所以还要分象限，我对每个容器都加了个0，0进行隔断。

今天学到了个额外的东西，就是自定义结构体内嵌比较器一定要写清楚，清楚到足以区分每个结构体，因为有些容器的排序是完全看你的自定义结构体内嵌比较器，如果不能够区分清楚，那电脑就会认为它们是同一个东西。

  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. struct node{
  5. 	int x, y, p;
  6. };
  7. bool cmp(node a, node b){
  8. 	if(a.x != b.x)  return a.x < b.x;
  9. 	else  return a.y < b.y;
  10. }
  11. signed main(){
  12.     int n, ans1 = 0, ans2 = 0;  cin >> n;
  13.     map<double, vector<node> > mp;
  14.     for(int i = 0; i < n; i++){
  15.     	int xx, yy, pp;  cin >> xx >> yy >> pp;
  16.     	ans1 += pp;
  17.     	if(mp[xx * 1.0 / yy].size() == 0){
  18.     		node a;
  19.     		a.x = 0, a.y = 0, a.p = 0;
  20.     		mp[xx * 1.0 / yy].push_back(a);
  21. 		}
  22. 		node b;
  23. 		b.x = xx, b.y = yy, b.p = pp;
  24. 		mp[xx * 1.0 / yy].push_back(b);
  25. 	}
  26. 	for(auto it = mp.begin(); it != mp.end(); it++){
  27. 		vector<node> v = (*it).second;
  28. 		sort(v.begin(), v.end(), cmp);
  29. 		int index = -1;
  30. 		for(int i = 0; i < v.size(); i++){
  31. 			if(v[i].p == 0)  continue;
  32. 			else if(v[i].p != 1)  ans2++;
  33. 			else{
  34. 				if(i == v.size() - 1 || v[i + 1].p != 1)  ans2++;
  35. 			}
  36. 		}
  37. 	}
  38. 	printf("%lld %lld\n", ans1, ans2);
  39. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/769698
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号