【HDOJ 5288】OO’s Sequence
枚举 题目给了个函数f(l,r) 求区间[l,r]有多少个数满足区间内任何一个数都不为他的约数 算出i [1,n] 每个位置的数的最大满足范围 即该位置的数对结果的贡献 两个函数 l[] r[] 存储每个位置的数贡献范围
譬如: 5 4 3 2 1 2 4 五个数的贡献范围分别为 (0,2) (0,4) (0,4) (3,6) (4,6)
计算区间范围 开一个数组pre[]存放遍历到此时每个数字在之前出现的位置 i(1->n) 每遍历一个数 更新之前出现的该数的倍数的区间右边界 (r[ pre[ num[i] ] ]) i(n->1) 每遍历一个数 更新之前出现的该数的倍数的区间左边界 (l[ pre[ num[i] ] ]) 最终结果为i(1->n) (i-l[i])*(r[i]-i) 的累加和对10^9+7取余
代码如下
;int num[100005],l[100005],r[100005],pre[100005];int main(){int n,j,i,mm;ll ans;while(~scanf(“%d”,&n)){mm = ans = 0;memset(pre,0,sizeof(pre));for(i = 1; i <= n; ++i){scanf(“%d”,&num[i]);mm = max(mm,num[i]);l[i] = 0;r[i] = n+1;for(j = num[i]; j <= mm; j += num[i])//找倍数时用了一个最大值变量mm进行剪枝 速度快很多 后面找左边界时同理if(pre[j] && r[pre[j]] > i) r[pre[j]] = i;pre[num[i]] = i;}memset(pre,0,sizeof(pre));mm = 0;for(i = n; i >= 1; –i){mm = max(mm,num[i]);for(j = num[i]; j <= mm; j += num[i])if(pre[j] && l[pre[j]] < i) l[pre[j]] = i;pre[num[i]] = i;}for(i = 1; i <= n; ++i){ans = (ans+((i-l[i])*(r[i]-i))%mod)%mod;}printf(“%lld\n”,ans);}return 0;}
，渐渐少了联络，友谊就变的淡了，所以，抽点时间，联络朋友一起聊聊天，
