百练-2018年北京大学软件工程学科夏令营上机练习 (待续)

本文共4009个字,预计阅读时间需要11分钟。

作为一个编程菜鸡,先刷刷前几题,八道题目争取6题有思路,5题能写出来,3题能AC(大佬勿嘲笑)。由于部分题目已经关闭,无法看到是否AC(以下代码可能无法通过全部测试用例),如有错误,请指出,O(∩_∩)O谢谢。

地址:

http://bailian.openjudge.cn/ssxly2018lx/

A:判决素数个数

全局题号2178 提交次数95 尝试人数32 通过人数28

总时间限制:
1000ms
内存限制:
65536kB
描述
输入两个整数X和Y,输出两者之间的素数个数(包括X和Y)。
输入
两个整数X和Y(1 <= X,Y <= 105)。
输出
输出一个整数,表示X,Y之间的素数个数(包括X和Y)。
样例输入
样例输出

C++代码


B:编码字符串

全局题号12556 提交次数56 尝试人数32 通过人数32

总时间限制:
1000ms
内存限制:
65536kB
描述
在数据压缩中,一个常用的方法是行程长度编码压缩。对于一个待压缩的字符串,我们可以依次记录每个字符及重复的次数。例如,待压缩的字符串为”aaabbbbcbb”,压缩结果为(a,3)(b,4)(c,1)(b,2)。这种压缩对于相邻数据重复较多的情况有效,如果重复状况较少,则压缩的效率较低。

现要求根据输入的字符串,首先将字符串中所有大写字母转化为小写字母,然后将字符串进行压缩。

输入
一个字符串,长度大于0,且不超过1000,全部由大写或小写字母组成。
输出
输出为编码之后的字符串,形式为:(a,3)(b,4)(c,1)(d,2),即每对括号内分别为小写字符及重复的次数,不含任何空格。
样例输入

样例输出

C++实现


C:岛屿周长

全局题号12558 提交次数38 尝试人数28 通过人数28

总时间限制:
1000ms
内存限制:
65536kB
描述
用一个n*m的二维数组表示地图,1表示陆地,0代表海水,每一格都表示一个1*1的区域。地图中的格子只能横向或者纵向连接(不能对角连接),连接在一起的陆地称作岛屿,同时整个地图都被海水围绕。假设给出的地图中只会有一个岛屿,并且岛屿中不会有湖(即不会有水被陆地包围的情况出现)。请判断所给定的二维地图中岛屿的周长。
输入
第一行为n和m,表示地图的大小(1<=n<=100, 1<=m<=100)。接下来n行,每行有m个数,分别描述每一格的数值。数值之间均用空格隔开。
输出
只有一行,即岛屿的周长(正整数)。
样例输入
样例输出

C++实现


D:Safecracker

全局题号250 提交次数35 尝试人数17 通过人数13

总时间限制:
1000ms
内存限制:
65536kB
描述
“The item is locked in a Klein safe behind a painting in the second-floor library. Klein safes are extremely rare; most of them, along with Klein and his factory, were destroyed in World War II. Fortunately old Brumbaugh from research knew Klein’s secrets and wrote them down before he died. A Klein safe has two distinguishing features: a combination lock that uses letters instead of numbers, and an engraved quotation on the door. A Klein quotation always contains between five and twelve distinct uppercase letters, usually at the beginning of sentences, and mentions one or more numbers. Five of the uppercase letters form the combination that opens the safe. By combining the digits from all the numbers in the appropriate way you get a numeric target. (The details of constructing the target number are classified.) To find the combination you must select five letters v, w, x, y, and z that satisfy the following equation, where each letter is replaced by its ordinal position in the alphabet (A=1, B=2, …, Z=26). The combination is then vwxyz. If there is more than one solution then the combination is the one that is lexicographically greatest, i.e., the one that would appear last in a dictionary.”

v – w2+ x3– y4+ z5= target

“For example, given target 1 and letter set ABCDEFGHIJKL, one possible solution is FIECB, since 6 – 92+ 53– 34+ 25= 1. There are actually several solutions in this case, and the combination turns out to be LKEBA. Klein thought it was safe to encode the combination within the engraving, because it could take months of effort to try all the possibilities even if you knew the secret. But of course computers didn’t exist then.”

“Develop a program to find Klein combinations in preparation for field deployment. Use standard test methodology as per departmental regulations.

输入
Input consists of one or more lines containing a positive integer target less than twelve million, a space, then at least five and at most twelve distinct uppercase letters. The last line will contain a target of zero and the letters END; this signals the end of the input.
输出
For each line output the unique Klein combination, or ‘no solution’ if there is no correct combination. Use the exact format shown below.”
样例输入