CF 468B Two Sets
2024-04-24 15:38:39
题意：
给定n个正整数与a，b两个集合，求一种方案使得这n个数恰好被分在这两个集合中且集合中无多余的数且若x在a中则A-x在a中，若x在b中则B-x在b中。
题意理解了我好半天...
解法1：并查集。
把x, A - x，B - x(如果不存在B - x，x就不能放B集合)放入同一个并查集即可。
实现时注意一些乱七八糟的东西，大力讨论即可。
#include <cstdio>
#include <map>
#include <cstring>
const int N = ; int a[N], ans[N], A, B, n, fa[N];
std::map<int, int> mp; inline int find(int x) {
if(x == fa[x]) {
return x;
}
return fa[x] = find(fa[x]);
}
inline bool check(int x, int y) {
return find(x) == find(y);
}
inline void merge(int x, int y) {
fa[find(x)] = find(y);
return;
} int main() {
memset(ans, -, sizeof(ans));
for(int i = ; i < N; i++) {
fa[i] = i;
}
scanf("%d%d%d", &n, &A, &B);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
mp[a[i]] = i;
}
for(int i = ; i <= n; i++) {
bool x = mp.find(A - a[i]) == mp.end();
bool y = mp.find(B - a[i]) == mp.end();
if(x && y) {
printf("NO");
return ;
}
else if(x) {
int &t = ans[mp[B - a[i]]];
if(t == ) {
printf("NO");
return ;
}
if(t == -) {
t = ;
}
ans[i] = ;
merge(i, mp[B - a[i]]);
}
else if(y) {
int &t = ans[mp[A - a[i]]];
if(t == ) {
printf("NO");
return ;
}
if(t == -) {
t = ;
}
ans[i] = ;
merge(i, mp[A - a[i]]);
}
else {
merge(i, mp[A - a[i]]);
merge(i, mp[B - a[i]]);
}
} for(int i = ; i <= n; i++) {
if(ans[i] == -) {
ans[i] = ans[find(i)];
}
else {
if(ans[find(i)] == -) {
ans[find(i)] = ans[i];
}
else if(ans[find(i)] != ans[i]) {
printf("NO");
return ;
}
}
}
printf("YES\n");
for(int i = ; i <= n; i++) {
if(ans[find(i)] == -) {
printf("0 ");
}
else {
printf("%d ", ans[find(i)]);
}
} return ;
}
AC代码
最新文章
- Java 技能树
- sqlHelper做增删改查
- React Native 的ES5 ES6写法对照表
- IQueryable,IEnumerable,List相互转换
- [MongoDB]mapReduce
- maven命令行跳过test
- opencv china 网站，好1376472449
- VC 串口通信类
- 在verilog中关于inout口的设计方法
- surfaceDestroyed什么时候被调用
- Entity Framework 处理并发
- iOS 热更新插件
- Head First设计模式之代理模式
- 【ASP.NET Core】解决“The required antiforgery cookie "xxx" is not present”的错误
- 代码之间-论文修改助手v1.0版本发布
- LeetCode之“动态规划”：Distinct Subsequences
- C# 温故之.NET 异步
- Oracle物理DG自动切换——Dataguard Broker配置
- yum-cron更新 CentOS yum update 不升级内核版本方法
- 使用python来建立http服务