2020牛客暑期多校訓練營(第八場)(2020.8.3)

不要問我爲什麼現在才寫，因爲懶。

全文口胡。

I、Interesting Computer Game

一開始以爲是個匹配，結果旁邊隊衝了一發匈牙利被卡掉了。然後寫不出來。

結果打完看題解發現確實是個圖論。把所有出現過的數位先離散化，然後若兩數分在一組則中間連一條邊。那麼對於每一條邊都只能選其中一個端點。

考慮樹形結構，則除了根節點以外其它節點都可以選到。而若在樹形結構上多加一條邊，則所有的節點都可以選了。所以最後只要弄一下圖裏連通塊的數量，按照邊數統計每個連通塊的貢獻就好了。

對於邊的處理單獨去數其實比較麻煩。可以根據握手定理統計每個節點的度數，其實就是存該節點的vector的size。自環需要特判一下，因爲自環對自己的貢獻爲2，並且不會在其它節點被統計到。

後記：很神奇的是我在複製的時候發現自己之前補的AC程式碼居然沒特判自環。出題人背鍋。現在這份判了，應該沒什麼大問題。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 10;
vector <int> G[MAXN];
pair <int, int> a[MAXN];
bool vis[MAXN];
int v = 0, e = 0;
void dfs(int u)
{
    v++; e += G[u].size();
    vis[u] = 1;
    for (auto &i : G[u])
    {
        if (!vis[i]) dfs(i);
        if (u == i) ++e;
    }
}
int main()
{
    int t; cin >> t;
    for (int p = 1; p <= t; ++p)
    {
        int n; cin >> n;
        vector <int> idx;
        for (int i = 1; i <= n; ++i)
        {
            int x, y; scanf("%d%d", &x, &y);
            a[i] = {x, y}; idx.push_back(x), idx.push_back(y);
        }
        sort(idx.begin(), idx.end());
        idx.erase(unique(idx.begin(), idx.end()), idx.end());
        for (int i = 0; i < idx.size(); ++i) G[i].clear();
        for (int i = 1; i <= n; ++i)
        {
            int u = lower_bound(idx.begin(), idx.end(), a[i].first) - idx.begin();
            int v = lower_bound(idx.begin(), idx.end(), a[i].second) - idx.begin();
            G[u].push_back(v), G[v].push_back(u);
        }
        memset(vis, 0, sizeof(vis)); int ans = 0;
        for (int i = 0; i < idx.size(); ++i)
            if (!vis[i]) v = 0, e = 0, dfs(i), ans += (e / 2 == v - 1? v - 1: v);
        printf("Case #%d: %d\n", p, ans);
    }
    return 0;
}

K、Kabaleo Lite

這場唯一出的一道題。% 璇大師 %

似乎有很多$O(nlogn)$的方法。不過璇大師的程式碼是$O(n)$的。

首先發現選的個數一定是$b[1]$。

之後想象出一個虛擬陣列，個數爲$b[1]$，初始化每個值都爲$a[1]$。之後從前往後遍歷。假設當前遍歷到$i$，那麼如果記當前元素能選的個數最多爲$c[i]=min_{j=1}^i\{b[j]\}$個，更新方法就是把虛擬陣列的前$c[i]$個覆蓋爲$sum[i]$。這個其實很好理解。

之後觀察性質。首先，我們發現$c[i]$一定是遞減的。其次，我們發現若當前元素需要更新陣列，那麼當前元素的字首和一定會比之前最大的字首和更大。

而利用$c[i]$是遞減的，就意味着後面更新的元素個數一定小於前面更新的元素個數，所以在虛擬陣列中所對應的更新的那一段區間的數位一定都是相同的，而且都等於它之前第一個比它大的數。

通過這兩個性質就可以很方便地更新數值了。所以連陣列都不需要開，記兩個變數就好。具體見程式碼。

這題還有一個坑點就是爆了ll。賽場__int128現學現賣。

後來發現我一開始想的那個用優先佇列的貪心方法其實是對的，只是因爲爆了ll所以哇了。

不過我的方法實在太爛，這裏只介紹璇式方法。並且我個人覺得這個方法應該可以繼續拓展解決一些奇奇怪怪的問題，不過暫時還沒想到(x

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
ll a[MAXN], b[MAXN];
void print(__int128_t t)
{
    bool np = 0; if (t < 0) np = 1, t *= -1;
    vector <int> dig;
    while (t) dig.push_back(t % 10), t /= 10;
    if (np) printf("-");
    for (auto i = dig.rbegin(); i != dig.rend(); ++i) printf("%d", *i);
}
int main()
{
    int t; cin >> t;
    for (int p = 1; p <= t; ++p)
    {
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
        for (int i = 1; i <= n; ++i) scanf("%lld", &b[i]);
        __int128_t sum = a[1] * b[1], all = a[1];//all:字首和
        ll prev = a[1], mini = b[1];//prev:當前最大的字首和 mini:當前最小的b[i]
        for (int i = 2; i <= n; ++i)
        {
            all += a[i];
            mini = min(mini, b[i]);
            if (all > prev) sum += (all - prev) * mini, prev = all;
        }
        printf("Case #%d: %d ", p, b[1]);
        print(sum); cout << endl;
    }
    return 0;
}

賽後總結：

《論罰坐》