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

_mei_tou_nao_ · 2025-11-07 16:05:53 · 题解

洛谷 P14444

思路

既然枚举每一位会超时，那就枚举每一个数字，只需要记录这个数字一共有几个就行，毕竟相同的数字结果也相同，时间复杂度还是 O(n^{2}) 但是经过优化能过，不过应该是一个非正解。

代码

#include <bits/stdc++.h>
using namespace std;
long long n, m, b[300005], cnt, a[300005], t, ans, ac, anss[300005];
map<int, int>mp;

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (!mp[a[i]]) {
                cnt++;
                b[cnt] = a[i];
            }
            mp[a[i]]++;
        }
        sort(b + 1, b + cnt + 1);
        for (int i = 1; i <= n; i++) {
            int tot = 0;
            int cnt1 = 0;
            for (int j = 1; j <= cnt; j++) {
                if (a[i] % b[j] != 0 && b[j] <= a[i]) {
                    cnt1 += mp[b[j]];
                }
                if (b[j] > a[i]) {
                    cnt1 += mp[b[j]];
                }
                if (cnt1 > 1) {
                    tot = 1;
                    break;
                }
            }
            if (i == 4) {
//              cout << "i " << i << " " << cnt1 << endl;
            }
            if (tot == 0 && cnt1 <= 1) {
                ans++;
                ac++;
                anss[ac] = i;
            }
        }
        cout << ans << endl;
        for (int i = 1; i <= ac; i++) {
            cout << anss[i] << " ";
        }
        cout << endl;
        ac = 0;
        ans = 0;
        cnt = 0;
        mp.clear();
    }
    return 0;
}