感谢 @mfeitveer 提供的思路。
昨天没听懂,今天想明白了。
大概是这样的,把众数取出来,然后把整个数组减掉众数(任意一个都行)。
拎出来众数以外的数,进行随机打乱。
然后枚举 \(i\),计算前缀和模 \(n\) 的余数,存储起来。
如果发现出现过相同的余数(设为 \([1,j]\)),那么 \([i+1,j]\) 内的元素就模 \(n\) 余 \(0\)。
把众数补上去(因为减掉之后为 \(0\))了,如果合法就输出答案。
反复随机打乱即可 AC()。
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
int n, _n, a[N], cnt[N];
vector <pair <int, int> > g;
unordered_map <int, int> Map;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n; _n = 2 * n - 1;
for (int i = 1; i <= _n; ++i) cin >> a[i], ++cnt[a[i]];
int d = n; for (int i = 0; i < n; ++i) if (cnt[i] > cnt[d]) d = i;
if (cnt[d] >= n) {
for (int i = 1, ct = 0; i <= _n; ++i) {
if (a[i] == d) cout << i << ' ', ++ct;
if (ct == n) break;
}
return cout << endl, 0;
}
for (int i = 1; i <= _n; ++i) if (a[i] ^ d) g.push_back({i, (a[i] - d + n) % n});
while (1) {
Map.clear(); int sum = 0, ct = 0;
for (auto [id, val]: g) {
(sum += val) %= n, ++ct; int &kel = Map[sum];
if (kel) {
if (!(ct - kel + cnt[d] >= n && ct - kel <= n)) continue;
vector <int> res; for (int i = kel; i < ct; ++i) res.emplace_back(g[i].first);
for (int i = 1; i <= _n; ++i) {
if (res.size() == n) break;
if (a[i] ^ d) continue; res.emplace_back(i);
}
for (auto to: res) cout << to << ' ';
return cout << endl, 0;
}
kel = ct;
}
random_shuffle(g.begin(), g.end());
}
return 0;
}
原文地址:http://www.cnblogs.com/MistZero/p/UOJ771-Sol.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性