题目:D. Pair of Numbers
思路:预处理每个数最右边和最左边能够整除它的下标,然后暴力,记得去重,不然会Wa
tag :dp + 预处理
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <vector> #include <map> using namespace std; #define maxn 300010 int l[maxn],r[maxn],num[maxn]; vector<int>ans; int main() { ans.clear(); int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&num[i]); l[i]=r[i]=i; } int index; for(int i=2;i<=n;i++) { index=i-1; while(num[index]%num[i]==0 && index>=1) index=l[index]-1; l[i]=l[index+1]; } for(int i=n-1;i>=1;i--) { index=i+1; while(num[index]%num[i]==0 && index<=n) index=r[index]+1; r[i]=r[index-1]; } int mx=-1; for(int i=1;i<=n;i++) { //printf("%d %d %dn",l[i],num[i],r[i]); //mx=max(mx,r[i]-l[i]); if(mx<r[i]-l[i]) { ans.clear(); mx=r[i]-l[i]; ans.push_back(l[i]); } else if(mx==r[i]-l[i]) { ans.push_back(l[i]); } } ans.erase(unique(ans.begin(),ans.end()),ans.end()); printf("%d %dn",ans.size(),mx); sort(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) { printf("%d",ans[i]); if(i+1==ans.size()) printf("n"); else printf(" "); } return 0; }
最后
以上就是天真仙人掌最近收集整理的关于Codeforces 209 div2 D. Pair of Numbers的全部内容,更多相关Codeforces内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复