CF 566A Matching Names

题目描述

给出n个名字和n个昵称，求一个名字和昵称的劈配方案，使得被劈配的名字和昵称的最长公共前缀长度的和最大。

1<=n<=100000

字符总数最多800000

输入格式

第一行n

后面n行名字

最后n行昵称

输出格式

第一行最大最长公共前缀长度和

后面n行每行两个整数分别为名字和昵称的编号代表劈配方案，有SPJ

这题好神仙。

本来一看匹配，费用流费用流，一看数据，萎了

考虑是匹配字符串，遂用一些字符串的算法。

要求总匹配长度最大，由贪心我们先令单次匹配较大的匹配，容易证得这样不会更差。

把字符串放到字典树上，根据种类进行编号。

然后在dfs时维护一个系统队列，每次把一个点为根的子树下面的点给统计好，再做上面的。

Code:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int N=800010;

struct node

{

    int ch[26];

    vector <pair <int,int > > per;

}t[N];

char c[N];

int tot,n;

void add(int typ,int num)

{

    int len=strlen(c);

    int now=0;

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

    {

        if(!t[now].ch[c[i]-'a']) t[now].ch[c[i]-'a']=++tot;

        now=t[now].ch[c[i]-'a'];

    }

    t[now].per.push_back(make_pair(num,typ));

}

int q[2][N],l[2],r[2],ans[2][N],cnt,sum;

void dfs(int now,int dep)

{

    int tl[2];

    tl[0]=l[0],tl[1]=l[1];

    l[0]=r[0]+1;

    l[1]=r[1]+1;

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

        if(t[now].ch[i])

            dfs(t[now].ch[i],dep+1);

    for(int i=0;i<t[now].per.size();i++)

    {

        int typ=t[now].per[i].second;

        q[typ][++r[typ]]=t[now].per[i].first;

    }

    while(l[0]<=r[0]&&l[1]<=r[1])

    {

        ans[0][++cnt]=q[0][r[0]--];

        ans[1][cnt]=q[1][r[1]--];

        sum+=dep;

    }

    l[0]=tl[0];

    l[1]=tl[1];

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%s",c);

        add(0,i);

    }

    for(int i=1;i<=n;i++)

    {

        scanf("%s",c);

        add(1,i);

    }

    dfs(0,0);

    printf("%d\n",sum);

    for(int i=1;i<=n;i++)

        printf("%d %d\n",ans[0][i],ans[1][i]);

    return 0;

}

2018.7.25

巴特西

CF 566A Matching Names

CF 566A Matching Names

题目描述

输入格式

输出格式

最新文章

热门文章