重新認識了Kruskal算法。

題目

T1：BZOJ 3293 / CQOI 2011 分金币 (coin)（亂搞？？？）

T2：BZOJ 1007 / HNOI 2008 水準可見直線 (line)（棧維護凸殼）

T3：BZOJ 1016 / JSOI 2008 最小生成樹計數 (award)（Kruskal+計數）

T1

分析

下面，将「第 i i 個人給第jj個人 k k 個金币」定義為：

k≥0k≥0，則第 i i 個人的金币數減kk，第 j j 個人的金币數加kk；

否則第 i i 個人的金币數加kk，第 j j 個人的金币數減kk，也就是第 j j 個人給第ii個人 −k − k 個金币。

并且第 i i 個人初始的金币數量為xixi，平均值為 x¯ x ¯ ， sum[l,r] s u m [ l , r ] 為 ∑ri=la[i] ∑ i = l r a [ i ] 的值。

首先考慮把第 1 1 個人的金币數量變成x¯x¯，那麼可以得到，第 1 1 個人給第22個人的金币加上第 1 1 個人給第nn個人的金币數量一定等于 x1−x¯ x 1 − x ¯ 。這樣第 1 1 個人給了第22個人和第 n n 個人金币之後，第22個人就不用再給第 1 1 個人金币了，也就是說第22個人隻需要給第 3 3 個人金币。照這樣計算下去，第11個人給了第 2 2 個人和第nn個人金币之後，對于所有的 1<i<n 1 < i < n ，第 i i 個人隻需要給第i+1i+1個人金币，使得第 i i 個人的金币數量變為x¯x¯。

而現在的關鍵就是求得第 2 2 個人被第11個人分到金币後的金币數目（下面記為 w w ）。

可以推出，第11個人分給了第 2 2 個人w−x2w−x2個金币，也分給了第 n n 個人x1+x2−w−x¯x1+x2−w−x¯個金币，代價為：

|w−(x1+x2−x¯)|+|w−x2| | w − ( x 1 + x 2 − x ¯ ) | + | w − x 2 | 。

再繼續考慮第 2 2 個人到第n−1n−1個人：

可以算出，第 2 2 個人分給第33個人金币，使得第 2 2 個人的金币數量變為x¯x¯的代價為 |w−x¯| | w − x ¯ | 。這樣，第 3 3 個人的金币數量變成了x3+w−x¯x3+w−x¯，是以分給第 4 4 個人金币的代價為|w−(2x¯−x3)||w−(2x¯−x3)|…

是以，對于所有的 2<i<n 2 < i < n ，第 i i 個人分給第i+1i+1個人金币的代價為：

|w−((i−1)x¯−sum[3,i])| | w − ( ( i − 1 ) x ¯ − s u m [ 3 , i ] ) | 。

是以，設一個新的數組 b b ，定義：

b1=x1+x2−x¯b1=x1+x2−x¯

b2=x2 b 2 = x 2

b3=x¯ b 3 = x ¯

∀3<i≤n,bi=(i−2)x¯−sum[3,i−1] ∀ 3 < i ≤ n , b i = ( i − 2 ) x ¯ − s u m [ 3 , i − 1 ]

這時候，就是要找到一個值 w w ，最小化∑ni=1|w−bi|∑i=1n|w−bi|的值。

顯然（也就是我不會嚴謹證明）， w w 的值為數組bb的中位數。将 b b 排序之後，就可以找到這個ww。

Source

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
typedef long long ll;
const int N =  + ;
int n; ll a[N], ave, sum[N], b[N], ans;
ll cyx(int l, int r) {
    return sum[r] - sum[l - ];
}
int main() {
    int i; n = read();
    for (i = ; i <= n; i++) ave += (a[i] = read()); ave /= n;
    if (n == ) return printf("0\n"), ;
    for (i = ; i <= n; i++) sum[i] = sum[i - ] + a[i];
    b[] = a[] + a[] - ave; b[] = a[]; for (i = ; i <= n; i++)
        b[i] = ave * (i - ) - cyx(, i - );
    sort(b + , b + n + ); if (!(n & )) {
        for (i = ; i <= (n >> ); i++) ans += b[n >> ] - b[i];
        for (i = (n >> ) + ; i <= n; i++)
            ans += b[i] - b[n >> ];
    }
    else {
        for (i = ; i <= (n >> ) + ; i++) ans += b[(n >> ) + ] - b[i];
        for (i = (n >> ) + ; i <= n; i++)
            ans += b[i] - b[(n >> ) + ];
    }
    cout << ans << endl;
    return ;
}

T2

分析

首先，将所有的直線按照斜率（ A A ）從小到大排序，相同情況按照BB從小到大排序，這樣， A A 相同的直線中隻有BB最大的才可見。這樣先去除掉一些一定被覆寫的直線，使每條直線的 A A 都不同。

如果合法直線隻有不到33條，那麼所有的合法直線都可見。

否則建立一個棧，把前 2 2 條直線加入棧中，這22條直線在其他的直線被加入之前全部可見。

考慮加入一條新的直線。加入一條新的直線之後，在這之前棧中的直線（可見）有可能被覆寫，但由于已經按 A A 排序，是以如果棧中的一條直線l1l1在加入了這條直線 l2 l 2 之後被覆寫，那麼棧中 l1 l 1 之後的直線（除 l2 l 2 外）必然被覆寫。是以在加入 l2 l 2 之前，應該：

（1）判斷棧頂直線是否會在加入 l2 l 2 之後被覆寫，如果有則轉（2），否則将 l2 l 2 加入棧中；

（2）将棧頂元素退棧，轉（1）。

操作完成後，棧中剩餘的直線就是答案。

Source

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
const int N =  + ; const double eps = ;
int n; struct cyx {
    int id, k, b;
} cx[N], pyz[N]; int top, stk[N]; bool del[N];
bool comp(cyx a, cyx b) {
    if (a.k != b.k) return a.k < b.k;
    return a.b < b.b;
}
bool slope(int p1, int p2, int p3) {
    double x1 =  * (cx[p2].b - cx[p1].b) / (cx[p1].k - cx[p2].k),
        x2 =  * (cx[p3].b - cx[p2].b) / (cx[p2].k - cx[p3].k);
    return x1 > x2 || abs(x1 - x2) <= eps;
}
int main() {
    int i, Tn, m = ; Tn = n = read();
    for (i = ; i <= n; i++) cx[i].k = read(), cx[i].b = read(), cx[i].id = i;
    sort(cx + , cx + n + , comp); for (i = ; i <= n; i++)
        if (i == n || cx[i].k != cx[i + ].k) pyz[++m] = cx[i];
    n = m; for (i = ; i <= n; i++) cx[i] = pyz[i];
    if (n < ) {
        for (i = ; i <= n; i++) del[cx[i].id] = ;
        for (i = ; i <= Tn; i++) if (del[i]) printf("%d ", i);
        printf("\n"); return ;
    }
    stk[] = ; stk[top = ] = ; for (i = ; i <= n; i++) {
        while (top >  && slope(stk[top - ], stk[top], i)) top--;
        stk[++top] = i;
    }
    for (i = ; i <= top; i++) del[cx[stk[i]].id] = ;
    for (i = ; i <= Tn; i++) if (del[i]) printf("%d ", i);
    cout << endl;
    return ;
}

T3 最小生成樹計數

分析

先把邊按權值排序。假設現在考慮到的是所有權值為 w w 的邊，并且所有權值小于ww的合法邊已經在最小生成樹内。這樣考慮一個貪心，把所有的權值為 w w 都加入最小生成樹内，但這樣會形成環。又由于要求邊權和最小的生成樹，是以要在所有邊權為ww的邊中，删掉盡可能少的邊，使得目前的生成樹沒有環。這樣等同于在目前的生成樹内，删掉這些邊後每對點之間的連通性不變。而一個 m m 個點的連通圖，去掉盡可能少的邊使圖仍然連通，答案一定是讓這個連通圖隻剩下m−1m−1條邊。

歸納一下，得出結論：在一張圖的每一個最小生成樹中，同一權值的邊的出現次數和連通的點集相同。

是以，先将邊按權值排序，然後做一遍Kruskal，求出每種權值邊的出現次數。

然後按順序考慮每種權值：由于同種權值的邊數 ≤10 ≤ 10 ，是以可以 210 2 10 暴力枚舉每條邊選或不選，隻要沒有環并且選出邊的條數恰好等于預處理出的次數，這種選法就是合法的。這時候，這種權值的結果就是合法方案的個數。

最後把每種權值的合法方案個數相乘，得到最終結果。

實作上的細節：

1、考慮完一種權值之後，要保留這種權值的邊連通的集合。具體用個例子： n=4 n = 4 ， m=5 m = 5 ，有邊 (1,2,1) ( 1 , 2 , 1 ) ， (1,3,1) ( 1 , 3 , 1 ) ， (2,3,2) ( 2 , 3 , 2 ) ， (2,4,2) ( 2 , 4 , 2 ) ， (3,4,2) ( 3 , 4 , 2 ) 。（三元組的第三個元素表示邊權）這時候如果不保留連通的集合，那麼權值 1 1 的結果為11，權值 2 2 的結果為33，但最後結果是 2 2 而不是33，原因很簡單：方案 (1,2) ( 1 , 2 ) (1,3) ( 1 , 3 ) (2,3) ( 2 , 3 ) ，雖然權值為 1 1 和22的邊都構不成環，但是合起來就構成環了。但如果保留連通集合，也就是考慮完權值 1 1 之後，将(1,2)(1,2) (1,3) ( 1 , 3 ) (2,3) ( 2 , 3 ) 标記為已連通，那麼權值為 2 2 的邊的選擇方案種，(2,3)(2,3)就不是一個合法的方案。具體可以用并查集來實作。

2、注意圖不聯通的情況，輸出 0 0 <script type="math/tex" id="MathJax-Element-266">0</script>。

Source

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
const int N = , M = , ZZQ = ;
int n, fa[N], m, d, cnt[M], pyz[M], sel[M], ans[M], L[M], R[M], F[M], lyt[M];
struct cyx {
    int u, v, w;
} orz[M];
bool comp(cyx a, cyx b) {
    return a.w < b.w;
}
int cx(int x) {
    if (fa[x] != x) fa[x] = cx(fa[x]);
    return fa[x];
}
bool zm(int x, int y) {
    int ix = cx(x), iy = cx(y);
    if (ix == iy) return ;
    return fa[iy] = ix, ;
}
void kruskal() {
    int i; for (i = ; i <= n; i++) fa[i] = i;
    for (i = ; i <= m; i++) if (zm(orz[i].u, orz[i].v)) sel[i] = ;
}
void dfs(int cyx, int dep, int sta) {
    if (dep == R[cyx] + ) {
        int i, cnt = ; for (i = ; i <= n; i++) fa[i] = F[i];
        for (i = ; i < R[cyx] - L[cyx] + ; i++)
            if ((sta >> i) & ) cnt++; if (cnt != pyz[cyx]) return;
        for (i = ; i < R[cyx] - L[cyx] + ; i++)
            if (((sta >> i) & ) && !zm(orz[L[cyx] + i].u, orz[L[cyx] + i].v))
                return; ans[cyx]++;
        if (ans[cyx] == ) for (i = ; i <= n; i++) lyt[i] = fa[i];
        return;
    }
    dfs(cyx, dep + , sta);
    dfs(cyx, dep + , sta | ( << dep - L[cyx]));
}
int main() {
    int i, j; n = read(); m = read();
    for (i = ; i <= m; i++) orz[i].u = read(), orz[i].v = read(),
        orz[i].w = read(); sort(orz + , orz + m + , comp);
    kruskal(); for (i = ; i <= m;) {
        L[++d] = i; for (j = i; orz[i].w == orz[j].w && j <= m; j++)
            cnt[d]++, pyz[d] += sel[j]; R[d] = j - ;
        i = j;
    }
    for (i = ; i <= n; i++) fa[i] = i;
    for (i = ; i <= d; i++) if (pyz[i] && cnt[i] == )
        zm(orz[L[i]].u, orz[L[i]].v);
    for (i = ; i <= n; i++) F[i] = fa[i], fa[i] = i;
    for (i = ; i <= d; i++) {
        if (!pyz[i]) continue;
        if (cnt[i] == ) ans[i] = ;
        else {
            dfs(i, L[i], );
            for (j = ; j <= n; j++) F[j] = lyt[j];
        }
    }
    int wohaocaia = ; for (i = ; i <= d; i++) if (pyz[i])
        wohaocaia = wohaocaia * ans[i] % ZZQ;
    for (i = ; i <= n; i++) fa[i] = i; for (i = ; i <= m; i++)
        zm(orz[i].u, orz[i].v); for (i = ; i <= n; i++)
        if (cx() != cx(i)) return printf("0\n"), ;
    cout << wohaocaia << endl;
    return ;
}

[題解]CLYZ2018省選訓(bao)練(zha)模拟賽 Day 1題目T1SourceT2T3 最小生成樹計數

題目

T1

分析

Source

T2

分析

Source

T3 最小生成樹計數

分析

Source

繼續閱讀

DTOJ3049 苋題目題解

題解 DTOJ #2802. 區間（interval）

DTOJ2161 Christmas題目題解

DTOJ3312 行走題目題解

DTOJ3320 GotoAndPlay題目題解

2019年藍橋杯省賽個人題解

計算機作業系統（第四版）湯小丹編著第一章習題

洛谷P2272 [ZJOI2007]最大半連通子圖——題解

牛牛愛博弈

八數位難題————Astar算法好

jzoj5290 【NOIP2017提高組A組模拟8.17】行程的交集 (樹上路徑交，dfs序+樹狀數組維護姿勢)

POJ 1321棋盤問題（dfs）

題解：2012 ACM-ICPC Asia Dhaka Regional ContestWedding of SultanMemory OverflowPoker End GamesOverlapping CharactersLearning Vector

B - No Name UVALive - 6319 思維or連結清單

C++:NOIP2011

LeetCode——224. 基本電腦(Basic Calculator)[困難]——分析及代碼（Java）一、題目二、分析及代碼三、其他