P1371 NOI元丹题解

Thenyu / 2023-08-23 / 原文

原题

题目要求的很简单，就是问一个任意加了 $ N,O,I $ 三个字母中的任意一个打的字符串里面能组成几个 $ NOI $ 。

先考虑不加字母的情况，直接枚举每一个 $ O $ 的前后 $ N $ 和 $ I $ 的数量相乘然后累加起来，最后就是答案，可以打出如下代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n;
string s;
long long a[N+5],b[N+5],ans;//a表示N的数量,b表示I的数量
int main()
{
	cin>>n>>s;
	s='@'+s;
	for(int i=1;i<=n;++i)
	{
		a[i]=a[i-1],b[i]=b[i-1];
		if(s[i]=='N')a[i]++;
		else if(s[i]=='I')b[i]++;
	}
	for(int i=1;i<=n;++i)
		if(s[i]=='O')ans+=a[i]*(b[n]-b[i]);//累加O前N的数量和O后I的数量的乘积 
	printf("%lld",ans);
	return 0;
}

然后再考虑加字母的情况，简单分析不加字母的代码可以知道：

如果加字母 $ N $ ，使每个字母 $ O $ 前有最多的字母 $ N $ 时答案最大，那么 $ N $ 应该加在字符串的开头。

如果加字母 $ O $ ，就要枚举每个位置，选当前位置前N的数量I的数量的乘积最大的地方加入时答案最大。

如果加字母 $ I $ ，使每个字母 $ O $ 后有最多的字母 $ I $ 时答案最大，那么 $ I $ 应该加在字符串的结尾。

最后再将加三种不同字母的答案中最大的输出即可。

然后就可以写出本题的代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n;
string s;
long long a[N+5],b[N+5],ans[4],maxs;
int main()
{
	cin>>n>>s;
	s='@'+s;
	for(int i=1;i<=n;++i)
	{
		a[i]=a[i-1],b[i]=b[i-1];
		if(s[i]=='N')a[i]++;
		else if(s[i]=='I')b[i]++;
	}
	for(int i=1;i<=n;++i)
	{
		if(s[i]=='O')
		{
			ans[1]+=(a[i]+1)*(b[n]-b[i]);//ans[1]求在开头加字母N的情况 
			ans[2]+=a[i]*(b[n]-b[i]),maxs=max(maxs,a[i]*(b[n]-b[i]));//ans[2]求不加任何字母的情况，然后maxs记录在每个位置加O可以得到最大的N与I数量的乘积，最后将ans[2]与maxs想加即为加字母O最大的答案 
			ans[3]+=a[i]*(b[n]-b[i]+1);//ans[3]求在结尾加字母I的情况 
		}
	}
	ans[2]+=maxs;//得出加字母O的最大答案 
	sort(ans+1,ans+4);//排序一下加三种字母得到的答案 
	printf("%lld",ans[3]);//输出三个答案中最大的答案 
	return 0;
}