程序设计训练题目

----------------------------------------------FIRST------------------------------------------------- （一）汽水瓶

题目描述

小明非常喜欢喝汽水，家门口的超市今天搞活动，2个汽水空瓶或者4个瓶盖可以换1瓶汽水，小明现在已经买了n瓶汽水，请问通过这个活动可以多得到多少瓶汽水？ 输入

每行输入一个整数n(0≤n≤10 8 ) ,如果n=0 ，表示输入结束，这个样例不需要处理。 输出

每行输出一个结果。 样例输入 1 5 0 样例输出 0 10

（二）局域网

题目描述

IPv4的地址是一个32位无符号整数，一般使用四段式表示，比如192.168.0.1，每一段表示一个字节的值。子网掩码也是一个32位无符号整数，也可以使用四段式表示，比如255.255.255.0。 IP地址与子网掩码的按位与的结果得到子网的网络地址,两台主机必须在同一个子网才能通信。比如，主机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(1≤K≤10000) ，表示样例的个数。每个样例占两行，每行一个主机的IP地址与子网掩码，使用四段式表示，数据保证输入的IP地址与子网掩码合法。

输出

依次输出每个样例的结果，如果在同一个子网，输出“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。 输出

每行输出一个样例的结果。 样例输入 abcd aabb abab abcba 样例输出 1 2 3 5

（四）置换

给一个置换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 。 输入

第一行是一个整数K(1≤K≤1000) ，表示样例的个数。

每个样例占一行，第一个整数是n(1≤n≤100) ，以后的n 个整数x i ,1≤x i ≤n 且 x i 是唯一的, (1x 1 2x 2 ?? nx n ) 表示一个置换。 输出

输出一个样例的结果。 样例输入 3 3 1 2 3 3 2 1 3 3 2 3 1 样例输出 1 2 3

（五）2048

2048是大家非常喜欢的一款小游戏，给定一个2048的局面，和下一步的指令，请计算出变化后的局面。 2048的游戏规则如下：

? ? ? ? ?

游戏是一个4×4 的格子

玩家可以使用上、下、左、右控制数字方格滑动，

每滑动一次，所有的数字方块都会往滑动的方向靠拢，相同数字的方块在靠拢、相撞时会相加。 不断的叠加最终拼凑出2048这个数字就算成功

每次滑动后，会在某个空白格子中出现随机的2或者4，如果不存在空白格子，则游戏结束。

输入

第一行是一个整数K，表示样例的个数。每个样例的前4行，每行4个整数，如果整数为0表示空白格子，其他为数字。每个样例的第5行，是指令，指令为\依次表示滑动的方向。

输出

输出每个样例的结果,每个样例后输出一个空行。

样例输入 3 2 2 0 0 2 0 2 0 2 0 0 2 0 0 2 2 LEFT 2 0 2 0 2 2 2 2 0 2 0 2 4 2 2 0 LEFT 2 4 2 2 0 2 2 0 0 4 4 4 0 0 0 2 LEFT 样例输出 4 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0 4 4 0 0 4 0 0 0 4 4 0 0 2 4 4 0 4 0 0 0 8 4 0 0 2 0 0 0

----------------------------------------------SECOND--------------------------------------------- （一）矩阵

题目描述

编写一个程序，将1 ~ n 2 按行依次填入n×n 的矩阵，执行若干条行或者列的循环移动的指令，再将数字按行依次取出。 指令如下：

指令 含义

L x y x行循环左移y次 R x y x行循环右移y次 U x y x列循环上移y次 D x y x列循环下移y次

输入

第一行是一个整数K，表示样例的个数。每个样例的第一行是两个整数n(1≤n≤10) 和

m(1≤m≤1000) ，分别表示矩阵的大小和指令的条数。

以后的m行是m条指令，矩阵的行列按1开始计数，指令满足1≤x≤n,1≤y≤n?1 。

输出

每行输出一个样例的结果，数字之间用一个空格隔开，行末无空格。

样例输入 4 3 1 L 1 1 3 1 R 1 1 3 1 U 1 1 3 1 D 1 1 样例输出

2 3 1 4 5 6 7 8 9

3 1 2 4 5 6 7 8 9 4 2 3 7 5 6 1 8 9 7 2 3 1 5 6 4 8 9

（二）0和1

题目描述

一个01字符串，长度是n，其中1比0多m个，请问不同的排列方案数有多少个？

输入

第一行是一个整数K，表示样例的个数。以后每行两个整数n和m，1≤n≤33,0≤m≤n 。

输出

每行输出一个样例的结果。

样例输入 4 2 0 2 1 3 0 3 1 样例输出 2 0 0 3 线索

第一个样例为\和\；第二、三个样例不存在这样的串；第四个样例为\

（三）子串

题目描述

求一个字符串长度为n的子串中出现次数最多的字典序最小的子串，及其出现次数。比如字符串为\，子串长度为2时，子串为{\分别出现{2,1,2}次。由于\的字典序比\要小，所以答案为\出现次数为2。

输入

存在多个字符串（个数不超过100），每行输入一个字符串和一个整数，字符串只含小写英文字母，长度不超过2000。整数表示子串的长度，值不超过10。

输出

每行输出一个样例的结果，先输出答案子串，再输出出现次数，中间用一个空格隔开。

样例输入 aabb 2 aaabbb 2 aaaaaa 3 样例输出 aa 1 aa 2 aaa 4

（四）素因子的种类

题目描述

给一个整数n，求其素因子一共有多少种？比如30，素因子为2,3,5，所以素因子的种类为3；比如8，素因子为2，所以种类数为1。

输入

第一行是一个整数k(1≤k≤10000) 。以后每行一个整数n(2≤n≤10 12 )

输出

每行输出一个样例的结果

样例输入 4 2 6

999999999989 1000000000000 样例输出 1

2 1 2

（五）考试安排

题目描述

Eric每次考试最头痛的就是安排考试时间，需要找合适的空闲时间安排考试真的是件很费神的事情。

Eric希望你能帮他算一下能哪些时间可以考试，当然Eric并不想周末进行考试，所以你只需要计算周1到周5的时间就可以了。我们假设每天有11节课的时间，上午1到4节，下午5-8节，晚上9-11节。Eric已经拿到了参加考试的班级的课表，以及考试需要的时长。注意：考试只能安排在上午、下午、晚上时段，不能跨区间。

输入

第一行是一个整数K(1≤K≤100) ，表示样例的个数

每个样例的第一行是两个整数N(1≤N≤100),T(2≤T≤4) ，分别表示这些班级课表的条目数和考试所需的课程节数。为了简化问题，Eric只留下了课表条目的上课时间。 以后的N行，每行一个课程的时间，为三个值，D(D∈

{Mon,Tue,Wen,Thur,Fri,Sat,Sun}),S,E(1≤S≤E≤11) ，分别表示上课时间为星期D 的第S 节到第E 节。

输出

每个样例先输出一行，为每个样例合适考试的不同时间段的个数。然后按时间先后顺序，每行输出一个时间段，分别为S,D,E ，中间用一个空格隔开。

样例输入 1 10 3 Mon 1 2 Tue 1 2 Wen 1 2 Thur 1 2 Fri 1 2 Mon 5 6 Tue 5 6 Wen 5 6 Thur 5 6 Fri 5 6 样例输出

5 Mon 9 11 Tue 9 11 Wen 9 11 Thur 9 11 Fri 9 11

（六）Beautiful Number

题目描述

如果一个数的二进制中只有1个0，那么我们称这样的数是“美丽数”，比如5 10 =101 2 。现在给你一个区间[a,b](1≤a≤b≤10 18 ) ，求区间内有多少个“美丽数”。

输入

第一行是一个整数K，表示样例的个数。每个样例是两个整数a和b。

输出

每行输出一个样例的结果。

样例输入 3 1 2 2 5

1 1000000000000000000 样例输出 1 2 1712 提示

第一个例子中，只有2是美丽数； 第二个例子中，2和5是美丽数；

----------------------------------------------THIRD------------------------------------------------

（一）Robot

题目描述

机器人一开始站在原点，可以上下左右（分别用“UDLR”表示）移动，每次移动一步。Estrella想知道对于某个指令序列，如果把某一种指令全部替换成另一种指令，新的指令序列可以让机器人回到原点。

输入

存在多个样例，每个样例一行，为一条指令序列，长度不超过200。

输出

每行输出一个样例的结果，可以输出“Yes”，否则输出“No”。

样例输入 LD LLDDD 样例输出 Yes No

（二）染色

题目描述

Alice在玩一个游戏，她在一个m×n 的格子里，随机涂黑k 个格子。然后她每次可以把一行或者一列的格子染成红色，但是这一行中不能有黑色的格子。请问她最多能把多少个格子涂成红色？

输入

第一行是一个整数T(T≤100) ，表示样例的个数。每个样例的第一行是

m(1≤m≤100),n(1≤n≤100),k(0≤k≤m×n) 。以后的k 行,每行两个整数x(1≤x≤m),y(1≤y≤n) ，表示(x,y) 为黑色格子。

输出

每行输出一个样例的结果。

样例输入

1 3 4 2 1 1 3 3 样例输出 8

（三）矩阵

题目描述

我们把1～N 2 按下面矩阵的规律进行排列：

145161736? 236151835 987141934 101112132033 252423222132 262728293031

请求第一列的累加和。

输入

每行一个整数N(1≤N≤10 9 ) ，如果N=0 表示输入结束，这个样例不需要处理。

输出

每行输出一个样例的结果，因为这个值可能很大，请将其对1,000,000,007 取模。

样例输入 1 2 3

1000000000 0 样例输出 1 5 10 499999881

（四）集合

题目描述

对于包含整数多值集合A={a 1 ,a 2 ,?,a n } ，执行以下两步操作

1. 将某些元素加上整数x 2. 将某些元素减掉整数y 请问能否使得A 的元素全部相等？

输入

第一行是一个整数K(1≤K≤100) ，表示样例的个数。 每个样例的第一行是一个整数n(1≤n≤100,000) 。 第二行是{a i |i=1,2,?n},0≤a i ≤1,000,000,000 。

输出

每行输出一个样例的结果，如果可以使得元素全部相等输出\否则输出\

样例输入 2 5

2 1 2 1 3 5

1 2 3 4 5 样例输出 Yes No

（五）Colombian Number

题目描述

对于正整数n ,不存在整数k ,使得n 等于k 加上k 的数码累加和，我们称这样的数是哥伦比亚数或者自我数。

比如 11就不是一个哥伦比亚数，因为10加上10的数码累加和1等于11;而20则是一个哥伦比亚数。

输入

第一行是一个整数K(K≤10,000) ，表示样例的个数。 以后每行一个正整数n(1≤n≤1,000,000,000)

输出

每行输出一个样例的结果，如果是哥伦比亚数输出\否则输出\。

样例输入 5 1 2 3 20 21 样例输出 Yes No Yes Yes No

（六）Bonus

题目描述

要过年了，老板准备发年终奖，老板准备根据员工的平时表现对比发放奖金，最低发888，每档再增加1000块。

由于工作表现记录有点问题，可能存在矛盾的描述，所以，如果无法发放的话，则所有人，每人发888元。

老板把这个任务交给你，希望你帮他算出一共需要给多少奖金，每人需要发多少奖金？

输入

第一行是一个整数K，表示样例的个数。每个样例的第一行是两个整数n(1≤n≤10000) 和

m(0≤m≤50000) ，分别表示员工的人数以及工作表现记录的数目，员工的编号从1 到n 。

以后的m 行为两个整数a和b(1≤a≠b≤n) ，表示员工a的工作表现比b好。 输入数据保证工作表现不会有重复记录。

输出

每个样例先输出一行为奖金总数，然后再输出一行，按员工号的顺序，输出每个员工的奖金数，中间用一个空格隔开。

样例输入 2 3 2 1 2 2 3 3 2 1 2 2 1 样例输出 5664

2888 1888 888 2664 888 888 888

巨大的输入输出，请使用C风格的输入输出。

本文来源：https://www.bwwdw.com/article/a0gr.html