专栏文章
题解:P14444 [ICPC 2025 Xi'an Practice] Great Indices
P14444题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minc4wx9
- 此快照首次捕获于
- 2025/12/01 23:59 3 个月前
- 此快照最后确认于
- 2025/12/01 23:59 3 个月前
P14444 [ICPC 2025 Xi'an Practice] Great Indices
水一发热身赛题解。
分析题意
找所有是至少是 个数倍数的下标。
分析做法
对于两个数 仅当 时 才有可能是 的倍数。
所以仅当当前的 为最大值或次大值时, 才有可能为剩下 或 个数的倍数。
所以我们只需找到该序列的最大值与次大值,判断是否符合条件即可。
时间复杂度 ,空间复杂度 。
代码
CPP#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
int a[300005];
vector<int> all;
signed main(){
cin>>T;
while(T--){
all.clear();
cin>>n;
int maxx=-1,maxx2=-1;
for(int i=1;i<=n;i++){
cin>>a[i];
maxx=max(maxx,a[i]);
}
for(int i=1;i<=n;i++){
if(a[i]!=maxx){
maxx2=max(maxx2,a[i]);
}
}
int flag1=0,flag2=0;
for(int i=1;i<=n;i++){
if(maxx%a[i]!=0){
flag1++;
}
}
for(int i=1;i<=n;i++){
if(maxx2%a[i]!=0){
flag2++;
}
}
if(flag1<=1){
for(int i=1;i<=n;i++){
if(a[i]==maxx){
all.push_back(i);
}
}
}
if(flag2<=1){
for(int i=1;i<=n;i++){
if(a[i]==maxx2){
all.push_back(i);
}
}
}
sort(all.begin(),all.end());
cout<<all.size()<<"\n";
for(int i=0;i<all.size();i++){
cout<<all[i]<<" ";
}
cout<<"\n";
}
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...