A+B 新思路:随机化算法
2025-10-02 21:42:49
发布于:浙江
69阅读
0回复
0点赞
显然,这是一道模拟题。
我们可以使用大学二年级就学过的“掰手指”方法,把 个元素放到 vector<int>A 中,把 个元素放到 vector<int>B 中,由于我们并不关心每个元素具体的权值,所以默认 。
接着,我们分别遍历 和 ,每次循环将一个随机权值压入 set<int>c 中,最后统计 的元素数量即可。由于使用随机化算法,一般情况下不会有压入重复元素的问题。
代码如下:
#include<bits/stdc++.h>
using namespace std;
signed main()
{
default_random_engine e;
e.seed(time(0));
int a,b;cin>>a>>b;
vector<int>A(a),B(b);
set<int>c;
for(auto it:A)c.insert(e());
for(auto it:B)c.insert(e());
cout<<c.size();
return 0;
}
不幸的是这份代码只通过了 7/8 的测试点,于是我们请来了 IOI 601pts 的选手复仇者_帅童帮我卡常。聪明的帅童只用了-INFs 就得到了思路:注意到 set 常数十分大,可以换成 vector,使用 sort+unique 去重。
于是有如下代码:
#include<bits/stdc++.h>
using namespace std;
signed main()
{
default_random_engine e;
e.seed(time(0));
int a,b;cin>>a>>b;
vector<int>A(a),B(b),c;
for(auto it:A)c.push_back(e());
for(auto it:B)c.push_back(e());
sort(c.begin(),c.end());
auto it=unique(c.begin(),c.end());
c.resize(distance(c.begin(),it));
cout<<c.size();
return 0;
}
在强力数据和 ACGO 神机的加持下,最后一个测试点仅使用了 114ms,顺利 AC。
全部评论 4
?????????????
1周前 来自 山东
0
2025-10-07 来自 广东
0根据生日悖论,这种做法在 的时候就会错,这说明 ACGO 对随机数的处理非常优秀,尽量避免了随机数相同的情况,绝对不是数据水啊,嗯。
2025-10-06 来自 广东
0正确的
2025-10-06 来自 江苏
0
%%%
2025-10-03 来自 浙江
0


























有帮助,赞一个