第十四屆藍橋杯省賽C++ B組(個人經歷 + 題解)

        2023-05-08 21:28:32       來源:博客園
        參賽感受

        這是我第一次參加藍橋杯的省賽,雖然沒什么參賽經驗,但是自己做了很多前幾屆藍橋杯的題,不得不說,這一屆藍橋杯省賽的難度相較于之前而言還是比較大的。之前很流行藍橋杯就是暴力杯的說法,但是隨著參賽人數的增多,比賽認可度的提升,比賽題目的質量也明顯越來越高了。這次省賽涉及知識點非常全面,而且難度都不小(題目涉及了暴力、模擬、數學、遞歸、動態規劃、廣度優先搜索、前綴和、最近公共祖先等)。總得來說,大概就是“你知道題目考的是什么,但是就是不太會做”。這也是我在比賽過程中的真實感受。

        不過最后成績還是不錯的,拿了省一。我算了一下自己的分數,大概是50-60分,頂多也就是對了五道題的樣子。我考完試都覺得可能完了,結果這個分數居然還能排在江蘇省一的中游,看來我運氣還是不錯的哈哈哈。


        (資料圖片僅供參考)

        時隔一個月,有些平臺上已經有了第十四屆藍橋杯的題目,我打算記錄一下自己參賽的經歷并寫下每道題的題解。PS: 本博客中編程題的代碼都是在Acwing平臺上提交且通過的代碼。

        A:日期統計 暴力枚舉 解題思路

        第一道題是一個填空題,大致意思就是一個由100個數字組成的序列,統計符合"\(2023mmdd\)"格式的無重復子序列的個數,"\(2023mmdd\)"表示一個2023年的一個合法的日期,其中"\(mm\)"表示月份的兩位數字,"\(dd\)"表示天數的兩位數字。

        我一開始有點不敢寫暴力,畢竟要八重循環呢!后來發現前四重循環在判斷年份的時候,由于年份確定為"2023",故只需要判斷當前循環是否符合即可,如果不符合,就跳過這一整層的循環,比如說第一層循環,只需要判斷是否等于2就行,如果胡等于2,就跳過。這樣前面四重循環可以節省大量的運行時間,整個八重循環基本上就變成一個四重循環了,總共就100個數,所以可以在一秒左右的時間就跑出結果。

        對于判重,我使用的是\(set\),每出現一個合法日期,用 \(月份 × 100 + 天數\) 設為對應哈希值,放入\(set\)中。最后返回\(set\)的大小即答案。

        答案235

        個人戰況

        這道題做出來了,但是消耗了很多時間,一直不敢寫暴力,自己在考場上可能也有緊張的因素,而且我一直都喜歡睡懶覺,所以上午做題可能多少也影響到我的狀態了哈哈哈。幸好最后還是做出來了。

        代碼
        #include#include#includeusing namespace std;const int N = 110;int num[N];set st;    //利用set去重int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);for(int i = 0; i < 100; i ++ ) cin >> num[i];   //輸入數據for(int y1 = 0; y1 < 100; y1 ++ ){if(num[y1] != 2) continue;for(int y2 = y1 + 1; y2 < 100; y2 ++ ){if(num[y2] != 0) continue;for(int y3 = y2 + 1; y3 < 100; y3 ++ ){if(num[y3] != 2) continue;for(int y4 = y3 + 1; y4 < 100; y4 ++ ){if(num[y4] != 3) continue;//判斷月份和天數for(int m1 = y4 + 1; m1 < 100; m1 ++ )for(int m2 = m1 + 1; m2 < 100; m2 ++ )for(int d1 = m2 + 1; d1 < 100; d1 ++ )for(int d2 = d1 + 1; d2 < 100; d2 ++ ){int m = num[m1] * 10 + num[m2], d = num[d1] * 10 + num[d2];if(m >= 1 && m <= 12 && d >= 1 && d <= day[m]){int res = m * 100 + d;   //月份成100 + 天數設為對應哈希值st.insert(res);}}}}}}cout << (int)st.size() << endl;return 0;}
        B:01串的熵 套公式 + 暴力枚舉 解題思路

        題目大致意思就是給一個信息熵的公式,然后現在給你一個信息熵的值和字符串的長度,且字符串中只有0和1,由此逆推0出現的次數。

        這道題給出的定義和公式看起來有點嚇人,然而字符串中只有0和1兩種字符,所以只要枚舉套公式求解即可。

        答案11027421

        個人戰況

        這道題還挺簡單的,但是我被第一道題給影響到了,畢竟我第一道題都花了很多時間,然后一看第二個填空題,給了個看起來很復雜的公式,一下子不知道怎么去做,然后當時就跳過了這道題。雖然分值只有五分,但是還是很可惜的,沒能做這道簡單的填空題。

        代碼
        #include#includeusing namespace std;const double eps = 1e-4;const int N = 23333333;//填入公式bool check(int n0){int n1 = N - n0;double p0 = n0 * 1.0 / N, p1 = n1 * 1.0 / N;double res1 = n0 * p0 * log(1.0 / p0) / log(2);double res2 = n1 * p1 * log(1.0 / p1) / log(2);return fabs(res1 + res2 - 11625907.5798) <= eps;}int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);//枚舉0出現的次數for(int i = 0; i < (N >> 1); i ++ )if(check(i)) {cout << i << endl;break;}return 0;}
        C:冶煉金屬 找規律 + 數學 解題思路

        題目大致意思就是,給出若干組 \(a\) 和 \(b\),其中 \(a\) 是使用的金屬原料的數量,\(b\) 是消耗 \(a\) 個原料最多可以得到的新金屬的數量。假設每得到一個新金屬需要消耗 \(v\) 個原料,這道題要確定的就是 \(v\) 的范圍,即 \(v\) 的最小可能值和最大可能值。

        這本質上是一個數學題,通過找規律可以發現,\(v\) 的最大可能值,即所有 \(?a/b?\) 的最小值;\(v\) 的最小可能值,是所有 \(?a/(b+1)? + 1\) 的最小值。

        此結論也可以通過推公式來得到:假設每得到一個新金屬需要消耗 \(v\) 個原料,消耗 \(a\) 的原料得到 \(b\) 個新金屬,但是無法得到 \(b + 1\) 個新金屬,所以 \(b \times v\le a< (b+1)\times v\)

        由此可得:\(\frac{a}{b+1} < v\le \frac{a}{b} \)

        由于 \(v\) 是整數,所以最小值為 \(\frac{a}{b+1} + 1\),最大值為 \(\frac{a}{b}\) 。

        個人戰況

        這道題應該是拿了全分的,不過考試的時候一直在找規律,處理整除操作上的細節,沒有直接從數學的角度去推導公式,所幸最后還是做出來了。

        代碼
        #include#includeusing namespace std;int maxv = 1e9, minv;  //maxv確定最大值上限 minv確定最小值下限int main(){    ios::sync_with_stdio(false);    cin.tie(0); cout.tie(0);        int a, b, n; cin >> n;    while(n -- ){        cin >> a >> b;        maxv = min(maxv, a / b);        minv = max(minv, a / (b + 1) + 1);    }        cout << minv << " " << maxv << endl;        return 0;}
        D:飛機降落 全排列 + 貪心 解題思路

        題目大致意思是給定 \(n\) 架飛機的最早降落時間 \(t\),盤旋時間 \(d\) 以及降落所需時間 \(l\),每架飛機從開始降落到降落結束過程中,其它飛機都不能降落,通俗得說就是這段時間里空中只有這一架飛機正在降落。求是否存在一種排列方案,使得所有飛機都可以降落到地面。

        這道題本質上就是一個求不相交區間的問題,我一開始想到的是純貪心,考試的時候,我通過直覺判斷用最晚降落時間\(t + d\)進行升序排序,這樣的容錯率感覺會更高,樣例應該是過了的。

        但純貪心的思路是錯誤的,由于這道題的數據比較小,最多只有10,所以應當遞歸實現全排列枚舉,然后判斷是否存在一種排列能夠使得所有飛機降落成功即可。

        對于每一層遞歸,只需要知道上一層的降落結束時刻 \(last\),由于每架飛機有一個最早降落時間 \(t\),所以當前一層遞歸的最早降落結束時刻應取 \(max(last, t) + l\),\(l\) 為降落所需時間。為了使得容錯率更高,當最晚降落開始時間 \(t + d\) 大于等于 上一層的降落結束時刻,就可以將這架飛機作為下一個降落的飛機。

        個人戰況

        我自己只想到貪心,估計只能過一半甚至都不到的樣例。

        代碼
        #include#includeusing namespace std;const int N = 12;int n;struct node{    int t, d, l;  //t為此飛機的最早降落時間 d為盤旋時間 l為降落所需時間}p[N];bool st[N];//DFS求全排列模型bool dfs(int u, int last){    if(u == n) return true;    for(int i = 0; i < n; i ++ ){        int t = p[i].t, d = p[i].d, l = p[i].l;        if(st[i]) continue;        if(t + d >= last){  //最晚降落時間t+d大于等于上一層的降落結束時刻            st[i] = true;            if(dfs(u + 1, max(last, t) + l)) return true; //當前層的最早降落結束時刻為max(last,t)+l            st[i] = false;        }    }    return false;}int main(){    ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    int T; cin >> T;    while(T -- ){        cin >> n;        for(int i = 0; i < n; i ++ ){            int t, d, l; cin >> t >> d >> l;            p[i] = {t, d, l};        }        memset(st, 0, sizeof(st));        cout << (dfs(0, 0) ? "YES" : "NO") << endl;    }    return 0;}
        E:接龍數列 線性DP(最長上升子序列) 解題思路

        逆向思維來考慮這道題,刪除最少的數字得到接龍數列,實際上就是求整個序列的最長接龍子序列,而這個問題和最長上升子序列本質是一樣的,不同的是,兩個數字前后連接的方式不一樣。如果說最長上升子序列前后數字的連接方式是前一個數字比后一個數字小,那么接龍數列前后數字的連接方式就是前一個數字的末尾位與后一個數字的首位相同,這本質上都是一樣的,只是連接方式不同而已。

        想到最長上升子序列還不足以做出這道題,因為數據范圍達到了\(10^{5}\),所以需要優化成一維線性DP。

        可以發現,每一位數字的范圍是 \(0 - 9\) ,只需要記錄以每一位數字結尾的最長接龍數列長度即可,這樣顯然可以省去原本最長上升子序列內層的循環。

        用 \(dp[i]\) 表示以數字 \(i\) 為末尾的最長接龍數列長度。對于每個數字,若其首位為 \(a\),末位為 \(b\),這個數字只有可能作為之前某個末位數字為 \(a\) 的數字后面,由此可得狀態轉移方程: \(dp[b] = max(dp[b], dp[a] + 1)\)

        統計以每一位數字結尾的最長接龍數列長度的最大值,最后用原始序列長度減去這個最大值即答案。

        個人戰況

        考試的時候只想到最長上升子序列,并沒有想到優化方法,估計過了不到一半的樣例。

        代碼
        #includeusing namespace std;int dp[10];   //dp[i]表示以數字i為末尾的最長接龍數列int n, res;int main(){    ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    cin >> n;    for(int i = 1; i <= n; i ++ ){        string s; cin >> s;        int a = s[0] - "0", b = s.back() - "0";        dp[b] = max(dp[b], dp[a] + 1);        res = max(res, dp[b]);    }    cout << n - res << endl;    return 0;}
        F:島嶼個數 BFS 解題思路

        這道題比較考驗思維能力。我一開始一直將思維卡死在如何判斷一個島嶼連通塊是否處于一個環內,也就是子島嶼的判斷上,實際上,并不需要糾結于如何判斷子島嶼。

        很容易想到要使用 \(BFS\),主要問題在于如何避免統計子島嶼。

        只需要在外層加一層海洋,外層海洋可以涌入的地方,如果涌入的地方周圍有陸地,那么這塊陸地一定不在一個子島嶼中,反之,某個地方外層海洋無法涌入,一定是被某個環狀島嶼包圍所導致的,即位于某個子島嶼中。外層海洋無法涌入的地方,無需遍歷。

        從 \((0, 0)\) 處進行外層海洋的\(BFS\),由于島嶼是上下左右四個方向的,相較于其而言,外層海洋\(BFS\)時需要八個方向進行遍歷。在進行外層海洋\(BFS\)時,如果遍歷到周圍存在陸地,那么說明這個陸地所在的島嶼連通塊需要被統計,此時進行島嶼\(BFS\)。

        總之,需要實現兩個\(BFS\),并且在外層海洋\(BFS\)中,嵌套調用島嶼\(BFS\)。

        個人戰況

        這道題很慘烈,我個人覺得自己做的 \(BFS\) 的題還是比較多的,對 \(BFS\) 類型的題比較有信心,但是這個題難住我了,考試的時候想了一會沒有思路,最后直接寫了個普通的 \(BFS\) 寄希望于騙分。

        應該是0分,考完藍橋杯省賽出來,因為這道題沒能做出一點東西,感到挺難受的。

        代碼
        #include#include#includeusing namespace std;typedef pair pii;#define x first#define y secondint dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};const int N = 55;char g[N][N];bool vis[N][N];int n, m, res;//島嶼BFSvoid bfs(int sx, int sy){    queue q;    q.push({sx, sy});    vis[sx][sy] = true;    while(!q.empty()){        auto [x, y] = q.front();        q.pop();        for(int k = 0; k < 4; k ++ ){            int nx = x + dx[k], ny = y + dy[k];            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;            if(g[nx][ny] == "0" || vis[nx][ny]) continue;            q.push({nx, ny}), vis[nx][ny] = true;        }    }}//外層海洋BFSvoid bfs_sea(int sx, int sy){    queue q;    q.push({sx, sy});    vis[sx][sy] = true;    while(!q.empty()){        auto [x, y] = q.front();        q.pop();        for(int k = 0; k < 8; k ++ ){            int nx = x + dx[k], ny = y + dy[k];            if(nx < 0 || nx > n + 1 || ny < 0 || ny > m + 1 || vis[nx][ny]) continue;            if(g[nx][ny] == "1") bfs(nx, ny), res ++ ; //如果遇到外層海水領近的陸地            else q.push({nx, ny}), vis[nx][ny] = true;        }    }}int main(){    ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    int T; cin >> T;    while(T -- ){        cin >> n >> m;        res = 0;        memset(g, "0", sizeof(g));        memset(vis, 0, sizeof(vis));        for(int i = 1; i <= n; i ++ )            for(int j = 1; j <= m; j ++ )                cin >> g[i][j];        bfs_sea(0, 0);        cout << res << endl;    }    return 0;}
        G:子串簡寫 前綴和 解題思路

        題目大致意思就是給定一個字符串,統計長度大于等于 \(k\) ,且首尾字符分別為 \(c_{1}\) 和 \(c_{2}\) 的子字符串個數。

        很明顯可以用前綴和來求解。統計字符 \(c_{1}\) 的前綴和,可以由如下遞推式得到前綴和:

        \(\begin{cases} pre[i] = pre[i-1] + 1, & s[i]=c_{1} \\ pre[i] = pre[i-1], & s[i] \ne c_{1}\end{cases}\)

        然后枚舉字符 \(c_{2}\) 的位置,只要在原字符串上在遍歷一次,累加 \((0, i-k+1]\) 范圍內的前綴和:

        \(\begin{cases} res = res + pre[i - k + 1], & s[i]=c_{2} \\ res = res, & s[i] \ne c_{2}\end{cases}\)

        記得開 \(long long\) 。

        個人戰況

        這道題基本上五分鐘就做出來了,一下子就想到前綴和,應該是拿的全分。

        代碼
        #include#includeusing namespace std;typedef long long ll;const int N = 5e5 + 10;int pre[N], k;char s[N], a, b;int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> k;cin >> s + 1 >> a >> b;int n = strlen(s + 1);//計算字符1的前綴和for(int i = 1; i <= n; i ++ )if(s[i] == a) pre[i] = pre[i - 1] + 1;else pre[i] = pre[i - 1];ll res = 0;//枚舉字符2的位置 累加前綴和for(int i = k; i <= n; i ++ )if(s[i] == b) res += (ll)pre[i - k + 1];cout << res << endl;return 0;}
        H:整數刪除 堆 + 雙鏈表模擬 解題思路

        題目大致意思就是,給定一個長度為 \(n\) 的序列,執行 \(k\) 次操作,操作為:找到當前序列中最小的數,刪除它并將其累加到相鄰的兩個數中。最后得到 \(n - k\) 個數字,按照原始的相對順序輸出這些數字。

        每次要取出最小數字,可以用小根堆進行模擬,存儲序列的及其下標,關鍵之處在于每次執行完刪除操作后,數字相鄰的下標位置會發生改變。

        可以用雙鏈表的方式存儲相鄰位置的下標,前驅數組為 \(l[i]\) ,記錄的是下標 \(i\) 相鄰的左邊的下標;后繼數組為 \(r[i]\),記錄的是下標 \(i\) 相鄰的右邊的下標。所以刪除操作即:\(l[r[i]] = l[i], r[l[i]] = r[i];\) ,\(i\) 為當前位置的下標。

        采用了堆的數據結構,無法在刪除數字的同時,直接將這個刪除的數字累加到相鄰位置的數字當中。所以,可以開一個數組 \(c[]\) 將累加值預先存起來,如果當前取出的最小值,累加值不是0,那么說明這個數字不應當作為當前的刪除數字,此時需要加上\(c[i]\),重新入隊,并且將 \(c[i]\) 置0。

        模擬直到最后堆中剩余 \(n - k\) 個數字,執行完最后一步操作后,堆中的有些數字依然存在累加值,并且需要按照原始的相對順序輸出,所以最后要累加到 \(res[]\) 數組中。

        個人戰況

        這道題也挺慘的,考試的時候,模擬了半天,結果發現思路不對,沒有想到用雙鏈表的方式去記錄相鄰下標位置。消耗了很多時間,最后兜兜轉轉還是寫了個暴力。

        代碼
        #pragma GCC optimize(1)#pragma GCC optimize(2)#pragma GCC optimize(3)#include#include#include#includeusing namespace std;typedef long long ll;typedef pair pii;const int N = 5e5 + 10;ll c[N], res[N];   //c[i]表示i處當前累加的和int l[N], r[N];    //l[i]表示i的前驅下標  r[i]表示i的后一個下標int n, k;int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> k;priority_queue, greater > q;  //小根堆for(int i = 1; i <= n; i ++ ){ll x; cin >> x;q.push({x, i});l[i] = i - 1, r[i] = i + 1;  //記錄左右相鄰的下標}while((int)q.size() > n - k){auto [cur, idx] = q.top();q.pop();if(c[idx]) q.push({cur + c[idx], idx}), c[idx] = 0; //如果c[idx]不為0,當前最小值不能彈出,累加后入隊else{    //否則 當前最小值可以最為被選擇的數c[l[idx]] += cur, c[r[idx]] += cur;      //左右下標累加值增加l[r[idx]] = l[idx], r[l[idx]] = r[idx];  //左右相鄰下標更改}}while(!q.empty()){auto [cur, idx] = q.top();q.pop();res[idx] = cur + c[idx];}for(int i = 1; i <= n; i ++ ) if(res[i]) cout << res[i] << " ";return 0;}
        I:景區導游 最近公共祖先 tarjan求LCA 解題思路

        題目大致意思就是給定一個樹的結構,有 \(n - 1\) 條無向邊,并且給了一個長度為 \(k\) 的序列,這個序列是訪問節點的順序。現在可以跳過這個序列中的一個節點,分別求出跳過第 \(1、2、3...k\) 節點的最短路徑距離。

        也就是說,需要求無向圖兩點之間的最短距離,可以通過求每兩個點的最近公共祖先,進而求出兩點間的最短距離。由于是無向圖且是樹的結構,樹中的任何一個點都可以作為根節點,一般將節點 \(1\) 設為根節點。

        假設此時需要求出節點 \(a\) 和節點 \(b\) 之間的最短距離,\(dist[a]\) 表示節點 \(a\) 到根節點的距離,\(dist[b]\) 表示節點 \(b\) 到根節點的距離,\(lca(a, b)\) 表示兩個節點的最近公共祖先,姑且先將其命名為 \(anc\) 。通過畫圖可以知道,兩點之間的最短距離就是 \(dist[a] + dist[b] - 2 * dist[anc]\) 。

        在下圖中,比如要求節點 \(6\) 和節點 \(5\) 的最短距離,可以看出兩節點的最近公共祖先是節點 \(3\),所以最近距離為 \(dist[5] + dist[6] - 2 * dist[3]\)。

        我自己用的是 \(tarjan\) 算法求 \(LCA\)。由題意可知,需要存儲序列中相鄰兩個節點之間的詢問,以及一個節點跳過其序列中右邊相鄰的節點,與右邊相鄰節點的下一個節點之間的詢問。

        然后先求出不跳過任何節點時的初始最短距離之和 \(sum\),最后枚舉中間跳過的節點,求出所有最短路徑距離之和即可。假設跳過的節點為 \(i\),那么需要減去節點 \(i\) 到 節點 \(i - 1\) 和 節點 \(i\) 到節點 \(i + 1\) 的最短路徑距離,再加上節點 \(i - 1\) 到節點 \(i + 1\) 的最短路徑。其中,跳過節點 \(1\) 和節點 \(k\) 需要特殊處理一下。

        個人戰況

        這道題有點懊悔,自己 \(tarjan\) 求 \(LCA\) 的模板沒有背熟,考試的時候應該是寫錯了,而且這道題也可以用倍增法求\(LCA\),然而我之前幾乎沒有寫過倍增。主要問題還有存儲詢問的方式,感覺自己的思維還是太死了,考試時沒有想到用 \(map\) 來存儲詢問以及相對應的 \(LCA\) 。

        代碼
        #include#include#includeusing namespace std;typedef long long ll;typedef pair pii;#define x first#define y secondconst int N = 1e5 + 10, M = 2 * N;int h[N], e[M], ne[M], w[M], idx;map query[N];int fa[N];int a[N];ll dist[N];bool st[N];int n, k;void init(){memset(h, -1, sizeof(h));for(int i = 1; i <= n; i ++ ) fa[i] = i;}int find(int x){return fa[x] == x ? x : (fa[x] = find(fa[x]));}void add(int a, int b, int c){e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;}//dfs求得根節點到節點距離void dfs(int u, int fa){for(int i = h[u]; ~i; i = ne[i]){int v = e[i], c = w[i];if(fa == v) continue;dist[v] = dist[u] + c;dfs(v, u);}}//tarjan離線求LCAvoid tarjan(int u){st[u] = true;for(int i = h[u]; ~i; i = ne[i]){int v = e[i];if(!st[v]){tarjan(v);fa[v] = u;}}for(auto p : query[u]){int v = p.x;if(st[v]) query[u][v] = find(v);}}//最近公共祖先int lca(int a, int b){if(query[a][b]) return query[a][b];return query[b][a];}//兩點最近距離ll d1(int i){return dist[a[i]] + dist[a[i + 1]] - 2 * dist[lca(a[i], a[i + 1])];}//跳過i的兩點最近距離ll d2(int i){return dist[a[i - 1]] + dist[a[i + 1]] - 2 * dist[lca(a[i - 1], a[i + 1])];}int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> k;init();for(int i = 0; i < n - 1; i ++ ){int u, v, c; cin >> u >> v >> c;add(u, v, c), add(v, u, c);}for(int i = 1; i <= k; i ++ ) cin >> a[i];for(int i = 1; i <= k - 1; i ++ ) query[a[i]][a[i + 1]] = 0, query[a[i + 1]][a[i]] = 0;for(int i = 1; i <= k - 2; i ++ ) query[a[i]][a[i + 2]] = 0, query[a[i + 2]][a[i]] = 0;dfs(1, -1);tarjan(1);ll sum = 0;for(int i = 1; i <= k - 1; i ++ ) sum += d1(i);  //原始路線距離//枚舉跳過的節點cout << sum - d1(1) << " ";      //跳過節點1for(int i = 2; i <= k - 1; i ++ ) cout << sum - d1(i - 1) - d1(i) + d2(i) << " ";cout << sum - d1(k - 1) << endl; //跳過節點kreturn 0;}
        J:砍樹 樹上差分 + tarjan求LCA 解題思路

        題目大致意思就是,給定一個樹的結構,樹有 \(n\) 個節點,給定 \(m\) 對節點,找到一個編號最大的邊,使得去除這條邊之后,每一對節點不連通。

        由于這是一個樹的結構,節點與節點之間的路徑是唯一的。所以,假設每一對節點之間的路徑都走一遍,在 \(m\) 對節點所構成的路徑網絡中,有一條邊經過了 \(m\) 次,那么這條邊就是每一對節點之間路徑上都存在的邊。故去除這條邊之后,能夠使得每對節點不連通。樹中可能存在多條邊滿足這個條件,所以需要預先記錄邊的編號,并且最后返回編號最大的邊。

        對于每條邊經過的次數,采用樹上差分(邊差分)來處理。

        邊差分公式

        \(\begin{cases}diff[a] = diff[a] + 1 \\diff[b] = diff[b] + 1 \\diff[lca(a, b)] = diff[lca(a,b)] - 2\end{cases}\)

        可以根據一維差分公式對其進行推導,這里不多贅述。

        然后用 \(dfs\) 在樹上自底向上再求一下前綴和就可以了。在 \(dfs\) 過程中,如果存在經過了 \(m\) 次的邊且編號比先前更大,則進行答案的更新。

        個人戰況

        看到這道題的時候以及沒時間了,一點代碼也沒寫。不過即使有時間這題也做不出,之前沒有學習過樹上差分,我要學的東西還是很多啊......

        代碼
        #include#include#includeusing namespace std;const int N = 1e5 + 10, M = 2 * N;int h[N], e[M], ne[M], id[M], idx;int fa[N];int st[N];int diff[N];vector query[N];int n, m, res;void init(){memset(h, -1, sizeof(h));for(int i = 1; i <= n; i ++ ) fa[i] = i;}void add(int a, int b, int i){e[idx] = b, ne[idx] = h[a], id[idx] = i, h[a] = idx ++ ; }int find(int x){return fa[x] == x ? x : (fa[x] = find(fa[x]));}void tarjan(int u){    st[u] = 1;    for(int i=h[u]; ~i; i = ne[i]){        int v = e[i];        if(st[v])continue;        tarjan(v);        fa[v] = u;    }    for(auto v : query[u])        if(st[v] == 2) diff[v] ++ , diff[u] ++ , diff[find(v)] -= 2;    st[u] = 2;}int dfs(int u, int fa){int sum = diff[u];for(int i = h[u]; ~i; i = ne[i]){int v = e[i];if(v == fa) continue;int c = dfs(v, u);if(c == m) res = max(res, id[i]);sum += c;}return sum;}int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;init();for(int i = 1; i <= n - 1; i ++ ){int u, v; cin >> u >> v;add(u, v, i), add(v, u, i);}for(int i = 0; i < m; i ++ ){int u, v; cin >> u >> v;query[u].push_back(v), query[v].push_back(u);}tarjan(1);dfs(1, -1);cout << (res ? res : -1) << endl;return 0;}
        個人總結

        在寫題解的過程中,我時刻在反思自己有些方法為什么當時沒有想到,以及我究竟能夠在有限的時間里解決多少問題。我并沒有在短短的四小時內將自己的實力發揮到極致,不過把自己所會的東西都做好,還是非常不容易的,很明顯我沒有做到這一點,這也是我自己能力不足、缺乏經驗所導致的。未來的比賽有很多,雖然這次藍橋杯拿到了省一,但是我并不覺得我證明了自己的實力有多強,事實上,我只是發揮得馬馬虎虎并且運氣還不錯而已。

        我所在的學校在算法競賽這一方面很弱,這是難以忽略的事實。也許在學校里我個人還算是不錯的,但是看到別的學校,算法競賽氛圍真的很好,努力的學生很多,高手很多,而且老師也都很用心。我很羨慕。

        我一直以來都想去到更高的平臺參加比賽,去參加ACM什么的。我身處的環境,基本上決定了我未來的道路會充滿挫折,但這不會阻擋我去飛向更高的天空。

        關鍵詞:
        x 廣告
        x 廣告

        Copyright @  2015-2022 海外生活網版權所有  備案號: 滬ICP備2020036824號-21   聯系郵箱:562 66 29@qq.com