DOC《安徽省2018年学科和技能竞赛》

(二)程序设计类赛题 专家委员会参照但不限于下列知识点进行命题,一般10~12题,比赛时间为5个小时. 数据结构知识:包括基础数据结构(链表、栈和队列、串、树和二叉树、图、排序与检索等);

树形结构(线段树,树状数组,字典树,伸展树,左偏树,动态树,LCA与RMQ问题,划分树,SBT等);

字符串(KMP、AC自动机、后缀数组、最小表示法);

其他(并查集、散列表、块状链表、双向链表)等. 基本算法知识:包括基础算法(枚举、贪心、递归、分治、递推、构造、模拟等);

动态规划(简单dp、线性dp、树形dp、状态压缩dp、单调性优化等);

搜索(dfs、bfs、记忆化搜索、优化与剪枝、双向搜索、A*、IDA*等)等. 图论:包括最短路径(单源、任意);

生成树(prim、kruskal、度限制最小生成树、最优比率生成树、次小生成树、最小树形图、生成树的计数、树的划分和枚举);

匹配问题(二分图的最大匹配、KM、2-SAT、同构);

网络流(最大流、最小费用最大流、最小割模型、网络流规约);

其他(拓扑排序、双连通分量、强连通分支及其缩点、图的割边与割点、最小环、欧拉路径、哈密顿路径、平面图、分层图思想、偶图)等. 数学:包括数论(素数和整除问题、进位制、同余模算术、整数因子分解、GCD、扩展欧几里得、求解模线性方程、中国余数定理、元素的幂);

组合数学(加法和乘法原理、排列组合、递推关系和母函数、容斥原理、抽屉原理、置换群与Polya定理、MoBius反演、偏序关系理论);

计算方法(二分法求解单调函数相关知识、三分法求解单峰(单谷)的极值、矩阵法、迭代逼近、高斯消元法、随机化算法、0/1分数规划);

计算几何(判断线段相交、判断直线相交、判断点是否在多边形内、凸多边形面积&

重心计算、求外接圆与内接圆、求凸包、最近点对问题、最远点对问题、点集或图形集合的最小覆盖圆、点集或图形集合的最小覆盖矩形、矩形的交与并、三角剖分等);

其他(博弈论、线性规划、整数规划、概率问题、多项式与快速傅里叶、数学思想与方法的综合运用如构造、猜想、归纳法、反证法等).

(三)单片机与嵌入式系统类赛题 竞赛试题由竞赛组委会征题,竞赛前一晚从安徽省机器人大赛组委会拟定题库中抽签选取,并由竞赛当日早晨08:00之前打印分发给竞赛选手,保证竞赛公平公正.

(四)数字媒体类赛题 大赛主题为 家乡之美 .参赛作品以体现 魅力家园,美丽家园,和谐家园,绿色家园 为方向,全面展现家乡特色文化、人文环境、建筑风貌等题材,运用数字媒体技术及艺术等表现形式来展现家乡之美,全方位立体式推广宣传家乡特色文化.参赛作品选题要言之有物,突出亮点,作品具有原创性. 征集的作品内容分为数字媒体技术应用类、数字媒体艺术应用类、数字媒体创新创意类三大类,涵盖虚拟现实VR/AR应用、沉浸式体感类应用、移动互联网应用、数字动画、影视后期、交互设计以及数字媒体创新创意应用等方面.大赛作品内容分类如下: 数字媒体技术应用类相关展示视频(高清、标清不限,MP4格式,25帧/s). 数字媒体艺术应用类(高清、标清不限,MP4格式,25帧/s,视频截图分辨率不得低于300dpi.交互设计类需提供全部的交互文件数据,同时提供一套可供平面印刷的电子文件,格式为JPG,效果图截图并进行并行排版,以A4幅面为尺寸,分辨率不低于300dpi,可使用RGB或CMYK格式.针对电子交互读物设计的作品,如果是微信类移动端的设计制作作品,需提供二维码)