2016 Hdu 多校赛第二场

发表于   |   分类于

Hdu 5734 Acperience

链接

Acperience

题意

已知 $W=(w_1,w_2,…,w_n)$ ,求$\Sigma {(w_i-\alpha * b_i)^2}$的最小值
其中$B=(b_1,b_2,…,b_n)(b_i \in {+1,-1}),\alpha \ge 0$

分析

设$F(\alpha)=\Sigma {(w_i-\alpha * b_i)^2}$,F的最小值即为所求答案。要想所F最小，每一项的值都必须最小。
$ \alpha $一定时，当$ w_i \le 0,{(w_i + \alpha)}^{2} = (|w_i| - \alpha)^2 $最小，当$ w_i>0,(w_i- \alpha )^2 $最小
即$b_i$与$w_i$同符号,可得$F=\Sigma {(|w_i|-\alpha)^2}=\Sigma {w_{i}^{2}}-2* \alpha *sum+n* \alpha ^2$
其中sum=|w1| + |w2| +…+ |wn|,F是开口向上的抛物线，当$\alpha = sum/n$时取最小值.化简得
$$F=\Sigma {w_{i}^{2}} -sum*sum/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
#include<stdio.h>
#include<string.h>
typedef long long LL;
const int N=100010;
LL w[N];
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        LL sum=0;
        LL ansx=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&w[i]);
            if(w[i]<0) w[i]=-w[i];
            sum+=w[i];
            ansx+=w[i]*w[i];
        }
        ansx=ansx*n-sum*sum;
        LL ansy=n;
        LL g=gcd(ansx,ansy);
        ansx/=g;
        ansy/=g;
        printf("%lld/%lld\n",ansx,ansy);
    }
    return 0;
}

Hdu 5738 Eureka

链接

Eureka

题意

一个好的集合P：$(u, v \in P, u \ne v)$,对于任何$w \in P,f(u,v) \ge g(u,v,w)$
$f(u,v)=\sqrt{(x_u-x_v)^2+(y_u-y_v)^2},g(u,v,w)=\frac{f(u,v)+f(v,w)+f(w,u)}{2}$
给一个包含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
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1010;
const int mod=1e9+7;
typedef long long LL;
struct point{
    int x,y;
    bool operator<(const point& a) const{
        if(x!=a.x)
            return x<a.x;
        return y<a.y;
    }
}p[N];
struct rate{
    int kx,ky;
    bool operator<(const rate& a) const{
        if(kx!=a.kx)
            return kx<a.kx;
        return ky<a.ky;
    }
};
bool vis[N];
vector<rate> ve;
LL two[N];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
void init()
{
    two[0]=1;
    for(int i=1;i<=1001;i++)
        two[i]=two[i-1]*2LL%mod;
}
void calRate(point a,point b)
{
    rate tmp;
    tmp.kx=a.x-b.x;
    tmp.ky=a.y-b.y;
    int g=gcd(tmp.kx,tmp.ky);
    tmp.kx/=g;
    tmp.ky/=g;
    ve.push_back(tmp);
}
int main()
{
    int T;
    scanf("%d",&T);
    init();
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        sort(p,p+n);
        memset(vis,false,sizeof(vis));
        LL ans=0;
        for(int i=0;i<n;i++){
            if(vis[i])
                continue;
            int cnt=1; //计算重点个数
            ve.clear();
            for(int j=i+1;j<n;j++){
                if(p[i].x==p[j].x&&p[i].y==p[j].y){
                    cnt++;
                    vis[j]=true;
                    continue;
                }
                calRate(p[i],p[j]);
            }  //t1:仅包含重点的best set
            LL t1=(two[cnt]-cnt-1+mod)%mod;
            ans=(ans+t1)%mod;
            t1+=cnt;  //t1:至少选一个重点的组合数
            sort(ve.begin(),ve.end());
            int l=0,r,sz=(int)ve.size();
            while(l<sz){
                for(r=l+1;r<sz;r++){
                    if((LL)ve[l].kx*ve[r].ky!=(LL)ve[l].ky*ve[r].kx)
                        break;
                }
                LL t2=two[r-l]-1;  //t2:至少选一个非重点的组合数
                ans=(ans+t1*t2%mod)%mod;
                l=r;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Hdu 5739 Fantasia

链接

Fantasia

题意

一个连通图的权重为其所有结点权值之积；一个不连通图的价值为其所有连通分量权重的价值之和。一个无向图G，删除第i个顶点后的子图为$G_i$,其权重为$z_i$.已知无向图G的n个顶点权值w[i]，以及m条边,求
$$ S = (\sum\limits_{i=1}^{n}i\cdot z_i) \text{ mod } (10^9 + 7)$$

分析

若某一连通分量的权重为 mul,删除顶点u后的权重分四种情况：
1.若u为非关节点
1）u为孤立点：删除后该连通分量权重为0
2）非孤立点：mul/w[u]
2.u为关节点
1）u该连通分量为根:子树的权重只和sum
2) 非根：mul/pro+sum (pro:删除该点会分离的所有子树的权重乘积（包括u点)）
首先可dfs求出图G各个连通分量的权重,以及整个图G的权重sumMul
再用tarjan算法求删除各个顶点后的权重，最后计算答案
注：本题涉及到除法和mod，需要求乘法逆元

参考代码

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
125
126
127
128
129
130
131
132
133
134
#include<stdio.h>
#include<string.h>
#include<algorithm>
typedef long long LL;
using namespace std;
const int N=100010;
const int mod=(int)1e9+7;
const int INF=99999999;
#define min(a,b) a<b?a:b
struct Edge{
    int to;
    int next;
}edge[N<<2];
LL w[N],mul[N],ans[N],sumMul;
int n,m,cnt,k,head[N],vt[N];
int low[N],dfn[N];
bool vis[N];
void addEdge(int u,int v)
{
    edge[k].to=v;
    edge[k].next=head[u];
    head[u]=k++;
}
void init()
{
    k=0;
    cnt=1;
    sumMul=0;
    memset(head,-1,sizeof(head));
    memset(vis,false,sizeof(vis));
    memset(low,INF,sizeof(low));
    memset(dfn,0,sizeof(dfn));
}
void dfs(int u)
{
    mul[u]=w[u];
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(!vis[v]){
            vis[v]=true;
            dfs(v);
            mul[u]=mul[u]*mul[v]%mod;
        }
    }
}
LL powMod(LL a,LL b)
{
    LL res=1;
    while(b){
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
LL tarjan(int u,int root)
{   //res以u为根的子树权值乘积
    //pro分离出的子树乘积和根结点u的总乘积
    //sum子树的乘积和
    LL res=w[u],sum=0,pro=w[u];
    low[u]=dfn[u]=cnt++;
    int child=0;
    bool flag=false;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(!dfn[v]){
            child++;
            LL tmp=tarjan(v,root);
            low[u]=min(low[u],low[v]);
            if((u==root&&child>=2)||(u!=root&&low[v]>=dfn[u])){
                flag=true;
            }
            if(u==root||(u!=root&&low[v]>=dfn[u])){
                sum=(sum+tmp)%mod;
                pro=(pro*tmp)%mod;
            }
            res=res*tmp%mod;
        }
        else{
            low[u]=min(low[u],dfn[v]);
        }
    }
    ans[u]=(sumMul-mul[root]+mod)%mod;
    if(!flag){ //非关节点
        if(u!=root||head[u]!=-1){ //非孤立点
            ans[u]=(ans[u]+mul[root]*powMod(w[u],mod-2))%mod;
        }
    }
    else{ //关节点
        if(u==root){ //根结点
            ans[u]=(ans[u]+sum)%mod;
        }
        else{
            ans[u]=(ans[u]+sum+mul[root]*powMod(pro,mod-2)%mod)%mod;
        }
    }
    return res;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%lld",&w[i]);
        init();
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            addEdge(x,y);
            addEdge(y,x);
        }
        int num=0;
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                vt[num++]=i;
                vis[i]=true;
                dfs(i);
                sumMul=(sumMul+mul[i])%mod;
            }
        }
        for(int i=0;i<num;i++){
            tarjan(vt[i],vt[i]);
        }
        LL ansS=0;
        for(int i=1;i<=n;i++){
            ansS=(ansS+ans[i]*i%mod)%mod;
        }
        printf("%lld\n",ansS);
    }
    return 0;
}

Hdu 5742 It’s All In The Mind

链接

It’s All In The Mind

题意

对于$ i \in {1,2,…,n},0 \le a_i \le 100,a_1 \ge a_2 \ge … \ge a_n$,且这些元素的和不能为0
已知这个序列中的m个数，求$\frac{a_1+a_2}{\sum_{i=1}^{n}{a_i}}$的最大值

分析

分数的分母越小，分数值越大，根据序列是非递增的性质，可求出a3,a4…an中未知的值，
然后枚举a[1]+a[2]的和，即可求出最大值

参考代码

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
#include<stdio.h>
#include<string.h>
const int N=110;
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int a[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        int sum=0;
        memset(a,-1,sizeof(a));
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            a[x]=y;
            if(x!=1&&x!=2)
                sum+=y;
        }
        if(n==2||a[2]==0){
            printf("1/1\n");
            continue;
        }
        if(a[n]==-1)
            a[n]=0;
        for(int i=n;i>=3;i--){
            if(a[i]==-1){
                a[i]=a[i+1];
                sum+=a[i];
            }
        }
        int _min,_max;  //记录a[1]+a[2]和的上下界
        if(a[1]==-1&&a[2]==-1){  //a[3]<=a[1],a[2]<=100
            _min=2*a[3];
            _max=200;
        }
        else if(a[1]==-1&&a[2]!=-1){ //a[2]<=a[1]<=100
            _min=a[2]+a[2];
            _max=100+a[2];
        }
        else if(a[1]!=-1&&a[2]==-1){ //a[3]<=a[2]<=a[1]
            _min=a[1]+a[3];
            _max=a[1]+a[1];
        }
        else if(a[1]!=-1&&a[2]!=-1){
            _min=a[1]+a[2];
            _max=a[1]+a[2];
        }
        int ansx=_min,ansy=sum+_min;
        for(int i=_min;i<=_max;i++){
            int tmpx=i;
            int tmpy=sum+i;
            if(ansx*tmpy<ansy*tmpx){
                ansx=tmpx;
                ansy=tmpy;
            }
        }
        int g=gcd(ansx,ansy);
        ansx/=g;
        ansy/=g;
        printf("%d/%d\n",ansx,ansy);
    }
    return 0;
}

Hdu 5744 Keep On Movin

链接

Keep On Movin

题意

有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
#include<stdio.h>
#include<string.h>
#include<queue>
const int N=100010;
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        int sum=0,cnt=0;
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            if(x&1)
                cnt++;
            sum+=x/2;
        }
        int ans=0;
        if(cnt==0)
            ans=sum*2;
        else{
            int k=sum/cnt;
            ans=k*2+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

Hdu 5745 La Vie en rose

链接

La Vie en rose

题意

给定一个长度为n的匹配串s和长度为m的模式串p，p可以进行变换，变换规则是任意交换两个相邻的字符,但是每个字符最多（被）交换一次。结果输出一个n位的二进制，对于匹配串的字符位置i，如果s的子串（si,si+1,si+2,…,si+m-1）可以由p串变换得出的话，则这个位置输出“1”，否则输出“0”

分析

题目给出的变换规则其实就是交换相邻元素, 并且每个元素最多交换一次.暴力即可

参考代码

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
#include<stdio.h>
#include<string.h>
const int N=100010;
char s[N],p[N];
char ans[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        scanf("%s%s",s,p);
        memset(ans,'0',sizeof(ans));
        for(int i=0;i<n-m+1;i++){
            int flag=1;
            for(int j=0;j<m;j++){
                if(p[j]==s[j+i])
                    continue;
                if(j!=m-1&&p[j]==s[j+i+1]&&p[j+1]==s[j+i]){
                    j++;
                }
                else{
                    flag=0;
                    break;
                }
            }
            ans[i]=flag+'0';
        }
        ans[n]=0;
        printf("%s\n",ans);
    }
    return 0;
}