[随机]BZOJ5365(Lydsy1805月赛)【回文树】题解

Author Avatar
ZigZagK 2018年5月27日 18:45
remove_red_eye 30

题目概述

给你 \(n\) 个点的树,每个点有一个 \([1,n]\) 的随机权值,问有多少回文路径。

解题报告

因为是随机的……所以你要有信仰,假装回文路径长度最多只有 \(5\) 就行了。

然后因为他只有 \(3s\) 时限……你会TLE不止(小常数巨佬们当我没说)……

我们再来理性分析一波:一个串是回文串的概率为 \(({1\over n})^{len/2}\) ,当 \(len=4\) 的时候概率就只有 \(10^{-10}\)真棒

所以我们只要考虑 \(len\le 3\) 的情况就行了,瞎搞搞。

ps:\(n\) 非常小的时候最好还是 \(O(n^2)\) 处理,但是BZOJ没卡我,不想管了XD……

示例程序

#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
typedef unsigned long long ULL;
const int maxn=100000,HASH=19260817;

int te,n,a[maxn+5],tp;long long ans;
int E,lnk[maxn+5],nxt[(maxn<<1)+5],son[(maxn<<1)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<1)+(tot<<3)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
#define Add(x,y) son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E
int sum[HASH],stk[maxn+5];
inline void Insert(int x) {if (sum[x]) sum[x]++; else stk[++stk[0]]=x,sum[x]=1;}
inline void Clear() {while (stk[0]) sum[stk[stk[0]--]]=0;}
int main(){
    freopen("H.in","r",stdin);
    freopen("H.out","w",stdout);
    for (readi(te);te;te--){
        readi(n);for (int i=1;i<=n;i++) readi(a[i]);
        E=0;memset(lnk,0,sizeof(lnk));ans=n;
        for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
        for (int i=1;i<=n;i++,Clear())
            for (int j=lnk[i];j;j=nxt[j])
                ans+=sum[a[son[j]]],Insert(a[son[j]]);
        for (int i=1;i<=n;i++)
            for (int j=lnk[i];j;j=nxt[j],Clear())
                if (a[i]==a[son[j]]&&i>son[j]){
                    ans++;
                    for (int t=lnk[i];t;t=nxt[t])
                        if (son[t]!=son[j]) Insert(a[son[t]]);
                    for (int t=lnk[son[j]];t;t=nxt[t])
                        if (son[t]!=i) ans+=sum[a[son[t]]];
                }
        printf("%lld\n",ans);
    }
    return 0;
}

本文链接:https://zigzagk.top/2018/05/27/bzoj5365
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。