2013腾讯编程马拉松初赛(3月22)赛题
- 格式:doc
- 大小:47.53 KB
- 文档页数:7
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.知道变量的意义,能够根据输入和代码推算出输出,能够运用变量实现诸如记分、计时、传递消息等功能。
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:ss
HH:MM:SS表示当前的时间,hh:mm:ss表示希望倒退回去的时间。
[Technical Specification]
00<=HH<=11
00<=hh<=99
00<=MM, SS, mm, ss<=59
Output
请计算并输出钟表倒退后显示的时间,要求输出格式为HH:MM:SS(即时分秒均显示2位,不足则补0),每组数据输出占一行。
Sample Input
2
11:28:32 02:14:21 05:00:00 96:00:01
Sample Output
09:14:11
04:59:59
1002 小明系列故事——女友的考验
Time Limit: 0.2 Seconds Memory Limit: 32768K
终于放寒假了,小明要和女朋友一起去看电影。
这天,女朋友想给小明一个考验,在小明正准备出发的时候,女朋友告诉他,她在电影院等他,小明过来的路线必须满足给定的规则:
1、假设小明在的位置是1号点,女朋友在的位置是n号点,则他们之间有n-2个点可以走,小明每次走的时候只能走到比当前所在点编号大的位置;
2、小明来的时候不能按一定的顺序经过某些地方。
比如,如果女朋友告诉小明不能经过1 -> 2 -> 3,那么就要求小明来的时候走过的路径不能包含有1 -> 2 -> 3这部分,但是1 -> 3 或者1 -> 2都是可以的,这样的限制路径可能有多条。
这让小明非常头痛,现在他把问题交给了你。
特别说明,如果1 2 3这三个点共线,但是小明是直接从1到3然后再从3继续,那么此种情况是不认为小明经过了2这个点的。
现在,小明即想走最短的路尽快见到女朋友,又不想打破女朋友的规定,你能帮助小明解决这个问题吗?
Input
输入包含多组样例,每组样例首先包含两个整数n和m,其中n代表有n个点,小明在1号点,女朋友在n号点,m代表小明的女朋友有m个要求;
接下来n行每行输入2个整数x 和y(x和y均在int范围),代表这n个点的位置(点的编号从1到n);
再接着是m个要求,每个要求2行,首先一行是一个k,表示这个要求和k个点有关,然后是顺序给出的k个点编号,代表小明不能走k1 -> k2 -> k3 ……-> ki这个顺序的路径;
n 和 m等于0的时候输入结束。
[Technical Specification]
2 <= n <= 50
1 <= m <= 100
2 <= k <= 5
Output
对于每个样例,如果存在满足要求的最短路径,请输出这个最短路径,结果保留两位小数;否则,请输出”Can not be reached!”(引号不用输出)。
Sample Input
3 1
1 1
2 1
3 1
2
1 2
2 1
0 0
1 1
2
1 2
5 3
0 0
5 3
1 2
1 22
5 21
3
1 2 3
2
4 5
2
1 5
0 0
Sample Output
2.00
Can not be reached!
21.65
Time Limit: 1.0 Seconds Memory Limit: 65536K
吉哥这几天对队形比较感兴趣。
有一天,有n个人按顺序站在他的面前,他们的身高分别是h[1], h[2] ... h[n],吉哥希望从中挑出一些人,让这些人形成一个新的队形,新的队形若满足以下三点要求,则称之为完美队形:
1、挑出的人保持他们在原队形的相对顺序不变;
2、左右对称,假设有m个人形成新的队形,则第1个人和第m个人身高相同,第2
个人和第m-1个人身高相同,依此类推,当然,如果m是奇数,中间那个人可以任意;
3、从左到中间那个人,身高需保证递增,如果用H表示新队形的高度,则H[1] < H[2]
< H[3] .... < H[mid]。
现在吉哥想知道:最多能选出多少人组成完美队形?
Input
第一行输入T,表示总共有T组数据(T <= 20);
每组数据先输入原先队形的人数n(1<=n <= 200),接下来一行输入n个整数,表示按顺序从左到右原先队形位置站的人的身高(50 <= h <= 250,不排除特别矮小和高大的)。
Output
请输出能组成完美队形的最多人数,每组数据输出占一行。
Sample Input
2
3
1 2 1
4
1 2 2 1
Sample Output
3
4
Time Limit: 1.0 Seconds Memory Limit: 65536K
吉哥又想出了一个新的完美队形游戏!
假设有n个人按顺序站在他的面前,他们的身高分别是h[1], h[2] ... h[n],吉哥希望从中挑出一些人,让这些人形成一个新的队形,新的队形若满足以下三点要求,则就是新的完美队形:
1、挑出的人保持原队形的相对顺序不变,且必须都是在原队形中连续的;
2、左右对称,假设有m个人形成新的队形,则第1个人和第m个人身高相同,第2个人和第m-1个人身高相同,依此类推,当然如果m是奇数,中间那个人可以任意;
3、从左到中间那个人,身高需保证不下降,如果用H表示新队形的高度,则H[1] <= H[2] <= H[3] .... <= H[mid]。
现在吉哥想知道:最多能选出多少人组成新的完美队形呢?
Input
输入数据第一行包含一个整数T,表示总共有T组测试数据(T <= 20);
每组数据首先是一个整数n(1 <= n <= 100000),表示原先队形的人数,接下来一行输入n个整数,表示原队形从左到右站的人的身高(50 <= h <= 250,不排除特别矮小和高大的)。
Output
请输出能组成完美队形的最多人数,每组输出占一行。
Sample Input
2
3
1 2 1
4
1 2 2 1
Sample Output
3
4
1005 湫湫系列故事——设计风景线
Time Limit: 3 Seconds Memory Limit: 65536K
随着杭州西湖的知名度的进一步提升,园林规划专家湫湫希望设计出一条新的经典观光线路,根据老板马小腾的指示,新的风景线最好能建成环形,如果没有条件建成环形,那就建的越长越好。
现在已经勘探确定了n个位置可以用来建设,在它们之间也勘探确定了m条可以设计的路线以及他们的长度。
请问是否能够建成环形的风景线?如果不能,风景线最长能够达到多少?
其中,可以兴建的路线均是双向的,他们之间的长度均大于0。
Input
测试数据有多组,每组测试数据的第一行有两个数字n, m,其含义参见题目描述;
接下去m行,每行3个数字u v w,分别代表这条线路的起点,终点和长度。
[Technical Specification]
1. n<=100000
2. m <= 1000000
3. 1<= u, v <= n
4. w <= 1000
Output
对于每组测试数据,如果能够建成环形(并不需要连接上去全部的风景点),那么输出YES,否则输出最长的长度,每组数据输出一行。
Sample Input
3 3
1 2 1
2 3 1
3 1 1
Sample Output
YES。