专栏文章

题解：P11873 最大拟合

bbelot
P11873题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipys9f1
此快照首次捕获于
2025/12/03 20:09
3 个月前
此快照最后确认于
2025/12/03 20:09
3 个月前
查看原文

最大拟合

题意

只有小学数学知识的我看不懂一点。
记叫声为 0,10, 1 以及结束标志为 22。
简单来说就是构造一些三元组 (u,v,w)(u∈[0,1],v∈[0,1],w∈[0,2])(u, v, w) (u\in[0, 1], v\in[0, 1], w\in[0, 2])，使其值不小于 00，不大于 11，且 (u,v,0)+(u,v,1)+(u,v,2)=1(u, v, 0)+(u, v, 1)+(u, v, 2)=1。即 cntu,v,wcnt_{u, v, w} 为 ss 中 si=u,si+1=v,si+2=w(i∈[1,n−1])s_i=u, s_{i+1}=v, s_{i+2}=w (i\in[1, n-1]) 的个数，要求最大化 w=∏u∈{0,1},v∈{0,1},w∈{0,1,2},cntu,v,w>0(u,v,w)cntu,v,ww=\prod_{u\in\{0, 1\}, v\in\{0, 1\}, w\in\{0, 1, 2\}, cnt_{u, v, w}>0} (u, v, w)^{cnt_{u, v, w}}，输出 ln⁡w\ln w。

解法

如果直接乘，精度损失也会导致算出了答案求不出对数。而题中要求输出对数就是一个提示，即把乘法操作换成对数操作。则 w=∑cntu,v,wln⁡(u,v,w)w=\sum cnt_{u, v, w}\ln(u, v, w)。而 cntcnt 是容易统计的，因此重点在考虑对数操作。首先对于每一对 u,vu, v，有 ∑(u,v,w)=1\sum (u, v, w)=1，因此考虑对每一对 u,vu, v 分别计算贡献。若 (u,v,w)(u, v, w) 非最后的三元组，则只有 ww 为 00 或 11 时 (u,v,w)(u, v, w) 才有可能大于 00。先考虑这种情况。
我们可以把它写成 max⁡a>0,b>0,0<p<1aln⁡(p)+bln⁡(1−p)\max_{a>0, b>0, 0<p<1} a\ln(p)+b\ln(1-p)。对 max⁡\max 里的式子求导得 ap−b(1−p)\frac a{p}-\frac b{(1-p)}，使其为 00，解得 p=aa+bp=\frac a{a+b}。而观察函数图像，是中间高两边低的，所以导数为 00 时取到最大值。即 p=aa+bp=\frac a{a+b} 时最大。
三元时同理，结论与二元类似。设其系数为 a,b,ca, b, c，则 pa=aa+b+c,pb=ba+b+c,pc=ca+b+cp_a=\frac a{a+b+c}, p_b=\frac b{a+b+c}, p_c=\frac c{a+b+c}。

Code

CPP
#include <iostream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define sz(x) ((int)x.size())
#define ms(f, x) memset(f, x, sizeof(f))
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define ACN(i, H_u) for (int i=H_u; i; i=E[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
	res=0; bool f=false; char ch=getchar();
	while (ch<'0'||ch>'9') f|=ch=='-', ch=getchar();
	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
	res=(f?-res:res);
}
template <typename INT, typename...Args>
void rd(INT &x, Args &...y) { rd(x), rd(y...); }
//dfs
const int maxn=1e5;
const int N=maxn+10;
char s[N]; int n, a[N], cnt[2][2][3];
//wmr

//incra

//lottle
signed main() {
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	scanf("%s", s+1); n=strlen(s+1);
	L(i, 1, n) a[i]=(s[i]=='H'?0:1); a[++n]=2;
	L(i, 1, n-2) ++cnt[a[i]][a[i+1]][a[i+2]];
	db ans=0;
	L(i, 0, 1) L(j, 0, 1) {
		int x=cnt[i][j][0], y=cnt[i][j][1], z=cnt[i][j][2];
		if (x+y+z) {
			if (x) ans+=x*log(1.0*x/(x+y+z));
			if (y) ans+=y*log(1.0*y/(x+y+z));
			if (z) ans+=z*log(1.0*z/(x+y+z));
		}
	}
	printf("%.6lf\n", ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...