题解：P14444 [ICPC 2025 Xi'an Practice] Great Indices

Nottingham_Forest · 2025-11-07 15:41:24 · 题解

题目传送门

思路

此题暴力不可取，考虑优化。

我们注意到要想最少有 n-1 个 a_i 的约数，a_i 只能取最大值和次大值。

于是我们可以记录最大值和次大值，因为有重复，所以我们还得记录所有最大值和次大值的下标。接着我们分别判断最大值和次大值是否满足要求，如是则把下标加入一个用来输出的 p 数组。

最后将 p 数组从小到大排序即可。

注意要特判全相等的情况及注意多测清空。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,cnt,p[3000005],e,f,k,l,flag;
struct node
{
    int y,id;
}a[3000005];
bool cmp(node c,node d)
{
    return c.y>d.y;
}//排序函数
vector<int> zd,cd;
signed main(){
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        cnt=0;
        zd.clear();
        cd.clear();
        for(int i=1;i<=n;i++)  p[i]=0;//清空
        flag=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i].y);
            if(a[i].y!=a[i-1].y&&i>1)  flag=1;
            a[i].id=i;
        }
        if(flag==0)
        {
            printf("%lld\n",n);
            for(int i=1;i<=n;i++)   printf("%lld ",i);
            printf("\n");
            continue;
        }//特判全相等
        sort(a+1,a+n+1,cmp);//排序找最大和次大值
        zd.push_back(a[1].id);
        e=0,f=n;
        for(int i=2;i<=n;i++)
        {
            if(a[i].y==a[1].y)  zd.push_back(a[i].id);
            else  
            {
                e=a[i].y;
                f=i;
                break;
            }
        }//最大
        cd.push_back(a[f].id);
        for(int i=f+1;i<=n;i++)
        {
            if(a[i].y==e)  cd.push_back(a[i].id);
            else  break;
        }//次大
        k=0;
        for(int i=1;i<=n;i++)
        {
            if(a[1].y%a[i].y!=0)  k++;  
        }
        if(k<=1)
        {
            for(int i=0;i<zd.size();i++)
            {
                p[++cnt]=zd[i];
            }
        }//判断最大是否满足要求
        k=0;
        for(int i=1;i<=n;i++)
        {
            if(a[f].y%a[i].y!=0)  k++;  
        }
        if(k<=1)
        {
            for(int i=0;i<cd.size();i++)
            {
                p[++cnt]=cd[i];
            }
        }//判断次大是否满足要求
        sort(p+1,p+cnt+1);//将答案排序
        printf("%lld\n",cnt);
        for(int i=1;i<=cnt;i++)  printf("%lld ",p[i]);//输出答案
        printf("\n");//记得换行
    }
}