AcWing 1250. 格子游戏
题目类型
- 并查集
题目链接
思路
- 将该二维矩阵弄成一维来计算，对于 (x, y) 映射为x * n + y
- 每次读入边的时候使用并查集判断是否构成环
- 如果构成环则游戏结束，如果没有，则平局 “draw”
AC代码
#include <iostream>
using namespace std;
const int N = 200 * 200 + 10;
int n, m;
int p[N];
int get(int x, int y)
{
return x * n + y;
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
// 初始化
for (int i = 0; i < n * n; i ++) p[i] = i;
int res = 0;
for (int i = 1; i <= m; i ++ )
{
int x, y;
char op;
cin >> x >> y;
x --, y --;
cin >> op;
int a = get(x, y); // 起点
int b;
if (op == 'R') b = get(x, y + 1);
else b = get(x + 1, y);
int pa = find(a), pb = find(b);
if (pa != pb)
{
p[pa] = pb;
}
else
{
res = i;
break;
}
}
if (res) cout << res << endl;
else cout << "draw" << endl;
return 0;
}
AcWing 1252. 搭配购买
题目类型
- 并查集
- 01背包
题目链接
思路
本题是并查集和01背包问题的结合
- 先用并查集把捆绑消费的物品合并成一个集合，注意除了维护好并查集p[N]数组，还要维护好w[N]和v[N]
- 再使用01背包问题解决
AC代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010;
int p[N];
int n, m, vol;
int w[N], v[N];
int f[N];
int find(int x) // 并查集
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m >> vol;
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
while (m -- )
{
int a, b;
cin >> a >> b;
int pa = find(a), pb = find(b);
if (pa != pb) // 将捆绑消费的商品放一块 合并成一个商品
{
v[pb] += v[pa];
w[pb] += w[pa];
p[pa] = p[pb];
}
}
// 01背包
for (int i = 1; i <= n; i ++)
{
// 判断是否是一个完整商品 只有根节点才是完整商品
if (p[i] == i)
{
for (int j = vol; j >= v[i]; j--)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
}
cout << f[vol] << endl;
return 0;
}
AcWing 237. 程序自动分析
题目类型
- 离散化
- 并查集
题目链接
思路
此题是NOI的一道题，掌握的话确实不难，而且感觉这题出的非常好，是并查集的经典题
- 由于该题数据是1e9 强行开1e9会TLE或者MLE，实际上用到最多只有只有2e5，所以使用离散化（这里不需要排序关系，使用哈希表）
- 所有等式相当于并查集合并，所有不等式相当于并查集查询
- 所以处理所有 ＝ 等式
- 再查询所有 ≠ 等式，如果出现两个数在不同集合，说明存在冲突
AC代码
// 题目数据是1e9 可以用离散化缩小到2e6 (最关键在这步，否则会TLE)
// 将相等的式子 合并方式
// 将不等的式子 查询方式
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 2e6 + 10;
int n, m;
int p[N];
unordered_map<int, int> S;
struct Query
{
int x, y, e;
}query[N];
int get(int x)
{
if (S.count(x) == 0) S[x] = ++ n;
return S[x];
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
n = 0;
S.clear();
scanf("%d", &m);
for (int i = 0; i < m; i ++)
{
int x, y, e;
scanf("%d%d%d", &x, &y, &e);
// 离散化处理
query[i] = {get(x), get(y), e};
}
// 初始化并查集
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 先处理合并
for (int i = 0; i < m; i ++ )
{
if (query[i].e == 1)
{
int pa = find(query[i].x), pb = find(query[i].y);
if (pa != pb) p[pa] = pb;
}
}
// 再处理查询
bool has_conflict = false;
for (int i = 0; i < m; i ++ )
{
if (query[i].e == 0)
{
int pa = find(query[i].x), pb = find(query[i].y);
if (pa == pb)
{
has_conflict = true;
break;
}
}
}
if (has_conflict) printf("NO\n");
else printf("YES\n");
}
return 0;
}
AcWing 239. 奇偶游戏
题目类型
思路
暂时还不会，待更
AC代码
AcWing 238. 银河英雄传说
题目类型
- 并查集
- 前缀和
题目链接
思路
可以看看这篇题解
AC代码
#include <iostream>
using namespace std;
const int N = 30010;
int m;
int p[N], sz[N], d[N]; // sz是集合的大小 d[x]为x到root的距离
int find(int x)
{
if (p[x] != x)
{
int root = find(p[x]);
d[x] += d[p[x]];
p[x] = root;
}
return p[x];
}
int main()
{
cin >> m;
// 初始化
for (int i = 1; i < N; i ++)
{
p[i] = i;
sz[i] = 1;
}
while (m -- )
{
char op[2];
int a, b;
cin >> op >> a >> b;
if (op[0] == 'M')
{
int pa = find(a), pb = find(b);
if (pa != pb)
{
d[pa] = sz[pb];
sz[pb] += sz[pa];
p[pa] = pb;
}
}
else
{
int pa = find(a), pb = find(b);
if (pa != pb) puts("-1");
else cout << max(0, abs(d[a] - d[b]) - 1) << endl;
}
}
return 0;
}
##
题目类型
思路
AC代码
##【未完待更】
