P6964题解

· · 题解

这是一个有些繁琐的字符串模拟题。

思路简述

  1. 首先用一个 vector<string> 的数组来存储每个单词，注意要把空格和特殊字符看做一个单独的单词。 因为可缩写的几个单词之间 只能 有 一个 空格。

  2. 然后开始一个单词一个单词进行模拟。若当前字符是一个无法缩写的串就直接输出；若是一个可缩写的就继续往后判断（ 核心代码 ）：首先看那个串后方是否有一个空格和另一个符合条件的串（即看当前部分是否可以缩写，因为只有一个符合题意的串是无法缩写的），若可以缩写就循环往后并判断，直到无法缩写，这同时也输出它们的缩写（每个的首字母），这部做完后再重新循环一遍把全称也输出（注意还有全称前后的括号、空格）。于是我们就完成了一次缩写。

代码如下。

#include<bits/stdc++.h>
using namespace std;
bool big(char x){if(x>='A'&&x<='Z')return 1;return 0;}
bool sma(char x){if(x>='a'&&x<='z')return 1;return 0;}
int pd(string a){
    int l=a.length();
    if(!big(a[0])) return 0;
    if(l<=1) return 0;
    for(int i=1;i<l;i++) if(!sma(a[i])) return 0;
    return 1;
}//看该单词是否可以缩写
signed main(){
    string s,no;
    while(getline(cin,s)){
        vector<string>se;int l=s.length();no="";
        for(int i=0;i<l;i++){
            if(big(s[i])||sma(s[i])) no+=s[i];
            else{
                se.push_back(no);no="";no+=s[i];
                se.push_back(no);no="";
            }
        }
        se.push_back(no);no="";
        int n=se.size(),i,j;
        for(i=0;i<n;i++){
            int ii=i;
            if(pd(se[i])){//核心代码如下
                if(i==n-1) {cout<<se[i];continue;}
                if(se[i+1]==" "&&pd(se[i+2])){//后面有空格和另一个符合条件的串
                    for(j=i;j<=n;j++){//往后判断
                        if((j-i)%2==0){
                            if(!pd(se[j])){
                                j--;
                                break;
                            }
                            else cout<<se[j][0];//输出缩写
                        }
                        else if(se[j]!=" ") break;
                    }
                    cout<<" (";
                    for(int k=i;k<j-1;k++) cout<<se[k];cout<<se[j-1]<<")";//输出全称
                    ii=j-1;
                }
                else cout<<se[i];
            }
            else cout<<se[i];
            i=ii;
        }
        cout<<endl;
    }
    return 0;
}

个人认为这个题其实没有什么太难的算法，但细节比较繁琐，比较耗时间，比较需要耐心。可以将这种题目用来练习自己的代码能力、耐心以及细心程度。

近年的 CSP 、 NOIP 其实也有不少这样的题，如 时间复杂度 ，同样是字符串的模拟； 种花 ，一个带点前缀和的模拟等。

如果还有问题可以私信我。

希望管理员大大通过。