首页 > 代码库 > 51nod - 1285 山峰和分段

51nod - 1285 山峰和分段

题目链接:1285 山峰和分段

技术分享

 

思路:枚举N的因子,然后检查每一段是不是都有山峰就好了。检查的时候用 RMQ。预处理时间复杂度为O(nlogn),总的复杂度也是这么多。

所说有O(n)的解法,不过没想出来。

 

 1 #include <bits/stdc++.h> 2 using namespace std; 3  4 std::vector<int> v; 5 const int maxn = 5e4 + 100; 6 bool s[maxn][20]; 7 int n, t; 8 void RMQ() { 9     for(int i=1; i<20; i++) {10         for(int j=1; j<=n; j++) {11             if(j+(1<<(i-1)) <= n) s[j][i] = s[j][i-1] || s[j+(1<<(i-1))][i-1];12         }13     }14 }15 bool query(int l, int len) {16     int t = (int)log2(len+0.5);17     return s[l][t] || s[l+len-(1<<t)][t];18 }19 std::vector<int> fac(int n) {20     std::vector<int> vv;21     for(int i=1; i*i<=n; i++) {22         if(n%i==0) {23             vv.push_back(i);24             if(i*i!=n) vv.push_back(n/i);25         }26     }27     sort(vv.begin(), vv.end());28     return vv;29 }30 int main() {31     memset(s, 0, sizeof(s));32     scanf("%d", &n);33     for(int i=0; i<n; i++) {34         scanf("%d", &t);35         v.push_back(t);36     }37     for(int i=1; i<n-1; i++) {38         if(v[i] > v[i-1] && v[i] > v[i+1]) s[i+1][0] = true;39     }40     RMQ();41     bool ok = false;42     int ans = 0;43     std::vector<int> vv = fac(n);44     for(int i=0; i<vv.size(); i++) {45         bool ook = true;46         int len = vv[i];47         for(int j=1; j<n; j+=len) {48             if(!query(j, len)) {49                 ook = false; break;50             }51         }52         if(ook) ok = true;53         if(ok) {54             ans = n/len; break;55         }56     }57     printf("%d\n", ans);58     return 0;59 }

 

51nod - 1285 山峰和分段