首页 > 代码库 > 2015年多校联合训练第一场OO’s Sequence(hdu5288)

2015年多校联合训练第一场OO’s Sequence(hdu5288)

题意:给定一个长度为n的序列,规定f(l,r)是对于l,r范围内的某个数字a[i],都不能找到一个相应的j使得a[i]%a[j]=0。那么l,r内有多少个i,f(l,r)就是几。

问全部f(l,r)的总和是多少。
公式中给出的区间,也就是全部存在的区间。

思路:直接枚举每个数字,对于这个数字,假设这个数字是合法的i,那么向左能扩展的最大长度是多少,向右能扩展的最大长度是多少。那么i为合法的情况就是左长度*右长度(包括i且i是合法的区间总数)。

统计左长度能够推断a[i]的约数是否在前面出现过…由于a[i]<=10000,能够用数组标记一下i左边的全部数字a[k],k

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int Max = 1e5+100;
const int mod = 1e9+7;
int a[Max];
int used[Max];
long long zuo[Max];
long long  you[Max];

int cal(int x)
{
    int m = sqrt(x*1.0);
    int maxi = max(used[1],used[x]);
    for(int i = 2; i <= m; ++i)
    {
        if(x % i == 0)
        {
            maxi = max( max(maxi,used[i]), used[x/i]);
        }
    }

    return maxi;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(used,0,sizeof(used));
        memset(zuo,0,sizeof(zuo));
        memset(you,0,sizeof(you));

        for(int i = 1; i <= n; ++i )
        {
             scanf("%d",a+i);
             zuo[i] = i - cal(a[i]);
             used[a[i]] = i;
        }
        memset(used,0,sizeof(used));
        //反过来求右边。n-i+1,自己模拟下就知道优点
        for(int i = 1; i <= n; ++i)
        {
            you[n-i+1] = i - cal(a[n-i+1]);
            used[a[n-i+1]] = i;
        }

        long long ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            ans +=( zuo[i]*you[i])%mod;
        }

        printf("%lld\n",ans%mod);
    }
    return 0;
}
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

2015年多校联合训练第一场OO’s Sequence(hdu5288)