专栏文章

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

P14444题解参与者 3已保存评论 3

文章操作

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

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

洛谷 P14444

思路

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

代码

CPP
#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;
}

评论

3 条评论,欢迎与作者交流。

正在加载评论...