多校 2013 8-白红宇

多校 2013 8

阅读量：4597 次

发布时间：2019-06-09

本文共 3471 字，大约阅读时间需要 11 分钟。

给你ABC三个串让你求D串

D是AB的子序列 C是D的子串

求D的长度

求出C在AB中出现的位子记录开始位子和结束位子

n^2 枚举在A中位子和在B中位子

然后得到AB 开始位子之前的lcs 和AB结束位子的lcs

开始预处理一下lcs

#include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define inf 1000000007#define MAXN 1010#define ll long longchar a[MAXN],b[MAXN],c[MAXN];int dp1[MAXN][MAXN],dp2[MAXN][MAXN];struct node{ int ind1,ind2;}x1[MAXN],x2[MAXN];int main(){ int t; scanf("%d",&t); int ca=1; while(t--) { scanf("%s%s%s",a+1,b+1,c+1); int len=strlen(c+1); int len1=strlen(a+1); int len2=strlen(b+1); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { if(a[i]==b[j]) dp1[i][j]=dp1[i-1][j-1]+1; else dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]); } } for(int i=len1;i>=1;i--) { for(int j=len2;j>=1;j--) { if(a[i]==b[j]) dp2[i][j]=dp2[i+1][j+1]+1; else dp2[i][j]=max(dp2[i+1][j],dp2[i][j+1]); } } int cnt1,cnt2; cnt1=cnt2=0; for(int i=1;i<=len1;i++) { if(a[i]==c[1]) { int k=2; int j; for(j=i+1;j<=len1&&k<=len;j++) { if(c[k]==a[j]) { k++; } } if(k==len+1) { x1[cnt1].ind1=i-1; x1[cnt1].ind2=j; cnt1++; } } } for(int i=1;i<=len2;i++) { if(b[i]==c[1]) { int k=2; int j; for(j=i+1;j<=len2&&k<=len;j++) { if(c[k]==b[j]) { k++; } } if(k==len+1) { x2[cnt2].ind1=i-1; x2[cnt2].ind2=j; cnt2++; } } } int mx=0; for(int i=0;i

View Code

n个点n-1条边你只可以去掉一条花费是这条边的权 * （块里面最大的距离）要求这个最小

显然这个和树的直径有关那么先2遍dfs求树的直径

然后枚举每条边 1 这条边在直径上那么要求的就是边两端点对应的子树的最大深度

2 不在直径上那么就是边权*直径

#include
      
       #include
       
        #include
        
         using namespace std;#define inf 2e9+7#define MAXN 100010int head[MAXN];struct node{    int v,w,next,id;}edge[MAXN<<1];int ds[MAXN],dt[MAXN],cnt,ms[MAXN],mt[MAXN];void add(int u,int v,int w,int id){    edge[cnt].id=id;    edge[cnt].v=v;    edge[cnt].w=w;    edge[cnt].next=head[u];    head[u]=cnt++;}void dfs(int u,int fa){    for(int i=head[u];i!=-1;i=edge[i].next)    {        int v=edge[i].v;        if(v==fa)            continue;        ds[v]=ds[u]+1;        dfs(v,u);    }}void dfs1(int u,int fa){    for(int i=head[u];i!=-1;i=edge[i].next)    {        int v=edge[i].v;        if(v==fa)            continue;        dt[v]=dt[u]+1;        dfs1(v,u);    }}void dfs2(int u,int fa){    mt[u]=dt[u];    for(int i=head[u];i!=-1;i=edge[i].next)    {        int v=edge[i].v;        if(v==fa)            continue;        dfs2(v,u);        mt[u]=max(mt[u],mt[v]);    }}void dfs3(int u,int fa){    ms[u]=ds[u];    for(int i=head[u];i!=-1;i=edge[i].next)    {        int v=edge[i].v;        if(v==fa)            continue;        dfs3(v,u);        ms[u]=max(ms[u],ms[v]);    }}int id,ans,len;void dfs4(int u,int fa){    for(int i=head[u];i!=-1;i=edge[i].next)    {        int v=edge[i].v;        if(v==fa)            continue;        if(ds[u]+dt[v]+1==len)        {            if(max(ms[u],mt[v])*edge[i].w
         
          ds[s])                s=i;        ds[s]=0;        dfs(s,-1);        int tt=1;        len=ds[1];        for(int i=1;i<=n;i++)            if(ds[i]>ds[tt])             {                  tt=i;                  len=ds[i];             }        dt[tt]=0;        dfs1(tt,-1);        dfs2(s,-1);        dfs3(tt,-1);        ans=inf;        dfs4(s,-1);        printf("Case #%d: %d\n",ca++,id);    }    return 0;}