1114人阅读
试题编号：
试题名称：
时间限制：
内存限制：
问题描述：
　　我们把一个数称为有趣的，当且仅当：
　　1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
　　2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
　　3. 最高位数字不为0。
　　因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：。
　　请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以的余数。
　　输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。
　　输出只有一行，包括恰好n 位的整数中有趣的数的个数除以的余数。
这道题如果有过dp（动态规划）的经验的话，可能做的很快，但是如果没有的话，可能会遇到麻烦，我最后看了官网给的答案，也是使用动态规划的思想，说一说我的思路吧。
首先，两个动态增加的量，一个是数字的位数N，另一个是0、1、2、3中出现的个数（虽然要求都至少出现一次，但是为了维护思想的完整性，所以从出现1个，2个。。。一直递推到4个，额，好像1个、2个完了后，再有个3个就递推到4个了，算了，不要在意这些细节）。数字的位数从1增加到N没有问题。关键我们来看看第二个增量。
首先，根据题目要求，如果出现一个数字，这个数字只有可能是2，所以出现一个数字，只有一种情况，我们约定为状态1.
如果出现两个数字，根据动态规划的思想，在必须有一个2的情况下，就有可能是2、0，2，3两种情况，我们分别约定为状态2，状态3.
如果出现三个数字，根据动态规划的思想，在必须有两个数字是2、0，或者2、3的情况下，可能出现2、0、1，2、0、3两种情况。我们约定为状态4，状态5.
如果出现4个数字就是2、0、1、3着一种情况啦，我们约定为状态6.
根据动态规划的思想：
前n步所有的最优解=前n-1步所有的最优解+第n步的最优解。
所以状态2和状态3的最优解，依赖于状态1；状态4的最优解依赖于状态2，状态5的最优解依赖于状态2和状态3，状态6的最优解，依赖于状态4和状态5.
使用一个二维数组a[N][6],横坐标表示数位N，纵坐标表示刚才的6种状态。数组的值，就表示满足两个增量的数的个数，比如a[5][4]，就表示有6位，满足状态5，的不同数字的个数。所以我们这道题需要的答案就是输出a[N-1][6]啦。
假设一个n+1位数,即a[n],那么
满足状态1：
a[n][0]=a[n-1][0]*1:状态1只能继承第n-1位的状态1,a[n-1][0]的最优解
a[n][1]=a[n-1][1]*2+a[n-1][0]*1:状态2依赖于状态1的最优解，状态1只有增加一个0这一种请况，变成状态2.继承第n-1位的状态2，a[n-1][1]，即之前n-1位已经包含2和0两个数字，所以第n位就可以随意选择2或者0,有两种情况。
a[n][2]=a[n-1][2]*1+a[n-1][0]*1:同状态2,注意因为出现了3，所以继承第n-1位时，只能出现3.
a[n][3]=a[n-1][3]*2+a[n-1][1]*1：继承a[n-1][3],则第n位可以出现2和1两种情况；状态2只能增加一个1到状态4；
a[n][4]=a[n-1][4]*2+a[n-1][1]*1+a[n-1][2]*1:同状态4
a[n][5]=a[n-1][5]*2+a[n-1][3]*1+a[n-1][4]*1;同上
然后用一个循环表示从1到n位：
a[0][0]=1;
for(int i=1;i
import java.util.S
public class Main2013124 {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
long a[][]=new long[N][6];
long mod=;
a[0][0]=1;
for(int i=1;i&N;i++){
a[i][0]=(a[j][0]*1)%
a[i][1]=(a[j][0]*1+a[j][1]*2)%
a[i][2]=(a[j][0]*1+a[j][2]*1)%
a[i][3]=(a[j][1]*1+a[j][3]*2)%
a[i][4]=(a[j][1]*1+a[j][2]*1+a[j][4]*2)%
a[i][5]=(a[j][3]*1+a[j][4]*1+a[j][5]*2)%
System.out.println(a[N-1][5]);
去oj上跑时，注意去掉包名和改类名。
关于动态规划：
如果没有动态规划经验的童鞋，建议先百度学习下动态规划。我的讲解能力确实不高，，，我有自知之明，害怕误导童鞋们。dp的思路用的地方非常的多，说点现实点的吧，不止ccf的认证有动态规划的题，大公司招聘也到处都是动态规划的题，我记得百度有一次的实习生招聘就有个度度熊吃饭问题，也是需要使用动态规划思想解决，而且那个题是个比较典型的01动态规划问题，我也想好久写篇博文我们一起探讨下，我拿到过阿里秋招实习生和IBM的实习生offer，给我的感觉，大公司对于算法很重视，对于算法考核很严格，我们还需要多下下功夫。吐槽下学院的数据结构考试，我周围随便一个人都可以上90。。。哪怕是一些把代码背下来，几乎不会编程的妹…（………(￣ε(#￣)☆╰╮o(￣皿￣///)…）所以，真正学到了多少东西还是只有我们自己明白啊。～～
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：10031次
排名：千里之外
(3)(1)(3)(1)(1)服务不可用。CCF计算机职业资格认证-计算机科学与技术学院
|||||||||||
当前位置：
CCF计算机职业资格认证
&&(点击： )
计算机职业资格认证
Computing Accreditation for Professionals (CAP)
计算机专业及相关产业属知识密集型领域，其中最重要的资源是人力资源，
软件开发人才的甄选与培养，无论对企业、学校还是科研单位都是一件困难和麻烦的事情，尤其是在编程能力甄别方面对于整个软件业非常重要。为此，中国计算机学会（CCF）发起了“计算机职业资格认证”工作，针对计算机软件开发、软件测试、信息管理等领域的专业人士进行能力认证。认证对象是
将要从事IT领域专业技术与技术管理人员，以及高校招考研究生的复试对象。
为有效地开展职业资格认证工作，CCF专门成立了认证委员会（Board），下设三个工作委员会（Committee）负责认证的具体组织管理工作。认证委员会是职业资格认证工作的决策管理机构（日常工作由认证委员会的执行委员会负责），技术委员会负责考试标准与考题管理、运营委员会负责考试的组织实施，业务拓展委员会负责市场推广工作。具体工作授权CCF下属的认证管理中心执行。
先期启动计算机软件能力认证
年，CCF将首先启动“计算机软件能力认证（CSP）”工作，它是CCF计算机职业资格认证系列之一。该项认证重点考察软件开发者实际编程能力，由CCF统一命题、统一评测，委托各地设立的考试机构进行认证考试。凡通过计算机软件能力认证考试的人员除可获取成绩单外，均获得由CCF颁发的认证证书。
由CCF组织制定的“计算机软件能力认证”，以被测试者熟练掌握程序设计、数据结构以及算法，通过一定范围内自选的通用编程语言，在指定时间空间内，熟练、准确地完成对给定问题的编程和调试为认证标准。编程语言允许使用C/C++或Java。测试的问题覆盖大学计算机专业所学习的程序设计、数据结构以及算法，以及相关的数学基础知识，并关注编程技巧的使用、性能的优化，以及奇异情况的正常处理。
认证的价值
是计算机领域内一个权威的学术组织，具有高端定位、崇高的价值追求、先进的治理架构和制度规范，拥有众多资深的学者和企业家为骨干会员。CCF开展的该认证工作，具有客观公正及很强的专业性，将解决企业及高校界普遍关心的软件开发人才评价问题，便于有关单位了解求职或求学者的实际开发能力，
可有助甄别及吸纳具有真才实学的技术人才，有效地减轻企业与高校在人才选择过程中组织大量上机考核的成本投入。为了更加贴近用人单位的需要，使得该认证有更强的针对性，CCF会同处于行业领先地位的高校与知名企业的专家，共同制定认证标准，审查考题内容。
目前诸多著名企业，如：华为、腾讯、百度、IBM、微软、金蝶、英特尔等均表示对该认证高度关注。随着认证工作的开展，以它们为代表的IT企业在进行人员招聘时，将陆续会以CCF颁发的计算机职业资格认证证书作为招聘参考的重要依据之一，清华大学等一批高校计算机专业也将以该认证考试取代研究生复试的上机考试。
计算机职业资格认证
软件能力认证
Certified Software Professional
1．&认证概况
认证名称：
计算机软件能力考试认证，简称软件能力认证。
认证定义：
软件能力包括软件的开发、测试、部署和运行维护能力等。本认证目前主要对软件开发能力，即使用计算机通过编程语言和算法，编制成能在计算机上稳定运行的软件模块的能力进行考察和认证。
认证对象：
高等院校的应届毕业生、从事或将要从事
领域技术与技术管理人员均可申请参与认证。
认证方法：
认证考试全部采用上机编程方式，编程语言允许使用
。考核为黑盒测试，以通过测试用例判断程序是否能够输出正确结果来进行评分。考试时间为
认证时间：
每年两次，分别在
2．&认证知识要求
考试内容主要覆盖大学计算机专业所学习的程序设计、数据结构以及算法，以及相关的数学基础知识。包括但不限于：
程序设计基础
逻辑与数学运算，分支循环，过程调用(递归)，字符串操作，文件操作等。
线性表（数组、队列、栈、链表）、树（堆、排序二叉树）、哈希表、集合与映射、图
算法与算法设计策略
排序与查找，枚举，贪心策略，分治策略，递推与递归，动态规划，搜索，图论算法，计算几何，字符串算法、
线段树、随机算法，近似算法
3．&认证标准
计算机软件能力认证以被测试者熟练掌握程序设计、数据结构以及算法，通过一定范围内自选的通用编程语言，在指定时间空间内，熟练、准确地完成对给定问题的编程和调试为认证标准
。编程语言允许使用
。所编程序的正确性由计算机系统根据事先给定的数据进行测试，通过者得分，否则不得分。
达到认证通过分数线的被测试者为合格。
认证机构对达到合格标准者发放认证合格证书（证书上标注所使用编程语言）。
测试的问题覆盖大学计算机专业所学习的程序设计、数据结构以及算法，以及相关的数学基础知识，并关注编程技巧的使用、性能的优化，以及奇异情况的正常处理
参加考试时可带纸质的参考资料，
但不得使用任何通讯工具、存储设备。参考资料
常用语言的程序设计基础书
数据结构的相关书籍、《算法导论》、《组合数学》（推荐卢开橙版）
　Copyright (C) 2017& 南华大学计算机科学与技术学院& All Rights Reserved
联系电话：& 传 真：& 电子信箱：关于报考第五次CCF软件能力认证的通知
-电子科技大学计算机科学与工程学院
关于报考第五次CCF软件能力认证的通知
作者：刘赟卓 来源：CCF
阅读次数：2797
一、主办单位：
中国计算机学会（CCF）—中国计算机领域最权威、最具影响力的专业组织
二、认证目的：
重点考察软件开发者的实际编程能力，向企业和高校推荐合格的软件人才。目前签约企业：华为、百度、阿里巴巴、腾讯、360、微软、金山、金蝶、Intel、软通动力、博彦科技、Salmon等；签约高校：清华大学、北京航空航天大学、国防科技大学、北京大学、哈尔滨工业大学、上海交通大学、华中科技大学、电子科技大学、中山大学、西安交通大学、中国人民大学、天津大学、山东大学等。CCF计划将认证推广到全国的高校和企业。
三、认证报名对象：
1.电子科技大学的本科、研究生；
2.川内其他高校的本科、研究生；
3.即将进入职场及IT行业一线技术人员和技术管理人员。
四、认证内容：
主要覆盖大学计算机软件工程专业所学习程序设计、数据结构、算法，以及相关数学基础知识。
五、认证方式：
认证全部采用上机编程方式，可以自带参考资料，包括：常用语言的程序设计基础书、数据结构的相关书籍、《算法导论》、《组合数学》（推荐卢开橙版）；
编程语言允许使用：C/C++或Java。考核为黑盒测试，编制的程序在限定的时间空间内以通过多组测试数据判断程序是否能够输出正确结果来进行评分；
认证时间为4小时，共5道题，从第一题至第五题，难度依次递进，每题100分，总分500分。
六、认证报名起止日期：
七、认证时间和地点：
时间：日下午13:30-17:30&&&&&
地点：电子科技大学
八、认证报名方式：
报名网址：http://cspro.org（IE浏览器），个人先注册再报名，考试机构请选择“电子科技大学”；准备1寸正面免冠证件电子照片1张，大小不超过1M，建议尺寸为150*200，格式为jpg、gif、png；
九、{C} 认证考试编译环境：
&&&&& C/C++：Dev-CPP 5.4.0 (Min GW 4.7.2)
&&&&& Java：Eclipse (Java SDK 1.7.0_15)
&&&&& 浏览器：Chrome
十、{C} 认证前模拟练习：
为了让考生熟悉考试操作环境，减少操作失误导致的失分，认证网站为所有注册的考生提供了模拟练习环境。同学们可以做历届真题，操作步骤：注册账号登录后点击“认证题库”→“历届真题”→“网上练习”，看到试题清单列表后，点击“查看试题/答案”，将编写好的代码复制到答题栏的答案程序中即可。系统支持在线评测。
另外，（http://cspro.org）网站上有两篇文章是指导如何做题的：《CCF软件能力认证上机指导书》和《软件能力认证注意事项及实例说明》，可以用作解题参考。
其他类似考试的学习网址：/contests（学习全国程序设计考试（PAT）的题目集网址）。
十一、收费标准：
1.&&&&& CCF会员免费；
2.&&&&& 非会员考生奖励政策（针对交纳100元报名费的非CCF会员人员）
参加第五次CCF计算机软件能力认证且成绩达到100分以上（含100分）的交纳报名费用者，每人奖励现金100元（奖金将支付到原缴费支付宝账户）。以下是通过对前几次CCF软件能力认证的总结，达到100分的几个条件，仅供参考：
（1）100分以上通过率是83.42%。
（2）具备计算机软件编程初级基础的高校在校生均可获得100分以上。
（3）试题难度可参考网站的模拟试题和历届真题。
十二、成绩效力
&&& 认证成绩公布后，CCF CSP认证中心会根据参与认证者的意愿把认证成绩信息发送给签约企业和高校，企业和高校会根据需要与被认证者进行联系。
十三、注意事项
1、已参加过CCF CSP软件能力认证者可凭原登录账号和密码直接登录CCF职业资格认证网站（http://cspro.org）进行报名。
2、报名成功并在认证网站通过支付宝支付报名费后，直接打印收据（支付时请标注姓名）。
3、认证结束后一周内通过网站查看成绩并直接打印成绩单。如果需要加盖CCF公章的成绩单，请发邮件到cspro@，注明姓名和准考证号。
4、作弊处理：认证现场除了有监考老师巡视外，CCF会派巡视员抽查考场。为发现CSP认证中的作弊现象，在评测过程中，CCF CSP技术委员会将采用两两比对的方法，对所有参加认证者的源程序进行比对，如发现源程序存在相似或雷同现象，会严肃处理，情节严重的取缔所在高校认证点并在CCF官网公布。
5、如果您有什么疑问或在报名过程中遇到任何问题，请发送电子邮件至cspro@或在工作日拨打电话与CCF CSP认证中心联系，相关工作人员将为您提供咨询服务，联系电话：010-/25。
6、关于CCF认证的相关内容详见CCF认证官方网站:http://cspro.org。
十四、历年被高薪企业录取的名单
http://www./sites/ccf/xhdtnry.jsp?contentId=1
http://mp./s?__biz=MjM5MTY5ODE4OQ==&mid=&idx=8&sn=b2dad5fdadf2fdcc8d4a443&scene=1#rd
上一篇：关于2015年暑期社会实践成果提交分类说明
下一篇：【URP】计算机学院2015年URP计划补充第二批次招生报名及面试通知
校内热点链接
电子科技大学主页
法语培训中心（成都法语联盟）
教育科研网
四川高校思政网
四川省大学生思想状况调查
电子科大老科协
第26届世界大运会
电子科技大学智能工程实验室
其他学院链接链接
通信与信息工程学院
电子工程学院
微电子与固体电子学院
物理电子学院
计算机科学与工程学院
自动化工程学院
机械电子工程学院
光电信息学院
生命科学与技术学院
数学科学学院
经济与管理学院
政治与公共管理学院
外国语学院
航空航天学院/空天科学技术研究院
信息与软件工程学院(示范性软件学院)
电子科学技术研究院
通信抗干扰技术国家级重点实验室
国际教育学院
东莞电子科技大学电子信息工程研究院
马克思主义教育学院
英才实验学院
能源科学与工程学院
资源与环境学院
格拉斯哥学院
无锡研究院
电子科技大学成都研究院
学校部门链接
学校办公室
纪律检查委员会
党委组织部
党委宣传部
党委学生工作部
党委统战部
科学技术发展研究院
合作发展部
计划财务处
国有资产与实验管理处
国际合作与交流处
继续教育学院
后勤管理处
离退休工作处
学报编辑部
国际教育学院
体育场馆管理中心
沙河校区管理委员会