算法练习题111111

回文

回文是指从前和从后读时均为左右对称的语句。例如 madam, elle, MOM, ZZZZZ 等即为回文。

在本问题中至少三个文字以上的语句看作为回文。即 A、BB 等不能成为回文。

现在长的字符串中要查找回文。

作为一个例子，请看以下字符串。

A V F S I O A A O I D A G E P L A R F E G R T H T R G E F W X G G H

上面的字符串中共计7个回文。

蓝色部分有 IOAAOI, OAAO 2个, 红色部分有 FEGRTHTRGEF, EGRTHTRGE, GRTHTRG, RTHTR, THT 5个，绿色部分的 GG 如上所述，不是回文。

在这7个回文中最长的回文是 FEGRTHTRGEF, 长度为 11。

请以这种方法编辑在字符串中求得长度最长的回文的程序。

[限制条件]

1. 字符串的长度L 为 3 以上 100 以下的整数。

2. 字符串仅可由大写罗马字母(A ~ Z)组成。

3. 回文的长度为3以上。

[输入 ]

输入构成如下。

首行给定测试用例的个数 T。

之后T个测试用例按照顺序给定。

各测试用例为一行,

首先给定字符串的长度 L, 之后给定长度 L的字符串。字符串的长度 L 与字符串之间用空格区分。

[输出 ]

各行以 #x 开头，(x 为测试用的编号 ) 留一个空格后, 按照问题的要求，输出字符串中最长回文的长度。

[输入输出示例]

(输入 )

3

34 AVFSIOAAOIDAGEPLARFEGRTHTRGEFWXGGH

10 XXYYZZWWUU

7 YOPQQPO

(输出 )

#1 11

#2 0

#3 6

-------------------------------------------------------

问题9 :制作暗号

中学生胜希在学校数学课上学习了进制以后，迷住了2进制数。胜希用2进制数制作了暗号。

胜希想的是暗号是，用一个自然数，实现多个常数的数列。实现的方法如下。 首先加密的自然数转化成2个常数。下一步将这2个常数的各位数从最后一位开始7位绑在一起。万一位数不是7个倍数，最后绑到一起的可能不到7位。这种情况，在前边的位子用0补充构成7位。像这样制作的7位数，各自用十进制数重新转换。像这样生成的10进制数从最高的位子绑到一起制作的数开始，按次序排列后就是暗号。

为方便题目的理解准备了如下例题。 例如：如做自然数23456789的暗号

先求23456789的二进制数1011001011110110000010101

将此二进制数从最后一位开始7个数一组分开

1011001011110110000010101 à 1011, 0010111, 1011000, 0010101

3. 不够7位的自然数在最前边加0，构成7位

1011, 0010111, 1011000, 0010101 à 0001011, 0010111, 1011000, 0010101

将每个7位的二进制数换成10进制，按照次序排列。

0001011, 0010111, 1011000, 0010101 à 11, 23, 88, 21

此时制作的11 23 88 21这个自然数就是23456789的暗号。

.

现在我们解读了侄子胜希的暗号，想求出胜希他想的自然数。按照上述规则生成的排列数的数组求原来自然数的程序

[限制条件]

1.通过解读暗号，出现的原来的自然数拥有1 以上 263

不到的值。

2. 暗号排列的数是0以上128不到的常数。

.

3. 暗号排列数的个数（N）是1以上9以下   。

[输入]

输入是像如下内容构成。

第一行是测试用例的个数T给予。

下一行T 是测试用例的次序给予

各测试用例是用一行实现的话，如下构成。

最开始，给出加密排列的个数N, 之后的暗号，排列数中相应的N个的常数由序列给出。各数字之间用空白区分。

[输出]

各行从#x 开始（x是测试用例号码）保留一个空白之后，按照问题要求输出原来的自然数的值。

[输入出 例]

(输入)

3

4 11 23 88 21

7 65 0 63 7 19 2 119

9 127 127 127 127 127 127 127 127 127

(输出)

#1 23456789

#2 285889949647223

#3 9223372036854775807

---------------------------------------------------------------

问题16：产品组装检查

某公司的工厂里生产各种各样的产品。此公司中生成的产品是组装各种组件生产的，这些组件是组装零件制造的。也就是一个组件是组装各种零件制造，一个产品是组装这些组件制造。此工厂取给零件的固有识别符合为A到Z的零件并且生产用这些零件组合制造的组件和产品。

组装一个组件中所需要的零件字符串按照组装的顺序指定，并且指定任意零件的字符串时，如下判断是否可以用任意零件的字符串生产该组件。根据组装工序的特性，比较两个零件的字符串，如果第一个零件的字符和最后一个零件的字符相同，其余零件的字符是种类和其数量一致时，用任意零件的字符串可以组装该组件的。比如A组件所需要的6个零件的字符串为按组装顺序是EEDHIA时，EHIEDA的零件字符串是可以生成A组件，但是FEDHIA，EDDHIA，EEDBIA等零件的字符串是不能生成A组件的。

该工厂为了生产某产品所需要的组件数量和各组件所需要的零件字符按照组装顺序指定，并且指定各组件的任意零件的字符串时，用任意零件的字符串制造的组件，请编写输出其数量的程序。

[输入]

第一行Test Case的数T，从下一行开始指定T个的Test Case.  每个Test Case是由3行构成，在第一行指定产品生产中所需要的组件的数N. 下一行指定各组件在生产中所需要的零件字符串以空白来区分，下下一行也是与上一行一样，按照组件的顺序任意零件的字符串以空白来区分指定的。但是，N为1以上20以下的自然数。

[输出]

每行以#x开始（x是Test Case的编号），空一格后输出用任意零件字符串制造的组件数量。

[输入输出的例]

（输入）

4

4

WUNYO EKHSLDK WNQRT MRTDN

WUNYO EKHSLDK WNQRT MRTDN

4

VTKROS VHSNIYERK QIPJMMI MLPI

BTABED VSIYNREIK QPMJIMI MPLI

5

PXWXLMGI MSDTIXOJS GYJYTDEN AHQV VPHUMUIWE

PYWXMGLI MSDTIXOJU GYYEDTJN AQHV VHPMUIUWE

6

TRNMU PYES NEYTILM FAKPP MNRV EAYDI

TNRMU PEYS NTEYMIM FPAKQ MRRV EDAYI

（输出）

#1 2

#2 2

#3 3

#4 3

先从理解上述问题。这是给出生产组件的零件字符串及任意零件的字符串时，能输出多少个用任意零件的字符串生产的组件的问题。这道题中最重要的用任意零件的字符串是否可以生产该组件的判断规则为如下。比较两个零件的字符串，第一个零件的字符和最后一个零件的字符相同，其之间的零件字符是种类和数量相同时，用此字符串可以生产该组件。也就是在问题的例子中可以看出，给出了EEDHIA的组件字符串和EHIEDA的任意字符串时，第一个零件是E，最后一个零件是A，两个字符串时相同，其之间的字符串中零件D是1个，E是1个，H是1个，I是1个，其种类和数量也是相同的。因此用指定的任意字符串是可以生产该组件的。FEDHIA的话第一个零件的字符是F，因此不同，EDDHIA的话D是2个，E是0个因此数量不同。最后一个EEDBIA的话B是1个，H是0个，因此种类和数量都不一致。

现在思考一下通过理解这些规则该怎样解答这道题。 首先，指定组件和任意字符串时，比较两个字符串判断一下第一个零件的字符和最后一个零件的字符是否相同。如果相同，应该确认其之间的零件字符的种类和数量的相同与否来判断是否可以生产该组件。这里的核心是怎样确认第一个字符和最后一个字符之间的字符的种类和数量是否相同。多个方法中最直观的是对组件之间在字符串中的所有字符的数量与任意字符串进行比较的方法。第二个方法是，如果第一个字符和最后一个字符相同，其之间的种类和数量相同的情况中，分别对齐两个字符串时，利用两个字符串正好一致的方法。

----------------------------------------------

问题 19 : 确定垃圾收回间隔时间

某城市特定区域内要通过模拟来确定垃圾收回时间间隔。此城市使用规格为50L的垃圾袋，并且市民都严格利用此规格的垃圾袋在每天早晨垃圾车经过前投放到指定收回地点。垃圾收回车辆是限定载重的，因车辆载重问题或者因非垃圾收回日所造成的垃圾堆积量不能超过800L，并且在模拟期间内垃圾都要收回。给出模拟期间天数、垃圾收回站可堆积的容量（L）及每天新投放的垃圾袋的个数的情况下，编写出满足上述条件并且费用最低的垃圾收回天数。注：为了便利起见，每次收回的车辆载重一致并且模拟期间开始和结束日期必须进行垃圾收回。

[输入]

第一行输出test case个数，下一行开始显示T个的test case。每个test case分为两行，

第一行模拟天数N和可装载量M(L),用空格隔开。第二行为每天堆积的垃圾袋(50L)个数,用空格隔开。N为大于5并且小于50的自然数，M为大于500小于5000并且以50为倍数的自然数。

[输出]

test   case编号之间留一个空格之后显示满足条件的最长日期。

[输出入样本]

(输入)

5

5 500

3 4 2 5 6

10 1000

2 10 5 4 9 8 4 7 5 4

20 1000

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

30 2000

1 1 6 3 3 4 6 4 4 3 3 1 4 4 5 4 3 1 4 1 5 5 5   1 1 4 5 1 2 6 

40 3000

1 1 6 4 1 5 2 5 1 4 2 2 6 3 3 2 5 5 6 2 4 4 1   5 5 2 2 4 2 4 6 2 4 3 4 1 4 2 3 6 ß 用一行构成

(输出)

#1 3

#2 2

#3 2

#4 4

#5 4

首先要理解此问题。上述问题为了解决某城市特定地点每天垃圾堆积问题，要求出用垃圾收回车辆收回垃圾的间隔天数。在此间隔内要处理所有的垃圾并且中间堆积量不能超过800L的最长日期。即，模拟日结束时收回垃圾之后不能有剩余。垃圾收回时所用的车辆装载量一致并且题中会给出装载量，并且模拟开始日和结束日都要进行垃圾收回。

根据上述条件想想该怎么解决这道题。最简单的话，日期间隔从1天开始到N-1天每个都试一次之后查找符合条件的最大值。此为方法称之为完全检索(Exhaustive Search)，在SW验证的大部分的初级问题和相当数量的中级问题中利用完全检索只要能找出规律的话就可以解决问题。将test case中第一个作为例子。模拟期间为5天，垃圾收回车载重为500L。首先将天数设定为1，那么可以收回10个垃圾袋。每天投放垃圾袋最大个数为6，故比10小，所以没有剩余垃圾可以一次性收回。设定天数为2，那么第一天为3个垃圾袋所以都可以回收。过了两天之后4+2=6，所以可以一次性回收。再过两天之后6+5=11，比10大所以无法一次性回收，所以结束模拟。将天数设定为3，第一天都可以收回。过3天之后的第4天垃圾数量为11(4 + 2 + 5)，留下一个垃圾之后全部收回，最后一天收回7个就可以全部收回。设定天数为4，那么到了最后一天垃圾数量为총 17(4 + 2 + 5 + 6)，

所以最后一天无法一次性全部收回。所以满足条件的最大天数为3.