首页 > 代码库 > 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 山峰和分段
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。