校长的收藏(洛谷 U4534)
2024-09-30 23:09:11
题目背景
XS中学的校长喜欢收集手办,家里面都是价值不菲的手办。
校长喜欢给手办们排队并且对于某些些区间内的手办喜爱有加。
现在,校长外出散步(找乐子),你潜入他的房间打算借(偷走)他的手办炫耀一下。
题目描述
现在有 一列 手办,并且校长给每个手办设置了独一无二的编号ai(可能 重复 ,等等,那怎么独一无二)。
现在给出区间喜爱度的定义:
如果一个区间【L,R】(第L个手办只第R个手办,L<=R),这个区间满足,存在一个k(L<= k <= R),并且对于任意的i(L<=x<=R),ai都能被ak整除。这样的一个区间 【L,R】的区间喜爱度为 R-L 。
为了让虚荣心最大化,你需要求出最大区间喜爱度和喜爱度最大的区间的个数(有交集的两个不完全重合的区间视为不同的两个区间)然后取走。
输入输出格式
输入格式:
第一行,一个整数n.
第二行,n个整数,第i个数代表第i个手办的编号ai
输出格式:
第一行两个整数,num和val,表示区间喜爱度最大的区间的个数以及最大区间喜爱度。
第二行num个整数,按升序输出每个喜爱度最大的区间的L.
输入输出样例
输入样例#1:
5
4 6 9 3 6
输出样例#1:
1 3
2
输入样例#2:
5
2 3 5 7 11
输出样例#2:
5 0
1 2 3 4 5
说明
1 <= n <= 500000 , 1 <= a < 2 ^ 31
保证数据随机。
Tips:有巧妙的搜索/枚举算法,也可以用令人%拜的RMQ或者ST表 硬刚。
/*
巧(zhi)妙(jie)枚举一个区间的ak,然后用这个ak向两边拓展找否个要求的区间,更新答案,要注意的是区间不能重复。
*/
#include<cstdio>
#include<iostream>
#define M 500010
using namespace std;
int a[M],b[M],tot,ans,n;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
{
int ll=i,rr=i;
while()
{
if(ll==)break;
if(a[ll-]%a[i]!=)break;
ll--;
}
while()
{
if(rr==n)break;
if(a[rr+]%a[i]!=)break;
rr++;
}
if(rr-ll>ans)
{
tot=;ans=rr-ll;
b[tot]=ll;
}
else if(rr-ll==ans&&ll!=b[tot])
{
b[++tot]=ll;
}
}
printf("%d %d\n",tot,ans);
for(int i=;i<=tot;i++)
printf("%d ",b[i]);
return ;
}
最新文章
- Cassandra中的数据一致性
- atitit 业务 触发器原理.&#160;与事件原理 docx
- session 学习
- python 登陆接口
- iOS应用程序开发之应用间的跳转(用着微信等第三方分享登陆)
- iOS 学习笔记 六 (2015.03.28)常见错误
- hibernate.cfg.xml 配置(摘录)
- Java开发者常犯的十个错误
- 不适用临时空间,交换变量a和b
- allegro 的光绘层概念
- 查找MobileSafari WebKit revision number的方法
- 业务类接口在TCP,HTTP,BLL模式下的实例 设计模式混搭 附源码一份
- ActionBarSherlock,SlidingMenu
- 小程序生成海报图片(或者原有的)并下载,&;&;相册授权&;&;按钮拉起二次授权
- Tp-validate进阶
- LeetCode OJ 94. Binary Tree Inorder Traversal
- unity中生成一个GUI格子(始终居中)
- Pr学习日记
- eclipse中Maven项目jar问题
- 【微信小程序】在微信开发工具上七牛云的图片可以看到,但是在真机上看不到的原因解决