【保研加分、综测助力】2023年度第四届全国大学生算法设计与编程挑战赛（春季赛）

时间：2023-04-19

　　2023年度第四届全国大学生算法设计与编程挑战赛（春季赛）

　　报名网址

　　www.saikr.com/vse/adpc/2023/spring

　　扫描上方二维码进入官网报名

　　NO.1

　　中国未来研究会大数据与数学模型专业委员会

　　天津市未来与预测科学研究会

　　NO.2

　　奖项设立

　　（1）本次秋季赛分为 A、B 两个类别，每个类别内分别计算获奖人数。

　　（2）本次竞赛支持个人参赛、两人参赛和三人参赛。为了保证本次竞赛的公平性，每个类别内设有单人组、双人组和三人组三个组别，按照组别内的参赛人数分别进行评奖。

　　本次竞赛设全国冠、亚、季军（冠军1支，亚军2支，季军3支）

　　冠军：可获得奖章和 1000 元奖金

　　亚军：可获得奖章和 500 元奖金

　　季军：可获得奖章和 300 元奖金

　　注：（按照两个类别的总排名评选）

　　获奖证书&志愿者证书

　　优秀组织单位奖&优秀指导教师奖

　　NO.3

　　问题解析

　　1、老师，这次大赛的参赛对象是哪些啊？

　　是普通高等院校、高职院校、二级学院、独立学院、本、专科在校大学生及研究生均可报名参加，专业不限；其他社会人员也可以报名参赛。

　　2、老师本次竞赛支持哪几类语言？有多少道题？

　　本次竞赛为混合赛，线上参赛，赛题设置10个题目，从易到难，涉及各类算法模型，出题模式与“蓝桥杯”、“ACM-ICPC”、“CCPC”相同。赛后公布所有题目的参考代码，并且由出题团队以视频的形式进行赛题解析，是学习算法同学一次学习交流的机会。以赛辅练，为学生后续的算法学习和算法设计水平的提高提供帮助

　　本次竞赛支持： C、C++、Java、Python 四种语言

　　3、老师考试时间是怎们安排的？

　　(1) 报名时间：即日起至 2023年6月2日14时

　　(2) 账号发放时间：2023年6月3日

　　(3) 测试时间： 2023年6月3日14时至17时

　　(4) 比赛时间： 2023年6月4日9 时至14时

　　(5) 赛题讲解时间：2023年6月5日19时

　　(6) 结果公布时间：2023年6月6日18时

　　4、老师报名分为几个组别啊？

　　第四届全国大学生算法设计与编程挑战赛（春季赛）分 A、B 两个类别，参赛者可根据自身情况选择不同类别进行参赛。

　　A类：社会人员、研究生及在校本科生

　　B类：专科生及高职高专类学生

　　5、老师个人报名和集体报名的流程是怎样的？

　　下面梳理一下

　　个人报名

　　1、参赛者可根据自身情况选择不同类别进行参赛：

　　报名网址：

　　www.saikr.com/vse/adpc/2023/spring

　　2、填写相关信息，完成注册缴费后，生成参赛编号。

　　3、报名成功后可进入官方交流群：

　　大赛QQ2群：217301223

　　大赛QQ3群：656135042

　　集体报名

　　欢迎各高等院校按照参赛规则及有关规定组织同学报名参赛。

　　1、集体报名高校负责人须通知本校参赛同学在报名官网:团队赛报名链接：

　　www.saikr.com/vse/adpc/2023/spring

　　完成注册，不需要缴费，生成参赛编号。

　　2、集体报名汇款信息如下：

　　银行户名：育人成才（天津）科技有限公司

　　开户行：招商银行股份有限公司天津高新区支行

　　帐号： 122913039510401

　　注：支付时请备注“学校+队数+支付者姓名”，集体转账后请负责人保留转账成功截图，并同《集体报名表》一同发至组委会邮箱（1593676935@qq.com），如果需要开发票，请把发票抬头、纳税人识别号、是否开成一张发票等信息一起发送到组委会邮箱。

　　3、填写《集体报名表格》，需准确填写参赛编号，同集体报名支付截图一同发至指定邮箱（1593676935@qq.com）。组委会工作人员接收集体报名表格后会在官网审核通过集体报名的队伍编号。

　　4、报名联系方式

　　组委会联系人：赵老师

　　电话&微信：15602038403

　　邮箱：1593676935@qq.com

　　NO.4

　　官方盖章通知文件

　　小题练手

　　题目描述

　　小蓝要用七段码数码管来表示一种特殊的文字

　　上图给出了七段码数码管的一个图示，数码管中一共有 7段可以发光的二极管，分别标记为 a,b,c,d,e,f,g。

　　小蓝要选择一部分二极管(至少要有一个)发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。

　　例如:6发光，其他二极管不发光可以用来表达一种字符

　　例如c发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。

　　例如:a,b,c,d,e 发光，f,g 不发光可以用来表达一种字符

　　例如:6,f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。

　　请问，小蓝可以用七段码数码管表达多少种不同的字符?

　　解题思路

　　我们可以把每个二极管看成一条边，并把相邻的边相连，那么这样题目就可以转换为:

　　有多少种选边方案，使得选出来的边构成的图只有一个联通快

　　于是现在只要枚举选边方案，再判断联通块的个数是否为 1 即可

　　枚举选边方案可以采用状压(当然直接 dfs 搜索也行): 用二进制 1、0分别表示

　　进制位所对应的边是选还是不选，复杂度为 2”

　　求联通块的个数可以采用 bfs (也可以采用并查集等方法): 从任意一个选中的边出发将所有能到达的选中的边全部打上标记;若标记夏盖了所有选中的边则联通块只有一个(满足条件) ，反之不止一个联通块 (不满足条件)

　　最后的答案为 88。

　　参考代码

　　1、C/C++

　　#include using namespace std; int ans , g[7][7] , vis[7] , flag[7]; void bfs(int x){ queueque; que.push(x); vis[x] = true; while(!que.empty()){ int u = que.front(); que.pop(); for(int i = 0 ; i <= 6 ; i ++){ if(g[u][i] && flag[i] && !vis[i]){ vis[i] = true; que.push(i); } } } } bool check(int x){ for(int i = 0 ; i <= 6 ; i ++) flag[i] = vis[i] = false; int cnt = 0; for(int i = 6 ; ~i ; i --) if(x >> i & 1) flag[i] = true; for(int i = 0 ; i <= 6 ; i ++){ if(flag[i] && !vis[i]){ bfs(i); cnt ++ ; } } return cnt == 1; } signed main() { g[0][1] = g[0][5] = 1; g[1][0] = g[1][2] = g[1][6] = 1; g[2][1] = g[2][3] = g[2][6] = 1; g[3][2] = g[3][4] = 1; g[4][3] = g[4][5] = g[4][6] = 1; g[5][0] = g[5][4] = g[5][6] = 1; g[6][1] = g[6][2] = g[6][4] = g[6][5] = 1; for(int i = 0 ; i < (1 << 7) ; i ++){ if(check(i)) { ans ++ ; } } cout << ans << '

　　'; return 0; }

　　2、Java

　　import java.util.*; public class Main { private static int ans; private static int[][] g = new int[7][7]; private static boolean[] vis = new boolean[7]; private static boolean[] flag = new boolean[7];

　　private static void bfs(int x) { LinkedList que = new LinkedList(); que.offer(x); vis[x] = true; while (!que.isEmpty()) { int u = que.peek(); que.poll(); for (int i = 0; i <= 6; i++) { if (g[u][i] != 0 && flag[i] && !vis[i]) { vis[i] = true; que.offer(i); } } } } private static boolean check(int x) { for (int i = 0; i <= 6; i++) { flag[i] = vis[i] = false; } int cnt = 0; for (int i = 6; i >= 0; i--) { if ((x >> i & 1) != 0) { flag[i] = true; } } for (int i = 0; i <= 6; i++) { if (flag[i] && !vis[i]) { bfs(i); cnt++; } } return cnt == 1; } public static void main(String[] args) { g[0][1] = g[0][5] = 1; g[1][0] = g[1][2] = g[1][6] = 1; g[2][1] = g[2][3] = g[2][6] = 1; g[3][2] = g[3][4] = 1; g[4][3] = g[4][5] = g[4][6] = 1; g[5][0] = g[5][4] = g[5][6] = 1; g[6][1] = g[6][2] = g[6][4] = g[6][5] = 1; for (int i = 0; i < (1 << 7); i++) { if (check(i)) { ans++; } } System.out.print(ans); System.out.print('

　　'); } }

　　别忘记报名哦

　　BONUS TIME

　　数学建模资料、视频讲解、历年赛题

　　后台回复【校苑】领取

　　推荐阅读（点击下方图片即可跳转）