专栏文章

题解：AT_abc413_d [ABC413D] Make Geometric Sequence

ssongge888
AT_abc413_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioz6y2e
此快照首次捕获于
2025/12/03 03:33
3 个月前
此快照最后确认于
2025/12/03 03:33
3 个月前
查看原文

AT_abc413_d [ABC413D] Make Geometric Sequence

题意

给你一个序列 aa，确保 aia_i 不为 00，判断是否存在一个 aa 的排列满足等比数列。

题解

先考虑 ai>0a_i>0：
显然先把数列从小到大排序，判断即可，发现直接求公比可能会出现精度损失，可以把除法转换成乘法，对于等比数列，一定有 ai−1×ai+1=ai2a_{i-1} \times a_{i+1}={a_i}^2。
然后考虑如果存在 ai<0a_i<0：
先进行特判：
  1. ∣正数的个数−负数的个数∣|{正数的个数-负数的个数}| 只能是 00 或 11。
  2. 数列中绝对值相同的数字出现次数只能是 11 或 nn。
接下来用一个 map 存下每个数字的正负：
  • 若 ai>0a_i>0，mpai=1mp_{a_i}=1。
  • 若 ai<0a_i<0，mpai=−1mp_{a_i}=-1。
可以发现，现在满足是等比数列的条件是：
mpai−1×mpai+1×ai−1×ai+1=ai2mp_{a_{i-1}} \times mp_{a_{i+1}} \times a_{i-1} \times a_{i+1}={a_i}^2
判断即可。

代码

CPP
#include<bits/stdc++.h>
#define int long long
#define double long double
#define bug cout<<"___songge888___"<<'\n';
using namespace std;
int t;
int n;
int a[200010];
map<int,int> vis,mp;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        int cnt1=0,cnt2=0;
        vis.clear();
        mp.clear();
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]>0){
            	cnt1++;
            	mp[a[i]]++;
				vis[a[i]]=1;
			}
            else if(a[i]<0){
            	cnt2++;
            	a[i]*=-1;
            	mp[a[i]]++;
            	vis[a[i]]=-1;
			}
        }
        int fl=0;
		sort(a+1,a+1+n);
		for(int i=1;i<=n;i++){
			if(mp[a[i]]>1&&mp[a[i]]!=n){
				fl=1;
			}
		}
		if(!fl){
			if(cnt1==0||cnt2==0){
				//不用考虑
			}
			else if(abs(cnt1-cnt2)>1){
				fl=1;
			}
		}
        if(fl){ 
            cout<<"No"<<'\n';
            continue; 
        }
        for(int i=2;i<n;i++){
            if(a[i]*a[i]!=vis[a[i-1]]*vis[a[i+1]]*a[i-1]*a[i+1]){
                fl=1;
                break;
            }
        }
        if(fl){
            cout<<"No"<<'\n';
        }
        else{
            cout<<"Yes"<<'\n';
        }
    }
    return 0;
}
提交记录

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...