muti多校-9

自用笔记算法

muti多校-9

HDU 6162

题目要求

有一个棵树 每个点有一个点权 若干次询问
每次询问给出起点s 终点t和上下限ab 经过点的点权必须在a和b之间
问s到t的点权和为多少

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int n,q,step;
LL w[maxn];
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn];
int val[maxn];
struct T{
    LL sum,Max,Min;
}tree[maxn<<2];
vector<int>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(id,0),mm(top,0),mm(val,0);
    mm(tree,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    id[x]=++step;
    val[id[x]]=x;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
}
void push_up(int rt){
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
    tree[rt].Max=max(tree[rt<<1].Max,tree[rt<<1|1].Max);
    tree[rt].Min=min(tree[rt<<1].Min,tree[rt<<1|1].Min);
}
void build(int rt,int l,int r){
    if(l==r){
        tree[rt].sum=tree[rt].Max=tree[rt].Min=w[val[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
LL query(int rt,int l,int r,int L,int R,LL x,LL y){
    if(l>=L && r<=R){
        if(tree[rt].Max<x || tree[rt].Min>y) return 0;
        if(tree[rt].Max<=y && tree[rt].Min>=x) return tree[rt].sum;
    }
    int mid=(l+r)>>1;
    LL ans=0;
    if(mid>=L) ans+=query(lson,L,R,x,y);
    if(mid<R) ans+=query(rson,L,R,x,y);
    return ans;
}
LL solve(int L,int R,LL x,LL y){
    LL sum=0;
    while(top[L]!=top[R]){
        if(dep[top[L]]<dep[top[R]]) swap(L,R);
        sum+=query(1,1,n,id[top[L]],id[L],x,y);
        L=fa[top[L]];
    }
    if(id[L]>id[R]) swap(L,R);
    sum+=query(1,1,n,id[L],id[R],x,y);
    return sum;
}
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&q)!=EOF){
        init();
        for(int i=1;i<=n;i++) scanf("%d",&w[i]);
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs1(1,0,0);
        dfs2(1,1);
        build(1,1,n);
        while(q--){
            int s,t;
            LL a,b;
            scanf("%d%d%lld%lld",&s,&t,&a,&b);
            LL ans=solve(s,t,a,b);
            if(q==0) printf("%lld\n",ans);
            else printf("%lld ",ans);
        }
    }
    return 0;
}

思路

由于是树链上的操作 所以用树链剖分和线段树
线段树维护最大值 最小值和sum
若某段的最大值小于x或最小值大于y 说明它不在x-y的区间内返回0
若在x-y之间说明该段有效 返回sum

HDU 6165

题目要求

问一个有向图是否存在任意两点uv都有路径u到v v到u

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m;
int vis[maxn],g[maxn][maxn];
vector<int>e[maxn];
void init(){
    mm(vis,0),mm(g,0);
    for(int i=0;i<=n;i++) e[i].clear();
}
void dfs(int st,int x){
    vis[x]=1;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(vis[next]) continue;
        g[st][next]=1;
        dfs(st,next);
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        init();
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
        }
        for(int i=1;i<=n;i++){
            mm(vis,0);
            dfs(i,i);
        }
        int flag=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) continue;
                if(g[i][j]==0 && g[j][i]==0){
                    flag=1;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag) puts("Light my fire!");
        else puts("I love you my love and our love save us!");
    }
    return 0;
}

思路

每个点暴力dfs 并把以该点为起点的g数组更新 最后判断g中有没有无法到达的点

HDU 6166

题目要求

在一个有向图中选取k个点 求这k个点中两两之间最短路的最小值

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const LL INF=(LL)1e18;
int n,m;
LL dis[maxn],ans;
int a[maxn];
struct node{
    int x;
    LL id;
    node(int u,LL w){x=u,id=w;}
    bool operator < (const node &a) const{
        return id>a.id;
    }
};
vector<node>e[maxn];
void init(){
    for(int i=0;i<=n;i++) e[i].clear();
    for(int i=1;i<maxn;i++) dis[i]=INF;
    mm(a,0);
}
void DJ(int s){
    priority_queue<node>q;
    q.push(node(s,0));
    while(!q.empty()){
        node now=q.top();
        q.pop();
        int len=e[now.x].size();
        for(int i=0;i<len;i++){
            node next=e[now.x][i];
            if(next.x != s && dis[next.x]>now.id +next.id){
                dis[next.x]=now.id+next.id ;
                q.push(node(next.x,dis[next.x]));
            }
        }
    }
}
int flag=1;
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int u,v;
            LL w;
            scanf("%d%d%lld",&u,&v,&w);
            e[u].push_back(node(v,w));
        }
        int k; scanf("%d",&k);
        for(int i=1;i<=k;i++){
            int x; scanf("%d",&x);
            a[i]=x;
        }
        for(int i=1;i<=k;i++) DJ(a[i]);
        LL Min = INF;
        for(int i=1;i<=k;i++) Min = min(Min,dis[a[i]]);
        printf("Case #%d: %lld\n",flag++,Min);
    }
    return 0;
}

思路

官方题解用集合代表每个点的归属情况 跑20次dj即可
本题用的是只初始化一次dis 全部初始化为INF 跑k次dj
最后找出dis[a[i]]的最小值即可

HDU 6168

题目要求

有一个长度为n的序列a1……an，根据a序列生成了一个b序列，b[i] = a[i]+aj，然后有一个人把a，b序列按随机顺序混合了起来，现在问你初始的a序列是什么

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 130050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
vector<int>a,b;
int main(){
//    freopen("input.txt","r",stdin);
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0){
            printf("0\n");
            continue;
        } 
        for(int i=0;i<=n;i++) a.clear(),b.clear();
        map<int,int>num;
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            b.push_back(x);
            num[x]++;
        }
        int len1=b.size();
        sort(b.begin(),b.end());
        a.push_back(b[0]);
        for(int i=1;i<len1;i++){
            int x=b[i];
            if(num[x]==0) continue;
            int len2=a.size();
            for(int j=0;j<len2;j++) num[x+a[j]]--;
            num[x]--;
            a.push_back(x);
        }
        int len2=a.size();
        printf("%d\n",len2);
        for(int i=0;i<len2;i++){
            if(i==0) printf("%d",a[i]);
            else printf(" %d",a[i]);
        }
        printf("\n");
    }    
    return 0;
}

思路

把数组b排序 最小的数字肯定在a中 把它放入a中 接着选择次小的数字 把b数组中次小数与a数组中每一个数的和删除 并把次小数也加入a中
重复以上操作
注意用map映射

本文标题:muti多校-9

文章作者:Hippopmonkey

发布时间:2017-08-23, 10:15:02

最后更新:2017-08-23, 14:38:15

原始链接:http://xuboming8.github.io/2017/08/23/muti多校-9/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. muti多校-9
    1. 1.1. HDU 6162
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6165
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6166
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 6168
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
|