• [模拟]攻略分队 2022RoboCom省赛D

    副本是游戏里的一个特色玩法，主要为玩家带来装备、道具、游戏资源的产出，满足玩家的游戏进程。

    在 MMORPG《最终幻想14》里，有一个攻略人数最大达到 56 人的副本“巴尔德西昂兵武塔”，因为有在副本里死亡不能复活、机制比较整蛊等特点，一度被玩家视作洪水猛兽。

    在副本的开始，我们会遇到第一个难关：攻略的玩家要分为两组，同时讨伐副本 BOSS “欧文”和“亚特”。

    已知以下信息：

    1. 玩家会组成 6 支队伍进入副本，其中第 i 队有 Vi​ 位玩家（i=1,⋯,6）。
    2. 每支队伍可能会有一些特殊角色：MT（主坦克）、工兵（负责探测陷阱）和指挥（负责指挥玩家）。

    我们的任务是合理安排玩家的分组，以最大程度增加副本通过概率。分组的原则如下：

    1. 要将所有队伍分成 2 组，每支队伍必须且仅属于其中一组；
    2. 每组必须有至少一个 MT（主坦克）。

    如果满足上述原则的分组方案不唯一，则按照下列规则确定唯一解：

    1. 优先选择每组有至少一个指挥和至少一个工兵的方案；
    2. 如果规则 1 无法满足，则优先选择每组至少有一个指挥的方案；
    3. 如果所有方案都不满足规则 2，或经过前 2 个规则筛选后，分组方案仍不唯一，则选择两边人数尽可能接近（即两边人数差尽可能小）的方案；
    4. 如果满足规则 3 的方案还不唯一，选择讨伐“欧文”的人数大于等于讨伐“亚特”的人数的方案；
    5. 如果满足规则 4 的方案还不唯一，选择讨伐“欧文”的队伍编号方案中最小的一个。

    注：一个队伍编号方案 A={a1​<⋯

    本题就请你给出满足所有分组原则的分配方案。

    感谢 王宪泉 同学对规则 4 的指正，于 2022-08-04 修改

    输入格式:

    输入第一行给出 6 支队伍的玩家数量，即 6 个非负整数 Vi​ (0≤Vi​≤8,1≤i≤6)。队伍人数为 0 时表示队伍不存在。

    随后 6 行，按队伍编号顺序，每行给出一支队伍的特殊角色，格式为 ABC，其中 A 对应 MT，B 对应工兵，C 对应指挥。三种角色对应取值 0 或 1，0 表示没有该角色，1 表示有。

    注：由于可能存在一人兼任多个特殊角色的情况，所以一支队伍中的特殊角色数量有可能大于该队伍的玩家数量。

    输出格式:

    输出分两行，第一行输出讨伐“欧文”的队伍编号，第二行输出讨伐“亚特”的队伍编号。同一行中的编号按升序输出，以 1 个空格分隔，行首尾不得有多余空格。

    如果不存在合法的方案，输出GG。

    输入样例1:

    1. 6 8 7 5 3 0
    2. 010
    3. 101
    4. 110
    5. 001
    6. 111
    7. 000

    输出样例1:

    1. 2 3
    2. 1 4 5

    输入样例2:

    1. 6 8 7 5 3 0
    2. 010
    3. 101
    4. 010
    5. 001
    6. 011
    7. 000

    输出样例2:

    GG

    题意： 根据题目中给出的各种规则，将若干队伍分为两组，若存在方案输出分组方案，否则输出GG。

    分析： 这道题目是一道比较麻烦的模拟题，可以先处理下每个队伍是否有MT、工兵和指挥，然后二进制枚举0~1<<6，对于枚举出来的一个数字就代表一种分组方案，这里我假设为1的位是讨伐欧文的队伍，为0的位是讨伐亚特的队伍，首先先找出来两组都包含MT的分组，如果不存在那么说明无解，如果分组唯一那就直接输出，如果分组不唯一就再遍历找出两组均有指挥和工兵的分组方案，如果不存在的话就只考虑指挥，之后就根据题目中的描述模拟就行，要严格按照题目中说的来，另外题面中规则4后来进行了修改，应该是讨伐“欧文”的人数大于等于讨伐“亚特”的人数而不是之前说的的大于！

    具体代码如下：

    1. #include 
    2. #define inf 0x3f3f3f3f
    3. using namespace std;
    4.  
    5. int num[10];
    6. bool mt[10];
    7. bool gb[10];
    8. bool zh[10];
    9. void Output(int i); 
    10.  
    11. signed main(){
    12. 	for(int i = 0; i < 6; i++)
    13. 		scanf("%d", &num[i]);
    14. 	for(int i = 0; i < 6; i++){
    15. 		string s;
    16. 		cin >> s;
    17. 		mt[i] = (s[0]=='1');
    18. 		gb[i] = (s[1]=='1');
    19. 		zh[i] = (s[2]=='1');
    20. 	}
    21. 	vector<int> alls;
    22. 	for(int i = 0; i < (1<<6); i++){
    23. 		if(i == 0 || i == (1<<6)-1) continue;
    24. 		bool mt1 = false, mt2 = false;
    25. 		for(int j = 0; j < 6; j++){
    26. 			if(i&(1<
    27. 				mt1 = max(mt1, mt[j]);
    28. 			else if(!(i&(1<
    29. 				mt2 = max(mt2, mt[j]);
    30. 		}
    31. 		if(mt1 && mt2) alls.push_back(i);
    32. 	}
    33. 	if(alls.size() > 1){
    34. 		vector<int> t1;
    35. 		for(int i = 0; i < alls.size(); i++){
    36. 			bool gb1 = false, gb2 = false, zh1 = false, zh2 = false;
    37. 			for(int j = 0; j < 6; j++){
    38. 				if(alls[i]&(1<
    39. 					gb1 = max(gb1, gb[j]);
    40. 					zh1 = max(zh1, zh[j]);
    41. 				}
    42. 				else if(!(alls[i]&(1<
    43. 					gb2 = max(gb2, gb[j]);
    44. 					zh2 = max(zh2, zh[j]);
    45. 				}
    46. 			}
    47. 			if(gb1 && gb2 && zh1 && zh2) t1.push_back(alls[i]);
    48. 		}
    49. 		if(t1.size() == 0){
    50. 			for(int i = 0; i < alls.size(); i++){
    51. 				bool zh1 = false, zh2 = false;
    52. 				for(int j = 0; j < 6; j++){
    53. 					if(alls[i]&(1<
    54. 						zh1 = max(zh1, zh[j]);
    55. 					}
    56. 					else if(!(alls[i]&(1<
    57. 						zh2 = max(zh2, zh[j]);
    58. 					}
    59. 				}
    60. 				if(zh1 && zh2) t1.push_back(alls[i]);
    61. 			}
    62. 		}
    63. 		if(t1.size() == 1){
    64. 			int i = t1[0];
    65. 			Output(i);
    66. 		}
    67. 		else{
    68. 			vector<int> t2;
    69. 			if(t1.size() > 1){//多个满足前两规则的 
    70. 				int _min = inf;
    71. 				for(int i = 0; i < t1.size(); i++){
    72. 					int n1 = 0, n0 = 0;
    73. 					for(int j = 0; j < 6; j++){
    74. 						if((t1[i]&(1<
    75. 							n1 += num[j];
    76. 						}
    77. 						else if(!(t1[i]&(1<
    78. 							n0 += num[j];
    79. 						}
    80. 					}
    81. 					if(n1 == 0 || n0 == 0) continue;
    82. 					_min = min(_min, abs(n1-n0));
    83. 				}
    84. 				for(int i = 0; i < t1.size(); i++){
    85. 					int n1 = 0, n0 = 0;
    86. 					for(int j = 0; j < 6; j++){
    87. 						if((t1[i]&(1<
    88. 							n1 += num[j];
    89. 						}
    90. 						else if(!(t1[i]&(1<
    91. 							n0 += num[j];
    92. 						}
    93. 					}
    94. 					if(n1 == 0 || n0 == 0) continue;
    95. 					if(abs(n1-n0) == _min) t2.push_back(t1[i]);
    96. 				}
    97. 			} 
    98. 			else{//不存在满足第二个规则的，更不存在满足前两个的 
    99. 				int _min = inf;
    100. 				for(int i = 0; i < alls.size(); i++){
    101. 					int n1 = 0, n0 = 0;
    102. 					for(int j = 0; j < 6; j++){
    103. 						if((alls[i]&(1<
    104. 							n1 += num[j];
    105. 						}
    106. 						else if(!(alls[i]&(1<
    107. 							n0 += num[j];
    108. 						}
    109. 					}
    110. 					if(n1 == 0 || n0 == 0) continue;
    111. 					_min = min(_min, abs(n1-n0));
    112. 				}
    113. 				for(int i = 0; i < alls.size(); i++){
    114. 					int n1 = 0, n0 = 0;
    115. 					for(int j = 0; j < 6; j++){
    116. 						if((alls[i]&(1<
    117. 							n1 += num[j];
    118. 						}
    119. 						else if(!(alls[i]&(1<
    120. 							n0 += num[j];
    121. 						}
    122. 					}
    123. 					if(n1 == 0 || n0 == 0) continue;
    124. 					if(abs(n1-n0) == _min) t2.push_back(alls[i]);
    125. 				}
    126. 			} 
    127. 			if(t2.size() == 1){
    128. 				int i = t2[0];
    129. 				Output(i);
    130. 			}
    131. 			else{//t2.size()不可能为0
    132. 				vector<int> t3;
    133. 				for(int i = 0; i < t2.size(); i++){
    134. 					int n1 = 0, n0 = 0;
    135. 					for(int j = 0; j < 6; j++){
    136. 						if((t2[i]&(1<
    137. 							n1 += num[j];
    138. 						}
    139. 						else if(!(t2[i]&(1<
    140. 							n0 += num[j];
    141. 						}
    142. 					}
    143. 					if(n1 == 0 || n0 == 0) continue;
    144. 					if(n1 >= n0) t3.push_back(t2[i]);
    145. 				}
    146. 				if(t3.size() == 1){
    147. 					int i = t3[0];
    148. 					Output(i); 
    149. 				}
    150. 				else if(t3.size() > 1){
    151. 					vectorint> > ans;
    152. 					for(int i = 0; i < t3.size(); i++){
    153. 						vector<int> temp;
    154. 						for(int j = 0; j < 6; j++){
    155. 							if((t3[i]&(1<
    156. 								temp.push_back(j+1);
    157. 							}
    158. 						}
    159. 						ans.push_back(temp);
    160. 					}
    161. 					sort(ans.begin(), ans.end());
    162. 					bool vis[10] = {false};
    163. 					printf("%d", ans[0][0]);
    164. 					vis[ans[0][0]-1] = true;
    165. 					for(int i = 1; i < ans[0].size(); i++){
    166. 						printf(" %d", ans[0][i]);
    167. 						vis[ans[0][i]-1] = true;
    168. 					}
    169. 					puts("");
    170. 					bool first = true;
    171. 					for(int i = 0; i < 6; i++){
    172. 						if(!vis[i] && num[i]){
    173. 							if(first){
    174. 								printf("%d", i+1);
    175. 								first = false;
    176. 							}
    177. 							else printf(" %d", i+1);
    178. 						}
    179. 					}
    180. 				}
    181. 				else{//欧文人数都比亚特少时无解 
    182. 					puts("GG");
    183. 					return 0;
    184. 				} 
    185. 			}
    186. 		}
    187. 	}
    188. 	else if(alls.size() == 1){
    189. 		int i = alls[0];
    190. 		Output(i);
    191. 	}
    192. 	else puts("GG");
    193. 	return 0;
    194. } 
    195.  
    196. void Output(int i){
    197. 	vector<int> ans1, ans2;
    198. 	for(int j = 0; j < 6; j++){
    199. 		if((i&(1<
    200. 			ans1.push_back(j+1);
    201. 		else if(!(i&(1<
    202. 			ans2.push_back(j+1);
    203. 	}
    204. 	printf("%d", ans1[0]);
    205. 	for(int j = 1; j < ans1.size(); j++)
    206. 		printf(" %d", ans1[j]);
    207. 	puts("");
    208. 	printf("%d", ans2[0]);
    209. 	for(int j = 1; j < ans2.size(); j++)
    210. 		printf(" %d", ans2[j]);
    211. }

  • 相关阅读:
    铁托（Tito）
    AIGC下一步：如何用AI再度重构或优化媒体处理？
    SSO 和 OAuth2.0 的关系是什么？
    软件测试面试必备，一文带你彻底掌握接口测试
    java建材公司管理系统计算机毕业设计MyBatis+系统+LW文档+源码+调试部署
    OSCP系列靶场-Esay-Moneybox保姆级
    【电商运营】如何吸引客户？经典WhatsApp营销案例分享！
    Python实时获取steam游戏数据
    【目标检测】YOLOX训练王者荣耀数据集
    Day4: 应用篇-1
  • 原文地址：https://blog.csdn.net/m0_55982600/article/details/126182578