[CSP-S模拟测试]:D（暴力+剪枝）
2024-09-04 20:23:23
题目传送门（内部题47）
输入格式
第一行一个正整数$n$。
第二行$n$个正整数，表示序列$A_i$。
输出格式
一行一个正整数，表示答案。
样例
样例输入：
5
30 60 20 20 20
样例输出：
80
数据范围与提示
样例解释：
最后四个元素形成的子序列权值最大。
数据范围：
对于前$30\%$的数据：$n\leqslant 2,000$
对于所有数据：
$1\leqslant n\leqslant {10}^5$
$1\leqslant A_i\leqslant {10}^9$
题解
再一次没有打正解……
$0\%$算法：
暴力枚举区间显然是$\Theta(n^2)$的，所以我们考虑$QJ$测试点，不得不承认这道题的数据不好造，所以我们可以当当前扫到的$a>gcd$时跳出即可。
毫无正确性，就是想吐槽一下出题人的数据。
不过说了也没用，真正考场上谁敢打呢？
时间复杂度：$\Theta($玄学$)$。
期望得分：$0$分。
实际得分：$100$分。
$100\%$算法：
暴力都会，我们现在考虑剪枝。
$\alpha.$将所有数求一个$gcd$，然后都把它们除这个$gcd$，最后答案记得乘上就好了。
$\beta.$如果以当前的$gcd$进行到序列最后也不能更新答案，那么$break$。
你可能会觉得会被卡成$\Theta(n^2)$，但是仔细分析一下会发现，最劣的情况即为等比数列，而等比数列长度不会长于$、\log \max(A_i)$，所以我们最多会将整个数列扫$\log \max(A_i)$遍。
时间复杂度：$\Theta(n\log \max(A_i)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
$0\%$算法：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100001];
long long ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
int gcd=a[i];
for(int j=i+1;j<=n;j++)
{
gcd=__gcd(gcd,a[j]);
if(1LL*(n-i+1)*gcd<=ans||gcd<a[j])break;
if(gcd==1){ans=n-i+1;break;}
ans=max(ans,1LL*(j-i+1)*gcd);
}
}
printf("%lld",ans);
return 0;
}
$100\%$算法：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100001];
int GCD;
long long ans;
int main()
{
scanf("%d%d",&n,&a[1]);GCD=a[1];
for(int i=2;i<=n;i++)
{
scanf("%d",&a[i]);
GCD=__gcd(GCD,a[i]);
}
for(int i=1;i<=n;i++)
{
a[i]/=GCD;
ans=max(ans,1LL*a[i]);
}
for(int i=1;i<=n;i++)
{
int gcd=a[i];
for(int j=i+1;j<=n;j++)
{
gcd=__gcd(gcd,a[j]);
if(1LL*(n-i+1)*gcd<=ans)break;
ans=max(ans,1LL*(j-i+1)*gcd);
}
}
printf("%lld",ans*GCD);
return 0;
}
rp++
最新文章
- js 实现图片实时预览
- 【转】通过Hibernate将数据 存入oracle数据库例子
- ecs CentOS 7 安装 mysql (mariadb)
- JavaScript 全局对象
- HTML在IE中的条件注释
- [css] 自适应布局 移动端自适应
- /var/spool/postfix/maildrop小文件太多造成inode索引使用完解决
- C#Lambda表达式学习日记
- JavaNIO深入学习
- 【待整理】MySQL alter table modify vs alter table add产生state不一样
- 最长k可重区间集问题
- idea构建maven多项目web架构
- SpringBoot数据库集成-Mybatis
- hibernate--博客
- Jmeter实现接口自动化测试
- BZOJ 3253 Fence Repair 哈夫曼树 水题
- 【ActiveMQ入门-10】ActiveMQ学习-通配符+异步接收
- [Android Pro] AtomicInteger的用法
- oracle的START WITH CONNECT BY PRIOR用法
- 05-maven学习-构建web项目