发布于

sp7586 NUMOFPAL

求一个字符串的回文子串个数。
凡是这类问题，优先考虑麻辣烫。
我们可以发现，依据题意，任意两个对称轴不同的回文串，都是「本质不同」的。
并且，每个回文串，和它对称轴相同的所有子串都必然是回文串。
故而我们先用麻辣烫处理，然后统计一遍即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int n,f[200005];
char ch[100005],s[200005];
inline void manacher(){
	int mx=0,nw;
	for(int i=2;i<=n;++i){
		if(i<mx){
			f[i]=Min(f[(nw<<1)-i],f[nw]-(i-nw));
		}else{
			f[i]=1;
		}
		while(s[i+f[i]]==s[i-f[i]]){
			++f[i];
		}
		if(i+f[i]>mx){
			mx=i+f[i];
			nw=i;
		}
	}
}
void init(){
	cin>>(ch+1);
	n=strlen(ch+1);
	s[1]=s[2]='#';
	for(int i=1;i<=n;++i){
		s[(i<<1)+1]=ch[i];
		s[(i<<1)+2]='#';
	}
	n=(n<<1)+2;
	s[n+1]=0;
	manacher();
	int ans=0;
	for(int i=1;i<=n;++i){
		ans+=f[i]/2;
	} 
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

 

发布于

sp1026 Favorite Dice

开始学习期望DP。
这是一道期望DP入门题。
首先我们设\(f[i]\)表示，已经取了\(i\)种数，距离取完的期望回合数。
根据概率的基本定理，我们可以知道，已经取了\(k\)种以后，下一种取到的是未取到过的概率是\(\frac{n-k}{n} \)；而取到的是取过的概率是\(\frac{k}{n}\)
我们很容易可以知道，已经取了\(i\)种数，下一次取可能有两种情况：
一：取到的是一种新的数。
二：取到的是已经取到过的数。
但无论如何都要再取一次才有造成状态改变的空间。
故而我们得到方程：
$$ f_{i}=\frac{n-i}{n}*f_{i+1}+\frac{i}{n}*f_{i}+1 $$
即：
$$ n*f_{i}=(n-i)*f_{i+1}+i*f_{i}+n $$
从而得到：
$$ f_{i}=\frac{(n-i)*f_{i+1}+n}{n-i} $$
等价于：
$$ f_{i}=f_{i+1}+\frac{n}{n-i} $$
于是我们得到了逆向的递推方程。
然后是边界条件。很显然，\(f_{n}=0\)，这是因为，已经取到\(n\)种以后，就意味着已经取完了。

#include<iostream>
#include<cstdio>
using namespace std;
double f[1005];
int n;
void init(){
    scanf("%d",&n);
    f[n]=0;
    for(int i=n-1;i>=0;--i){
        f[i]=f[i+1]+(double)n/(n-i);
    }
    printf("%.2lf\n",f[0]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}