雪落月夜 - 牛客多校
type: channel
link: http://xpoi.top/index.php/tag/牛客多校/
items: 牛客多校第八场

牛客多校第八场
type: item
date: 2020-08-03T22:24:00+08:00
description: 总结收获牛客爆零记录X1嘛......其实就是菜，没得洗。这次的题目难度总体来说感觉比前面几场要难，甚至签到题都没做出来orz（看出来是并查集那也是之后的事了，再说了，看出来跟写出来是两码事）。暂时只补了两道过题多的，其他的慢慢补。主要问题在于还是不太会灵活的运用一些基础的数据结构，大部分算法的应用也还局限在板子题内，需要更多的刷题量。好了放题目吧。I Interesting Computer Game题目描述原题传送门：点我直达人话翻译：给你若干组数，每组两个数。现在你可以在每组的两个数之中任选一个或者不选任何一个，但选择的数必须是在当前这组数之前的组中没有选过的数。问最多能够在给出的所有组数中选出几个数。样例输入261 22 33 41 41 32 451 21 21 32 35 6样例输出Case #1: 4Case #2: 4题目分析考场上一开始想到的是暴力模拟，真zz。分情况都分不完，更别说AC了。仔细分析题目易知（想不到我也有用这个词的一天），每一组数都可以看做一条边，边的顶点就是这两个数。最后将所有组数连成若干个连通图后，连通图大小之和就是结果。但这里有一个重要的细节，每组数的选择之间有着互相影响的特性。换句话说，我不能将每组选择独立来看，而需要考虑到每个数字在其他组中的关系。那这个时候，就需要并查集来解决了。并查集可以很好地处理若干组数字之间的关系，并且能够随时获取任意一个数字所关联的根数字。实际代码中，将每一组数字的第二个数字关联到第一个数字上同时将第二个数字累积的连通分量加到第一个数字的根数字上（具体怎么做下面说）。最后将每一个连通图大小累加即可。那到底怎么利用连通图大小计算结果呢？先看结论：对任意一个不成环的连通图，他的边数就是这个连通图中所有点经过若干组选择后最多选出的数字数量；对于任意一个成环的连通图，则将边数+1即为答案。直观理解，两个点一组数，一组数至多选一个出来，刚好可以用点数-1的形式表达这种数量关系。同时又因为并查集的合并处理，可以将1-2 2-3 3-4这一系列点（如果有）像连接绳子一样联系起来（虽然实际上是压缩路径），因此刚好就是所有点数-1的关系。显然，若同一组关系出现两次（如1-2 1-2共出现两次），则特判处理，结果+1即可。AC代码#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const ll inf = 1e15; const int maxn = 100000 + 10; int T, sum = 0, n, k = 1; ll c[maxn * 2], d[maxn * 2], a[maxn], b[maxn], size[2 * maxn], vis[2 * maxn]; ll fa[2 * maxn]; inline bool read(int &num) { //quick read char in; bool IsN = false; in = getchar(); if (in == EOF) return false; while (in != '-' && (in < '0' || in > '9')) in = getchar(); if (in == '-') { IsN = true; num = 0; } else num = in - '0'; while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; } if (IsN) num = -num; return true; } ll query(ll x) { return lower_bound(d + 1, d + sum + 1, x) - d; //使用原属于找到离散化后缩小的数据（大的找小的） } ll getf(ll x) { //获取并查集父亲节点 if (fa[x] == x) return x; return fa[x] = getf(fa[x]); } void solve() { int tot = 0; sum = 0; read(n); for (int i = 0; i <= (2 * n) + 1; i++) fa[i] = i;//并查集初始化父集 fill(vis + 1, vis + (2 * n) + 5, 0);//初始化每一个节点都没有被使用 fill(size + 1, size + (2 * n) + 5, 1);//初始化每一个连…