洛谷P7390 「EZEC-6」造树

zrzring 2021-01-25 PM 50℃ 0条

考虑贪心,按权值排序,对于枚举到的节点$i$,我们要尽量让这个点和小的点连边,考虑到我们要保证这棵树存在,所以留1的度数用来让这棵树能和剩下的点连起来,于是每次枚举的连通块都需要预留至少1度数和后面的点连边

我们用一个指针$j$表示$[1, j]$已经变成了一个连通块,那么对于枚举到的$i$就从$j$往后开始连,所以任意时刻我们连出来的一定仅有一个连通块的,根据上面的结论,我们再维护这个连通块的度数使他保持有至少为1的度数即可

我写题解一般都写的很少的,但这次是验题的工作,所以写一下详细证明

若当前枚举到的$i$使得$[1, j]$连通块最后仅剩$i$这个点有$1$的度数,且$j + 1$的点度数为1,那么连这个点就会导致无法和后面的点连通,所以要找到后面第一个度数大于1的点$k$相连,然后再处理i到k之间的点直到$k$的度数为1或区间内的点被连完,如果这个区间还有剩下的点就继续寻找下一个$k$,直到$[1, k]$为一个连通块或者已经连到了$n$,由于题目保证树存在,所以连到$n$的时候已经不需要保证度数可以直接相连

若已知$a > b > c > d$,在所有将他们分成两对分别求乘积的和的方案中,最大值为$ab + cd$

所以对于上述过程,因为在任意时刻,全局最小的权值会和当前该权值能连边的最小权值相乘,所以最终结果一定是最大值

可以反证,首先初始的边集为空集,肯定为最优解的子集,如果最小的权值$a$没有和它能连的最小权值$b$相连,而和$c$相连,那么一定会存在一个比$a$大的权值$d$和$b$相连,这违背了上述结论,所以这个解一定不是最优的,故上述结论构成的子集一定是最优解的子集,于是如果当前为最优解的子集,之后每步加的边都是最优解的子集

这个过程具有对称性,所以对权值的排序从小到大和从大到小是等价的

而我们保证了$[1, j]$为连通块,每次相连一定与$[j + 1, n]$的点相连,对于$k$来说,因为$i$到$k$路径上的点度数均为1,所以和$k$相连的点不可能与之前的连通块构成环,剩下的点与$[k + 1, n]$的点相连,这时可以理解为这些点已经不存在,并且后面的点度数改变,由于题目保证可以构成树,加上我们限制了每个点至少要保留1的度数,所以这个过程毫无影响正确性

时间复杂度O(n),这里为了复杂度对应用的桶排,实际上用sort可以在2s内通过所有数据

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

#define mp(x, y) make_pair(x, y)
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);

using namespace std;

const int N = 1e7 + 10;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct NODE {int d, val;} dat[N], t[N];

int n, m = 5e5, last, cnt[N];

long long ans;

namespace STD {
    unsigned seed;
    unsigned rnd(unsigned x) {
        x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x;
    }
    int rad(int x, int y) {
        seed = rnd(seed); return seed % (y - x + 1) + x;
    }
    void init() {
        seed = read();
        for(int i = 1; i <= n; i++) t[i].d = 1, t[i].val = rad(1, 500000);
        for(int i = 1; i <= n - 2; i++) t[rad(1, n)].d++;
    }
}

void sort() {
    for (int i = 1; i <= n; i++) cnt[t[i].val]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = 1; i <= n; i++) dat[cnt[t[i].val]--] = t[i];
}

int main() {
    int type = read(); n = read();
    if (type == 1) STD::init(); else {
        for (int i = 1; i <= n; i++) t[i].d = read();
        for (int i = 1; i <= n; i++) t[i].val = read();
    }
    sort(); last = 1;
    for (int i = 1, j = 2, k = 2; i <= n; i++, j = max(j, i + 1)) {
        while (dat[i].d == 0 && i <= n) i++; if (i > n) break;
        while (dat[i].d > 1) {
            while (dat[j].d == 0) j++; if (dat[j].d > 1) last = j;
            ans += 1ll * dat[i].val * dat[j].val; dat[i].d--; dat[j].d--; j++;
        }
        if (last == i) {
            k = max(j, k); while (dat[k].d <= 1 && k < n) k++;
            ans += 1ll * dat[i].val * dat[k].val; dat[i].d--; dat[k].d--; i = j;
            while (i < k && dat[k].d > 1) {
                ans += 1ll * dat[i].val * dat[k].val; dat[i].d--; dat[k].d--; i++;
            }
            if (dat[k].d == 1) last = i; else last = k; i--;
        } else {
            while (dat[j].d == 0 && j < n) j++; if (dat[j].d > 1) last = j;
            ans += 1ll * dat[i].val * dat[j].val; dat[i].d--; dat[j].d--; j++;
        }
    }
    printf("%lld", ans);
    return 0;
}
Title - Artist
0:00