P9184 [USACO23OPEN] Moo Language B 题解

恶♂趣♂味♂大♂模♂拟♂。

首先是构造语句部分：

• 开始肯定是尽可能地多用上不及物语句和及物语句；

• 接着，因为及物语句的单词数量一定比不及物语句多，所以贪心地尽可能多地将不及物语句改为及物语句；

• 然后，为了增加语句长度，再次贪心地在及物语句中尽可能多地添加名词和逗号即可。

接下来是输出部分：

• 对于一个语句中的单词，若其编号 \(\ge 1\)，则需要输出空格；若其编号 \(\ge 3\)，则需要输出逗号；

• 对于不是最后一句的语句，若它还能够与其他语句通过连词相连，则使用一个连词。

代码：

void solve(){
	//读入与初始化
	cin>>n>>c>>p,sum=tot=ttot=0;
	for(int i=0;i<4;i++) a[i].clear();
	for(int i=1;i<=n;i++){
		string s,op; cin>>s>>op;
		if(op[0]=='n') a[0].push_back(s);
		else if(op[0]=='t') a[1].push_back(s);
		else if(op[0]=='i') a[2].push_back(s);
		else a[3].push_back(s);
	}
	
	p+=min(p,(int)(a[3].size())); //计算语句总数
	for(;a[0].size()&&a[2].size()&&tot<p;sum+=2){ //使用不及物语句
		ans[++tot]=a[4];
		ans[tot].push_back(a[0].back()),ans[tot].push_back(a[2].back());
		a[0].pop_back(),a[2].pop_back();
	}
	for(ttot=tot;a[0].size()>=2&&a[1].size()&&tot<p;sum+=3){ //使用及物语句
		ans[++tot]=a[4];
		ans[tot].push_back(a[0].back()),ans[tot].push_back(a[1].back());
		a[0].pop_back(),a[1].pop_back();
		ans[tot].push_back(a[0].back());
		a[0].pop_back();
	}
	for(;ttot&&a[0].size()&&a[1].size();ttot--,sum++){  //尽量用及物语句替代不及物语句
		ans[ttot].pop_back();
		ans[ttot].push_back(a[1].back()),ans[ttot].push_back(a[0].back());
		a[0].pop_back(),a[1].pop_back();
	}
	for(;ttot!=tot&&a[0].size()&&c;c--,sum++) //添加名词和逗号
		ans[tot].push_back(a[0].back()),a[0].pop_back();

	cout<<sum+min(tot/2,(int)(a[3].size()))<<'\n'; //输出语句总数
	for(int i=1;i<=tot;i++){
		for(int j=0;j<ans[i].size();j++){
			if(j>2) cout<<',';
			if(j) cout<<' ';
			cout<<ans[i][j];
		}
		if(i<tot){
			if(i%2&&a[3].size()) //若能够使用连词
				cout<<' '<<a[3].back()<<' ',a[3].pop_back();
			else cout<<". ";
		}
	}
	if(sum) cout<<".\n"; //若有答案才输出句号
}