CodeForces

CodeForces - 204C Little Elephant and Furik and Rubik

个人感觉是很好的一道题

 

这道题乍一看我们无从下手，那我们就先想想怎么打暴力

暴力还不简单？枚举所有字串，再枚举所有位置，算出所有答案不就行了

我们自然不能无脑暴力，但是暴力可以给我们启发

我们知道所有对答案做出贡献的字符一定是相同的(废话)

所以我们可以O(n^2)首先枚举两个字符串中相同的字符然后再考虑如何贡献

然后计算出所有的方案下的值，再除以n*(n+1)*(2*n+1)/6 [不知道式子怎么来的去面壁]

我们发现：如果这两个相同的字符要做出贡献，那么它们一定在字串相同的位置

换句话说，这两个字符左边被选择的字符一定要同样多(同样的，此时右侧的字符一定也一样多)

比如:(下标均从1开始)

s1 : abbaca

s2 : baabac

这里面如果s1[1],s2[2]两个相同的字符'a'要做出贡献，那么左边必须有0 ，1 , 2 , 3 ... 

我们发现左边一个字符都不能有

那如果s1[3],s2[4]做出贡献呢？左边只能有2个字符：因为其中下标的最小值是3，3-1=2

所以我们发现每次左边最多的字符数量只与最靠左的字符有关

相应的，每次右边最多的字符的数量只与最靠右的字符有关。

那，贡献呢？？

我们可以枚举最靠右的字符，再去计算和那些在他左侧的字符对答案做出贡献

假如我们现在确定了s1[4]，考虑让其做出贡献。

在 <= 4 的情况中

s2[2] 做出贡献 : (6-4)*(2)  

s2[3] 做出贡献 : (6-4)*(3)  

那么我们发现，每个贡献只与另一个字符串中 <= pos 的字符的下标之和有关

 

所以我们线性扫一遍，过程累加下标和，直接O(n)计算即可

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 200010;
char s1[maxn],s2[maxn];
double a[256],b[256];
int main(){
    int n;read(n);
    scanf("%s%s",s1+1,s2+1);
    double ans = 0;
    for(int i=1;i<=n;++i){
        b[s2[i]] += i;
        ans += 1LL*(n-i+1)*(a[s2[i]] + b[s1[i]]);
        a[s1[i]] += i;
    }
    printf("%.20lf
",6.0*ans/n/(n+1)/(n<<1|1));
    getchar();getchar();
    return 0;
}