题解：P11873 最大拟合

· · 题解

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

定义 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);
}

后记

纯纯语文神题。