本文主要是介绍hdu contest day1 1001 OO’s Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1001&cid=589
思路：超级大暴力：枚举l，r，暴力判断每个数，复杂度O(n^4)爆炸了
那么枚举l，r肯定不行了。
换个思路，判断每个数对多少个区间产生了贡献
对于第i个数a[i]，我们分别往左和往右找到第一个约数，他们的位置分别为j-1,k+1
那么a[i]就能对(i-j+1)*(k-j+1)个区间产生贡献
暴力找，O(n^2)爆炸了
然后就是打表找规律时间了。
因为0<a[i]<=10000,经过打表发现，约数最多的数7560也只有64个约数
开10000个vector记录值为0-10000的位置
那么我们就枚举约数，在vector里二分找离现在这个数的位置最近的，更新
复杂度O(64*n*logn)
#include<ctime>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
const int maxn=100010;
const int mod=1e9+7;
using namespace std;
struct data{int a,id;}num[maxn];
int n,divi[maxn][70],cnt[maxn],pri[maxn],minp[10010],maxp[10010];
vector<int> c[maxn];inline bool cmp(data a,data b){return a.a<b.a||(a.a==b.a&&a.id<b.id);}void getdiv(){for (int i=1;i<=10000;i++){for (int j=1;j<=i/2;j++)if (!(i%j)) divi[i][++cnt[i]]=j;divi[i][++cnt[i]]=i;}
}int bs0(int p,int id){int l=0,r=c[p].size()-1,mid=(l+r)>>1,res=0;while (l<=r){if (c[p][mid]<id) res=c[p][mid],l=mid+1;else r=mid-1;mid=(l+r)>>1;}return res;
}
int bs1(int p,int id){int l=0,r=c[p].size()-1,mid=(l+r)>>1,res=n+1;while (l<=r){if (c[p][mid]>id) res=c[p][mid],r=mid-1;else l=mid+1;mid=(l+r)>>1;}return res;
}int main(){getdiv();while (scanf("%d",&n)!=EOF){int ans=0;for (int i=1;i<=10000;i++) c[i].clear();for (int i=1;i<=n;i++){scanf("%d",&num[i].a),num[i].id=i;}sort(num+1,num+1+n,cmp);for (int i=1;i<=n;i++) c[num[i].a].push_back(num[i].id);for (int i=1;i<=n;i++){int t=num[i].a,l=1,r=n;for (int j=1;j<=cnt[t];j++){int x=divi[t][j];if (c[x].size()==0) continue;int p0=bs0(x,num[i].id)+1,p1=bs1(x,num[i].id)-1;l=max(l,p0),r=min(r,p1);}ans=(ans+(r-num[i].id+1)*(num[i].id-l+1))%mod;}printf("%d\n",ans);}return 0;
}这篇关于hdu contest day1 1001 OO’s Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
