2018.10.30 NOIp模拟赛T2 数字对
2024-09-02 01:30:48
【题目描述】
小 H 是个善于思考的学生,现在她又在思考一个有关序列的问题。
她的面前浮现出一个长度为 n 的序列{ai},她想找出一段区间[L, R](1 <= L <= R <= n)。
这个特殊区间满足,存在一个 k(L <= k <= R),并且对于任意的 i(L <= i <= R),ai 都能被 ak 整除。这样的一个特殊区间 [L, R]价值为 R - L。
小 H 想知道序列中所有特殊区间的最大价值是多少,而有多少个这样的区间呢?这些区间又分别是哪些呢?你能帮助她吧。
【输入格式】
第一行,一个整数 n.
第二行,n 个整数,代表 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
【数据范围】
30%: 1 <= n <= 30 , 1 <= ai <= 32.
60%: 1 <= n <= 3000 , 1 <= ai <= 1024.
80%: 1 <= n <= 300000 , 1 <= ai <= 1048576.
100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31.
思路
可以想到所有特殊区间必定满足区间最小值等于区间GCD。于是可以使用ST表来维护这两个东西,最后二分求解。
目测0(nlogn)的复杂度,我觉得海星。
#include <iostream>
#include <cstdio>
#include <cmath> using namespace std; #define MAXN 500005 int n;
int a[MAXN], ans[MAXN], _ans, g[MAXN][];
int minn[MAXN][]; int gcd(int a, int b) {
return b == ? a : gcd(b, a % b);
} bool query(int l, int r) {
int s = log2(r - l + );
return min(minn[l][s], minn[r - ( << s) + ][s]) == gcd(g[l][s], g[r - ( << s) + ][s]);
} bool judge(int lim) {
int tmp = _ans;
_ans = ;
for(int i = ; i <= n - lim; ++i)
if(query(i, i + lim))
ans[++_ans] = i;
if(_ans == )
return _ans = tmp, false;
return true;
} int main() {
freopen("pair.in", "r", stdin);
freopen("pair.out", "w", stdout); scanf("%d", &n); for(int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
minn[i][] = g[i][] = a[i];
} for(int j = ; j <= ; ++j)
for(int i = ; i + ( << j) - <= n; ++i)
minn[i][j] = min(minn[i][j - ], minn[i + ( << (j - ))][j - ]),
g[i][j] = gcd(g[i][j - ], g[i + ( << (j - ))][j - ]); int l = , r = n, maxL;
while(l <= r) {
int mid = (l + r) >> ;
if(judge(mid))
l = mid + , maxL = mid;
else
r = mid - ;
} printf("%d %d\n", _ans, maxL);
for(int i = ; i <= _ans; ++i)
printf("%d ", ans[i]);
printf("\n"); fclose(stdin);
fclose(stdout); return ;
}
点击查看代码qwq
最新文章
- 基于DDS的任意波形发生器
- Numerical Optimization: Understanding L-BFGS
- 使用匿名函数在回调函数中正确访问JS循环变量
- POI实现word文档转html文件
- sql server查询出的结果中添加一列序列行
- 发布项目MVC4-EF6.0出错
- UrlPathEncode与UrlEncode的区别
- oracle学习----逻辑读
- QT绘制系统简介
- Linux常用使用技巧
- cygwin下配置alias
- Nignx入门location、root配置
- javaweb项目环境搭建,jdk,tomcat,myeclipse,sqlserver安装 配置
- python数据库多字段插入
- 前端es6基础语法
- Uart串口
- 论文阅读笔记三十八:Deformable Convolutional Networks(ECCV2017)
- 初步掌握node的路由控制
- python 之模块之 xml.dom.minidom解析xml
- FireFox 火狐主页被劫持