自动搬运

查看原文

来自洛谷，原作者为

	rzh123 而我将 爱你所爱的人间 / 愿你所愿的笑颜 / 你的手我蹒跚在牵 / 请带我去明天

搬运于2025-08-24 21:28:54，当前版本为作者最后更新于2021-08-21 15:22:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P1770 题解

1.题意

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

2.解法

首先，这道题中说：

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

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