网站建设上线流程,网页设计师专业培训,江西建设职业技能教育咨询网站,google关键词分析本题链接#xff1a;登录—专业IT笔试面试备考平台_牛客网
题目#xff1a;
样例1#xff1a; 输入 4 5 9
2 3 4 5 输出 YES 0 0 1 1 样例2#xff1a; 输入 3 3 4
1 2 4 输出 NO 思路#xff1a; 这道题关键点在于。 当集合中有一个元素均存在于集合 A 和集合 B 的时…本题链接登录—专业IT笔试面试备考平台_牛客网
题目
样例1
输入 4 5 9
2 3 4 5 输出 YES 0 0 1 1 样例2
输入 3 3 4
1 2 4 输出 NO 思路 这道题关键点在于。 当集合中有一个元素均存在于集合 A 和集合 B 的时候是 NO。 并且 的范围是 1 ~ 1e9 所以当 max(a,b) 的时候也是 NO。 我们同时可以指定一个 元素范围外的 一个元素作为 根元素集合 AB 其次我们可以将 下标 作为对应的每一个元素最后进行合并求结果即可。
代码详解如下
#include iostream
#include vector
#include unordered_map
#define umap unordered_map
#define int long long
#define endl \n
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;umapint,intpos; // 存储元素对应的下标// 存储元素集合,至于为什么也用 umap ,由于 Pi 的数据范围上限是 1e9
// 我们要将数组无法开辟这么大所以我们只能弄个映射 来存储对应的 AB 根元素
umapint,intfather; // 并查集查找函数
inline int Finds(int x)
{int t x; // 记录其实查找结点while(x ! father[x]) x father[x]; // 开始查找father[t] x; // 路径压缩查找return x; // 返回结果
}// 并查集合并操作
inline void Union(int a,int b)
{a Finds(a),b Finds(b); // 查找对应根节点father[a] b; // 合并对应根节点
}inline void solve()
{int n,a,b;cin n a b;int maxs max(a,b); // 获取对应 a b 最大值int A maxs 1; // 根据对应的最大值赋值一个元素范围外的元素作为 集合 A 的根节点int B maxs 2; // 根据对应的最大值赋值一个元素范围外的元素并且不同于集合A的根元素的元素作为 集合 B 的根节点father[A] A,father[B] B; // 集合根节点初始化vectorintv(n 2,0); // 存储对应元素for(int i 1;i n;i){cin v[i];if(v[i] maxs) // 如果存在 元素 大于 a 和 b 那么放不了 任意集合无解输出 NO{cout NO endl;return ;}pos[v[i]] i; // 映射对应的下标father[i] i; // 对应下标 根节点初始化}for(int i 1;i n;i){// 如果对应的元素存在的话我们将其元素的下标与当前的下标进行操作合并对应的集合if(pos[b - v[i]]) Union(i,pos[b - v[i]]); // 另一元素存在 集合 b 那么我们合并对应下标 else Union(A,i); //如果不符合那么合并另一个集合if(pos[a - v[i]]) Union(i,pos[a - v[i]]); // 另一元素存在 集合 a 那么我们合并对应下标 else Union(B,i); //如果不符合那么合并另一个集合}A Finds(A),B Finds(B); // 根据对应的 结合 根节点元素查找if(A B) cout NO endl; // 如果最终集合 A 和 集合 B 的根节点也给合并了说明无解 NOelse{cout YES endl;for(int i 1;i n;i){
// cout bool(Finds(i) B) ; // 这样输出是错误的有可能这里没考虑一个情况就是 A B 的时候也有可能返回值的原因if(Finds(i) A) cout 0 ;else cout 1 ;}cout endl;}
}signed main()
{IOS;int ___t 1;while(___t--) solve(); return 0;
}
最后提交
