程序设计训练题目.docx

1、-FIRST-（一）汽水瓶题目描述小明非常喜欢喝汽水，家门口的超市今天搞活动，2 个汽水空瓶或者 4 个瓶盖可以换 1 瓶汽水，小明现在已经买了 n 瓶汽水，请问通过这个活动可以多得到多少瓶汽水？输入每行输入一个整数 n(0n10 8 ) ,如果 n=0 ，表示输入结束，这个样例不需要处理。输出每行输出一个结果。样例输入150样例输出010（二）局域网题目描述IPv4 的地址是一个 32 位无符号整数，一般使用四段式表示，比如 192.168.0.1，每一段表示一个字节的值。子网掩码也是一个 32 位无符号整数，也可以使用四段式表示，比如 255.255.255.0。 IP 地址与子网掩码的按

2、位与的结果得到子网的网络地址,两台主机必须在同一个子网才能通信。比如，主机 A 的 IP 是192.168.0.1，子网掩码是 255.255.255.0；主机 B 的 IP 是 192.168.0.2，子网掩码是 255.255.255.0。所以，这两个主机的子网地址都是 192.168.0.0，它们是可以通信的。现在给你两个主机的 IP 地址与子网掩码，请判断一下它们是否属于同一个子网？输入第一行是一个整数 K(1K10000) ，表示样例的个数。 每个样例占两行，每行一个主机的 IP 地址与子网掩码，使用四段式表示，数据保证输入的 IP 地址与子网掩码合法。输出依次输出每个样例的结果，如

3、果在同一个子网，输出“Yes”，否则输出“No”。样例输入2 192.168.0.1 255.255.255.0 192.168.0.2 255.255.255.0 192.168.0.1 255.255.255.0 192.168.1.2 255.255.255.0样例输出Yes No（三）最长回文子序列题目描述给一个字符串，任取若干个字符，按照其在字符串中的相对顺序，组成的序列，我们称其为子序列。如果这个子序列是回文的，我们称其为回文子序列。求一个字符串最长回文子序列的长度。输入存在多个样例（样例数量不超过 100），每行一个字符串，字符串只包含英文小写字母，长度不超过1000。输出每行输

4、出一个样例的结果。样例输入abcdaabbabababcba样例输出1235（四）置换给一个置换 P(x )，P n (x )=x ，求最小的 n。比如置换 P=(12 23 34 41 ) , P(x 1 ,x 2 ,x 3 ,x 4 )P 2 (x 1 ,x 2 ,x 3 ,x 4 )P 3 (x 1 ,x 2 ,x 3 ,x 4 )P 4 (x 1 ,x 2 ,x 3 ,x 4 ) = (x 4 ,x 1 ,x 2,x 3 )(x 3 ,x 4 ,x 1 ,x 2 )(x 2 ,x 3 ,x 4 ,x 1 )(x 1 ,x 2 ,x 3 ,x 4 ) 所以 n=4 。输入第一行是一个整数

5、 K(1K1000) ，表示样例的个数。每个样例占一行，第一个整数是 n(1n100) ，以后的 n 个整数 x i ,1x i n 且 x i 是唯一的, (1x 1 2x 2 nx n ) 表示一个置换。输出输出一个样例的结果。样例输入33 1 2 33 2 1 33 2 3 1样例输出123（五）20482048 是大家非常喜欢的一款小游戏，给定一个 2048 的局面，和下一步的指令，请计算出变化后的局面。2048 的游戏规则如下： 游戏是一个 44 的格子 玩家可以使用上、下、左、右控制数字方格滑动， 每滑动一次，所有的数字方块都会往滑动的方向靠拢，相同数字的方块在靠拢、相撞时会相加。

6、 不断的叠加最终拼凑出 2048 这个数字就算成功 每次滑动后，会在某个空白格子中出现随机的 2 或者 4，如果不存在空白格子，则游戏结束。输入第一行是一个整数 K，表示样例的个数。每个样例的前 4 行，每行 4 个整数，如果整数为 0 表示空白格子，其他为数字。每个样例的第 5 行，是指令，指令为“LEFT“,“DOWN“,“RIGHT“,“UP“,依次表示滑动的方向。输出输出每个样例的结果,每个样例后输出一个空行。样例输入32 2 0 02 0 2 02 0 0 20 0 2 2LEFT2 0 2 02 2 2 20 2 0 24 2 2 0LEFT2 4 2 20 2 2 00 4 4

7、40 0 0 2LEFT样例输出4 0 0 04 0 0 04 0 0 04 0 0 04 0 0 04 4 0 04 0 0 04 4 0 02 4 4 04 0 0 08 4 0 02 0 0 0-SECOND-（一）矩阵题目描述编写一个程序，将 1 n 2 按行依次填入 nn 的矩阵，执行若干条行或者列的循环移动的指令，再将数字按行依次取出。指令如下：指令 含义L x y x 行循环左移 y 次R x yx 行循环右移 y 次U x yx 列循环上移 y 次D x yx 列循环下移 y 次输入第一行是一个整数 K，表示样例的个数。 每个样例的第一行是两个整数 n(1n10) 和m(1m1

8、000) ，分别表示矩阵的大小和指令的条数。以后的 m 行是 m 条指令，矩阵的行列按 1 开始计数，指令满足 1xn,1yn1 。输出每行输出一个样例的结果，数字之间用一个空格隔开，行末无空格。样例输入43 1L 1 13 1R 1 13 1U 1 13 1D 1 1样例输出2 3 1 4 5 6 7 8 93 1 2 4 5 6 7 8 94 2 3 7 5 6 1 8 97 2 3 1 5 6 4 8 9（二）0 和 1题目描述一个 01 字符串，长度是 n，其中 1 比 0 多 m 个，请问不同的排列方案数有多少个？输入第一行是一个整数 K，表示样例的个数。 以后每行两个整数 n 和

9、m，1n33,0m n 。输出每行输出一个样例的结果。样例输入42 02 13 03 1样例输出2003线索第一个样例为“01“和“10“；第二、三个样例不存在这样的串；第四个样例为 “011“,“101“,“110“（三）子串题目描述求一个字符串长度为 n 的子串中出现次数最多的字典序最小的子串，及其出现次数。 比如字符串为“aaabbb“，子串长度为 2 时，子串为“aa“,“ab“,“bb“,分别出现2,1,2 次。 由于“aa“的字典序比“bb“要小，所以答案为 “aa“,出现次数为 2。输入存在多个字符串（个数不超过 100）， 每行输入一个字符串和一个整数，字符串只含小写英文字母，

10、长度不超过 2000。 整数表示子串的长度，值不超过 10。输出每行输出一个样例的结果，先输出答案子串，再输出出现次数，中间用一个空格隔开。样例输入aabb 2aaabbb 2aaaaaa 3样例输出aa 1aa 2aaa 4（四）素因子的种类题目描述给一个整数 n，求其素因子一共有多少种？比如 30，素因子为 2,3,5，所以素因子的种类为 3；比如 8，素因子为 2，所以种类数为 1。输入第一行是一个整数 k(1k10000) 。 以后每行一个整数 n(2n10 12 ) 输出每行输出一个样例的结果样例输入4269999999999891000000000000样例输出1212（五）考试安

11、排题目描述Eric 每次考试最头痛的就是安排考试时间，需要找合适的空闲时间安排考试真的是件很费神的事情。Eric 希望你能帮他算一下能哪些时间可以考试，当然 Eric 并不想周末进行考试，所以你只需要计算周 1 到周 5 的时间就可以了。 我们假设每天有 11 节课的时间，上午 1 到 4 节，下午 5-8节，晚上 9-11 节。Eric 已经拿到了参加考试的班级的课表，以及考试需要的时长。注意：考试只能安排在上午、下午、晚上时段，不能跨区间。输入第一行是一个整数 K(1K100) ，表示样例的个数每个样例的第一行是两个整数 N(1N100),T(2T4) ，分别表示这些班级课表的条目数和考试

12、所需的课程节数。为了简化问题，Eric 只留下了课表条目的上课时间。以后的 N 行，每行一个课程的时间，为三个值，D(DMon,Tue,Wen,Thur,Fri ,Sat,Sun),S,E(1SE11) ，分别表示上课时间为星期 D 的第 S 节到第 E 节。输出每个样例先输出一行，为每个样例合适考试的不同时间段的个数。 然后按时间先后顺序，每行输出一个时间段，分别为 S,D,E ，中间用一个空格隔开。样例输入110 3Mon 1 2Tue 1 2Wen 1 2Thur 1 2Fri 1 2Mon 5 6Tue 5 6Wen 5 6Thur 5 6Fri 5 6样例输出5Mon 9 11Tue

13、 9 11Wen 9 11Thur 9 11Fri 9 11（六）Beautiful Number题目描述如果一个数的二进制中只有 1 个 0，那么我们称这样的数是“ 美丽数”，比如 5 10 =101 2 。 现在给你一个区间a,b(1 ab10 18 ) ，求区间内有多少个 “美丽数”。输入第一行是一个整数 K，表示样例的个数。 每个样例是两个整数 a 和 b。输出每行输出一个样例的结果。样例输入31 22 51 1000000000000000000样例输出121712提示第一个例子中，只有 2 是美丽数； 第二个例子中，2 和 5 是美丽数；-THIRD-（一）Robot题目描述机器人

14、一开始站在原点，可以上下左右（分别用“UDLR”表示）移动，每次移动一步。Estrella想知道对于某个指令序列，如果把某一种指令全部替换成另一种指令，新的指令序列可以让机器人回到原点。输入存在多个样例，每个样例一行，为一条指令序列，长度不超过 200。输出每行输出一个样例的结果，可以输出“Yes”，否则输出“No” 。样例输入LDLLDDD样例输出YesNo（二）染色题目描述Alice 在玩一个游戏，她在一个 mn 的格子里，随机涂黑 k 个格子。然后她每次可以把一行或者一列的格子染成红色，但是这一行中不能有黑色的格子。请问她最多能把多少个格子涂成红色？输入第一行是一个整数 T(T100) ，表示样例的个数。每个样例的第一行是 m(1m100),