Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


select解题报告

题目描述

LYK带着悲伤行走在黑暗里。寂穆的夜空没有星月的点缀,身旁的树木、房屋、万事万物连同你自己,都融于宇宙的虚无缥缈之中。黑暗,压抑、膨胀、严严实实包围整个世界,LYK害怕,彷徨,无奈。突然,眼前出现一扇窗,流漏出点点昏黄的灯光。LYK欣喜地奔去看,原来这里有n个数字,LYK深深地被它们吸引。
这个问题是这样的,如果一个区间[L,R]存在一个数ai,使得这个数是这个区间所有数的约数,那么[L,R]这段区间,是一段好区间。
现在,LYK想知道最长的好区间的长度是多少,并且它想知道最长的好区间具体的位置,如果有多个,从小到大输出它们的左端点。


解题思路

枚举每一个点,向左向右拓展,直到不能拓展,记录长度,与最大值比较,然后可以直接跳到向右拓展的最末位置,继续进行拓展。


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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
void read(int &x){
char c = getchar(); x = 0;
while(c < '0' || c > '9') c = getchar();
while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar();
}
int a[300005],len,maxn,sum;
int dot[300005],top;
int main(){
freopen("select.in","r",stdin);
freopen("select.out","w",stdout);
int n;read(n);
for(int i = 1;i <= n;i++)
read(a[i]);
for(int i = 1;i <= n;i++){
len = 1;
int l = i-1;
while(l > 0){
if(!(a[l]%a[i]))
len++;
else break;
l--;
} l++;
int r = i+1;
while(r <= n){
if(!(a[r]%a[i]))
len++;
else break;
r++;
} r--;
if(maxn == len)
sum++,dot[++top]=l,i=r;
if(len > maxn){
top=0;
sum=1;
maxn = len;
dot[++top]=l;
i=r;//优化,直接从r往右找。
}
}
printf("%d %d\n",sum,maxn);
for(int i = 1;i <= sum;i++)
printf("%d ",dot[i]);
return 0;
}

Markdown

最近的文章

stick解题报告

题目描述 LYK有很多木棍,具体的,总共有n根,且每根木棍都有一个长度。为了方便起见,我们可以用一个正整数ai表示第i根木棍的长度。LYK有一把小刀,但这把小刀由于削木棍很不方便,对于一根木棍而言,它只能用这把小刀削掉恰好1的长度。LYK觉得如果4根木棍头尾相连能恰好拼成长方形,说明这4根木棍是可以 …

于  模拟 继续阅读
更早的文章

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in …

于 继续阅读