NOIP2012 题解

发表于 | 分类于 |
字数统计: 5,296 字

本文包含了NOIP2012十道题目的题解。

普及T1 质因数分解

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=2;i*i<=n;i++)
        if(n%i==0){
            printf("%d\n",n/i);
            return 0;
        }
    return 0;
}

普及T2 寻宝

题目地址

模拟，时间复杂度$O(nm)$。
每一层记录一下有楼梯的房间数，找房间用一个循环实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
int n,m,sum=0,p=20123,at[10005][105][2],access[10005]={0},st;
int main(){
    scanf("%d%d",&n,&m);
    int tmp=0,lf;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            scanf("%d%d",&at[i][j][0],&at[i][j][1]);
            if(at[i][j][0])access[i]++;
        }
    scanf("%d",&st);
    for(int i=0;i<n;i++){
        lf=at[i][st][1];
        sum+=lf,lf%=access[i],tmp=st;
        if(!lf)lf=access[i];
        for(;;){
            if(at[i][tmp][0])lf--;
            if(!lf)break;
            tmp=(tmp+1)%m;
        }
        st=tmp,sum%=p;
    }
    printf("%d\n",sum);
    return 0;
}

普及T3 摆花

题目地址

很容易看出来这是一个$DP$。
设$f(i,j)$为摆到第i种花，共有$j$盆的方案数。
那么

时间复杂度：$O(nm^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <ctime>
using namespace std;
int n,m,a[105],dp[105][105]={0},p=1000007;
int main(){
    int i,j,k;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<=a[0];i++)
        dp[1][i]=1;
    for(i=2;i<=n;i++)
        for(j=0;j<=m;j++)
            for(k=0;k<=a[i-1];k++)
                if(j-k>=0)dp[i][j]+=dp[i-1][j-k],dp[i][j]%=p;
                else break;
    printf("%d\n",dp[n][m]);
    return 0;
}

普及T4 文化之旅

题目地址

错误方法

不正确，但却能快速通过本题的方法是$SPFA$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define INF 1000000000
using namespace std;
typedef struct{
    int v,cost,_next; 
}Edge; 
Edge edge[20005];
int cnt=0,at[105],n,k,m,s,t;
int que[10005][105],f,r,c[105],mat[105][105],d[105],in[105]={0};
void addedge(int _u,int _v,int _cost){
    edge[cnt].v=_v,
    edge[cnt].cost=_cost,
    edge[cnt]._next=at[_u],
    at[_u]=cnt++;
}
void spfa_bfs(){
    fill(d+1,d+n+1,INF);
    d[s]=0;
    que[r][0]=s,que[r++][c[s]]=1,in[s]=1;
    int i,_u,_v,_co,j,ok,cul;
    while(r-f){
        _u=que[f++][0],in[_u]=0;
        for(i=at[_u];i!=-1;i=edge[i]._next){
            _v=edge[i].v,_co=edge[i].cost,cul=c[_v];
            for(ok=1,j=1;j<=k;j++)
                if(mat[cul][que[f-1][j]]){
                    ok=0;break;
                }
            if(!ok)continue;
            if(d[_u]+_co<d[_v]){
                d[_v]=d[_u]+_co;
                if(!in[_v]){
                    in[_v]=1,que[r][0]=_v;
                    for(j=1;j<=k;j++)
                        que[r][j]=que[f-1][j];
                    r++;
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
    int i,j,u,v,_c;
    for(i=1;i<=n;i++)
        scanf("%d",&c[i]);
    for(i=1;i<=k;i++)
        for(j=1;j<=k;j++)
            scanf("%d",&mat[i][j]);
    memset(at,-1,sizeof(at));
    for(i=0;i<m;i++)
        scanf("%d%d%d",&u,&v,&_c),
        addedge(u,v,_c),
        addedge(v,u,_c);
    spfa_bfs();
    printf("%d\n",d[t]>=INF-100?-1:d[t]); 
    return 0;
}

正解

正解是搜索。考虑使用高效算法进行优化，那么先以$T$为起点跑$SPFA$，然后从起点搜索的时候，如果不考虑文化的容斥关系都有“当前点到$T$最短路长$+$当前已走距离$\ge ans$”的话就停止搜索。
用$DFS$，跑的还比较快。
upd:上述的做法是正确的，但是这题数据很恶，所以要调整搜索顺序，倒着搜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int to[20005],at[105],nex[20005],cnt=0;
int V,E,K,S,T,mat[105][105],c[105],dis[105][105];
int que[10005],f,r,dist[105],in[105];
int vis[105],ans=1000000000;
void spfa(){
    fill(dist+1,dist+V+1,INF);
    f=r=0,que[r++]=S,in[S]=1,dist[S]=0;
    int h,v;
    while(r>f){
        h=que[f++],in[h]=0;
        for(int i=at[h];i;i=nex[i]){
            v=to[i];
            if(dist[v]>dist[h]+dis[h][v]){
                dist[v]=dist[h]+dis[h][v];
                if(!in[v])
                    in[v]=1,que[r++]=v;
            }
        }
    }
}
void dfs(int cur,int d){
    if(cur==S){
        ans=min(ans,d);
        return ;
    }
    if(d+dist[cur]>=ans)return ;
    vis[c[cur]]=1;
    for(int i=at[cur];i;i=nex[i]){
        int v=to[i],flag=0;
        if(vis[c[v]])continue;
        for(int j=1;j<=K;j++)
            if(vis[j]&&mat[c[v]][j]){
                flag=1;
                break;
            }	
        if(flag)continue;
        dfs(v,d+dis[cur][v]);
    }
    vis[c[cur]]=0;
} 
void init(){
    V=read(),K=read(),E=read(),S=read(),T=read();
    for(int i=1;i<=V;i++)c[i]=read();
    for(int i=1;i<=K;i++)
        for(int j=1;j<=K;j++)
            mat[i][j]=read();
    for(int i=1;i<=V;i++)
        for(int j=1;j<=V;j++)
            dis[i][j]=INF;
    for(int i=1;i<=E;i++){
        int u=read(),v=read(),co=read();
        if(dis[u][v]<co)continue;
        dis[u][v]=dis[v][u]=co;
        to[++cnt]=v,nex[cnt]=at[u],at[u]=cnt;
        to[++cnt]=u,nex[cnt]=at[v],at[v]=cnt;
    }
    spfa();
}
void solve(){
    dfs(T,0);
    printf("%d\n",ans==INF?-1:ans);
}
int main(){
    init();
    solve();
    return 0;
}

提高D1T1 Vigenère密码

题目地址

这个加密运算其实就是循环移位。
密文是循环进位，我们倒着做就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
char key[1005],tex[1005];
int get(char a,char b){
    return (b-'a'-(a-'a')+26)%26;
}
int main(){
    scanf("%s%s",key,tex);
    int l1=strlen(key),l2=strlen(tex);
    for(int i=0;i<l1;i++)
        key[i]=tolower(key[i]);
    for(int i=0;i<l2;i++){
        if(isupper(tex[i]))
            putchar('A'+get(key[i%l1],tolower(tex[i])));
        else
            putchar('a'+get(key[i%l1],tex[i]));
    }
    return 0;      
}

提高D1T2 国王游戏

题目地址

考虑第$i$和第$i+1$个人，他们手上的数字分别为，第$i+1$个人站在第$i$个人身后。
设第$i$个人前面所有人左手数字的积为$T$，那么这两个人拿到的金币数分别为
如果两人交换顺序，那么两人拿到的金币数分别为
为了让获得最多金币的人得到的金币尽量少，我们就需要根据和判断是否该让两个人交换顺序。如果交换了顺序使得取得的$max$更小，那么就需要交换。而根据归纳法，对每一对人按这种方法排一个序，就可以求出正确的答案。此时排序的时间复杂度为$O(n^2)$。
但仔细观察可以发现，。因此只需要确定了和的大小关系，就可以根据不等号的传递性判断哪一种顺序产生的最大值更小。
而对上面两个式子变形，消去$T$并且移项便可以发现：只要比较和的大小就可判断。于是可以以为关键字排序，来确定整个队伍的顺序。
此时，时间复杂度为$O(nlogn+$高精度运算需要的时间$)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>      
#include <algorithm>  
#include <cstring>  
#include <cstdlib>  
using namespace std;
typedef long long ll;
struct P{
    int a,b,t;
};
bool operator<(const P &u,const P &v){
    return (u.t<v.t);
}
P p[1005];
int d1[3]={0},d2[5000]={0},d3[5000],ans[5000]={0},n;
void mul(int s1[],int s2[],int to[]){
    to[0]=s1[0]+s2[0];
    for(int i=1;i<=s1[0];i++){
        int x=0;
        for(int j=1;j<=s2[0];j++)
            x=s1[i]*s2[j]+x+to[i+j-1],to[i+j-1]=x%10000,x/=10000;
        to[i+s2[0]]=x;
    }
    for(;to[0]>1&&to[to[0]]==0;)to[0]--;
}
void div(int s1[],int s2,int to[]){
    to[0]=s1[0];
    int x=0;
    for(int i=s1[0];i>=1;i--)
        to[i]=(x*10000+s1[i])/s2,x=x*10000+s1[i]-to[i]*s2;
    for(;to[0]>1&&to[to[0]]==0;)to[0]--;
}
int smaller(int n1[],int n2[]){//<0 ：小于 
    if(n1[0]!=n2[0])return n1[0]-n2[0];
    else{
        for(int i=n1[0];i>=1;i--)
            if(n1[i]!=n2[i])return n1[i]-n2[i];
        return 0;
    }
}
void output(int s[]){
    printf("%d",s[s[0]]);
    for(int i=s[0]-1;i>=1;i--)
        printf("%04d",s[i]);
    printf("\n");
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
        scanf("%d%d",&p[i].a,&p[i].b),p[i].t=p[i].a*p[i].b;
    sort(p+1,p+1+n);
    d1[0]=d2[0]=d2[1]=1;
    for(int i=0;i<n;i++){
        memset(d3,0,sizeof(d3));
        d1[1]=p[i].a,mul(d1,d2,d3),memcpy(d2,d3,sizeof(d3));
        div(d2,p[i+1].b,d3);
        if(smaller(ans,d3)<0)
            memcpy(ans,d3,sizeof(d3));
    }
    output(ans);
    return 0;
}

提高D1T3 开车旅行

题目地址

倍增。
倍增出小A小B经过$2^k$个回合的情况，然后找最近的最小值用排序+双向链表或者$BST$即可。时间复杂度：$O((n+m)logn)$。
边界的一些处理比较烦，需要注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 2100000000
using namespace std;
typedef long long ll;
int high[100005][2],_h[100005][2],
lf[100005],rt[100005],n,lg,X,S;
ll dis[100005][4],_dis[100005][18][4];
//dis [0] 小A开距离 [1]小A开到 [2]小B开距离  [3]小B开到
//_dis[i][j]过2^j个回合 [0]小a开距离 [1]小b开距离 [2]开到 [3]总路程 
int cmp(const void *a,const void *b){
    return *(int*)a-*(int*)b;
}
void init(){
    int i,j,lis[4],m1[2],m2[2],d;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&high[i][0]),
        high[i][1]=i;
    memcpy(_h,high,sizeof(high));
    qsort(_h,n,sizeof(_h[0]),cmp);
    lf[_h[0][1]]=-1;
    for(i=1;i<n;i++)
        lf[_h[i][1]]=_h[i-1][1];
    rt[_h[n-1][1]]=-1;
    for(i=0;i<n-1;i++)
        rt[_h[i][1]]=_h[i+1][1];
    for(i=0;i<n;i++){
        lis[0]=lf[i],lis[1]=rt[i];
        lis[2]=(lf[i]<0)?-1:lf[lis[0]];
        lis[3]=(rt[i]<0)?-1:rt[lis[1]];
        m1[0]=m2[0]=INF;
        m1[1]=m2[1]=-1;
        //m1：最小 m2：第二小 [0]距离 [1]位置
        for(j=0;j<4;j++)
            if(lis[j]>=0){
                d=abs(high[lis[j]][0]-high[i][0]);
                if(d<m1[0]||(d==m1[0]&&high[lis[j]][0]<high[m1[1]][0]))//lis[j]的海拔低
                    m2[0]=m1[0],m2[1]=m1[1],
                    m1[0]=d,m1[1]=lis[j];
                else if(d<m2[0]||(d==m2[0]&&high[lis[j]][0]<high[m2[1]][0]))
                    m2[0]=d,m2[1]=lis[j];
            }
        if(m2[0]>=INF)m2[0]=0;
        if(m1[0]>=INF)m1[0]=0;
        dis[i][0]=m2[0],
        dis[i][1]=m2[1],
        dis[i][2]=m1[0],
        dis[i][3]=m1[1];
        if(rt[i]>=0)lf[rt[i]]=lf[i];
        if(lf[i]>=0)rt[lf[i]]=rt[i];//自我删除
    }
    for(i=1,d=0;i<n;i<<=1,d++);
    lg=d;
    for(i=0;i<n;i++){
        _dis[i][0][0]=dis[i][0];
        if(dis[i][1]>=0)
            _dis[i][0][1]=dis[dis[i][1]][2],
            _dis[i][0][2]=dis[dis[i][1]][3];
        else _dis[i][0][1]=0,_dis[i][0][2]=-1;
        _dis[i][0][3]=_dis[i][0][0]+_dis[i][0][1];
    }
    for(j=1;j<=lg;j++)
        for(i=0;i<n;i++){
            _dis[i][j][0]=_dis[i][j-1][0],
            _dis[i][j][1]=_dis[i][j-1][1];
            if(_dis[i][j-1][2]>=0)//目的地存在 
                _dis[i][j][0]+=_dis[_dis[i][j-1][2]][j-1][0],
                _dis[i][j][1]+=_dis[_dis[i][j-1][2]][j-1][1],
                _dis[i][j][2]=_dis[_dis[i][j-1][2]][j-1][2];
            else _dis[i][j][2]=-1;
            _dis[i][j][3]=_dis[i][j][0]+_dis[i][j][1];
        }
}
void ask(int id,int &a,int &b){
    int i;
    for(i=lg;i>=0;i-- )
        if(_dis[id][i][3]+a+b<=X&&_dis[id][i][2]>=0){
            a+=_dis[id][i][0],
            b+=_dis[id][i][1],
            ask(_dis[id][i][2],a,b);
            break;
        }
    if(i<0)
        for(i=0;i<=lg;i++)
            if(_dis[id][i][0]+a+b<=X){
                a+=_dis[id][i][0];
                break;
            }
}
void solve1(){
    int i,_d[2],d_[2],ans;
    double bi=1e12,t1,t2; 
    scanf("%d",&X);
    for(i=0;i<n;i++){
        d_[0]=d_[1]=0;
        ask(i,d_[0],d_[1]);
        t1=d_[0],t2=d_[1];
        if(!t2)t1=1e11;
        else t1/=t2;
        if(bi>t1||(abs(bi-t1)<0.0000001&&high[i][0]>high[ans][0]))
            bi=t1,_d[0]=d_[0],_d[1]=d_[1],ans=i;
    }
    printf("%d\n",ans+1);        
}
void solve2(){
    int m,i,u,v;
    scanf("%d",&m);
    for(i=0;i<m;i++)
        scanf("%d%d",&S,&X),
        u=0,v=0,
        ask(S-1,u,v),
        printf("%d %d\n",u,v);
}
int main(){
    init();
    solve1();
    solve2();
    return 0;
}

提高D2T1 同余方程

题目地址

就是让你求一个逆元。
用快速幂+欧拉函数或者扩欧都行。我只写了扩欧，但是前者应该好写一点。
时间复杂度：$O(logn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>   
using namespace std;
typedef long long ll;
ll extgcd(ll a,ll b,ll &x,ll &y){  
    ll d=a;
    if(b){  
        d=extgcd(b,a%b,y,x);  
        y-=(a/b)*x;  
    }else x=1,y=0;  
    return d;  
}
int main(){  
    ll a,m,x,y;
    scanf("%lld%lld",&a,&m);  
    extgcd(a,m,x,y);
    x=(x%m+m)%m;
    printf("%lld\n",x);  
    return 0;  
}

提高D2T2 借教室

题目地址

方法一

维护一种数据结构，它支持:
1.区间减法
2.检查最小值的正负性
线段树即可。这种方法常数很大。
时间复杂度：$O((n+m)logn)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int seg[2200000],tag[2200000]={0};
int n,size,_a,_b,m,rec[3][1000005],_v;
int read(){
    int x=0;char ch=getchar(); 
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
void pushdown(int id){
    if(tag[id]&&id<size)
        tag[id<<1]+=tag[id],tag[id<<1|1]+=tag[id],
        seg[id<<1]+=tag[id],seg[id<<1|1]+=tag[id],
        tag[id]=0; 
}
void init(){
    int i;
    for(size=1;size<n;size<<=1);
    for(i=size;i-size<n;i++)seg[i]=read();
    for(;i<(size<<1);i++)seg[i]=INF;
    for(i=size-1;i>=1;i--)
        seg[i]=min(seg[i<<1],seg[i<<1|1]);
}
void minus(int id,int l,int r){
    if(l>_b||r<_a)return ;
    if(_a<=l&&r<=_b){ 
        tag[id]+=_v,seg[id]+=_v;
        return ;
    }
    pushdown(id);
    minus(id<<1,l,(l+r)>>1);
    minus(id<<1|1,(l+r+1)>>1,r);
    seg[id]=min(seg[id<<1],seg[id<<1|1]);
}
int solve(){
    for(int i=0;i<m;i++){
        _v=-rec[0][i],_a=rec[1][i],_b=rec[2][i],
        minus(1,1,size);
        if(seg[1]<0)return i+1;
    }
    return -1;
}
int main(){
    n=read(),m=read();
    init();
    for(int i=0;i<m;i++)
        rec[0][i]=read(),rec[1][i]=read(),rec[2][i]=read();
    int ans=solve();
    if(ans<0)printf("0\n");
    else printf("-1\n%d\n",ans); 
    return 0;
}

方法二

我们发现随着订单的增多，可用教室的数量是只减不增的，所以我们尝试二分。
二分一个最大订单量，然后区间减法用差分实现，最后扫一遍，看看是否存在负值即可。
（差分：
假设我们有一个数列: 定义它的差分数列是 这样可以发现差分数列中前$n$个元素的和就是原来数列当前位置元素的值。
然后为什么说他可以用来做区间减法呢？比方有$5$个数，$a_1,a_2,a_3,a_4,a_5$，差分数列就是$a_1,a_2-a_1,a_3-a_2,a_4-a_3,a_5-a_4$，然后第$2$到$4$个每一个减掉$p$，那么原数列就是

新的差分数列就是

可以发现，本来要修改多个元素，在差分数列里就只要修改$2$个元素。由于我们只要在处理完所有区间操作后再扫一遍查询负数，所以这么做能满足我们的需求。
时间复杂度：$O((n+m)logn)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int n,m,d[N],q[N],s[N],e[N];
int oold,nnew;
void update(){
    if(nnew>oold){
        for(int i=oold+1;i<=nnew;i++)
            d[s[i]]-=q[i],d[e[i]+1]+=q[i];
    }else{
        for(int i=oold;i>nnew;i--)
            d[s[i]]+=q[i],d[e[i]+1]-=q[i];
    }
}
bool C(){
    int flag=0,sum=0;
    update();
    for(int i=1;i<=n;i++){
        sum+=d[i];
        if(sum<0){
            flag=1;
            break;
        }
    }
    return flag;
}
void init(){
    n=read(),m=read();
    int lst=read();
    d[1]=lst;
    for(int i=2;i<=n;i++)
        d[i]=read(),d[i]-=lst,lst+=d[i];
    d[n+1]=-lst;
    for(int i=1;i<=m;i++)
        q[i]=read(),s[i]=read(),e[i]=read();
}
void solve(){
    int L=1,R=m;
    oold=0;
    while(R>L){
        nnew=(L+R)>>1;
        if(C())R=nnew;
        else L=nnew+1;
        oold=nnew;
    }
    if(L==m)printf("0\n");
    else printf("-1\n%d\n",L);
}
int main(){
    init();
    solve();
    return 0;
}

提高D2T3 疫情控制

题目地址

容易发现时间越多，控制疫情的任务越有可能完成。所以先二分一个答案$x$，然后判断它可不可行。
显然，一个军队走的越高，他能控制的就越多，所以让军队尽量向上走，直到走到根或者时间不够为止。如果可以走到根就记录一下走到根的时候剩余的时间，走不到就给最后到的点打一个标记，这个向上走可以用倍增实现。
还可以发现的是，与根直接相连的点很重要，我们称呼他们为关键点，只要全部控制了他们就完成了任务。而判断一个关键点是否被控制可以用一遍$DFS$实现。对于没被控制的关键点，我们把他们到根的路径长记录下来。
我们要让可以到根的军队发配到相应的关键点，并且使得这个分配尽可能合理。怎么做呢？考虑贪心，让剩余时间少的军队去占领最近的关键点，时间多的去占领远的。所以给军队剩余时间和关键点的距离分别排序，做一个贪心即可。
注意，如果当前扫到的军队无法前往最近的关键点，那就让他回到他之前到根的路上经过的关键点。这样可以最大程度的利用军队。
综上，我们在$O(nlogn+mlognlogw)$的时间复杂度内完成了本题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 10000000000000ll
#define LOG 17
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
P left[50005],city[50005];
int to[100005],nex[100005],at[50005],cnt=0;
int n,m,p[100005],par[50005][20],secfa[50005];
int cost[100005],depth[50005],maxd=0,dis[50005][20];
int tot=0,totc=0;
bool vis[50005];

int query(int u,int t){
    if(depth[u]<=t)return 1;
    for(int i=LOG;i>=0;i--)
        if(par[u][i]&&dis[u][i]<=t)
            t-=dis[u][i],u=par[u][i];
    return u;
}
void dfs2(int cur,int fa){
    if(vis[cur])return ;
    bool flag=1,isleaf=1;
    for(int i=at[cur];i;i=nex[i]){
        if(to[i]==fa)continue ;
        dfs2(to[i],cur),flag&=vis[to[i]];
        isleaf=0;
    }
    if(!isleaf)vis[cur]=flag;
}
bool C(int x){
    tot=totc=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=m;i++){
        int goal=query(p[i],x);
        if(goal==1)left[++tot].first=x-depth[p[i]],left[tot].second=p[i];
        else vis[goal]=1;
        //打标记
    }
    dfs2(1,0);
    if(vis[1])return 1;//根节点的子树全部被覆盖了 
    for(int i=at[1];i;i=nex[i])
        if(!vis[to[i]])city[++totc].second=to[i],city[totc].first=cost[i];
    sort(left+1,left+tot+1);
    sort(city+1,city+totc+1);
    int r=1,fr;
    for(int i=1;r<=totc&&i<=tot;i++){
        fr=left[i].second;
        if(left[i].first<city[r].first){
        	vis[secfa[fr]]=1;
        }else{
            vis[city[r].second]=1,r++;
        }
        while(vis[city[r].second]&&r<=totc)r++;
    }
    if(r==totc+1)return 1;
    return 0;
}
void addedge(int _u,int _v,int _c){
    to[++cnt]=_v,cost[cnt]=_c,nex[cnt]=at[_u],at[_u]=cnt;
}
void dfs(int cur,int fa){
    par[cur][0]=fa,maxd=max(maxd,depth[cur]);
    for(int j=1;j<=LOG;j++)
        if(par[cur][j-1])
            par[cur][j]=par[par[cur][j-1]][j-1],
            dis[cur][j]=dis[cur][j-1]+dis[par[cur][j-1]][j-1];
    for(int i=at[cur];i;i=nex[i]){
        if(to[i]==fa)continue ;
        int _v=to[i],_c=cost[i];
        depth[_v]=depth[cur]+_c,
        dis[_v][0]=_c;
        if(cur==1)secfa[_v]=_v;
        else secfa[_v]=secfa[cur]; 
        dfs(_v,cur);
    }
}
void init(){
    n=read();
    int u,v,c; 
    for(int i=1;i<n;i++)
        u=read(),v=read(),c=read(),
        addedge(u,v,c),addedge(v,u,c);
    m=read();
    for(int i=1;i<=m;i++)p[i]=read(); 
    dfs(1,0);
}
void solve(){
    int son=0;
    for(int i=at[1];i;i=nex[i])son++;
    if(son>m){
        printf("-1\n");
        return ;
    }
    int L=0,R=2*maxd,M;
    while(R>L){
        M=(L+R)>>1;
        if(C(M))R=M;
        else L=M+1;
    }
    printf("%d\n",L);
}
int main(){
    init();
    solve();
    return 0;
}

Powered By Valine
v1.5.2