CCPC-Wannafly 自闭day2

佚名 4年前 (2020-01-17) 随笔 618人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

$f[i]$表示长度为$i$的所有子串所包含的元音字母的总数（同一个位置的元音字母可能计算多次）

$sum[i]$表示$1$到$i$之间元音字母数量。

$f[1] = sum[n]$

$f[2] = f[1] + sum[n - 1] - sum[1]$

$f[3] = f[2] + sum[n - 2] - sum[2]$

一层层往上加，因为包含某字母的子串的数量从两边到中间逐渐递减。因此sum不断往中间靠近。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1000001 + 8888;
long long f[MAXN];
int sum[MAXN];
char s[MAXN];
int n;

bool pd(char c){
    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'y')
        return true;
    return false;
}

void solve(){
    scanf("%s",s + 1);
    n = strlen(s + 1);
    for(int i = 1;i <= n;i ++){
        if(pd(s[i])) sum[i] = sum[i - 1] + 1;
        else sum[i] = sum[i - 1];
    }
    for(int i = 1;i <= n;i ++)
        f[i] = f[i - 1] + sum[n - i + 1] - sum[i - 1];
    double ans = 0.0;
    for(int i = 1;i <= n;i ++) ans += double(f[i]) / i;
    ans = ans / double(1LL * n * (n + 1) / 2);
    printf("%.10lf",ans);
    return;
}

int main(){
    solve();
    return 0;
}

View Code

E：

树的启发式合并。

子树的节点编号排序后的序列为，这个节点的“结实程度”就是：

求每个节点的“结实程度”。

首先一遍dfs处理出每个节点的子树大小。

然后再dfs，从叶节点开始合并子树信息。

考虑将每个节点开一个set，然后不断插入，这里有一个优化，父节点的set初值为子树最大的子节点的set值。

最后不要忘记把父节点插入set中。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int MAXN = 4000009 + 111;
vector<int>G[MAXN];
int fa[MAXN],sz[MAXN];
ll a[MAXN];
int n;
void dfs1(int x)
{ 
    sz[x] = 1;
    for(int i = 0;i < G[x].size();i ++){
        int v = G[x][i];
        if(v == fa[x]) continue;
        dfs1(v);
        sz[x] += sz[v];
    }
    return;
}

set<int>dfs(int x){
    set<int>S;
    if(sz[x] == 1){
        S.insert(x);
        return S;
    }
    ll ans = 0;
    int pos = 0,Max = -1;
    for(int i = 0;i < G[x].size();i ++)
        if(sz[G[x][i]] > Max && G[x][i] != fa[x]) 
            Max = sz[G[x][i]],pos = G[x][i];
    S = dfs(pos);
    ans = a[pos];
    set<int>::iterator f = S.lower_bound(x);
    if(f == S.begin())
        ans += 1LL * (*f - x) * (*f - x); 
    else if(f == S.end())
        f --,ans += 1LL * (x - *f) * (x - *f);
    else {
        int t1 = *f,t2;
        f --,t2 = *f;
        ans -=  1LL * (t1 - t2) * (t1 - t2);
        ans += 1LL * (x - t2) * (x - t2) + 1LL * (t1 - x) * (t1 - x);
    }
    S.insert(x);
    for(int i = 0;i < G[x].size();i ++){
        int  v = G[x][i];
        if(v == fa[x] || v == pos) continue;
        set<int>SS = dfs(v);
        for(set<int>::iterator it = SS.begin();it != SS.end();it ++){
            set<int>::iterator f = S.lower_bound(*it);
            if(f == S.begin())
                ans += 1LL * (*f - *it) * (*f - *it); 
            else if(f == S.end())
                f --,ans += 1LL * (*it - *f) * (*it - *f);
            else {
                int t1 = *f,t2;
                f --,t2 = *f;
                ans -=  1LL * (t1 - t2) * (t1 - t2);
                ans += 1LL * (*it - t2) * (*it - t2) + 1LL * (t1 - *it) * (t1 - *it);
            }
            S.insert(*it);
        }
    }
    a[x] = ans;
    return S;
}

void solve(){
    cin >> n;
    for(int i = 2;i <= n;i ++){
        scanf("%d",&fa[i]);
        G[fa[i]].push_back(i);
        G[i].push_back(fa[i]);
    }
    dfs1(1);
    dfs(1);
    for(int i = 1;i <= n;i ++)
        printf("%lld\n",a[i]);
}

int main(){
    solve();
    return 0;
}