【Codeforces Round #476 (Div. 2) [Thanks, Telegram!] E】Short Code

在这里输入题意

【题解】

先建立一棵字典树。
显然,某一些节点上会被打上标记。
问题就转化成求所有标记的深度的和的最小值了。
(标记可以上移,但是不能在同一位置

则我们用树形动规的方法。

从底往上递归处理。

考虑以x为根的一棵子树。

如果这个节点被打上了标记。

那么就直接将答案累加上这个节点的深度。

如果没有打上标记。

那么就把这个子树下面某个深度最高的点移动到这个位置上来。

显然这样贪心做是最优的。

用multiset维护某个子树下面的深度最大值。

然后用启发式合并合并multiset就好。

O(能过)

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

const int N = 1e5;

int n,tot=1,root=1,ch[N+10][26+5],tag[N+10],index[N+10];

multiset<int> myset[N+10];

LL ans = 0;

string s;

void ins(string s){

    int p = root;

    for (int i = 0;i < (int)s.size();i++){

        if (!ch[p][s[i]-'a']) ch[p][s[i]-'a'] = ++tot;

        p = ch[p][s[i]-'a'];

    }

    tag[p] = 1;

}

void dfs(int x,int dep){

    for (int i = 0;i < 26;i++)

        if (ch[x][i]){

            dfs(ch[x][i],dep+1);

        }

    if (x==root) return;

    index[x] = x;

    for (int i = 0;i < 26;i++)

        if (ch[x][i]){

            if((int)myset[index[ch[x][i]]].size()>(int)myset[index[x]].size())

                swap(index[ch[x][i]],index[x]);

            for (int y:myset[index[ch[x][i]]]) myset[index[x]].insert(y);

        }

    if (tag[x]){

        ans+=dep;

        myset[index[x]].insert(dep);

    }else

        if (!myset[index[x]].empty()){

            auto temp = myset[index[x]].end();temp--;

            int bottomdep = *(temp);

            myset[index[x]].erase(temp);

            ans-=bottomdep-dep;

            myset[index[x]].insert(dep);

        }

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> n;

    rep1(i,1,n){

        cin >> s;

        ins(s);

    }

    dfs(root,0);

    cout<<ans<<endl;

	return 0;

}

巴特西

【Codeforces Round #476 (Div. 2) [Thanks, Telegram!] E】Short Code

最新文章

热门文章