2013腾讯编程马拉松初赛(3月22)赛题

acm初赛试题及答案# acm初赛试题及答案1. 问题描述给定一个整数n，求出n以内所有正整数的和。

2. 输入格式输入包含一个整数n（1≤n≤10000）。

3. 输出格式输出一个整数，表示n以内所有正整数的和。

4. 样例输入```100```5. 样例输出```5050```6. 问题分析本题要求计算从1到n的所有正整数的和。

这是一个简单的数学问题，可以通过公式求解。

7. 解题思路使用求和公式：\( \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \)。

8. 算法实现编写一个函数，输入n，输出计算结果。

9. 代码示例```pythondef sum_of_numbers(n):return n * (n + 1) // 2n = int(input())print(sum_of_numbers(n))```10. 注意事项输入的n可能会非常大，需要考虑整数溢出的问题。

11. 测试用例- 输入：1输出：1- 输入：10输出：55- 输入：10000输出：5000500012. 评分标准- 正确性：算法正确，输出结果符合预期。

- 效率：算法执行效率高，能在规定时间内完成计算。

- 代码风格：代码可读性好，注释清晰。

13. 常见错误- 未考虑整数溢出。

- 未正确使用求和公式。

- 代码中存在语法错误。

14. 扩展思考- 如果要求计算从m到n的所有正整数的和，应该如何修改算法？ - 如何优化算法以处理更大的输入值？15. 参考答案- 对于扩展思考的第一个问题，可以将求和公式修改为：\( \sum_{i=m}^{n} i = \frac{n(n+1)}{2} - \frac{(m-1)m}{2} \)。

- 对于扩展思考的第二个问题，可以考虑使用更高效的数据结构或者算法来减少计算量。

以上是ACM初赛试题及答案的完整内容。

北京理工大学珠海学院A-G共7题注意：题目难度与题号无关A老吴的棋盘游戏Time Limit: 1s Memory Limit: 256MProblem Description集训的结束带来的就是新学期的到来。

开学已久，ACMer们许久没A题也有些无聊了，不过最近老吴发现了一个游戏可以用来消磨时间。

其实就是一个棋盘游戏，它的规则是这样的，全场只有一颗棋子，初始坐标在（1，1）点，下一步只能往（1，2）（0，1）（2，1）三个方向移动。

后面该棋子也以这个规则移动。

对家提问恰好走N步且不经过已走过的点有多少种走法，而你只需回答有M种走法就行了。

大胆地去猜测具体规则吧，骚年。

Input有多组测试数据。

每行都有一个整数N（N<=20），当N小于或等于0时结束全部输入。

Output输出占一行，为对家提问的结果M。

Sample Input13Sample Output317AuthorBy-廖瑞华B老陈逛校园Time Limit: 1s Memory Limit: 256MProblem Description老吴的棋盘游戏好不好玩？不过瘾的话来做一个有意义的事吧，荔枝园去过么？没去过不要紧，我们的活动不在那里进行，在全校范围内，假设学校有N个地点，M条道路。

是这样的，有一天老陈出去校门口送pc坐车回家，回来时忽然心血来潮就把学校走了一圈。

他发现其实我们学校真的很大，只是我们都没去走过而已。

这样吧，你们去走遍北理珠校园？走归走，从2饭到图书馆有很多路径可以选择，你们应该寻找捷径。

走过后最好就给老陈画一张地图啦。

不过只需要给老陈路径的数据就可以了，绘制就由他来做吧。

大胆地去开发校园吧，别留遗憾。

Input有多组测试数据。

第一行都有2个整数N M（1<=N<=1000，0<=M<=10000），接下来有M行a b c，（1<=a,b<=N，0<=c<=10000），表示a与b之间有一条长度为c的道路。

acm竞赛试题及答案ACM竞赛试题及答案1. 问题描述：给定一个整数数组，找出数组中没有出现的最小的正整数。

2. 输入格式：第一行包含一个整数n，表示数组的长度。

第二行包含n个整数，表示数组的元素。

3. 输出格式：输出一个整数，表示数组中没有出现的最小的正整数。

4. 样例输入：53 4 1 2 55. 样例输出：66. 问题分析：首先，我们需要理解题目要求我们找出数组中缺失的最小正整数。

这意味着我们需要检查数组中的每个元素，并确定最小的正整数是否在数组中。

7. 算法描述：- 遍历数组，使用一个哈希集合记录出现的数字。

- 从1开始，检查每个正整数是否在哈希集合中，直到找到不在集合中的最小正整数。

8. 代码实现：```pythondef find_missing_positive(nums):seen = set()for num in nums:if num <= 0:continuewhile num in seen or num > len(nums):num += 1seen.add(num)return min(set(range(1, len(nums) + 1)) - seen)```9. 测试用例：- 输入：[3, 4, -1, 1]- 输出：210. 答案解析：在给定的测试用例中，数组[3, 4, -1, 1]中没有出现的最小正整数是2。

这是因为-1不是正整数，所以可以忽略。

数组中已经出现了1和3，所以下一个最小的正整数就是2。

11. 注意事项：- 确保数组中的元素是整数。

- 考虑数组中可能包含0或负数的情况。

- 算法的时间复杂度应尽可能低。

12. 扩展思考：- 如果数组非常大，如何优化算法？- 如果数组中的元素可以是浮点数，算法应该如何修改？13. 参考答案：- 针对大数组，可以考虑使用更高效的数据结构，如平衡二叉搜索树。

- 如果元素是浮点数，需要先将其转换为整数，然后再进行处理。

acm大赛试题及答案ACM大赛试题及答案1. 题目一：字符串反转问题描述：编写一个程序，输入一个字符串，输出其反转后的字符串。

输入格式：输入包含一个字符串，字符串长度不超过100。

输出格式：输出反转后的字符串。

示例：输入：hello输出：olleh答案：```pythondef reverse_string(s):return s[::-1]input_string = input().strip()print(reverse_string(input_string))```2. 题目二：计算阶乘问题描述：编写一个程序，输入一个非负整数n，输出n的阶乘。

输入格式：输入包含一个非负整数n，n不超过20。

输出格式：输出n的阶乘。

示例：输入：5输出：120答案：```pythondef factorial(n):if n == 0:return 1else:return n * factorial(n - 1)n = int(input())print(factorial(n))```3. 题目三：寻找最大数问题描述：给定一个包含n个整数的数组，找出数组中的最大数。

输入格式：输入包含一个整数n，表示数组的大小，随后是n个整数。

输出格式：输出数组中的最大数。

示例：输入：5 1 2 3 4 5输出：5答案：```pythonn = int(input())numbers = list(map(int, input().split()))max_number = max(numbers)print(max_number)```4. 题目四：判断闰年问题描述：编写一个程序，输入一个年份，判断该年份是否为闰年。

输入格式：输入包含一个整数，表示年份。

输出格式：如果输入的年份是闰年，则输出"Yes"，否则输出"No"。

示例：输入：2000输出：Yes答案：```pythonyear = int(input())if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):print("Yes")else:print("No")```5. 题目五：斐波那契数列问题描述：编写一个程序，输入一个非负整数n，输出斐波那契数列的第n项。

【题目背景】此题为2013年3月23日，腾讯马拉松编程预赛第一题解答。

【题目概述】已知当前日期，推算一定天数以前的日期和一定天数以后的日期。

例如，当前日期为2012年4月25日，4天后的日期为2012年4月29日，4天前的日期为2012年4月21日。

程序默认日期为2013年3月24日。

/********************* 此题为2013年腾讯** 马拉松编程预赛** 3月24日第一题解答*********************/#include <iostream>using namespace std;class date //声明日期类{public:int year;int month;int day;date(int y=2013,int m=3,int d=24);friend bool leap(int year);friend void add(date d,int);};date::date(int y,int m,int d){year=y;month=m;day=d;}void add(date d,int addNum=0) //将当期日期向未来移，并且输出{int i=0,j,k,flag;int day=d.day,month=d.month,year=d.year;intday_table[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31} };while(i<addNum){if(leap(d.year))flag=1;elseflag=0;for(j=month;j<=12;j++){if(day+addNum-i<day_table[flag][d.month-1]){d.day+=addNum-i;i+=addNum-i;break;}elsefor(k=day;k<=day_table[flag][d.month-1];k++){d.day++;i++;if(d.day>day_table[flag][d.month-1]){d.day=1;d.month++;day=1;break;}}if(d.month>12){d.month=1;month=1;d.year++;break;}}}cout << d.year << "/" << d.month << "/" << d.day <<"\t";}void dele(date d,int deleNum) //追溯历史，并输出日期{int i=0,j,k,flag;int day=d.day,month=d.month,year=d.year;intday_table[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31} };while(i<deleNum){if(leap(d.year))flag=1;elseflag=0;for(j=month;j>0;j--){if(day-deleNum+i>0){d.day-=deleNum-i;i+=deleNum-i;break;}elsefor(k=day;k>0;k--){d.day--;i++;if(d.day==0){d.month--;if(d.month==0)d.day=day_table[flag][11];elsed.day=day_table[flag][d.month-1];day=d.day;break;}}if(d.month==0){d.month=12;month=12;d.year--;break;}}}cout << d.year << "/" << d.month << "/" << d.day <<"\n\n";}bool leap(int year) //判断是否为闰年{if(year%4==0 && year%100!=0 || year%400==0)return true;elsereturn false;}int main(){date aDay; //创建对象时，可以给出自己的日期，如date aDay(2013,4,29) int n,i,Num;cout << "输入计算次数：";cin >> n;for(i=0;i<n;i++){cout << "天数：";cin >> Num;add(aDay,Num);dele(aDay,Num);}return 0;}【截图】说明：此结果是日期为2013年3月24日时的结果。

全国计算机技术与软件专业技术资格（水平）考试2013年上半年程序员上午试卷（考试时间 9 : 00～11 : 30 共 150 分钟）1. 在答题卡的指定位置上正确写入你的姓名和准考证号，并用正规 2B 铅笔在你写入的准考证号下填涂准考证号。

2. 本试卷的试题中共有 75 个空格，需要全部解答，每个空格 1 分，满分75 分。

3. 每个空格对应一个序号，有 A、B、C、D 四个选项，请选择一个最恰当的选项作为解答，在答题卡相应序号下填涂该选项。

4. 解答前务必阅读例题和答题卡上的例题填涂样式及填涂注意事项。

解答时用正规 2B 铅笔正确填涂选项，如需修改，请用橡皮擦干净，否则会导致不能正确评分。

例题● 2013 年上半年全国计算机技术与软件专业技术资格（水平）考试日期是（88）月（89）日。

（88）A. 3 B. 4 C. 5 D. 6（89）A. 20 B. 21 C. 22 D. 23因为考试日期是“5 月 20 日”，故（88）选 C，（89）选 A，应在答题卡序号 88 下对 C 填涂，在序号 89 下对 A 填涂（参看答题卡）。

●在Word的编辑状态下，若要防止在段落中间出现分页符，可以通过单击鼠标右键在弹出的菜单中选择（1）命令;在“段落”对话框中，选择“换行和分页”选项卡，然后再勾选（2）。

(1)A.段落(P) B.插入符号(S) C.项目符号(B) D.编号(N)(2)A. B.C. D.●某Excel工作表如下所示，若在D1单元格中输入=$A$1+$B$1+C1，则D1的值为(3)；此时，如果向垂直方向拖动填充柄至D3单元格，则D2和D3的值分别为（4）。

(3)A.34 B.36 C.39 D.54(4)A.79和99 B.69和93 C.64和60 D.79和93●(5)服务的主要作用是实现文件的上传和下载。

(5)A.Gopher B.FTP C.TelnetD.E-mail●与八进制数1706等值的十六进制数是（6）。

2013上半年程序员考试真题及答案-下午卷试题一平面上一个封闭区域内稳定的温度函数是一个调和函数。

如果区域边界上各点的温度是已知的（非常数），那么就可以用数值方法近似地计算出区域内各点的温度。

假设封闭区域是矩形，可将整个矩形用许多横竖线切分成比较细小的网格，并以最简单的方式建立坐标系统，从而可以将问题描述为：已知调和函数u(i,j)在矩形{0≤i≤m；0≤j≤n}四边上的值，求函数u在矩形内部各个网格点{(i,j)|i=1，…，m-1；j=1，…，n-1}上的近似值。

根据调和函数的特点可以推导出近似算式：该矩形内任一网格点上的函数值等于其上下左右四个相邻网格点上函数值的算术平均值。

这样，我们就可以用迭代法来进行数值计算了。

首先将该矩形内部所有网格点上的函数值设置为一个常数，例如u(0,0);然后通过该迭代式计算矩形内各网格点上的新值。

这样反复进行迭代计算，若某次迭代后所有的新值与原值之差别都小于预定的要求（如0.01),则结束求解过程。

阅读以上说明和流程图，填补流程图中的空缺（1)〜（5)，将解答填入答题纸的对应栏内。

(1) 0或任意一个负数(2) (u(ij+1)+u(ij-1)+u(i-1j)+u(i+1j))/4或等价表示(3) max(4) new或（(u(i,j+l)+u(i，j-l)+u(i-lj)+u(i+l，j))/4或等价表示(5) max试题二（共15分）本题考查算法（数值计算）流程的描述。

封闭区域内稳定（没有奇异点）的温度场、磁场等都是调和函数。

已知边界上的值，就可以近似计算区域内各点的值。

对于网格化后的矩形区域{0≤i≤m；0≤j≤n},其边界点为{(0，j)丨j=0，..，n}、{((i，0)丨i=0，..，m}、{(m，j)丨j=0,..,n}、{((i,n)|i=0,..,m}，其内点为{(i，j)|i=1，•.•m-l;j=1，...，n-l}。

本题采用迭代法进行近似计算。

2013腾讯编程马拉松初赛（3月22）赛题1001 小Q系列故事——为什么时光不能倒流Time Limit: 0.1 Seconds Memory Limit: 65536K我以为我会是最坚强的那一个我还是高估了自己我以为你会是最无情的那一个还是我贬低了自己就算不能够在一起我还是为你担心就算你可能听不清也代表我的心意那北极星的眼泪闪过你曾经的眼角迷离那玫瑰花的葬礼埋葬的却是关于你的回忆如果时光可以倒流我希望不要和你分离如果注定分离我希望不要和你相遇. ——摘自《小Q失恋日记》第17卷520页这是码农小Q第58次失恋了，也是陷得最深的一次。

要知道，小Q自从第一次到腾讯公司报到，就被风姿绰约的前台MM彻底迷住了，这1000多个日日夜夜他无时无刻不在憧憬着他们美好的未来。

为了能见到MM，他每天早到晚归，甘愿加班，连续3年被评为优秀员工，并且以全公司最快的速度晋级到四级岗位。

就在他终于鼓足勇气准备表白的时候，MM却满面春风地送来了一包喜糖......现在小Q专门请了年休假治疗情伤，但情绪总不见好转，每天足不出户，眼睛盯着墙上的钟表，反复念叨：“表白要趁早，时光不倒流，表白要趁早，时光不倒流......”假设现在已知当前的时间，让时间倒退回若干，你能计算出钟表显示的时间吗？Input输入首先包含一个整数N，表示有N组测试用例。

接下来的N行表示N个测试用例，每行包括2个时间HH:MM:SS hh:mm:ssHH:MM:SS表示当前的时间，hh:mm:ss表示希望倒退回去的时间。

[Technical Specification]00<=HH<=1100<=hh<=9900<=MM, SS, mm, ss<=59Output请计算并输出钟表倒退后显示的时间，要求输出格式为HH:MM:SS（即时分秒均显示2位，不足则补0），每组数据输出占一行。

Sample Input211:28:32 02:14:21 05:00:00 96:00:01Sample Output09:14:1104:59:591002 小明系列故事——女友的考验Time Limit: 0.2 Seconds Memory Limit: 32768K终于放寒假了，小明要和女朋友一起去看电影。

1001 小Q系列故事——屌丝的逆袭Time Limit: 0.1Seconds Memory Limit: 65536K毕业于普通本科的小Q一直自称是资深屌丝，不仅学校不知名，甚至他自己在这个普通学校也是默默无闻——直到临近毕业的时候，班里5朵金花中的2位甚至从没和他说过话！谁又能想到，如此不起眼的小Q在历经重重面试环节后，竟然如愿以偿加入了心仪已久的腾讯公司！消息刚刚传开的那几天，这在他们班甚至整个学院都是讨论的热门话题，如果这时候你还表示不知道小Q是谁，你都会被大家当作怪物的。

正所谓野百合也有春天，屌丝也有逆袭的那一天！刚到腾讯大厦上班的那几天，小Q眼中的一切都是那么新鲜，连每天见到的前台MM在他眼中都胖的那么可爱。

小Q就这样在紧张与兴奋的情绪中度过了一天又一天，每天即勤奋认真又小心翼翼，很希望能给主管留下个好印象，以免失去这来之不易的工作机会。

一段时间以后，随着对工作环境以及同事的熟悉，小Q逐渐放松下来，在工作间隙，他细细观察了自己的工作环境，发现整个工作室是一个N行M列的矩形布局，或者是因为屌丝的本性逐步暴露，他还暗自给每个同事在心里进行了魅力值评分（为区别男女，男生一律用负整数表示，女生一律用正整数表示）。

现在，小Q把所有人的数据记录下来，并且这样定义一个位置的价值：1、一个位置的价值只和其上下左右四个邻居的魅力值有关（对于靠边的位置，只考虑其存在的邻居）；2、如果某位置的邻居和该位置主人性别不同，则总分加上邻居魅力值的绝对值，否则减去；3、对周围所有邻居的数据处理后，最终的得分即为这个位置的最终得分，得分越高，则该位置越好；现在你能帮助小Q计算一下哪里才是最佳位置吗？Input输入包含多组测试数据；每组测试数据的第一行包含2个整数N和M，表示工作室的布局是N行M列；接下来的N行，每行有M个整数，分别表示对应位置员工的魅力值数据Ki，正整数表示女生的魅力值，负整数表示男生的魅力值；N和M为0的时候表示输入数据结束。

核桃编程马拉松真题A卷一、初赛满分及考试时间初赛满分为100分，测试时间90分钟二、答题方式线上答题三、试卷内容结构选择题20道，每道2分，合计40分编程题a 20分编程题b 40分四、具体考点：（一）编程工具使用，基础知识代码块1.简单事件、代码拼接2.移动、旋转、方向等运动类功能性代码块的使用3.说、造型、特效等外观类功能性代码块的使用4.坐标系考试要求1.掌握代码块的拼接方式，能够用【当开始被点击】、【当按下按键】、【当角色被点击】等启动程序；2.知道移动、旋转和方向的关系，能够运用运动类代码块制作动画，根据运动类代码块的拼接推断代码执行结果；3.能够使用说、造型和特效等代码块制作对话故事，创作动画效果，根据代码推断执行结果；4.建立Scratch里坐标的映射关系，知道移到、滑行的区别，知道增加和设为的区别。

（二）基本程序结构1.顺序执行2.循环3.条件判断4.并行考试要求1.知道最基本的程序执行方式——从上到下依次执行2.能够区分循环和循环体，运用循环简化代码3.能够运用条件判断编写选择结构的代码，实现根据不同情况执行不同代码的功能4.能够阅读混合顺序、循环和条件判断三种结构的代码5.知道程序并行的问题，能够解决诸如子弹碰敌人，一方消失另外一方不消失的问题；（三）Scratch技巧1.负数的应用2.随机数的应用考试要求1.知道负数的含义，知道负数在Scratch中的应用，例如变小，后退，坐标定位等；2.知道随机数的含义，知道随机数在Scratch中的应用，例如随机位置、随机造型、时间等；（四）高级编程功能1.克隆2.广播3.数学和逻辑运算4.变量考试要求1.能够区分本体和克隆体，知道控制本体和克隆体的地方；2.知道广播的特性，能够区分广播和广播并等待。

能够运用广播协调角色间的动作，解决并行问题等；3.能够使用四则运算符和比较运算符等进行简单的数学运算；4.知道逻辑与、或、非，能够根据效果灵活运用逻辑运算符解决问题；5.知道变量的意义，能够根据输入和代码推算出输出，能够运用变量实现诸如记分、计时、传递消息等功能。

更多CCF真题及答案，请搜索：/acpchenpeng/article/category/5965279试题编号：201312-1试题名称：出现次数最多的数1.#include<cstdio>2.#include<cstdlib>3.#include<iostream>4.#include<string>5.#include<vector>6.#include<list>7.#include<map>8.ing namespace std;10.11.int main()12.{13.int n,m,max;14.int num=0;15. cin >> n;16. map<int,int> f; //有序容器17.18.for(int i = 0;i < n; i++)19. {20. cin>>m;21. f[m]++;22. }23.24.for(map<int,int>::iterator it = f.begin();it!=f.end();it++)25. {26.if(it->second > num)27. {28. num = it->second;29. max = it->first;30. }31. }32.33. cout << max;34.35.return 0;36.37.}201312-2试题名称：ISBN号码[cpp]view plaincopy1.#include<cstdlib>2.#include<iostream>3.#include<string>4.#include<vector>5.#include<map>6.ing namespace std;8.9.int main()10.{11. string s;12. cin >> s;13.int a[10]={0};14.int sum =0;15.int j =0;16.for(string::iterator i = s.begin() ;i != s.end(); i++)17. {18.19.if(*i != '-')20. {21. a[j] = *i - '0';22.if(j < 9)23. sum += a[j] * (j+1);24. j++;25. }26. }27.28.29.if(sum % 11 == a[9] ||(sum % 11 == 10 && s[12] == 'X'))30. cout << "Right" << endl;31.32.else33. {34.if(sum % 11 == 10)35. s[12] = 'X';36.else37. s[12] = sum % 11 + '0'; //不要忘记+‘0’38. cout << s << endl;39.40. }41.42.return 0;43.}试题编号： 3试题名称：最大的矩形[cpp]view plaincopy1.#include<cstdlib>2.#include<iostream>3.#include<string>4.#include<vector>5.#include<map>6.ing namespace std;8.9.int main()10.{11.int n,m;12. cin >> n;13.14. vector<int> v;15.for(int i =0; i< n;i++)16. {17. cin >> m;18. v.push_back(m);19. }20.21.int s_max=0; //全局变量，用于保存最大的面积22.23.for(int i=0;i<n;i++)24. {25.int h_min = v[i]; //保存最小高26.27.for(int j=i;j<n;j++)28. {29.if(v[j] < h_min)30. h_min = v[j]; //更新最小高,注意是v[j],不是j31.int s = h_min * (j-i+1); //计算当前面积32.if( s > s_max)33. s_max = s; //更新最大面积34. }35. }36. cout << s_max <<endl;37.38.return 0;39.}试题编号：201312-4试题名称：有趣的数#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <vector>#include <deque>#include <list>using namespace std;long long f[2000][3][2]; // f[seq_k to place][0: to place 0 , 1: ethier 0 or 1, 2 : must be 1][3 is placed ?1 : 0]int dp(int n, int p1, int p3){long long &now = f[n][p1][p3];if (now != -1)return now;if (n == 0){if (p1 == 2 && p3 == 1){now = 1;}else{now = 0;}return now;}now = 0;if (p1 == 0){now += dp(n-1, 1, p3); // go 0}else if (p1 == 1){now += dp(n-1, 1, p3); // go 0 now += dp(n-1, 2, p3); // go 1 }else // p1 == 2{now += dp(n-1, 2, p3); // go 1}if (p3 == 0){now += dp(n-1, p1, p3); // go 2;now += dp(n-1, p1, 1); // go 3;}else{now += dp(n-1, p1, 1); // go 3;}now %= 1000000007;}int main(){int n;cin >> n;memset(f, -1, sizeof(f));int ans = dp(n - 1, 0, 0); // seq[n] is 2cout << ans << endl;return 0;}试题编号：201312-5试题名称：I’m stuck!#include <cstdio>#include <string>#include <vector>#include <deque>#include <cstring>#include <list>using namespace std;//class Move{ public:virtual bool CanMove(char from, char to, int dx, int dy) = 0; };class ForwardMove : public Move{public:virtual bool CanMove(char from, char to, int dx, int dy) {if (to == '#') return false;switch (from){case '+' : case 'S' : case 'T' : return true; break;case '-' : return dy != 0; break;case '|' : return dx != 0; break;case '.' : return dx == 1; break;}return false;}};class BackwardMove : public Move{public:virtual bool CanMove(char from, char to, int dx, int dy) {if (to == '#') return false;switch (to){case '+' : case 'S' : case 'T' : return true; break;case '-' : return dy != 0; break;case '|' : return dx != 0; break;case '.' : return dx == -1; break;}return false;};char s[100][100];typedef bool ARR[100][100];ARR bs, bt;int sx, sy, tx, ty;int d[4][2] = {{-1, 0},{1, 0},{0, 1},{0, -1}};void Bfs(ARR b, Move *move, int x, int y){if (b[x][y])return;b[x][y] = true;for (int o = 0; o < 4; o++){int dx = d[o][0];int dy = d[o][1];int xx = x + dx;int yy = y + dy;if (move->CanMove(s[x][y], s[xx][yy], dx, dy)) {Bfs(b, move, xx, yy);}}}int n, m;int main(){cin >> n >> m;for (int i = 0; i <= n + 1; i++)for (int j = 0; j <= m + 1; j++)s[i][j] = '#';for (int i = 1; i <= n; i++)cin >> s[i]+1;for (int i = 0; i <= n + 1; i++)s[i][m + 1] = '#';for (int i = 0; i <= n + 1; i++){for (int j = 0; j <= m + 1; j++){if (s[i][j] == 'S'){sx = i; sy = j;}if (s[i][j] == 'T'){tx = i;ty = j;}}}Bfs(bs, new ForwardMove(), sx, sy); Bfs(bt, new BackwardMove(), tx, ty);int ans = 0;for (int i = 0; i <= n + 1; i++){for (int j = 0; j <= m + 1; j++){if (bs[i][j] && ! bt[i][j])ans ++;}}if (bs[tx][ty] == false)cout << "I'm stuck!" << endl;elsecout << ans << endl;return 0;}。

取石子游戏Time Limit:1S Memory Limit:1000KTotal Submit:505 Accepted:90Description有两堆石子，数量任意，可以不同。

游戏开始由两个人轮流取石子。

游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。

最后把石子全部取完者为胜者。

现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

Input输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。

Output输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

Sample Input2 18 44 7Sample Output1跳蚤Time Limit:1S Memory Limit:1000KTotal Submit:198 Accepted:44DescriptionZ城市居住着很多只跳蚤。

在Z城市周六生活频道有一个娱乐节目。

一只跳蚤将被请上一个高空钢丝的正中央。

钢丝很长，可以看作是无限长。

节目主持人会给该跳蚤发一张卡片。

卡片上写有N+1个自然数。

其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。

跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。

而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。

比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。

而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。

当确定N和M后，显然一共有M^N张不同的卡片。

19.2 十九届提高组一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）1．一个32位整型变量占用（ A ）个字节。

A．4 B．8 C．32 D．1282．二进制数11.01在十进制下是（ A ）。

A．3.25 B．4.125 C．6.25 D．11.1253．下面的故事与（ B ）算法有着异曲同工之妙。

从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事…………………………’”A．枚举B．递归C．贪心D．分治4．1948年，（ D ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

A．冯•诺伊曼(John von Neumann) B．图灵（Alan Turing）C．欧拉（Leonhard Euler） D．克劳德•香农（Claude Shannon）【分析】香农信息论鼻祖5．已知一棵二叉树有2013个节点，则其中至多有（ A ）个节点有2个子节点。

A．1006 B．1007 C．1023 D．1024【分析】（1）树根深度为0，深度为10的满二叉树节点总数2047；（2）本题树深为10的完全二叉树，与满二叉树相比少了34个节点，（3）深度为9的满二叉树节点总数量为1023；（4）1023-（34/2）=10066．在一个有向图中，如果任意两点之间都存在路径相连，则称其为连通图。

右图是一个有5个顶点、8条边的连通图。

若要使它不再是连通图，至少要删去其中的（ B ）条边。

A．2 B．3 C．4 D．5【分析】要使图不联通，只要其中某一个节点不连通即可，所有顶点度最少是3，所以最少需要删除3条边7．斐波那契数列的定义如下：F1=1，F2=1，F n=F n-1+F n-2（n≥3）。

如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（ D ）。

一、单选题（15*1.5）1、A，一个字节有8个bit，32位整型变量占用4个字节，故选A。

2、A，二进制11.01转为十进制，（11.01）2 = 1*2+1+0*0.5+1*0.25 = （3.25）10 。

3、B,老和尚给小和尚讲的故事里边有故事本身，递归是函数内部调用函数本身，故选B，递归。

4、D，香农信息论鼻祖。

5、A，一定是满二叉树时拥有2个字节点的节点数最多，最下一层会有2013-1023=990个节点，于是倒数第二层会有990/2=495个节点有2个字节点，从第1层到倒数第三层共有1023-2^9=511个节点，且这些节点都是用2个子节点的节点，所以共有495+511=1006个，选A。

6、B，要使图不联通，只要其中某一个节点不连通即可，所有顶点度最少是3，所以最少需要删除3条边，选B。

7、D，此题最开始一眼扫到的时候脑子进水，跟学生将选B，O（n），实际上不是，计算F1需要1次，计算F2需要一次，计算Fn需要计算F(n-1)的次数加上F（n-2）的次数，所以其实就是计算Fn次，于是答案选择D，至于这个Fn到底是多大，数学上可以计算，它等于O((（1+sqrt(5)）/2)^n).8、B，这个必须是B，没有什么好说的，中序遍历保证左边都是小于根的，右边都是大于根的，所以可以保证是一个有序序列。

9、D，A项6和17对11取余都是6发生冲突，B项10的平方和17的平方对11取余都是1发生冲突，C项6的两倍和17的两倍对11取余都是1发生冲突，D 项分别为1，2，3，4，不冲突。

10、D，IPV6地址是128位的。

谢谢网友指正！11、C，二分为6个和6个的顶点，此时边最多，有36条边。

12、B，我的学生几乎全选A去了，因为之前讲题只介绍过ASCII码，但是看到统一二字也应该想到Uni...前缀啊。

13、D，64位非零浮点数强制转换成32位浮点数，两个数会有大小上的细微差别，但不会发生符号变化，因为有专门的符号位。

YMO初赛三年级试卷专业课原理概述部分一、选择题（每题1分，共5分）1. 下列哪个是YMO初赛三年级试卷中的基础概念？A. 数据结构B. 机器学习C. 算法分析D. 操作系统2. 在YMO初赛三年级试卷中，哪个概念与数据库管理系统无关？A. 关系模型B. 事务管理C. 信号量D. 索引3. 以下哪个不是YMO初赛三年级试卷中的网络协议？A. TCP/IPB.C. FTPD. SMTP4. 在YMO初赛三年级试卷中，哪个是面向对象编程的基本特征？A. 继承B. 循环C. 数组D. 递归5. 以下哪个不是YMO初赛三年级试卷中的编程语言？A. PythonB. JavaC. C++D. HTML二、判断题（每题1分，共5分）1. YMO初赛三年级试卷中的算法都是高效的。

（）2. 在YMO初赛三年级试卷中，操作系统的主要功能是管理硬件资源。

（）3. YMO初赛三年级试卷中的网络编程只需要了解TCP协议即可。

（）4. YMO初赛三年级试卷中的数据结构只包括线性结构。

（）5. 在YMO初赛三年级试卷中，编程语言的选择对程序的性能没有影响。

（）三、填空题（每题1分，共5分）1. YMO初赛三年级试卷中，算法的时间复杂度通常用______表示。

2. 在YMO初赛三年级试卷中，______是数据库管理系统的基础。

3. YMO初赛三年级试卷中，______是一种自底向上的程序设计方法。

4. 在YMO初赛三年级试卷中，______是一种用于解决多线程同步问题的机制。

5. YMO初赛三年级试卷中，______是一种面向对象的编程语言。

四、简答题（每题2分，共10分）1. 简述YMO初赛三年级试卷中算法的基本概念。

2. 简述YMO初赛三年级试卷中操作系统的主要功能。

3. 简述YMO初赛三年级试卷中网络编程的基本概念。

4. 简述YMO初赛三年级试卷中数据结构的基本概念。

5. 简述YMO初赛三年级试卷中编程语言的基本概念。

noc编程马拉松国赛真题1、题目描写叙述nowcoder在家极度无聊。

于是找了张纸開始统计素数的个数。

设函数f(n)返回从1-n之间素数的个数。

nowcoder 发现：f(1) = 0f(10) = 4f(100) = 25…满足g(m) = 17 * m^2 / 3 - 22 * m / 3 + 5 / 3当中m为n的位数。

他非常激动，是不是自己发现了素数分布的规律了！请你设计一个程序，求出f(n)。

来验证nowcoder是不是正确的，或许还能够得诺贝尔奖呢。

输入描写叙述：输入包括多组数据。

每组数据仅有一个整数n (1≤n≤10000000)。

输出描写叙述：对于每组数据输入，输出一行。

为1->n(包括n)之间的素数的个数。

输入样例：110651000输出样例：0418252、时间限制：1秒空间限制：32768K通过比例：13.93%最佳记录：0 ms|8460K题目描写叙述有一位阿拉伯老人，生前养有11匹马。

他去世前立下遗嘱：大儿子、二儿子、小儿子分别继承遗产的1/2、1/4、1/6。

儿子们想来想去没法分：他们所得到的都不是整数，即分别为11/2、11/4、11/6，总不能把一匹马割成几块来分吧？聪明的邻居牵来了自己的一匹马，对他们说：“你们看，如今有12匹马了，老大得12匹的1/2就是6匹，老二得12匹的1/4就是3匹，老三得12匹的1/6就是2匹。

还剩一匹我照旧牵回家去。

”这样把难分的问题攻克了。

如今又有一个老人要分遗产了，他有m 匹马(1≤m≤1000000)，而且有n个儿子(1≤n≤10)。

每一个儿子分别得到1/a1、1/a2、…、1/an的遗产。

由于马不能切割。

而且遗产要所有分完，所以请你用上面那位聪明的邻居的方法计算一下每一个儿子能分到几匹马。

输入描写叙述：输入包括多组測试数据。

每组測试数据包括两行：第一行为m、n。

分别代表老人拥有的马匹数和几个儿子。

第二行有n个数据a1、a2、…、an。