题解 - Vijos

2

Lifi LV 10 @ 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

Sky1231 (sky1231) LV 10 @ 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

郑浩文 LV 8 @ 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

Baigker LV 8 @ 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

wsmzjzz LV 8 @ 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

dkfleet LV 10 @ 2015-02-01 16:22:42

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

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

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

0

liyinghaowei LV 10 @ 2014-08-08 20:15:21

注意是ansistring

0

哥少先队的 LV 9 @ 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

Veili LV 9 @ 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

chen199277 LV 10 @ 2009-11-09 19:54:34

dfs即可。

0

gyh LV 10 @ 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

notblack LV 10 @ 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

claire_ LV 10 @ 2009-08-15 19:52:25

思路不难，注意细节！！！

0

1s LV 10 @ 2009-08-04 18:52:07

李寰，你迟到了……

0

how LV 10 @ 2009-07-31 18:16:17

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

0

郭亚奇 LV 10 @ 2009-02-16 16:03:25

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

0

xukemn LV 7 @ 2008-11-11 08:57:11

感谢董吉神牛

0

cx24 LV 6 @ 2008-11-06 10:38:10

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

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

根本不用分情况

0

R.Aurora LV 3 @ 2008-10-29 22:18:48

找S和T的最近公共祖先

0

dpuppet LV 4 @ 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.

题解

36 条题解

机密信息

信息

状态

开发

支持

题解

36 条题解

机密信息

信息

状态

开发

支持

还没有账户？

登录