题解

36 条题解

  • 2
    @ 2019-05-13 20:10:18

    先由s一路向上到根,同时加上长度和时间,再由t到根,加上未访问的,减去重复的。@Baigker
    感谢大佬的思路,那么就只需要记住从s和t到根,分别访问了哪几个点,就可以了。使用bool量做翻牌,每次访问vis[i]=!vis[i];这样正好可以去除中间访问重复的点,其中第一个访问重复的点是s和t的共同父辈,这个点要做特殊处理。然后把vis为真的点的字符串长度和访问时间都加起来,由于起点和终点不需要访问,减去起点终点两个访问时间。

    #include <iostream>
    #include <string>
    
    using namespace std;
    
    int ti[10005]={0};
    int len[10005]={0};
    int fa[10005]={0};
    int n,in,out;
    bool vis[10005]={0};
    bool flag=true;
    
    int main()
    {
        string str;
        cin>>n>>in>>out;
        int i,j,k,l;
        for(i=0;i<n;i++)
        {
            cin>>j>>k>>str;
            len[j]=str.length();
            ti[k]++;
            fa[j]=k;
        }
        i=in;
        while(i!=0)
        {
            vis[i]=!vis[i];
            i=fa[i];
        }
        i=out;
        while(i!=0)
        {
            if(flag&&vis[i])//共同父辈
            {
                flag=false;
                i=fa[i];
                continue;
            }
            vis[i]=!vis[i];
            i=fa[i];
        }
        k=0;
        l=0;
        for(i=0;i<=n;i++)
        {
            if(vis[i])
            {
                l+=len[i];
                k+=ti[i];
            }
        }
        k-=ti[in];
        k-=ti[out];
        cout<<l<<endl<<k<<endl;
        return 0;
    }
    
  • 1
    @ 2020-10-24 19:15:52
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <limits>
    using namespace std;
    
    namespace dts
    {
        int ft=0,cnt;
        class tr_node
        {
            public:
                int fa,dep,size,hs,top,id;
                vector<int> s;
        };
        int len[(1<<14)+1],siz[(1<<14)+1],scnt[(1<<14)+1],tim[(1<<14)+1];
        int rk[(1<<14)+1];
        tr_node tr[(1<<14)+1];
        void tr_dfs1(int now,int fa)
        {
            tr[now].fa=fa;
            tr[now].dep=tr[tr[now].fa].dep+1;
            tr[now].size=1;
            tr[now].hs=-1;
            if (now!=ft)
            {
                siz[now]=siz[fa]+len[now];
                tim[now]=tim[fa]+scnt[now];
            }
            else
                len[now]=siz[now]=tim[now]=0;
            for (int i=0;i<tr[now].s.size();i++)
            {
                int next=tr[now].s[i];
                tr_dfs1(next,now);
                tr[now].size+=tr[next].size;
                if (tr[now].hs==-1)
                    tr[now].hs=next;
                else if (tr[tr[now].hs].size<tr[next].size)
                    tr[now].hs=next;
            }
        }
        void tr_dfs2(int now,int top)
        {
            tr[now].top=top;
            tr[now].id=++cnt;
            rk[cnt]=now;
            if (tr[now].hs!=-1)
            {
                tr_dfs2(tr[now].hs,top);
                for (int i=0;i<tr[now].s.size();i++)
                    if (tr[now].s[i]!=tr[now].hs)
                        tr_dfs2(tr[now].s[i],tr[now].s[i]);
            }
        }
        void tr_build()
        {
            cnt=0;
            tr_dfs1(ft,ft);
            tr_dfs2(ft,ft);
        }
        int lca(int x,int y)
        {
            while (tr[x].top!=tr[y].top)
            {
                if (tr[tr[x].top].dep<tr[tr[y].top].dep)
                    swap(x,y);
                x=tr[tr[x].top].fa;
            }
            if (tr[x].dep<tr[y].dep)
                return x;
            else
                return y;
        }
        
        int n,s,t;
        
        void main()
        {
            scanf("%d%d%d\n",&n,&s,&t);
            memset(len,0,sizeof(len));
            memset(siz,0,sizeof(siz));
            memset(scnt,0,sizeof(scnt));
            memset(tim,0,sizeof(tim));
            for (int i=0;i<=n;i++)
                tr[i].s.clear();
            for (int i=1;i<=n;i++)
            {
                int now,fa;
                char stri[1<<10];
                memset(stri,0,sizeof(stri));
                scanf("%d%d%s\n",&now,&fa,stri);
                len[now]=strlen(stri);
                tr[fa].s.push_back(now);
                scnt[fa]++;
            }
            tr_build();
            int lcan=lca(s,t);
            printf("%d\n%d\n",siz[s]+siz[t]-2*siz[lcan]+len[lcan],tim[s]+tim[t]-2*tim[lcan]+scnt[lcan]-scnt[s]-scnt[t]);
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 1
    @ 2016-10-30 15:13:35

    单向BFS:

    以s为起点BFS
    找到t点即可

    不用分情况

    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <queue>
    #include <algorithm>
    using namespace std;
    
    const int maxn=5e4+10;
    
    struct Edge
    {
        int f,t,next;
        Edge() {}
        Edge(int from,int to,int nex):f(from),t(to),next(nex) {}
    }edges[maxn]; int pre[maxn],cnt;
    
    int n,s,t;
    int son[maxn],len[maxn];
    
    void init()
    {
        memset(son,0,sizeof(son));
        memset(len,0,sizeof(len));
        memset(pre,-1,sizeof(pre)); cnt=0;
        scanf("%d%d%d",&n,&s,&t);
        for (int i=1;i<=n;i++)
        {
            int h,pi,L; char c[300];
            scanf("%d%d%s",&h,&pi,&c);
            L=strlen(c); len[h]=L; son[pi]++;
            edges[cnt]=Edge(pi,h,pre[pi]); pre[pi]=cnt++;
            edges[cnt]=Edge(h,pi,pre[h]); pre[h]=cnt++;
        }
    }
    
    void work()
    {
        queue<int> q,ti,L; int state[maxn];
        memset(state,0,sizeof(state));
        q.push(s); ti.push(0);  L.push(len[s]);
        while (!q.empty())
        {
            int u=q.front(),tim=ti.front(),tl=L.front();
            q.pop(); ti.pop(); L.pop();
            for (int i=pre[u];~i;i=edges[i].next)
            {
                int v=edges[i].t;
                if (v==t) { printf("%d\n%d\n",tl+len[v],tim); return; }
                if (!state[v]) {
                    q.push(v);
                    ti.push(tim+son[v]);
                    L.push(tl+len[v]);
                    state[v]=1;
                }
            }
        }
    }
    int main()
    {
        init();
        work();
        return 0;
    }
    
  • 1
    @ 2016-07-20 10:12:49

    先由s一路向上到根,同时加上长度和时间,再由t到根,加上未访问的,减去重复的。注意lca要再加一次(因为之前s回溯时加了一次,t回溯减了一次)。
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<vector>
    using namespace std;
    const int N=30010;
    int fa[N],son[N],vis[N],Len[N];
    int n,s,t,l,c,lca;
    bool b;
    int main(){
    memset(fa,0,sizeof(fa));
    memset(vis,0,sizeof(vis));
    memset(son,0,sizeof(son));
    memset(Len,0,sizeof(Len));
    scanf("%d%d%d",&n,&s,&t);
    int u,v;char ch[100010];
    for (int i=1;i<=n;i++){
    scanf("%d%d%s",&u,&v,ch);
    fa[u]=v;son[v]++;Len[u]=strlen(ch);
    }
    l=c=0;
    b=false;
    c-=son[s];c-=son[t];
    while (s!=0){

    l+=Len[s];c+=son[s];
    vis[s]++;
    s=fa[s];
    }
    while (t!=0){
    if (!vis[t]){
    l+=Len[t];c+=son[t];
    }
    else{
    l-=Len[t];c-=son[t];
    if (b==false){b=true;lca=t;}
    }
    t=fa[t];
    }
    l+=Len[lca];c+=son[lca];
    printf("%d\n",l);
    printf("%d\n",c);
    }

  • 0
    @ 2017-10-01 20:53:52

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <cstdio>
    #include <string>
    using namespace std;

    const int N = 10003;
    struct Edge {
    int v, next;
    };
    Edge edge[N << 1];
    int first[N];
    int len[N], cost[N], fa[N];
    int anc[25][N], dep[N];
    int n, num_edge, st, ed, root;

    inline void add_edge(int &u, int &v);
    void lca_init();
    void dep_init(int x);
    int lca(int a, int b);

    /*
    time不能做变量名,OJ上编译错误,与std某东西重名
    改为cost[]
    */

    int main()
    {
    cin >> n >> st >> ed;
    int u, v; string name;
    for (int i = 1; i <= n; ++i) {
    cin >> v >> u >> name;
    if (u == 0) u = n + 1;
    add_edge(u, v);
    add_edge(v, u);
    fa[v] = u;
    ++cost[u];
    len[v] = name.length();
    }
    lca_init();
    int ances = lca(st, ed);
    // 权值在点上所以不能减两遍LCA,而是一次LCA一次fa[LCA]
    cout << len[st] + len[ed] - len[ances] - len[fa[ances]]<< "\n";
    // st本身不用打开,又因打开父文件夹能看到子文件夹名,故ed不用打开
    // 因此花费从fa[st]和fa[ed]算起
    cout << cost[fa[st]] + cost[fa[ed]] - cost[ances] - cost[fa[ances]] << "\n";

    return 0;
    }

    inline void add_edge(int &u, int &v)
    {
    edge[++num_edge] = {v, first[u]};
    first[u] = num_edge;
    }

    void lca_init()
    {
    dep[root = n + 1] = 1;
    dep_init(root);
    for (int j = 1; j <= 15; ++j)
    for (int i = 1; i <= n; ++i)
    anc[j][i] = anc[j - 1][anc[j - 1][i]];
    }

    void dep_init(int x)
    {
    for (int i = first[x]; i != 0; i = edge[i].next) {
    const int &v = edge[i].v;
    if (dep[v] == 0) {
    dep[v] = dep[x] + 1;
    anc[0][v] = x;
    cost[v] += cost[x];
    len[v] += len[x];
    dep_init(v);
    }
    }
    }

    int lca(int a, int b)
    {
    if (dep[a] > dep[b]) swap(a, b);
    int dx = dep[b] - dep[a];
    for (int j = 15; j >= 0; --j)
    if ((1 << j) & dx) b = anc[j][b];
    if (a == b) return a;
    for (int j = 15; j >= 0; --j)
    if (anc[j][a] != anc[j][b]) {
    a = anc[j][a];
    b = anc[j][b];
    }
    return anc[0][a];
    }

  • 0
    @ 2015-02-01 16:22:42

    一定要注意一开始就在给出的起始文件夹内.
    这样,长度之和就是起始s到最终t的路径上的所有文件夹的字符串长度.

    耗时需要分类讨论.
    如果s是t的祖先,那么文件夹t不用打开;
    如果t是s的祖先,那么文件夹s不用打开;
    如果s和t的最近公共祖先不是它们之一,那么s和t都不用打开.

    不需要过多的考虑根目录.
    最好先DFS建树记深度,这样LCA比较好写.

  • 0
    @ 2014-08-08 20:15:21

    注意是ansistring

  • 0
    @ 2013-10-25 07:33:30

    注意范围是10000— —
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 696 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 688 KiB, score = 10
    测试数据 #2: Accepted, time = 3 ms, mem = 696 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 696 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 696 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 688 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 692 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 696 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 696 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 692 KiB, score = 10
    Accepted, time = 33 ms, mem = 696 KiB, score = 100
    代码
    #include<cstdio>
    int n,s,t,d,f[10002],c[10002],N[10002],l[10002],a=0,b=0;
    char q;
    int main(){
    scanf ("%d%d%d",&n ,&s ,&t);
    for (int i=1; i<=n; i++) {
    scanf("%d" ,& d );
    scanf("%d" ,& f[d]);
    scanf("%c%c",&q, & q );
    N[ f [ d ] ] += 1 ;
    while(q!='\n'){l[d]+=1; scanf("%c",&q); }
    }
    int i=t; a-=N[t]; b =l[t];
    while ( i ) { c[i] =1; i =f[i]; }
    while ( !c[s] ) { b+=l[s]; s =f[s]; a+=N[s]; }
    while ( t !=s ) { a+=N[t]; t =f[t]; b+=l[t]; }
    printf("%d\n%d",b,a);
    }

  • 0
    @ 2009-11-11 20:14:04

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    为了内存,我不惜一切:

    ---|---|---|---|---|---|---|---|--Code---|---|---|---|---|---|---|---|---|---|---|

    program info;

    type

    eagetype = ^eage;

    eage = record

    v: integer;

    next: eagetype;

    end;

    const

    mxn = 10000;

    var

    n,s,t,u,v,ansl,anst,i,len,time: longint;

    e,g: array[0..mxn] of eagetype;

    ch: char;

    flag: boolean;

    temp: string;

    l,p: array[0..mxn] of longint;

    used: array[0..mxn] of boolean;

    procedure solve(u:integer);

    var i: eagetype;

    begin

    if flag then exit;

    if u=t then begin

    flag:=true;

    ansl:=len;

    anst:=time;

    exit;

    end;

    used:=true;

    i:=g;

    while inil do begin

    inc(len,l);

    inc(time,p);

    if not used then solve(i^.v);

    dec(len,l);

    dec(time,p);

    i:=i^.next;

    end;

    end;

    begin

    readln(n,s,t);

    for i:= 1 to n do begin

    g[i]:=nil;

    p[i]:=0;

    end;

    for i:= 1 to n do begin

    read(u,v);

    inc(p[v]);

    read(ch);

    readln(temp);

    l:=length(temp);

    new(e[v]);

    e[v]^.v:=u;

    e[v]^.nexT:=g[v];

    g[v]:=e[v];

    new(e);

    e^.v:=v;

    e^.next:=g;

    g:=e;

    end;

    flag:=false;

    len:=l;

    solve(s);

    writeln(ansl);

    writeln(anst-p[t]);

    end.

  • 0
    @ 2009-11-09 19:54:34

    dfs即可。

  • 0
    @ 2009-11-03 21:26:47

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 181ms

    ├ 测试数据 09:答案正确... 353ms

    ├ 测试数据 10:答案正确... 275ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:809ms

    没秒%>_

  • 0
    @ 2009-08-27 02:28:23

    血的教训 ToT

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案错误...程序输出比正确答案长

    如果是这样子的,极有可能你读入数据的时候把循环变量和编号i弄混了!

  • 0
    @ 2009-08-15 19:52:25

    思路不难,注意细节!!!

  • 0
    @ 2009-08-04 18:52:07

    李寰,你迟到了……

  • 0
    @ 2009-07-31 18:16:17

    汗....典型的并查集...

  • 0
    @ 2009-02-16 16:03:25

    原来就是找最近公共祖先啊

  • 0
    @ 2008-11-11 08:57:11

    感谢董吉神牛

  • 0
    @ 2008-11-06 10:38:10

    S向上拓展直到找到根目录,过程中染色并记录时间、长度

    T向上拓展直到已染色,输出

    根本不用分情况

  • 0
    @ 2008-10-29 22:18:48

    找S和T的最近公共祖先

  • 0
    @ 2008-10-29 16:16:12

    DFS!!!

    var

    n,s,t,i,cost,len:longint;

    num,fa,son:array[0..10001] of longint;

    ch:char;

    flag:boolean;

    f:array[0..10001] of boolean;

    s1:array[0..10001] of string;

    procedure Init;

    begin

    readln(n,s,t);

    for i:=1 to n do

    begin

    read(num[i]);

    read(fa[num[i]]);

    inc(son[fa[num[i]]]);

    read(ch);

    readln(s1[num[i]]);

    end;

    end;

    procedure dfs(p:longint);

    var

    i:longint;

    begin

    f[p]:=true;

    if p=t then

    begin

    flag:=true;

    end

    else

    begin

    for i:=1 to n do

    begin

    if ((num[i]=fa[p]) or (fa[num[i]]=p)) and (not f[num[i]]) then

    dfs(num[i]);

    if flag then

    begin

    len:=len+length(s1[num[i]]);

    if num[i]t then

    cost:=cost+son[num[i]];

    exit;

    end;

    end;

    end;

    end;

    procedure Work;

    begin

    if fa=fa[t] then

    begin

    writeln(length(s1)+length(s1[t]));

    writeln('0');

    halt;

    end;

    len:=len+length(s1);

    dfs(s);

    writeln(len);

    writeln(cost);

    end;

    begin

    Init;

    fillchar(f,sizeof(f),false);

    flag:=false;

    Work;

    end.

信息

ID
1427
难度
7
分类
树结构 | 最近公共祖先字符串 点击显示
标签
(无)
递交数
1259
已通过
245
通过率
19%
被复制
2
上传者