杭电ACM基础题（1200、1251、1256、1321、1328、1379、1288、1804、1860、1982）

1200、To and Fro[将加密的字符串进行解密]

Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down

t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x

Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ‘x’ to pad the message out to make a rectangle, although he could have used any letter.

Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as

toioynnkpheleaigshareconhtomesnlewx

Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.
Input
There will be multiple input sets. Input for each set will consist of two lines. The first line will contain an integer in the range 2. . . 20 indicating the number of columns used. The next line is a string of up to 200 lower case letters. The last input set is followed by a line containing a single 0, indicating end of input.
Output
Each input set should generate one line of output, giving the original plaintext message, with no spaces.
Sample Input

5
toioynnkpheleaigshareconhtomesnlewx
3
ttyohhieneesiaabss
0

Sample Output

theresnoplacelikehomeonasnowynightx
thisistheeasyoneab

Code

/* 对加密的字符串进行解密后输出 （n列，每列1个字符，书写方式是先从左到右，然后从右到左） 解密：先将其还原为矩形。然后对每一列从上到下输出来 */
#include<iostream>
#include<cstring>
using namespace std;
char letter[300],a[200][200];
int main(){
    int n;while(cin>>n){
    if(n==0) return 0;cin>>letter;int len=strlen(letter);//letter/n行，n列 int cow=len/n;int k=0,t; for(int i=0;i<cow;i++){
    t=n-1;for(int j=0;j<n;j++){
    if(i%2==0){
    //从左到右读取 a[i][j]=letter[k];k++;} else{
    //从右往左读取 a[i][t]=letter[k];k++;t--; }    }}//将a[][]中的值按每一列从上到下输出for(int i=0;i<n;i++){
    for(int j=0;j<cow;j++){
    cout<<a[j][i];}} cout<<endl;}return 0;
} 

1251、统计难题[输出以指定字符串为前缀的单词的数量]

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input

banana
band
bee
absolute
acmba
b
band
abc

Sample Output

2
3
1
0

Code

//输入一张单词表，输出以指定字符串为前缀的单词的数量
//map<typename1,typename2>mp;,typename1是键的类型，typename2是值的类型 
#include<iostream>
#include<map>
#include<string>
using namespace std;int main(){
    //利用map将所有单词的前缀保存起来map<string,int> m;string str;m.clear();while(getline(cin,str)){
    if(str.size()==0) break; for(int i=1;i<=str.size();i++){
    m[str.substr(0,i)]++;}} while(cin>>str){
    cout<<m[str]<<endl;}return 0;
} 

1256、画8[画图题]

谁画8画的好,画的快,今后就发的快,学业发达,事业发达,祝大家发,发,发.
Input
输入的第一行为一个整数N,表示后面有N组数据.
每组数据中有一个字符和一个整数,字符表示画笔,整数(>=5)表示高度.
Output
画横线总是一个字符粗,竖线随着总高度每增长6而增加1个字符宽.当总高度从5增加到6时,其竖线宽度从1增长到2.下圈高度不小于上圈高度,但应尽量接近上圈高度,且下圈的内径呈正方形.
每画一个"8"应空一行,但最前和最后都无空行.
Sample Input

2
A 7
B 8

Sample Output

  AA
AA  AA
AA  AAAA
AA  AA
AA  AAAABBB
BB   BB
BB   BBBBB
BB   BB
BB   BB
BB   BBBBB

Code

/* 理解题意：（本题中粗细和高度是一个概念，宽度是水平方向字符的数量） 1、画横线总是一个字符粗————8的横线部分总是由一行字符组成的 2、竖线随着总高度每增长6而增加1个字符宽————竖线的宽度=(height/6)+1 3、下圈高度不小于上圈高度,但应尽量接近上圈高度,且下圈的内径呈正方形.—— ---若(height-3)%2==0，则上下高度相同，又下圈内径为正方形，故可以得出横线的宽度(height-3)/2; ---否则若(height-3)%2==1,则上下不能均分，下圈的高度为（height-3)/2+1,横线的宽度也为此值 思路：以某一规律打印 */
#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    char c;int height;cin>>c>>height;//竖线的宽度int width=(height/6)+1;//下层圈的高度int ddepth;if((height-3)%2==0){
    ddepth=(height-3)/2;}else{
    ddepth=(height-3)/2+1;}//下层圈的高度等于横线的宽度，且横线的宽度+竖线的宽度为总列//横线宽度为ddepth for(int i=0;i<height;i++){
    //打印第一行，最后一行，中间一行 if(i==0||i==height-1||i==(height-ddepth-2)){
    for(int k=0;k<width;k++){
    cout<<" ";}for(int k=0;k<ddepth;k++){
    cout<<c;}cout<<endl;}//打印上圈的竖线部分 else if(i<=(height-3-ddepth)){
    for(int k=0;k<width;k++){
    cout<<c;}for(int k=0;k<ddepth;k++){
    cout<<" ";}for(int k=0;k<width;k++){
    cout<<c;}cout<<endl;}//输出下圈竖直高度的部分 else{
    for(int k=0;k<width;k++){
    cout<<c;}for(int k=0;k<ddepth;k++){
    cout<<" ";}for(int k=0;k<width;k++){
    cout<<c;}cout<<endl;}}if(t>0){
    cout<<endl;}}} 

1321、Reverse Text[翻转字符串]

In most languages, text is written from left to right. However, there are other languages where text is read and written from right to left. As a first step towards a program that automatically translates from a left-to-right language into a right-to-left language and back, you are to write a program that changes the direction of a given text.
Input
The input contains several test cases. The first line contains an integer specifying the number of test cases. Each test case consists of a single line of text which contains at most 70 characters. However, the newline character at the end of each line is not considered to be part of the line.
Output
For each test case, print a line containing the characters of the input line in reverse order.
Sample Input

3
Frankly, I don't think we'll make much
money out of this scheme.
madam I'm adam

Sample Output

hcum ekam ll'ew kniht t'nod I ,ylknarF
.emehcs siht fo tuo yenom
mada m'I madam

Code

//将从左到右的字符串转化为从右到左的字符串
#include<iostream>
#include<string.h>
#include<string>
using namespace std;
int main(){
    int t;string m;cin>>t;getline(cin,m);//吸收换行符 while(t--){
    string sentence;getline(cin,sentence);int len=sentence.size();for(int i=len-1;i>=0;i--){
    cout<<sentence[i];} cout<<endl;}return 0;
} 

1328、IBM Minus One[字符串变化]

ou may have heard of the book ‘2001 - A Space Odyssey’ by Arthur C. Clarke, or the film of the same name by Stanley Kubrick. In it a spaceship is sent from Earth to Saturn. The crew is put into stasis for the long flight, only two men are awake, and the ship is controlled by the intelligent computer HAL. But during the flight HAL is acting more and more strangely, and even starts to kill the crew on board. We don’t tell you how the story ends, in case you want to read the book for yourself ?

After the movie was released and became very popular, there was some discussion as to what the name ‘HAL’ actually meant. Some thought that it might be an abbreviation for ‘Heuristic ALgorithm’. But the most popular explanation is the following: if you replace every letter in the word HAL by its successor in the alphabet, you get … IBM.

Perhaps there are even more acronyms related in this strange way! You are to write a program that may help to find this out.
Input
The input starts with the integer n on a line by itself - this is the number of strings to follow. The following n lines each contain one string of at most 50 upper-case letters.
Output
For each string in the input, first output the number of the string, as shown in the sample output. The print the string start is derived from the input string by replacing every time by the following letter in the alphabet, and replacing ‘Z’ by ‘A’.

Print a blank line after each test case.
Sample Input

2
HAL
SWERC

Sample Output

String #1
IBMString #2
TXFSD

Code

//将给定的大写字符串中的每个字母转化成其后继字母，其中Z变为A
#include<iostream>
#include<string>
using namespace std;
int main(){
    int t,num=0;string s;cin>>t;getline(cin,s);while(t--){
    num++;string word;getline(cin,word);int len=word.size();for(int i=0;i<len;i++){
    if(word[i]=='Z'){
    word[i]='A';}else{
    word[i]=word[i]+1;}}cout<<"String #"<<num<<endl;cout<<word<<endl<<endl;}return 0;
} 

1379、DNA Sorting[字符串问题]

One measure of unsortedness’’ in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence DAABEC, this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence AACEDGG’’ has only one inversion (E and D)–it is nearly sorted–while the sequence ZWQM’’ has 6 inversions (it is as unsorted as can be–exactly the reverse of sorted).

You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of sortedness’’, from most sorted’’ to ``least sorted’’. All the strings are of the same length.
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
Input
The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (1 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.

Output
Output the list of input strings, arranged from most sorted'' toleast sorted’’. If two or more strings are equally sorted, list them in the same order they are in the input file.
Sample Input

110 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Sample Output

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

Code

/*给出一组字符串，按给定指标（最大排序-最小排序）输出 思路：判断每个字符串中，未排序的数量有几个，将未排序的数量从小到大输出 （如：DAABEC--D大于右边的四个字母，E大于右边的一个字母，故其未排序数量为5） */ 
#include<iostream> 
#include<string>
#include<algorithm>
using namespace std;struct word{
    string str;int num;
}letter[200]; bool comp(word a,word b){
    return a.num<b.num;
}int main(){
    int t;cin>>t;while(t--){
    int n,m;//n(0,50] m(1,100] cin>>n>>m;for(int i=0;i<m;i++){
    cin>>letter[i].str;//计算每个字符串中未排序的数量letter[i].num=0;for(int j=0;j<n-1;j++){
    for(int k=j+1;k<n;k++){
    if(letter[i].str[j]>letter[i].str[k]){
    letter[i].num++;}}} }sort(letter,letter+m,comp);//输出for(int i=0;i<m;i++){
    cout<<letter[i].str<<endl;} }
}

1288、Hat’s Tea[贪心算法]

Hat is a member of PG Studio. Hat codes a lot and so he often buys tea at tea vending machine. But the tea vending machine just eat coins and spit out tea, if you feed the machine more coins than the tea’s price and the machine will not spit out your change.
Your program will be given numbers and types of coins Hat has and the tea price. The tea vending machine accepts coins of values 1, 5, 10 RMB (Jiao). The program should output which coins Hat has to use paying the tea so that he uses as many coins as possible.
Input
Each line of the input contains four integer numbers separated by a single space describing one situation to solve. The first integer on the line N, , is the tea price in Jiao. Next four integers , , are the numbers of YiJiao (1 Jiao.RMB), WuJiao (5 Jiao.RMB), and ShiJiao (10 Jiao.RMB) in Hat’s valet. The last line of the input contains four zeros and no output should be generated for it.
Output
For each situation, your program should output one line containing the string " T1 YiJiao, T2 WuJiao, and T3 ShiJiao ", where T1, T2, T3 are the numbers of coins of appropriate values Hat should use to pay the tea while using as many coins as possible. If Hat does not have enough coins to pay the tea exactly, your program should output "Hat cannot buy tea.”.
Sample Input

6653 226 72 352 
578 5 127 951
0 0 0 0 

Sample Output

Hat cannot buy tea.
3 YiJiao, 115 WuJiao, and 0 ShiJiao

Code

/* 题目：给定茶的价格，以及一定数量的1角、5角、10角钱，尽可能用多的硬币买茶，计算最多需要多少硬币 思路：贪心-- 1、如果总金额小于茶的价格，或者茶能被5角支付剩下来的零钱大于1角的个数，或者茶能被10角支付剩下来的钱大于5角和1角的总和，则不能支付。 即剩下的零头无法被满足。 2、若用1角支付， 如果1角的总和大于茶的价格，则用全部一角的数量去支付。 3、若1角不能完全支付，则尽可能多的用1角，即除了用1角支付5角剩下的零头，如果剩下来1角的钱能替换5角，就用5个1角去替换1个5角 此后，剩下来的钱肯定能被5整除。 4、用5角支付，如果5角能支付，就全用5角支付。5角不能支付，则用光所有的5角，剩下的用10角。此时剩下的钱也是5角的倍数。 5、(此时剩下的钱要么能被10整除，要么余5）用10角支付,如果不能被10角整除 ,则剩余钱除以10角的余数必定是5. 这时,用1个5角，或者5个1角来补余下的部分 */ 
#include<iostream>
using namespace std;
int main(){
    int p1,y,w,s;int t1,t2,t3;//代表使用硬币的数量 while(cin>>p1>>y>>w>>s){
    if(p1==0&&y==0&&w==0&&s==0) return 0;//判断出所有不可能的情况if(y+w*5+s*10<p1||p1%5>y||y%10>w*5+y){
    cout<<"Hat cannot buy tea."<<endl;continue;}if(y>=p1){
    cout<<p1<<" YiJiao, 0 WuJiao, and 0 ShiJiao"<<endl;continue;}t1=p1%5+(y-p1%5)/5*5;//一角可以补足的五角的余的数量以及一角替换5角的数量p1=p1-t1;//剩下的钱可以全部用5角 if(w*5>=p1){
    t2=p1/5;cout<<t1<<" YiJiao, "<<t2<<" WuJiao, "<<"and 0 ShiJiao"<<endl;continue;}//剩下的钱全部用完5角还不够t2=w;p1=p1-t2*5;//剩下的钱要么能够被10整除，要么余5 if(p1%10==5){
    if(t2>0) t2--;//用5去补 else t1-=5;//用1去补 p1=p1+5; } //此时p是可以被10整除的 t3=p1/10;cout<<t1<<" YiJiao, "<<t2<<" WuJiao, "<<"and "<<t3<<" ShiJiao"<<endl;} return 0;
}

1804、Deli Deli[将单词的单数转变为复数形式]

Mrs. Deli is running the delicatessen store “Deli Deli”. Last year Mrs. Deli has decided to expand her business and build up an online store. She has hired a programmer who has implemented the online store.

Recently some of her new online customers complained about the electronic bills. The programmer had forgotten to use the plural form in case that an item is purchased multiple times. Unfortunaly the programmer of Mrs. Deli is on holiday and now it is your task to implement this feature for Mrs. Deli. Here is a description how to make the plural form:

1. If the word is in the list of irregular words replace it with the given plural.
2. Else if the word ends in a consonant followed by “y”, replace “y” with “ies”.
3. Else if the word ends in “o”, “s”, “ch”, “sh” or “x”, append “es” to the word.
4. Else append “s” to the word.
   Input
   The first line of the input file consists of two integers L and N (0 ≤ L ≤ 20, 1 ≤ N ≤ 100). The following L lines contain the description of the irregular words and their plural form. Each line consists of two words separated by a space character, where the first word is the singular, the second word the plural form of some irregular word. After the list of irregular words, the following N lines contain one word each, which you have to make plural. You may assume that each word consists of at most 20 lowercase letters from the english alphabet (‘a’ to ‘z’).
   Output
   Print N lines of output, where the ith line is the plural form of the ith input word.
   Sample Input

3 7
rice rice
spaghetti spaghetti
octopus octopi
rice
lobster
spaghetti
strawberry
octopus
peach
turkey

Sample Output

rice
lobsters
spaghetti
strawberries
octopi
peaches
turkeys

Code

/* 将单词的单数形式转变为复数形式 利用map */#include<iostream>
#include<string>
#include<map>
using namespace std;
int main(){
    int m,n;while(cin>>m>>n){
    map<string,string>maps,mp;maps.clear();mp.clear();//输入不规则的单词变复数的形式string str,str1,str2,s;for(int i=0;i<m;i++){
    cin>>str1>>str2;mp[str1]=str2;//str1对应的复数形式为str2}//输入待转化为复数形式的单词for(int i=0;i<n;i++){
    cin>>str;//辅音+y结尾 复数形式变为iesint len=str.size();s=str;bool flag=true;//判断其是否是不规则的复数形式for(map<string,string>::iterator it=mp.begin();it!=mp.end();it++){
    if(it->first==str){
    maps[str]=mp[it->first];cout<<maps[str]<<endl;flag=false;break;}}if(flag==true){
    //辅音加y结尾if(len>=2&&str[len-1]=='y'&&str[len-2]!='a'&&str[len-2]!='e'&&str[len-2]!='i'&&str[len-2]!='o'&&str[len-2]!='u'){
    str[len-1]='i';str=str+"es";maps[s]=str;cout<<maps[s]<<endl;}//o s ch sh x 结尾 加selse if(str[len-1]=='o'||str[len-1]=='s'||(len>=2&&str[len-1]=='h'&&str[len-2]=='c')||(len>=2&&str[len-1]=='h'&&str[len-2]=='s')||str[len-1]=='x'){
    str=str+"es";maps[s]=str;cout<<maps[s]<<endl;}else{
    str=str+"s";maps[s]=str;cout<<maps[s]<<endl;}}}//遍历map数组 map内部会自动排序/* for(map<string,string>::iterator it=maps.begin();it!=maps.end();it++){cout<<it->second<<endl}*/}return 0;
}

1860、统计字符

统计一个给定字符串中指定的字符出现的次数
Input
测试输入包含若干测试用例，每个测试用例包含2行，第1行为一个长度不超过5的字符串，第2行为一个长度不超过80的字符串。注意这里的字符串包含空格，即空格也可能是要求被统计的字符之一。当读到’#'时输入结束，相应的结果不要输出。
Output
对每个测试用例，统计第1行中字符串的每个字符在第2行字符串中出现的次数，按如下格式输出：
c0 n0
c1 n1
c2 n2
…
其中ci是第1行中第i个字符，ni是ci出现的次数。
Sample Input

I
THIS IS A TEST
i ng
this is a long test string
#

Sample Output

I 2
i 35
n 2
g 2 
注：第2个测试用例中，空格也是被统计的字符之一。 

Code

//统计第一行中的字符串中的各字母在第二行中出现的次数，包括空格
#include<iostream>
#include<string>
using namespace std;
int main(){
    string str1,str2;while(getline(cin,str1)){
    int len1=str1.size();if(str1=="#") return 0;getline(cin,str2);int len2=str2.size();//计算str1中的每个字符在str2中的次数int num;for(int i=0;i<len1;i++){
    num=0;cout<<str1[i]<<" ";for(int j=0;j<len2;j++){
    if(str1[i]==str2[j]){
    num++;}}cout<<num<<endl;} }return 0;
} 

1982、Kaitou Kid - The Phantom Thief (1)[字符串变换]

Do you know Kaitou Kid? In the legend, Kaitou Kid is a master of disguise, and can take on the voice and form of anyone. He is not an evil person, but he is on the wrong side of the law. He’s the very elusive phantom thief who never miss his prey although he always uses word puzzles to announce his targets before action.
You are the leader of a museum. Recently, you get several priceless jewels and plan to hold an exhibition. But at the moment, you receive Kid’s word puzzle… Fortunately, It seems Kid doesn’t want to trouble you, and his puzzle is very easy. Just a few minutes, You have found the way to solve the puzzle:
(1) change 1 to ‘A’, 2 TO ‘B’,…,26 TO ‘Z’
(2) change ‘#’ to a blank
(3) ignore the ‘-’ symbol, it just used to separate the numbers in the puzzle

Input
The first line of the input contains an integer C which means the number of test cases. Then C lines follow. Each line is a sentence of Kid’s word puzzle which is consisted of ‘0’ ~ ‘9’ , ‘-’ and ‘#’. The length of each sentence is no longer than 10000.
Output
For each case, output the translated text.
Sample Input

4
9#23-9-12-12#19-20-5-1-12#1-20#12-5-1-19-20#15-14-5#10-5-23-5-12
1-14-4#12-5-1-22-5#20-8-5#13-21-19-5-21-13#9-14#20#13-9-14-21-20-5-19
1-6-20-5-18#20-8-5#15-16-5-14-9-14-7#15-6#20-8-5#5-24-8-9-2-9-20-9-15-14
7-15-15-4#12-21-3-11

Sample Output

I WILL STEAL AT LEAST ONE JEWEL
AND LEAVE THE MUSEUM IN T MINUTES
AFTER THE OPENING OF THE EXHIBITION
GOOD LUCK

code

/* 按一定的规则对字符串进行转换 规则： (1) change 1 to 'A', 2 TO 'B',..,26 TO 'Z' (2) change '#' to a blank (3) ignore the '-' symbol, it just used to separate the numbers in the puzzle */ 
#include<iostream>
#include<string> 
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    string puzzle;cin>>puzzle;int len=puzzle.size();//A的ASCII码值是65，a是97 for(int i=0;i<len;i++){
    if(puzzle[i]=='#'){
    cout<<" ";continue;}int sum=0;while(puzzle[i]!='#'&&puzzle[i]!='-'&&puzzle[i]!='\0'){
    sum=sum*10+(puzzle[i]-'0');//重点 i++;}if(sum!=0){
    cout<<char(sum+64); //转化为字符输出 i--;}}cout<<endl;}return 0;
}