自动搬运

查看原文

来自洛谷，原作者为

	dg114514 qq 8268838 欢迎加 || 壶关条件 U540059

搬运于2025-08-24 23:10:59，当前版本为作者最后更新于2025-03-10 18:38:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目描述过于考语文，我们简化下题意：

定义 $f(i,a,b,c)$ 表示 $s_{i−2}=a$，且 $s_{i=1}=b$ 的情况下， $s_i=c$ 的概率。
给定字符串 $s$，求出

$$\ln\prod^{|s|+1}_{i=3}f(i,s_{i-2},s_{i-1},s_i)$$

其中，$s_{|s|+1}$ 代表字符串的结束标志。

思路十分简单，直接计算出所有对应的三元组出现的概率，然后由于要输出的是自然对数，可以变幻为 $\sum^{|s|+1}_{i=3} \ln f(i,s_{i-2},s_{i-1},s_i)$。

代码

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
map<pair<char,char>,map<char,int>>cnt;//三元组出现次数
map<pair<char,char>,map<char,double>>mp;//三元组出现概率
signed main(){
	string s;
	cin>>s;
	int n=s.size()+1;
	s=" "+s+"&";//'&' 就是结束标记
	for(int i=3;i<=n;i++)
		cnt[{s[i-2],s[i-1]}][s[i]]++;//三元组出现次数
	for(auto &i:cnt){
		int res=0;
		for(auto &j:i.y) res+=j.y;//总共的 c
		for(auto &j:i.y) mp[{i.x.x,i.x.y}][j.x]=cnt[{i.x.x,i.x.y}][j.x]*1./res;//计算概率：i.x.x 是 a，i.x.y 是 b，j.x 就是 c。
	}
	double ans=0;
	for(int i=3;i<=n;i++)
		ans+=log(mp[{s[i-2],s[i-1]}][s[i]]);
	printf("%.10lf",ans);
} 

后记

纯纯语文神题。