程序设计训练题目.docx

-FIRST-（一）汽水瓶题目描述小明非常喜欢喝汽水，家门口的超市今天搞活动，2个汽水空瓶或者4个瓶盖可以换1瓶汽水，小明现在已经买了n瓶汽水，请问通过这个活动可以多得到多少瓶汽水？输入每行输入一个整数n(0n108) ,如果n=0 ，表示输入结束，这个样例不需要处理。输出每行输出一个结果。样例输入150样例输出010（二）局域网题目描述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(1K10000) ，表示样例的个数。 每个样例占两行，每行一个主机的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。输出每行输出一个样例的结果。样例输入abcdaabbabababcba样例输出1235（四）置换给一个置换P(x)，Pn(x)=x ，求最小的n。比如置换P=(12233441) , P(x1,x2,x3,x4)P2(x1,x2,x3,x4)P3(x1,x2,x3,x4)P4(x1,x2,x3,x4)=(x4,x1,x2,x3)(x3,x4,x1,x2)(x2,x3,x4,x1)(x1,x2,x3,x4)所以n=4 。输入第一行是一个整数K(1K1000) ，表示样例的个数。每个样例占一行，第一个整数是n(1n100) ，以后的n 个整数xi,1xin 且 xi 是唯一的, (1x12x2nxn) 表示一个置换。输出输出一个样例的结果。样例输入33 1 2 33 2 1 33 2 3 1样例输出123（五）20482048是大家非常喜欢的一款小游戏，给定一个2048的局面，和下一步的指令，请计算出变化后的局面。 2048的游戏规则如下： 游戏是一个44 的格子 玩家可以使用上、下、左、右控制数字方格滑动， 每滑动一次，所有的数字方块都会往滑动的方向靠拢，相同数字的方块在靠拢、相撞时会相加。 不断的叠加最终拼凑出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 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-（一）矩阵题目描述编写一个程序，将1n2 按行依次填入nn 的矩阵，执行若干条行或者列的循环移动的指令，再将数字按行依次取出。指令如下：指令含义L x yx行循环左移y次R x yx行循环右移y次U x yx列循环上移y次D x yx列循环下移y次输入第一行是一个整数K，表示样例的个数。 每个样例的第一行是两个整数n(1n10) 和m(1m1000) ，分别表示矩阵的大小和指令的条数。以后的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和m，1n33,0mn 。输出每行输出一个样例的结果。样例输入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）， 每行输入一个字符串和一个整数，字符串只含小写英文字母，长度不超过2000。 整数表示子串的长度，值不超过10。输出每行输出一个样例的结果，先输出答案子串，再输出出现次数，中间用一个空格隔开。样例输入aabb 2aaabbb 2aaaaaa 3样例输出aa 1aa 2aaa 4（四）素因子的种类题目描述给一个整数n，求其素因子一共有多少种？比如30，素因子为2,3,5，所以素因子的种类为3；比如8，素因子为2，所以种类数为1。输入第一行是一个整数k(1k10000) 。 以后每行一个整数n(2n1012) 输出每行输出一个样例的结果样例输入4269999999999891000000000000样例输出1212（五）考试安排题目描述Eric每次考试最头痛的就是安排考试时间，需要找合适的空闲时间安排考试真的是件很费神的事情。Eric希望你能帮他算一下能哪些时间可以考试，当然Eric并不想周末进行考试，所以你只需要计算周1到周5的时间就可以了。 我们假设每天有11节课的时间，上午1到4节，下午5-8节，晚上9-11节。Eric已经拿到了参加考试的班级的课表，以及考试需要的时长。注意：考试只能安排在上午、下午、晚上时段，不能跨区间。输入第一行是一个整数K(1K100) ，表示样例的个数每个样例的第一行是两个整数N(1N100),T(2T4) ，分别表示这些班级课表的条目数和考试所需的课程节数。为了简化问题，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 9 11Wen 9 11Thur 9 11Fri 9 11（六）Beautiful Number题目描述如果一个数的二进制中只有1个0，那么我们称这样的数是“美丽数”，比如510=1012 。 现在给你一个区间a,b(1ab1018) ，求区间内有多少个“美丽数”。输入第一行是一个整数K，表示样例的个数。 每个样例是两个整数a和b。输出每行输出一个样例的结果。样例输入31 22 51 1000000000000000000样例输出121712提示第一个例子中，只有2是美丽数； 第二个例子中，2和5是美丽数；-THIRD-（一）Robot题目描述机器人一开始站在原点，可以上下左右（分别用“UDLR”表示）移动，每次移动一步。Estrella想知道对于某个指令序列，如果把某一种指令全部替换成另一种指令，新的指令序列可以让机器人回到原点。输入存在多个样例，每个样例一行，为一条指令序列，长度不超过200。输出每行输出一个样例的结果，可以输出“Yes”，否则输出“No”。样例输入LDLLDDD样例输出YesNo（二）染色题目描述Alice在玩一个游戏，她在一个mn 的格子里，随机涂黑k 个格子。然后她每次可以把一行或者一列的格子染成红色，但是这一行中不能有黑色的格子。请问她最多能把多少个格子涂成红色？输入第一行是一个整数T(T100) ，表示样例的个数。每个样例的第一行是m(1m100),n(1n100),k(0kmn) 。以后的k 行,每行两个整数x(1xm),y(1yn) ，表示(x,y) 为黑色格子。输出每行输出一个样例的结果。样例输入13 4 21 13 3样例输出8（三）矩阵题目描述我们把1N2 按下面矩阵的规律进行排列：145161736236151835987141934101112132033252423222132262728293031请求第一列的累加和。输入每行一个整数N(1N109) ，如果N=0 表示输入结束，这个样例不需要处理。输出每行输出一个样例的结果，因为这个值可能很大，请将其对1,000,000,007 取模。样例输入12310000000000样例输出1510499999881（四）集合题目描述对于包含整数多值集合A=a1,a2,an ，执行以下两步操作1. 将某些元素加上整数x 2. 将某些元素减掉整数y 请问能否使得A 的元素全部相等？输入第一行是一个整数K(1K100) ，表示样例的个数。每个样例的第一行是一个整数n(1n100,000) 。第二行是ai|i=1,2,n,0ai1,000,000,000 。输出每行输出一个样例的结果，如果可以使得元素全部相等输出Yes,否则输出No样例输入252 1 2 1 351 2 3 4 5样例输出YesNo（五）Colombian Number题目描述对于正整数n ,不存在整数k ,使得n 等于k 加上k 的数码累加和，我们称这样的数是哥伦比亚数或者自我数。比如 11就不是一个哥伦比亚数，因为10加上10的数码累加和1等于11;而20则是一个哥伦比亚数。输入第一行是一个整数K(K10,000) ，表示样例的个数。以后每行一个正整数n(1n1,000,000,000) 输出每行输出一个样例的结果，如果是哥伦比亚数输出Yes,否则输出No。样例输入51232021样例输出YesNoYesYesNo（六）Bonus题目描述要过年了，老板准备发年终奖，老板准备根据员工的平时表现对比发放奖金，最低发888，每档再增加1000块。由于工作表现记录有点问题，可能存在矛盾的描述，所以，如果无法发放的话，则所有人，每人发888元。老板把这个任务交给你，希望你帮他算出一共需要给多少奖金，每人需要发多少奖金？输入第一行是一个整数K，表示样例的个数。每