2015 Hdu 多校赛第一场

发表于   |   分类于

第一场比赛，基本是在打酱油。。。
xiaom

Hdu 5288 OO’s Sequence

链接

OO’s Sequence

题意

$f(l,r): 满足a_i \% a_j \neq 0 的i的个数 (i \in [l,r],j \in [l,r],j \neq i) $
已知n个数 $a_1,a_2,…a_n$,求
$$\sum _ {i=1}^{n}\sum _ {j=i}^{n}f(i,j) \ mod \ (10^{9}+7)$$

分析

$这个题实质是对于一个包含 a_i的区间，如果a_i符合上述条件，$
$即对于a_j,a_i \% a_j \neq 0，则a_j不是a_i的因子 $
$对于每一个数 a_i,分别向左向右去找离它最近的因子的下标L[i],R[i],$
ans+=(i-L[i])*(R[i]-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
#include<stdio.h>
#include<string.h>
#include<algorithm>
const int N=100000;
#define Mod 1000000007
using namespace std;
int a[N+10],id[N+10],L[N+10],R[N+10];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(id,0,sizeof(id));
        for(int i=1;i<=n;i++){    //向左找最近的因子下标
            L[i]=0;
            for(int j=1;j*j<=a[i];j++)
                if(a[i]%j==0){   //j和a[i]/j都为a[i]的因子
                    if(id[j])
                        L[i]=max(L[i],id[j]);  //取最大的下标即为最近的
                    if(id[a[i]/j])
                        L[i]=max(L[i],id[a[i]/j]);
                }
            id[a[i]]=i;  //记录a[i]的下标
        }
        memset(id,0,sizeof(id));
        for(int i=n;i>=1;i--){    //向右找最近的因子下标
            R[i]=n+1;
            for(int j=1;j*j<=a[i];j++)
                if(a[i]%j==0){
                    if(id[j])
                        R[i]=min(R[i],id[j]);
                    if(id[a[i]/j])
                        R[i]=min(R[i],id[a[i]/j]);
                }
            id[a[i]]=i;
        }
        long long ans=0;
        for(int i=1;i<=n;i++)
            ans=(ans+(long long)(i-L[i])*(R[i]-i)%Mod)%Mod;
        printf("%I64d\n",ans);
    }
}

Hdu 5289 Assignment

链接

Assignment

题意

一个公司有n个员工，每个员工有一个能力值a[i]，
求有多少个区间满足区间内任意两个员工的能力差值小于k

分析

区间内最大差值即为区间内最大值与最小值的差
只要其差满足条件，则该区间符合条件
左区间l先固定,去找最大区间符合条件，即[l,r-1]符合 那么$ans+=\binom{r-l}{2} + r-l$
然后r不变，l不断加1，直到找到符合条件的 [l,r]为止，那么[l,j-1]会被重复算，需要减掉
为了更快的查询每个区间的最大最小值，用线段树实现的

参考代码

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
#include<stdio.h>
#include<algorithm>
#define INF 1000000007
const int N=100010;
using namespace std;
struct stu{
    int minA,maxA;
}tree[N<<2];
int a[N],minA,maxA;
void pushUp(int node)
{
    tree[node].minA=min(tree[node<<1].minA,tree[node<<1|1].minA);
    tree[node].maxA=max(tree[node<<1].maxA,tree[node<<1|1].maxA);
}
void build(int l,int r,int node)
{
    if(l==r){
        tree[node].maxA=a[l];
        tree[node].minA=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,node<<1);
    build(mid+1,r,node<<1|1);
    pushUp(node);
}
void query(int l,int r,int node,int ql,int qr)
{
    if(ql<=l&&r<=qr){
        maxA=max(maxA,tree[node].maxA);
        minA=min(minA,tree[node].minA);
        return ;
    }
    int mid=(l+r)>>1;
    if(ql<=mid)
        query(l,mid,node<<1,ql,qr);
    if(mid<qr)
        query(mid+1,r,node<<1|1,ql,qr);
}
int main()
{
    int T,n,k;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        build(1,n,1);
        int l=1,r=1;
        long long ans=0,cnt;
        while(l<=n&&r<=n){
            minA=INF,maxA=-INF;
            query(1,n,1,l,r);
            if(maxA-minA<k){
                if(r==n){
                    cnt=r-l+1;
                    ans+=cnt*(cnt-1)/2+cnt;
                }
                r++;
            }
            else{
                cnt=r-1-l+1;
                ans+=cnt*(cnt-1)/2+cnt;
                l++;
                while(l<r){
                    minA=INF,maxA=-INF;
                    query(1,n,1,l,r);
                    if(maxA-minA<k)
                        break;
                    l++;
                }
                if(l<r){
                    cnt=(r-1)-l+1;
                    ans-=cnt*(cnt-1)/2+cnt;
                    r++;
                }
            }
        }
        printf("%I64d\n",ans);
    }
    return 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
35
36
37
38
39
40
41
42
43
44
45
46
int main()
{
    int T,n,k;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        build(1,n,1);
        int l=1,r=1;
        long long ans=0,cnt;
        minA=a[1],maxA=a[1];
        while(l<=n&&r<=n){
            minA=min(minA,a[r]);
            maxA=max(maxA,a[r]);
            if(maxA-minA<k){
                if(r==n){
                    cnt=r-l+1;
                    ans+=cnt*(cnt-1)/2+cnt;
                }
                r++;
            }
            else{
                cnt=r-1-l+1;
                ans+=cnt*(cnt-1)/2+cnt;
                l++;
                while(l<r){
                    minA=INF,maxA=-INF;
                    query(1,n,1,l,r);
                    if(maxA-minA<k)
                        break;
                    l++;
                }
                if(l<r){
                    cnt=(r-1)-l+1;
                    ans-=cnt*(cnt-1)/2+cnt;
                    r++;
                }
                minA=INF,maxA=-INF;
                query(1,n,1,l,r);
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}