专栏文章
题解: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
思路
既然枚举每一位会超时,那就枚举每一个数字,只需要记录这个数字一共有几个就行,毕竟相同的数字结果也相同,时间复杂度还是 但是经过优化能过,不过应该是一个非正解。
代码
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 条评论,欢迎与作者交流。
正在加载评论...