刘汝佳uva 字符串专题

第一题 palindrome

点击打开链接uva 401

题目意思：给定一个字符串判断是什么类型
分析：
1 根据输出我们知道这个字符串总共有4种类型
2 首先应该是否是“palindrome ”，判断的理由很简单直接对这个字符串进行判断，但是这里有个地方会出错就是‘0’和‘O’，题目明确说明了‘0’和‘O’看成相同，所以我们应该在输入的时候就把所有的‘0’处理成‘O’，注意这里不能把‘O’改成‘0’（想想为什么？）
3 接下来判断是否是“mirrored string”，这个地方是最容易错的，注意题目说了“each of the elements of the string is changed to its reverse ”意思是前提必须是这个字符串的每一个字母必须都要有对应的字母；第二如果满足了第一个条件那么就应该判断得到的这个新字符串从后往前读是否和原始的字符串相等，如果满足两个条件就是“mirrored string”
4 利用map来映射

代码：

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100;
map<char , char>m;

//映射
void init(){
    m['A'] = 'A' , m['H'] = 'H' , m['I'] = 'I' , m['M'] = 'M';
    m['O'] = 'O' , m['T'] = 'T' , m['U'] = 'U' , m['V'] = 'V';
    m['W'] = 'W' , m['X'] = 'X' , m['Y'] = 'Y' , m['1'] = '1'; 
    m['E'] = '3' , m['J'] = 'L' , m['L'] = 'J' , m['S'] = '2';
    m['Z'] = '5' , m['2'] = 'S' , m['3'] = 'E' , m['5'] = 'Z';
    m['8'] = '8';
}

//判断是否是palindrome
bool isPalin(char *str){
     int len = strlen(str);
     int i = 0 , j = len-1;
     while(i <= j){
        if(str[i] != str[j])
           return false;
        i++ , j--;
     }
     return true;
}

//判断是否是mirrored string
bool isMirr(char *tmpStr , char *str){
    int len = strlen(str);
    int pos = len-1;
    for(int i = 0 ; i < len ; i++ , pos--){
       if(tmpStr[i] != str[pos])
          return false;
    }
    return true;
}

int main(){
    char str[MAXN] , tmpStr[MAXN];
    bool is_palin , is_mirr;
    init();
    while(scanf("%s" , str) != EOF){
         printf("%s" , str);
         int len = strlen(str);
         for(int i = 0 ; i < len ; i++){
            if(str[i] == '0')
              str[i] = 'O';
         }
         is_palin = isPalin(str);
         memcpy(tmpStr , str , sizeof(tmpStr)); 
         bool mark = true; 
         for(int i = 0 ; i < len ; i++){
            if(m[str[i]])
                str[i] = m[str[i]];
            else{
                mark = false;
                break;
            }
         }
         if(mark) //如果字符串的每一个字符都有对应的字符
             is_mirr = isMirr(tmpStr , str);
         else
             is_mirr = false;  
         if(is_palin && is_mirr) printf(" -- is a mirrored palindrome.\n\n");
         if(is_palin && !is_mirr) printf(" -- is a regular palindrome.\n\n");
         if(!is_palin && is_mirr) printf(" -- is a mirrored string.\n\n");
         if(!is_palin && !is_mirr) printf(" -- is not a palindrome.\n\n");
    }
    return 0;
}

第二题 Where's Waldorf ?

点击打开链接uva 10010

题目意思：给定一个n*m的字母方阵，然后给定k个字符串，要求找到每一个字符串在这个字母方阵中的起始位置
分析：
1 首先分析题目，我们可以知道这个字母方阵和这k个字符串，我们只要去匹配即可
2 题目最后一句“All words can be found at least once in the grid. ”说明每一个单词至少有一处可以匹配，所以我们不用担心匹配不成功的问题
3 题目还告诉我们，匹配可以从8个方向开始，并且如果有多处都可以匹配那么选择最上面并且最左边的。
4 知道这写条件，我们就可以考虑怎样去匹配，题目说了要尽量选择“最上面且最左边”，很明显我们只要按照方阵枚举从第一个字母到最后最后一个字母，然后每一个字母都进行判断，只要发现有满足就输出，这样肯定可以保证是最优的解

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

const int MAXN = 55;
char words[MAXN][MAXN];
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int n , m;

bool isOk(int x , int y , char *str){
     int tmpx , tmpy , pos;
     int len = strlen(str);
     for(int i = 0 ; i < 8 ; i++){
        tmpx = x , tmpy = y , pos = 0;
        while(1){
            if(pos == len) return true;
            if(tmpx < 0 || tmpx >= n || tmpy < 0 || tmpy >= m)
                break;
            if(toupper(words[tmpx][tmpy]) != toupper(str[pos])) break;
            tmpx += dir[i][0] , tmpy += dir[i][1] , pos++;
        }
     }
     return false;
}

void solve(char *str){
    for(int i = 0 ; i < n ; i++){
       for(int j = 0 ; j < m ; j++){
          if(toupper(words[i][j]) == toupper(str[0])){
             if(isOk(i , j , str)){
                printf("%d %d\n" , i+1 , j+1);
                return;
             }  
          }
       }
    }
}

int main(){
    int Case , k;
    bool isOne = true;
    char str[MAXN];
    scanf("%d" , &Case);
    while(Case--){
        if(isOne) isOne = false;
        else printf("\n");
        scanf("%d%d" , &n , &m);
        gets(words[0]);//把空行读掉
        for(int i = 0 ; i < n ; i++)
           gets(words[i]);
        scanf("%d" , &k);
        for(int i = 0 ; i < k ; i++){
           scanf("%s" , str);
           solve(str);
        }
    }
    return 0;
}

第三题 Automatic Poetry

点击打开链接uva10361

题意：给定n对字符串，第一个字符串的形式s1<s2>s3<s4>s5，输出的时候只可以删除'<'和'>'，第二个字符串s...，输出的时候利用s4s3s2s5代替"..."

分析：
1 对于第一个字符串的输出应该是比较容易的，只要判断一下是否是'<'和'>'删除之即可
2 对于第二个字符串，前面部分也是直接枚举判断到'.'的时候退出，关键是下面的s4s3s2s5。很明显还是要枚举第一个字符串，找到第一'<'就可以做了，这里利用string来保存s2 s3 s4 s5，最后输出即可。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 110;

void solve(char *str1 , char *str2){
    //输出第一个字符串
    int len1 = strlen(str1);
    for(int i = 0 ; i < len1 ; i++){
       if(str1[i] == '<' || str1[i] == '>')
         continue;
       printf("%c" , str1[i]);
    }
    printf("\n");
    //输出第二个字符串的之前部分
    int len2 = strlen(str2);
    for(int i = 0 ; i < len2 ; i++){
       if(str2[i] == '.')
         break;
       printf("%c" , str2[i]);
    }
    //找s2 s3 s4 s5
    string s2 , s3 , s4 , s5;
    s2 = s3 = s4 = s5 = "";
    int i , j;
    for(i = 0 ; i < len1 ; i++){
       if(str1[i] == '<'){
          for(j = i+1 ; str1[j] != '>' ; j++)
             s2 += str1[j];
          for(j++ ; str1[j] != '<'; j++)
             s3 += str1[j];
          for(j++ ; str1[j] != '>' ; j++) 
             s4 += str1[j];
          for(j++; j < len1 ; j++)
             s5 += str1[j];
          break;
       }
    }
    cout<<s4<<s3<<s2<<s5<<endl;//输出后半部分
}

int main(){
    int n;
    char str1[MAXN] , str2[MAXN];
    scanf("%d%*c" , &n);
    while(n--){
        gets(str1);
        gets(str2);
        solve(str1 , str2);
    }
    return 0;
}

版本二

// UVaOJ 10361
// Automatic Poetry
// by A Code Rabbit

#include <cstdio>
#include <iostream>
using namespace std;

string s1, s2, s3, s4, s5;
string s;

int main() {
    int tot_case;
    scanf("%d", &tot_case);
    getchar();
    while (tot_case--) {
        // Input.
        getline(cin, s1, '<');
        getline(cin, s2, '>');
        getline(cin, s3, '<');
        getline(cin, s4, '>');
        getline(cin, s5);
        getline(cin, s);
        // Output.
        cout << s1 << s2 << s3 << s4 << s5 << endl;
        s.erase(s.end() - 3, s.end());
        cout << s << s4 << s3 << s2 << s5 << endl;
    }

    return 0;
}

第四题 Artificial Intelligence?

点击打开链接uva 537

题意：题目是给定一个式子 P = U*I，现在通过一句话任意给定两个量，要求第三个量的值
分析：
1 很明显我们只要去找到是给定哪两个量即可求出第三个量
2 做法是枚举字符串，观察样例可知初始化值的时候肯定是 P = x mW 或 P = x W 或 P = x MW（其它U 和 I类似）。那么我们就可以通过条件判断求出P U I
3 这里利用字符串转整型的函数atoi()，我们先把要求的数字存在一个字符串里面，然后利用atoi()函数求出。注意P U I的初始值可能会有小数点已经P U I 的单位。

代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1000010;

int main(){
   int n , Case = 1;
   double P , U , I;
   char str[MAXN];
   char tmp[MAXN];
   scanf("%d%*c" , &n);
   while(n--){
      gets(str);
      P = U = I = 0;
      int len = strlen(str);
      int i , j , pos;
      bool mark;
      memset(tmp , '\0' , sizeof(tmp));
      for(i = 0 ; i < len ; i++){
         //求U的初始化
         if(str[i] == 'U' && str[i+1] == '='){
            i+=2 , pos = 0 , mark = false;
            for(j = i ; str[j] != 'V' ; j++){
               if(str[j] == '.'){
                 U += atoi(tmp);
                 pos = 0;  
                 mark = true;
               }
               else{
                 if(isdigit(str[j])) tmp[pos++] = str[j];
               }
            }
            if(mark) U += 1.0*atoi(tmp)/pow(10,pos);
            else U += atoi(tmp);
            //单位
            if(str[j-1] == 'm') U /= 1000;
            if(str[j-1] == 'k') U *= 1000;
            if(str[j-1] == 'M') U *= 1000000; 
            i = j;
            memset(tmp , '\0' , sizeof(tmp));
         }
         //求P的初始化
         if(str[i] == 'P' && str[i+1] == '='){
            i+=2 , pos = 0 , mark = false;
            for(j = i ; str[j] != 'W' ; j++){
               if(str[j] == '.'){
                 P += atoi(tmp);
                 pos = 0;  
                 mark = true;
               }
               else{
                 if(isdigit(str[j])) tmp[pos++] = str[j];
               }
            }
            if(mark) P += 1.0*atoi(tmp)/pow(10,pos);
            else P += atoi(tmp);
            //单位
            if(str[j-1] == 'm') P /= 1000;
            if(str[j-1] == 'k') P *= 1000;
            if(str[j-1] == 'M') P *= 1000000; 
            i = j;
            memset(tmp , '\0' , sizeof(tmp));
         }
         //求I的初始化
         if(str[i] == 'I' && str[i+1] == '='){
            i+=2 , pos = 0 , mark = false;
            for(j = i ; str[j] != 'A' ; j++){
               if(str[j] == '.'){
                 I += atoi(tmp);
                 pos = 0;  
                 mark = true;
               }
               else{
                 if(isdigit(str[j])) tmp[pos++] = str[j];
               }
            }
            if(mark) I += 1.0*atoi(tmp)/pow(10,pos);
            else I += atoi(tmp);
            //单位
            if(str[j-1] == 'm') I /= 1000;
            if(str[j-1] == 'k') I *= 1000;
            if(str[j-1] == 'M') I *= 1000000; 
            i = j;
            memset(tmp , '\0' , sizeof(tmp));
         }
      }
      printf("Problem #%d\n" , Case++);
      if(P&&U) printf("I=%.2lfA\n\n" , P/U);
      if(P&&I) printf("U=%.2lfV\n\n" , P/I);
      if(U&&I) printf("P=%.2lfW\n\n" , U*I);
   }
   return 0;
}

第五题 Excuse Excuse!

点击打开链接uva 409

题目意思：给定k个keywords 和 e个excuses，要求输出keywords最多的excuse
分析：
1 观察第一个样例我们可以知道在匹配的时候是不区分大小写的
2 如果一个keywords在一个excuse中出现多次那要按照多次计算，并且keywords和excuse匹配的时候一定要满足是到非字母处，举例keywords 为“war” ， 匹配excuse里面的“fdgh fghkwar fghk”第二个刚好匹配到空格（非字母），这一句“A keyword ``occurs" in an excuse if and only if it exists in the string in contiguous form and is delimited by the beginning or end of the line or any non-alphabetic character or a space. ”
3 如果有多个excuse的keywords出现的次数相同，那么按照输入的顺序输出这些excuse
4 注意输入的格式

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 25;
const int MAXN = 100;
char words[N][MAXN];
char excuse[N][MAXN];
int  n , m;

void solve(){
    int num[MAXN];
    int Max = 0;
    memset(num , 0 , sizeof(num));
    for(int i = 0 ; i < m ; i++){
       int len = strlen(excuse[i]);
       for(int j = 0 ; j < len ; j++){
          for(int k = 0 ; k < n ; k++){
             if(toupper(excuse[i][j]) == toupper(words[k][0])){
               int tmpLen = strlen(words[k]);
               int t , pos = j;
               for(t = 0 ; t < tmpLen && pos < len ; t++){
                  if(toupper(excuse[i][pos]) != toupper(words[k][t]))
                      break;
                  pos++;
               }
               //这里判断是否匹配到非字母处
               if(t == tmpLen && !isalpha(excuse[i][pos])) num[i]++;
             }
          }
       }
       Max = max(Max , num[i]);
    }
    for(int i = 0 ; i < m ; i++){
       if(num[i] == Max)
         printf("%s\n" , excuse[i]);
    }
}

int main(){
    int Case = 1;
    while(scanf("%d%d%*c" , &n , &m) != EOF){
        for(int i = 0 ; i < n ; i++)
           gets(words[i]);
        for(int i = 0 ; i < m ; i++)
           gets(excuse[i]);
        printf("Excuse Set #%d\n" , Case++);
        solve();
        printf("\n");
    }
    return 0;
}

第六题 Decode the tape

点击打开链接uva 10878

题意：给定一条纸袋，要求输出纸袋所含的信息
分析：
1 分析样例我们知道纸袋上面是一个二进制数，‘o’表示1，空格表示0。然后求出这个二进制数后转化为字符输出
2 注意输入的格式，如果是先用scanf("%s" , str)后面又用gets(str)应该注意第一行的'\n'没有被消除，这里应该用scanf("%s%*c" , str);另外一种简便的方法就是全部用gets(str)这样读入
3 求2的幂的时候尽量不要用库函数里面的pow(),尽量自己写。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100;

int Pow(int x){
    int sum = 1;
    for(int i = 1 ; i <= x ; i++)
       sum *= 2;
    return sum;
}

int main(){
    char str[MAXN];
    gets(str);//或者scanf("%s%*c" , str);
    while(1){
          gets(str);
          if(!strcmp(str , "___________"))
              break;
          int len = strlen(str);
          int num = 0 , pos = 6;
          for(int i = 2 ; i < len-1 ; i++){
              if(str[i] == '.') continue;
              else{
                 if(str[i] != ' ')
                   num += Pow(pos);
                 pos--;
              }
           }
           printf("%c" , num);
    }
    return 0;
}

第7题 Andy's First Dictionary

点击打开链接uva 10815

题意：输入一串字符串，然后对里面的单词进行排序输出
分析：
1 题目的难点就是如何输入，对于这种输入有多汗并且每一行的字符数不确定的情况下，我们一般采用getchar()输入。
2 我们利用单个字符的读入，然后取出里面的单词。怎么取单词呢，这里我们采用string 和 STL的set，我们把单词全部插入set里面set不仅可以排序还可以做到去重，所以我们只需要把单词插入set即可，最后输出。
3 注意怎么取单词，我们以非字母为界限，并且还要注意上一个字符是'\n'，下一个字符也是'\n'的情况，所以在插入的时候应该判断是单词才插入。

代码：

#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    char ch;
    set<string>s;
    string str;
    while((ch = getchar())!= EOF){
        if(!isalpha(ch)){
           if(str != "")//是单词才插入
              s.insert(str);
           str = "";
        }
        else
            str += tolower(ch);
    }
    //插入
    set<string>::iterator it;
    for(it = s.begin() ; it != s.end() ; it++)
        cout<<*it<<endl;
    return 0;
}

第8题 Immediate Decodability

点击打开链接uva 644

题意：给定一序列的01字符串每一组以9结尾，现在问是否所有的字符串都不是其它的字符串的前缀
分析：
1 题目明确说明01字符串的最长为10，并且最多8个字符串
2 很明显的暴力题目，这么少的字符串的数我们只要去枚举每一个字符串是不是都满足即可

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 15;
char str[N][N];

bool isOk(int pos){
    for(int i = 0 ; i < pos ; i++){
       int len_i = strlen(str[i]);
       for(int j = 0 ; j < pos ; j++){
          if(i == j) continue;
          int len_j = strlen(str[j]);
          if(len_i > len_j) continue;
          int k;
          for(k = 0 ; k < len_i ; k++){
             if(str[i][k] != str[j][k])
               break;
          }
          if(k == len_i) return false;
       }
    }
    return true;
}

int main(){
    int pos , Case = 1;
    char tmp[N];
    while(scanf("%s" , tmp) != EOF){
        pos = 1;
        memcpy(str[0] , tmp , sizeof(str[0]));
        while(scanf("%s" , tmp)){
            if(!strcmp(tmp , "9"))
               break;
            memcpy(str[pos++] , tmp , sizeof(tmp));
        }
        if(isOk(pos)) printf("Set %d is immediately decodable\n" , Case++);
        else printf("Set %d is not immediately decodable\n" , Case++);
    }
    return 0;
}

第九题 Automatic Editing

点击打开链接uva 10115

题意：给定n个规则和一个测试的字符串，现在要我们利用这n个规则求出变换后的字符串
分析：
1 根据题目我们可以知道怎么利用规则，首先我们应该先利用第一个规则直到没有可换然后再下一个规则，依次做下去
2 这个地方应该注意不要使用map来映射，我就是利用了map错了很久。还有应该注意就是输入不要使用scanf应该要使用gets()，因为会有空白字符

代码：

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 15;
const int MAXN = 300;
int n;
char text[MAXN];
char rule[N][MAXN]  , mp[N][MAXN];

void solve(){
    int len , pos;
    bool mark;
    char tmp[MAXN];
    for(int i = 0 ; i < n ;){
       mark = false;
       len = strlen(text);//重新求出text的长度，每一次的text都在改变
       for(int j = 0 ; j < len ; j++){
          if(text[j] != rule[i][0]) 
              continue;
          memset(tmp , '\0' , sizeof(tmp));
          pos = 0;
          for(int k = j ; k < len ; k++){
             tmp[pos++] = text[k];
             if(!strcmp(tmp , rule[i])){//找到可以替换
                memset(tmp , '\0' , sizeof(tmp));
                strcpy(tmp , text);
                strcpy(tmp+j , mp[i]);
                strcpy(tmp+j+strlen(mp[i]) , text+k+1);
                memcpy(text , tmp , sizeof(text));//重新复制到text
                mark = true;
                break;//退出重新开始
             }
          }
          if(mark) break;//退出重新开始
       }
       if(!mark) i++;//如果这次没有找到可换的，跳到下一条规则
    }
}

int main(){
    char str[MAXN];
    while(scanf("%d%*c" , &n) && n){
        for(int i = 0 ; i < n ; i++){
           gets(rule[i]);
           gets(mp[i]);
        }
        gets(text); 
        solve();
        printf("%s\n" , text);
    }
    return 0;
}