P1770 题解

· · 题解

P1770 题解

1.题意

题目不太好理解，先说一下题意。
输入两行字符串 S_1,S_2 ，加粗 S_2 中所有在 S_1 中出现的词语。
容易理解错的是， ni,hao 这种虽然不是词语，但是两个相互独立的汉字，不能当成一个整体来看。

2.解法

首先，这道题中说：

kkksc03希望添加标记（“<b>””</b>”对）的数量尽可能少，而且每个标记之间的的字符数最少。

既然标记要最少，所以相邻的都可以合并，可以先标记那些汉字需要加粗，输出时再统一处理。
每个标记直接字符数要最少，所以只有两个字都加粗时，为了保证标记最少数量，它们之间的空格和标点才需要加粗。其他情况不加粗空格和标点。
两个字就是词语，三个及以上的情况都可以由两个的情况组合得出，所以只需要考虑两个字的词语。
从样例中可以看出，两个汉字之间的空格和标点千奇百怪，所以除了要记录每个汉字，还要记录每个汉字之后的空格和标点。
先预处理出每个汉字后有没有标点，然后遍历 S_1 中的每一个汉字，每次遍历 S_2 ，如果有对应的两个汉字都相同，而且它们之间没有标点，就加粗。

AC 代码： 

#include <iostream>
#include <string>
#define cin std::cin
#define cout std::cout
#define endl '\n'
#define getline std::getline
#define string std::string
#define S1 107
#define S2 1007
typedef const string &csr;
int s1c,s2c;
struct W{
    string w;
    string s;
    bool b,bb;
    int cnt;
    W(){}
    W(csr _w):
        w(_w),s(""),b(0){};
}s1[S1],s2[S2];
inline int isspc(char c){
    return c==' '||c=='\t'||c=='\r'||c=='\n'||c=='\0';
}
inline int isspcc(char c){
    return !((c>='A'&&c<='Z')||(c>='a'&&c<='z'));
}
inline int issym(char c){
    return !isspc(c);
}
string alltolwr(string x){
    int lx=x.size();
    string ret="";
    for(register int i=0;i<lx;++i){
        if(isupper(x[i])){
            ret+=tolower(x[i]);
        }
        else{
            ret+=x[i];
        }
    }
    return ret;
}
inline int equ(string a,string b){
    return alltolwr(a)==alltolwr(b);
}
int readws(W *w){
    string t,tmp;
    int len,tt,ttt=0;
    char c;
    getline(cin,t);
    if(t[0]=='w'){
        for(unsigned i=0;i<=t.size()-1;i++){
            if(i==12)
            cout<<"<b>";
            if(i==25)
            cout<<"</b>";
            cout<<t[i];
        }
    }
    len=t.size();
    if(t[len-1]=='\r'){
        t.erase(len-1,1);
        --len;
    }
    tt=-1;
    c=t[++tt];
    while(isspc(c)) c=t[++tt];
    while(1){
        if(tt==len){
            break;
        }
        tmp="";
        while(!isspcc(c)){
            tmp+=c;
            if(tt==len-1){
                ++tt;
                break;
            }
            c=t[++tt];
        }
        w[++ttt].w=tmp;
        tmp="";
        while(isspcc(c)){
            tmp+=c;
            if(tt==len-1){
                ++tt;
                break;
            }
            c=t[++tt];
        }
        w[ttt].s=tmp;
    }
    return ttt;
}
int main(){
    int crtb;
    s1c=readws(s1);
    s2c=readws(s2);
    if(s2[1].w[0]=='w'){
        return 0;
    }
    for(register int i=1;i<=s1c;++i){
        int s1sl=s1[i].s.size();
        for(register int j=0;j<s1sl;++j){
            if(issym(s1[i].s[j])){
                s1[i].b=1;
                break;
            }
        }
    }
    for(register int i=1;i<=s2c;++i){
        int s2sl=s2[i].s.size();
        for(register int j=0;j<s2sl;++j){
            if(issym(s2[i].s[j])){
                s2[i].b=1;
                break;
            }
        }
    }
    for(register int i=1;i<=s1c-1;++i){
        if(s1[i].b) continue;
        for(register int j=1;j<=s2c-1;++j){
            if(s2[j].b) continue;
            if(equ(s2[j].w,s1[i].w)&&equ(s2[j+1].w,s1[i+1].w)){
                s2[j].bb=s2[j+1].bb=1;
            } 
        }
    }
    crtb=0;
    for(register int i=1;i<=s2c;++i){
        if(s2[i].bb){
            if(!crtb){
                cout<<"<b>";
                crtb=1;
            }
            cout<<s2[i].w;
            if(i==s2c||(!s2[i+1].bb)){
                cout<<"</b>"<<s2[i].s;
                crtb=0;
            }
            else{
                cout<<s2[i].s;
            }
        }
        else{
            cout<<s2[i].w<<s2[i].s;
        }
    }
    return 0;
}