开发者社区> 哈沙给> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

蓝桥杯(受约束的10人参赛问题)

简介: A、B、C、D、E、F、G、H、I、J 共10名学生有可能参加本次计算机竞赛,也可能不参加。 因为某种原因,他们是否参赛受到下列条件的约束:    1. 如果A参加,B也参加;    2. 如果C不参加,D也不参加;    3. A和C中只能有一个人参加;    4. B和D中有且仅有一个人参加;    5. D、E、F、G、H 中至少有2人参加;    6. C和G或者都参加,或者都不参加;    7. C、E、G、I中至多只能2人参加      8. 如果E参加,那么F和G也都参加。
+关注继续查看

A、B、C、D、E、F、G、H、I、J 共10名学生有可能参加本次计算机竞赛,也可能不参加。

因为某种原因,他们是否参赛受到下列条件的约束:

   1. 如果A参加,B也参加;

   2. 如果C不参加,D也不参加;

   3. A和C中只能有一个人参加;

   4. B和D中有且仅有一个人参加;

   5. D、E、F、G、H 中至少有2人参加;

   6. C和G或者都参加,或者都不参加;

   7. C、E、G、I中至多只能2人参加  

   8. 如果E参加,那么F和G也都参加。

   9. 如果F参加,G、H就不能参加

   10. 如果I、J都不参加,H必须参加

请编程根据这些条件判断这10名同学中参赛者名单。如果有多种可能,则输出所有的可能

情况。每种情况占一行。参赛同学按字母升序排列,用空格分隔。

比如:

C D G J

就是一种可能的情况。

 

 1 //该题的关键还在于如何枚举10个数,可以10重for循环,也可以类似素数环进行回溯,或者二进制枚举 
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int vis[11] = {0};
 7 
 8 //vis若是bool 变不可写成两数相加减 
 9 bool judge()
10 {
11      //a推出(蕴含)b,等价于(非a或b);或者a ==1&&b==1||a==0,等价于a==0||b==1,此次用到了短路表达式的性质 
12      bool t1 = (vis[0]== 0||vis[1] == 1);
13      //类似第一个;或者c==0&&d==0||c=1 
14      bool t2 =( vis[2] == 1||vis[3] == 0);
15      //从第四个条件可以看出这个包含都不参加的情况,等价于都不参加或者只参加一个人,反面是两个人都参加,再取反 !(a==1&&c==1)等价于a==0||c==0,转化为a+c<=1
16      bool t3 = ((vis[0] + vis[2])<=1);//或者等于0 
17      //反面是同时参加或者同时不参加,再取反!(b==d),等价于b+d ==1
18      bool t4 = (vis[1] + vis[3]==1);
19      bool t5 = ((vis[3] + vis[4] + vis[5] + vis[6] + vis[7]) >=2);
20      //c==g,可化为就、相加为0或者2 
21      bool t6 = (vis[2] == vis[6]);
22      bool t7 = ((vis[2]+vis[4]+vis[6]+vis[8])<=2);
23      //类似第一个 
24      bool t8 = (vis[4] == 0||(vis[5] + vis[6] == 2));
25      bool t9 = vis[5]==0||(vis[6]+vis[7]==0);
26      //(i ==0&&j==0)&&h==1||(ij至少一人参加),等价于(i==1||j==1)||h==1 
27      bool t10 = (vis[8]+vis[9]>0)||vis[7]==1;
28      return t1&&t2&&t3&&t4&&t5&&t6&&t7&&t8&&t9&&t10;
29 }
30 void print()
31 {
32      int i,j,k;
33      for(i=0; i<10; i++)
34           if(vis[i]>0)//若vis是bool,所以不可写成vis[i]>0 
35           {
36                char ch = i + 'A';
37                cout<<ch<<" ";
38           }
39 }
40 int main()
41 {
42      int i,j,k;
43      //二进制枚举比递归回溯好理解 
44      //二进制枚举,两数的与或疑惑分别表示集合的交并对称差 
45      int total = 0;//
46      memset(vis,0,sizeof(vis));
47      while(total<1024)//用total的前十位表示参加状态,1024并不是来自1<<10,而是十个1表示(1<<10-1) 
48      {
49           total++;//不可能全都不参加,所以先自增了
50           for(i=0; i<10; i++)//用total的底10为表示状态,或者total按求余法求的底十位 
51           {
52                int temp = (1<<i);
53                int tag = (temp & total);
            // 也可以用临时变量先存储total,然后total每次右移,与1求与,刘汝佳课本上不是这种方法 
54 if(tag) 55 { 56 //cout<<"*******"<<endl; 57 vis[i] = 1;//把赋值号写成了等号 58 } 59 else 60 vis[i] = 0; 61 } 62 bool flag = judge(); 63 //cout<<flag<<endl; 64 if(flag) 65 { 66 print(); 67 cout<<endl; 68 } 69 } 70 cout<<"----"<<endl; //结果没输出,看看是否执行到了这一步 71 cout<<endl; 72 while(1); 73 return 0; 74 } 75 //把给的例子带入发现正确,说明judge函数没问题,那么就是while循环有问题了 ,结果发现vis全为0 ,再以发现把赋值号写成了等号 76 77
 1 //递归回溯 
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int vis[11] = {0};
 7 
 8 //vis若是bool 变不可写成两数相加减 
 9 bool judge()
10 {
11      //a推出(蕴含)b,等价于(非a或b);或者a ==1&&b==1||a==0,等价于a==0||b==1,此次用到了短路表达式的性质 
12      bool t1 = (vis[0]== 0||vis[1] == 1);
13      //类似第一个;或者c==0&&d==0||c=1 
14      bool t2 =( vis[2] == 1||vis[3] == 0);
15      //从第四个条件可以看出这个包含都不参加的情况,等价于都不参加或者只参加一个人,反面是两个人都参加,再取反 !(a==1&&c==1)等价于a==0||c==0,转化为a+c<=1
16      bool t3 = ((vis[0] + vis[2])<=1);//或者等于0 
17      //反面是同时参加或者同时不参加,再取反!(b==d),等价于b+d ==1
18      bool t4 = (vis[1] + vis[3]==1);
19      bool t5 = ((vis[3] + vis[4] + vis[5] + vis[6] + vis[7]) >=2);
20      //c==g,可化为就、相加为0或者2 
21      bool t6 = (vis[2] == vis[6]);
22      bool t7 = ((vis[2]+vis[4]+vis[6]+vis[8])<=2);
23      //类似第一个 
24      bool t8 = (vis[4] == 0||(vis[5] + vis[6] == 2));
25      bool t9 = vis[5]==0||(vis[6]+vis[7]==0);
26      //(i ==0&&j==0)&&h==1||(ij至少一人参加),等价于(i==1||j==1)||h==1 
27      bool t10 = (vis[8]+vis[9]>0)||vis[7]==1;
28      return t1&&t2&&t3&&t4&&t5&&t6&&t7&&t8&&t9&&t10;
29 }
30 
31 void print()
32 {
33      int i,j,k;
34      for(i=0; i<10; i++)
35           if(vis[i]>0)//若vis是bool,所以不可写成vis[i]>0 
36           {
37                char ch = i + 'A';
38                cout<<ch<<" ";
39           }
40 }
41 
42 void dfs(int n)
43 {
44      if(n>=10)
45      {
46           if(judge())
47           {
48                print();
49                cout<<endl;
50           }
51           return ;
52      }
53      vis[n] = 0;
54      dfs(n+1);
55      vis[n] = 1;
56      dfs(n+1);
57 }
58 
59 int main()
60 {
61      int i,j,k;
62      int total = 0;//
63      memset(vis,0,sizeof(vis));
64      dfs(0);
65      cout<<"----"<<endl; //结果没输出,看看是否执行到了这一步      
66      cout<<endl;
67      while(1);
68      return 0;
69 }
70 //把给的例子带入发现正确,说明judge函数没问题,那么就是while循环有问题了 ,结果发现vis全为0 ,再以发现把赋值号写成了等号 
71      
72      


看视频加上写代码和注释共约4个小时,还是相当有成就感的。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【蓝桥杯历年真题】每日算法详解解析(C/C++)
【蓝桥杯历年真题】每日算法详解解析(C/C++)
20 0
【蓝桥杯】KMP算法难以理解只能硬背?东哥这个思路让你10分钟彻底掌握
KMP 算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法,效率很高,说实话,有点复杂。
21 0
Ubuntu16.04下驱动西克雷达 LMS511及用进行slam建图
Ubuntu16.04下驱动西克雷达 LMS511及用进行slam建图
81 0
阿里云容器服务Kubernetes 基于GPU指标自动伸缩
### 基于GPU的指标扩缩容 在深度学习训练中,训练完成的模型,通过Serving服务提供模型服务。本文介绍如何构建弹性自动伸缩的Serving服务。 Kubernetes 支持HPA模块进行容器伸缩,默认支持CPU和内存等指标。
3577 0
【Xamarin.Forms】XAML命名空间——将XAML名称空间声明为引用类型
XAML使用xmlns XML属性来进行名称空间声明。 本文将介绍XAML命名空间语法,并演示如何声明XAML命名空间以访问类型。 概观 有两个XAML名称空间声明总是在XAML文件的根元素中。
1073 0
MySQL 第九篇:Mysql 与 ORACLE 开发差异、Mysql 优化
我把MySQL的内容整理成9篇博客,学完这9篇博客虽不能说能成为大神,但是应付一般中小企业的开发已经足够了,有疑问或建议的欢迎留言讨论。 Mysql 与 ORACLE 开发差异 一、 常用的基本数据类型对比 二、 常用 SQL函数以及其它语法差异 Mysql 优化 一、 数据库设计 a) 适当的违反三大范式。
1741 0
MySQL在RR隔离级别下的unique失效和死锁模拟
今天在测试MySQL事务隔离级别的时候,发现了一个有趣的问题,也参考了杨一之前总结的一篇。http://blog.itpub.net/22664653/viewspace-1612574/     问题的背景是在MySQL隔离级别为RR(Repeatable Read)时,唯一性约束没有失效,多并发的场景下能够复现出下面的问题。
1085 0
mysql不能正常yum remove怎么办?--noscripts
rpm -e mysql-server.x86_64 --noscripts
777 0
图像分割之(四)OpenCV的GrabCut函数使用和源码解读
     图像分割之(四)OpenCV的GrabCut函数使用和源码解读                     分类:            图像处理            计算机视觉             2013-01-23 17:19     12031人阅读     评论(33)    收藏    举报     图像分割之(四)OpenCV的GrabCut函数使用和源码解读 zouxy09@qq.com http://blog.csdn.net/zouxy09         上一文对GrabCut做了一个了解。
6269 0
+关注
哈沙给
渣渣一枚
1101
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载