5-14 掉入陷阱的数字 (25分)

发表于 模拟 分类,标签:
 对任意一个自然数N_0N0,先将其各位数字相加求和,再将其和乘以3后加上1,变成一个新自然数N_1N1;然后对N_1N1重复这种操作,可以产生新自然数N_2N2;……多次重复这种操作,运算结果最终会得到一个固定不变的数N_kNk,就像掉入一个数字“陷阱”。本题要求对输入的自然数,给出其掉入“陷阱”的过程。输入格式:在一行内给出一个自然数N_0N0(N_0<N0<30000)。输出格式:对于输入的N_0N0,逐行输出其掉入陷阱的步骤。第ii行描述NN掉入陷阱的第ii步,格式为: ii:N_iNi (i\ge1i≥1)。当某一步得到的自然数结果N_kNk(k\ge1k≥1)与上一步N_{k-1}Nk−1相同时,停止输出。输入样例:5输出样例:1:162:223:134:13代码:#include <bits/stdc+...

5-18 最大子列和问题 (25分)

发表于 模拟 分类,标签:
 给定KK个整数组成的序列{ N_1N1, N_2N2,..., N_KNK },“连续子列”被定义为{ N_iNi, N_{i+1}Ni+1,..., N_jNj },其中 1\lei\lej\leK1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{-2,11,-4,13,-5,-2},其连续子列{11,-4,13}有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下:数据1:与样例等价,测试基本正确性;数据2:102个随机整数;数据3:103个随机整数;数据4:104个随机整数;数据5:105个随机整数;输入格式:输入第1行给出正整数K...

5-9 英文单词排序 (25分)

发表于 排序 分类,标签:
 本题要求编写程序,输入若干英文单词,对这些单词按长度从小到大排序后输出。如果长度相同,按照输入的顺序不变。输入格式:输入为若干英文单词,每行一个,以#作为输入结束标志。其中英文单词总数不超过20个,英文单词为长度小于10的仅由小写英文字母组成的字符串。输出格式:输出为排序后的结果,每个单词后面都额外输出一个空格。输入样例:blueredyellowgreenpurple#输出样例:red blue green yellow purple代码:#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define eps 1e-4/*hhtc14...

5-17 宿舍谁最高? (25分)

发表于 模拟 分类,标签:
 学校选拔篮球队员,每间宿舍最多有4个人。现给出宿舍列表,请找出每个宿舍最高的同学。定义一个学生类Student,有身高height,体重weight等。输入格式:首先输入一个整型数n(1<=n<=1000000),表示n位同学。紧跟着n行输入,每一行格式为:宿舍号,name,height,weight。宿舍号的区间为[0,999999],name由字母组成,长度小于16,height,weight为正整数。输出格式:按宿舍号从小到大排序,输出每间宿舍身高最高的同学信息。题目保证每间宿舍只有一位身高最高的同学。输入样例:7000000 Tom 175 120 000001 Jack 180 130000001 Hale 160 140000000&...

5-21 二分法求多项式单根 (20分)

发表于 搜索 分类,标签:
 二分法求函数根的原理为:如果连续函数f(x)f(x)在区间[a,b][a,b]的两个端点取值异号,即f(a)f(b)<0f(a)f(b)<0,则它在这个区间内至少存在1个根rr,即f(r)=0f(r)=0。二分法的步骤为:检查区间长度,如果小于给定阈值,则停止,输出区间中点(a+b)/2(a+b)/2;否则如果f(a)f(b)<0f(a)f(b)<0,则计算中点的值f((a+b)/2)f((a+b)/2);如果f((a+b)/2)f((a+b)/2)正好为0,则(a+b)/2(a+b)/2就是要求的根;否则如果f((a+b)/2)f((a+b)/2)与f(a)f(a)同号,则说明根在区间[(a+b)/2,b][(a+b)/2,b],令a=(a+b)/2a=(a+b)/2,重复循环;如果f((a+b)/2)f((a+b)/2)与f(b)f(b)同号,则...

5-3 猴子选大王 (20分)

发表于 模拟 分类,标签:
 一群猴子要选新猴王。新猴王的选择方法是:让N只候选猴子围成一圈,从某位置起顺序编号为1~N号。从第1号开始报数,每轮从1报到3,凡报到3的猴子即退出圈子,接着又从紧邻的下一只猴子开始同样的报数。如此不断循环,最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王?输入格式:输入在一行中给一个正整数N(\le≤1000)。输出格式:在一行中输出当选猴王的编号。代码:#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define eps 1e-6/*hhtc1406405047*/int main(){    int ...

5-8 树的同构 (25分)

发表于 分类,标签:
 给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。  图1图2现给定两棵树,请你判断它们是否是同构的。 输入格式:输入给出2棵二叉树树的信息。对于每棵树,首先在一行中给出一个非负整数NN (\le10≤10),即该树的结点数(此时假设结点从0到N-1N−1编号);随后NN行,第ii行对应编号第ii个结点,给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。输出格式:如果两棵树是同构的,输出“Yes”,否则输出“No”。输入样例1(对应...

5-15 PAT排名汇总 (25分)

发表于 排序 分类,标签:
 计算机程序设计能力考试(ProgrammingAbilityTest,简称PAT)旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力,科学的评价计算机程序设计人才,为企业选拔人才提供参考标准(网址http://www.patest.cn)。每次考试会在若干个不同的考点同时举行,每个考点用局域网,产生本考点的成绩。考试结束后,各个考点的成绩将即刻汇总成一张总的排名表。现在就请你写一个程序自动归并各个考点的成绩并生成总排名表。输入格式:输入的第一行给出一个正整数N(\le≤100),代表考点总数。随后给出N个考点的成绩,格式为:首先一行给出正整数K(\le≤300),代表该考点的考生总数;随后K行,每行给出1个考生的信息,包括考号(由13位整数字组成)和得分(为[0,100]区间内的整数),中间用空格分隔。输出格式:首先在第一行里输出考生总数。随...

#1015 : KMP算法

发表于 匹配 分类,标签:
 http://hihocoder.com/problemset/problem/1015时间限制:1000ms单点时限:1000ms内存限制:256MB描述小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。这一天,他们遇到了一只河蟹,于是河蟹就向小Hi和小Ho提出了那个经典的问题:“小Hi和小Ho,你们能不能够判断一段文字(原串)里面是不是存在那么一些……特殊……的文字(模式串)?”小Hi和小Ho仔细思考了一下,觉得只能想到很简单的做法,但是又觉得既然河蟹先生这么说了,就肯定不会这么容易的让他们回答了,于是他们只能说道:“抱歉,河蟹先生,我们只能想到时间复杂度为(文本长度*特殊文字总长度)的方法,即对于每个模式串分开判断,然后依次枚举起始位置并检查是否能够匹配,但是这不是您想要的方法是吧?”河蟹点了点头...

#1014 : Trie树

发表于 分类,标签:
 http://hihocoder.com/problemset/problem/1014时间限制:10000ms单点时限:1000ms内存限制:256MB描述小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。这一天,他们遇到了一本词典,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能对于每一个我给出的字符串,都在这个词典里面找到以这个字符串开头的所有单词呢?”身经百战的小Ho答道:“怎么会不能呢!你每给我一个字符串,我就依次遍历词典里的所有单词,检查你给我的字符串是不是这个单词的前缀不就是了?”小Hi笑道:“你啊,还是太年轻了!~假设这本词典里有10万个单词,我询问你一万次,你得要算到哪年哪月去?”小Ho低头算了一算,看着那一堆堆的0,顿时感觉自己这辈子都要花在上面了...小Hi看着小Ho的囧样...