总结

收获牛客爆零记录X1
嘛......其实就是菜，没得洗。这次的题目难度总体来说感觉比前面几场要难，甚至签到题都没做出来orz（看出来是并查集那也是之后的事了，再说了，看出来跟写出来是两码事）。暂时只补了两道过题多的，其他的慢慢补。主要问题在于还是不太会灵活的运用一些基础的数据结构，大部分算法的应用也还局限在板子题内，需要更多的刷题量。
好了放题目吧。

I Interesting Computer Game

题目描述

原题传送门：点我直达

人话翻译：给你若干组数，每组两个数。现在你可以在每组的两个数之中任选一个或者不选任何一个，但选择的数必须是在当前这组数之前的组中没有选过的数。问最多能够在给出的所有组数中选出几个数。

样例输入

2
6
1 2
2 3
3 4
1 4
1 3
2 4
5
1 2
1 2
1 3
2 3
5 6

样例输出

Case #1: 4
Case #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);//初始化每一个连通块的大小都是1
    fill(d + 1, d + (2 * n) + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        c[++tot] = a[i];
        c[++tot] = b[i];
    }
    sort(c + 1, c + tot + 1);
    for (int i = 1; i <= tot; i++) {
        if (i == 1 || c[i] != c[i - 1])
            d[++sum] = c[i]; //m是去重后的个数，仅与问题数量有关
    }
    for (int i = 1; i <= n; i++) {
        ll ida = query(a[i]), idb = query(b[i]);
        ll faa = getf(ida), fab = getf(idb);
        if (faa == fab) {
            vis[faa] = 1;//父亲都一样说明一定会使用这个父亲，父亲入度+1（也可以理解为多出来的边）
        } else {
            fa[faa] = fab;//其实顺序无所谓，随意定义为fab合并到faa中
            size[fab] += size[faa];
            vis[fab] = vis[faa] | vis[fab];//有一个被标记就连续标记
        }
    }
    ll ans = 0;
    for (int i = 1; i <= sum; i++) {
        ll faa = getf(i);//一个个点的遍历就行，不关心顺序
        if (vis[faa]) { //必选点（多出来的边），算完后恢复vis
            ans += 1;
            vis[faa] = 0;
        }
        if (fa[i] == i) { //说明找到了一个连通块
            ans += size[i] - 1;//减掉那个入度为1的点（n-1条边）
        }
    }
    cout << "Case #" << k++ << ": " << ans << endl;
}

int main() {
    for (cin >> T; T--;) solve();
    return 0;
}

K Kabaleo Lite

题目描述

原题传送门：点我直达

人话翻译：现在有若干种菜，每种菜若干份，同时每一种菜都有各自的收益。假设每个客人只能从第一份菜开始吃，并且必须按照菜的序号顺序吃。问最多能够卖出给多少个人，最大收益是多少。

样例输入

2
3
2 -1 3
3 2 1
4
3 -2 3 -1
4 2 1 2

样例输出

Case #1: 3 8
Case #2: 4 13

题目分析

这题std写的不知道是啥，但其实就是个模拟题。（我连模拟想不到，太菜了）
容易发现，不管如何，由于客人只能从第一种菜（简称一号菜）开始吃，而且还不能跳过它必须顺序吃，所以第一道菜的数量就是最大客人数量，第一小问解决。
第二小问则是个贪心过程，假设ci为到第i号菜为止的前缀和收益。店铺若想最大化收益，则应该尽量保证每一位客人都为店铺贡献尽量多的收益，也就是直接按照ci从大到小的顺序排序遍历。当然有限制条件，虽然是个贪心，但题目限制了必须顺序吃这一条件。这就导致我们必须在这道题中稍微运用一下木板定理，到底能满足多少个人贡献当前的ci收益取决于在1到i这个区间的那个最小人数。这显而易见，假设j<i且j号菜的数量为1到i中最少的，j号菜只有2份，那这两个人可以吃到j号菜，大于两个人的时候剩下的人就当然吃不到j号菜了。又因为必须连续着吃，这就直接导致j到i这个区间的菜根本没办法供应给客人。所以易知，这个j就是我们需要的那个当前ci最大贡献人数。
好了，人数确定了，那怎么贪心呢？将ci用优先队列从大到小排，挨个遍历。同时为了方便，可以用结构体将当前ci对应的1-i中的j（j的意义和上面说的一致），以及i这个编号一起绑定排序（怎么给结构体排序见另一篇博客）。每次遍历时都记录上一次遍历的j和i，如果当前这次遍历发现当前ci对应的i>上一次遍历的i，就直接跳进下一次循环。原因也很简单，因为每一次遍历到可行ci时，都将当前ci乘以j对应的人数得到当前ci最大贡献。此时j号菜就已经卖完了，如果后面还有其他ci对应的i在这个j后面，那就根本卖不了（菜都没了怎么卖）。

AC代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

struct node {
    __int128 ci;
    ll bi;
    int i;

    bool operator<(const node &n2) const {
        return ci < n2.ci;
    }
};

const ll inf = 1e15;
const int maxn = 100000 + 10;
priority_queue<node> pq;
ll T, n, k = 1;
ll b[maxn];
__int128 a[maxn],c[maxn];

inline __int128 read128() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

inline bool read(ll &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;
}

inline void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}

void solve() {
    read(n);
    for (int i = 1; i <= n; i++) a[i] = read128();
    for (int i = 1; i <= n; i++) read(b[i]);
    for (int i = 1; i <= n; i++) {
        if (i == 1) c[i] = a[i];
        else c[i] = c[i - 1] + a[i];
    }
    ll minb = b[1], bestMinb = 0, pos = n + 1;
    __int128 ans = 0;
    for (int i = 1; i <= n; i++) {
        minb = min(minb, b[i]);
        pq.push(node{c[i], minb, i});//将所有节点按照收益前缀和从大到小的顺序排列
    }
    while (!pq.empty()) {
        node cur = pq.top();
        pq.pop();
        if (cur.i >= pos) continue;
        ans += cur.ci * (cur.bi - bestMinb);
        bestMinb = cur.bi;
        pos = cur.i;
    }
    cout << "Case #" << k++ << ": " << b[1] << " ";
    print(ans);
    cout << endl;
}

int main() {
    for (cin >> T; T--;) solve();
    return 0;
}