专栏文章

题解: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

水一发热身赛题解。

分析题意

找所有是至少是 n1n-1 个数倍数的下标。

分析做法

对于两个数 x,yx,y 仅当 xyx\leq yyy 才有可能是 xx 的倍数。
所以仅当当前的 aia_i 为最大值或次大值时,aia_i 才有可能为剩下 nnn1n-1 个数的倍数。
所以我们只需找到该序列的最大值与次大值,判断是否符合条件即可。
时间复杂度 O(nlogn)O(n\log{n}),空间复杂度 O(n)O(n)

代码

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 条评论,欢迎与作者交流。

正在加载评论...