2016 Hdu 多校赛第一场

发表于   |   分类于

Abandoned country

链接

Abandoned country

题意

给你一个无向图，保证边权都不相同，让你求一棵最小生成树。然后在这棵树上任选两点（起点和终点），问这两点距离的期望是多少

分析

官方题解

参考代码

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
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
typedef long long LL;
using namespace std;
const int N=100010;
struct stu{
    int u;
    int v;
    int w;
}edge[N*10];
int n,m,f[N];
double ans=0;
vector<pair<int,int> > G[N];
bool cmp(stu a,stu b)
{
    return a.w<b.w;
}
void init()
{
    sort(edge+1,edge+1+m,cmp);
    for(int i=1;i<=n;i++){
        f[i]=i;
        G[i].clear();
    }
    ans=0;
}
int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}
LL kruskal()
{
    int k=0;
    LL sum=0;
    for(int i=1;i<=m;i++){
        int fx=find(edge[i].u);
        int fy=find(edge[i].v);
        if(fx!=fy){
            sum+=edge[i].w;
            G[edge[i].u].push_back(make_pair(edge[i].v,edge[i].w));
            G[edge[i].v].push_back(make_pair(edge[i].u,edge[i].w));
            f[fx]=fy;
            k++;
        }
        if(k==n-1)
            break;
    }
    return sum;
}
int dfs(int pos,int fa)
{
    int cnt=0;
    for(int i=0;i<(int)G[pos].size();i++){
        int v=G[pos][i].first;
        double w=G[pos][i].second;
        int tmp=0;
        if(v!=fa)
            tmp=dfs(v,pos);
        cnt+=tmp;
        ans+=w*tmp*(n-tmp);
    }
    return cnt+1;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
        }
        init();
        LL sum=kruskal();
        dfs(1,0);
        ans=ans*2/n/(n-1);
        printf("%lld %.2lf\n",sum,ans);
    }
    return 0;
}

Hdu 5724 Chess

链接

Chess

题意

n行20列的棋盘，对于每行，如果当前棋子右边相邻格没棋子，则直接走到右边的相邻格，如果有就跳过右侧的棋子走到第一个空格，每个格只能放一个棋子，棋子不能走到棋盘外，两人轮流下棋，每次可任选一行的某一个棋子操作，最后谁无法操作则输，给定每行棋子状态，问先手是否必胜

分析

组合博弈+SG
要预处理出所有状态的Sg值，因为列为固定的20,所以状态压缩后可以存下所有状态。

参考代码

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<stdio.h>
#include<string.h>
const int N=1<<20;
int sg[N+5];
void init()
{
    for(int s=0;s<N;s++){
        bool vis[25]={false};
        for(int i=19;i>=0;i--){
            if(((s>>i)&1)==0)
                continue;
            for(int j=i-1;j>=0;j--){
                if((s&(1<<j))==0){
                    vis[sg[s^(1<<i)^(1<<j)]]=true;
                    break;
                }
            }
        }
        for(int i=0;i<=20;i++){
            if(!vis[i]){
                sg[s]=i;
                break;
            }
        }
    }
}
int main()
{
    int T;
    init();
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        int res=0;
        while(n--){
            int m;
            scanf("%d",&m);
            int s=0;
            for(int i=1;i<=m;i++){
                int x;
                scanf("%d",&x);
                s|=1<<(20-x);
            }
            res^=sg[s];
        }
        if(!res)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

Hdu 5726 GCD

链接

GCD

题意

给你n个数，Q次询问，求(l,r)区间的gcd，以及整个序列中，有多少区间的gcd和询问的GCD是相同的

分析

gcd(al,a​l+1,…,ar)，当l固定不动的时，r=l…n时，我们可以容易的发现,随着r的増大gcd(al,a​l+1,…,ar)是非递增的，我们可以在log级别的时间处理出所有的以L开头的左区间的gcd(al,a​l+1,…,ar).枚举左区间，然后不断二分查找右区间，统计总和即为答案.为了快速查询某一区间的gcd,可以用线段树实现，二分查找也是在线段树上进行。
时间复杂度O(n*(log n)*(log n)）。

参考代码

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
124
#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
const int N=100010;
int a[N];
int tree[N<<2];
map<int,long long> mp;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
void pushUp(int node)
{
    tree[node]=gcd(tree[node<<1],tree[node<<1|1]);
}
void build(int l,int r,int node)
{
    if(l==r){
        tree[node]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,node<<1);
    build(mid+1,r,node<<1|1);
    pushUp(node);
}
int query(int l,int r,int node,int ql,int qr)
{
    if(ql<=l&&r<=qr){
        return tree[node];
    }
    int mid=(l+r)>>1;
    int ans=0;
    if(mid>=ql)
        ans=gcd(ans,query(l,mid,node<<1,ql,qr));
    if(mid<qr)
        ans=gcd(ans,query(mid+1,r,node<<1|1,ql,qr));
    return ans;
}
//以下二分实现，总时间复杂度n*(log n)*(log n)*(log n)，会TLE
/*int binSearch(int n,int l,int r,int g,int now)
{
    while(l<=r){
        int mid=(l+r)>>1;
        int tmp=query(1,n,1,l,mid);
        if(gcd(now,tmp)<g)
            r=mid-1;
        else{
            now=gcd(now,tmp);
            l=mid+1;
        }
    }
    return r+1;
}*/
int binSearch(int l,int r,int node,int ql,int qr,int g,int &now)
{
    if(ql<=l&&r<=qr){
        if(gcd(now,tree[node])<g){
            if(l==r)
                return l;
            int mid=(l+r)>>1;
            int left=0;
            left=binSearch(l,mid,node<<1,ql,qr,g,now);
            if(left!=0)
                return left;
            return binSearch(mid+1,r,node<<1|1,ql,qr,g,now);
        }
        else{
            now=gcd(now,tree[node]);
            return 0;
        }
    }
    int mid=(l+r)>>1;
    int left=0,right=0;
    if(ql<=mid){
        left=binSearch(l,mid,node<<1,ql,qr,g,now);
        if(left!=0)
            return left;
    }
    if(mid<qr)
        right=binSearch(mid+1,r,node<<1|1,ql,qr,g,now);
    return right;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        printf("Case #%d:\n",k);
        int n;
        scanf("%d",&n);
        mp.clear();
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        build(1,n,1);
        for(int i=1;i<=n;i++){
            int g=a[i];
            int left=i;
            int G=query(1,n,1,i,n);
            while(left<=n){
                if(G==g){
                    mp[G]+=n-left+1;
                    break;
                }
                //int pos=binSearch(n,i,n,g,a[i]);
                int now=a[i];
                int pos=binSearch(1,n,1,i,n,g,now);
                mp[g]+=pos-left;
                left=pos;
                g=gcd(g,a[left]);
            }
        }
        int q;
        scanf("%d",&q);
        int l,r;
        while(q--){
            scanf("%d%d",&l,&r);
            int g=query(1,n,1,l,r);
            printf("%d %lld\n",g,mp[g]);
        }
    }
    return 0;
}

Hdu 5727 Necklaces

链接

Necklaces

题意

你有2n个珠子，珠子都阴阳两种，各有n个，你需要弄成一个环形的且阴阳交替的链。
然后给你M条边a,b。表示如果a阳珠与b阴珠相邻，那么a阳珠就会暗淡。
求构造一条链，暗淡的阳珠的最小值

分析

dfs枚举阴珠的排列，然后用匈牙利算法（阴珠排列之间的空位与阳珠匹配）求最大匹配，黯淡的阳珠=n-最大匹配。若阴珠a和阴珠b紧邻i位置左右，若阳珠c可与a和b紧邻，则i位置能放阳珠c,那么建一条c->i的边,然后进行匹配

参考代码

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
#include<stdio.h>
#include<string.h>
#define min(a,b) a<b?a:b
const int N=15;
int n,m,a[N][N];
int ans,order[N],link[N];
bool vis[N],edge[N][N],used[N];
int dfsHgy(int pos)
{
    for(int i=1;i<=n;i++){
        if(edge[pos][i]&&!used[i]){
            used[i]=true;
            if(link[i]==-1||dfsHgy(link[i])){
                link[i]=pos;
                return 1;
            }
        }
    }
    return 0;
}
void dfs(int pos)
{
    if(pos==n+1){
        memset(edge,0,sizeof(edge));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int t=j+1;
                if(j==n)
                    t=1;
                if(!a[i][order[j]]&&!a[i][order[t]])
                    edge[i][j]=1;
            }
        }
        int s=0;
        memset(link,-1,sizeof(link));
        for(int i=1;i<=n;i++){
            memset(used,0,sizeof(used));
            s+=dfsHgy(i);
        }
        ans=min(ans,n-s);
        return;
    }
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            order[pos]=i;
            vis[i]=true;
            dfs(pos+1);
            vis[i]=false;
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0){
            printf("0\n");
            continue;
        }
        memset(a,0,sizeof(a));
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            a[x][y]=1;
        }
        ans=99999;
        memset(vis,0,sizeof(vis));
        order[1]=1;
        dfs(2);
        printf("%d\n",ans);
    }
    return 0;
}