HDU 5288 OO’s Sequence-白红宇

HDU 5288 OO’s Sequence

阅读量：5223 次

发布时间：2019-06-14

本文共 1772 字，大约阅读时间需要 5 分钟。

题意：给一个序列，函数f(l, r)表示在[l, r]区间内有多少数字不是其他数字的倍数，求所有区间的f(l, r)之和。

解法：第一次打多校……心里还有点小激动……然而一道签到题做了俩点……呜呜呜……今天的题还算简单……明天就更难了……写个题解纪念一下多校……

对于序列中的每一个数，要找到从它的位置起向左右找最远连续不能被它整除的数的位置设为l和r，这个数的位置为pos，答案就是(pos - l + 1) * (r - pos + 1)，只要分析一下样例就可以得到这个式子……然后为了找到l和r，先预处理出每个数的倍数，分别正序和倒序遍历序列，每次对标记用的数组更新倍数对应的因数位置，等遍历到这个倍数时就可以知道最近的因数位置了。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define LL long longusing namespace std;vector 
                   
                     v[10005];int num[100005];const int mod = 1e9 + 7;void init(){ for(int i = 1; i < 10005; i++) { for(int j = 1; j * j <= i; j++) { if(i % j == 0) { v[j].push_back(i); if(j * j != i) v[i / j].push_back(i); } } }}int s[10005], flag[10005];int minn1[100005], minn2[100005];int main(){ int n; init(); while(~scanf("%d", &n)) { for(int i = 0; i < n; i++) { scanf("%d", &num[i]); } int ans = 0; for(int i = 0; i < n; i++) { minn1[i] = n - 1, minn2[i] = 0; } memset(s, 0, sizeof s); memset(flag, 0, sizeof flag); for(int i = 0; i < n; i++) { int len = v[num[i]].size(); minn1[i] = s[num[i]]; if(flag[num[i]]) minn1[i]++; for(int j = 0; j < len; j++) { flag[v[num[i]][j]] = 1; s[v[num[i]][j]] = i; } } for(int i = 0; i < 10005; i++) s[i] = n - 1; memset(flag, 0, sizeof flag); for(int i = n - 1; i >= 0; i--) { int len = v[num[i]].size(); minn2[i] = s[num[i]]; if(flag[num[i]]) minn2[i]--; for(int j = 0; j < len; j++) { flag[v[num[i]][j]] = 1; s[v[num[i]][j]] = i; } } for(int i = 0; i < n; i++) { ans += (i - minn1[i] + 1) * (minn2[i] - i + 1) % mod; if(ans > mod) ans -= mod; } printf("%d\n", ans); } return 0;}

转载于:https://www.cnblogs.com/Apro/p/4666008.html

你可能感兴趣的文章