這是我第一次參加藍橋杯的省賽，雖然沒什么參賽經(jīng)驗，但是自己做了很多前幾屆藍橋杯的題，不得不說，這一屆藍橋杯省賽的難度相較于之前而言還是比較大的。之前很流行藍橋杯就是暴力杯的說法，但是隨著參賽人數(shù)的增多，比賽認可度的提升，比賽題目的質(zhì)量也明顯越來越高了。這次省賽涉及知識點非常全面，而且難度都不?。}目涉及了暴力、模擬、數(shù)學、遞歸、動態(tài)規(guī)劃、廣度優(yōu)先搜索、前綴和、最近公共祖先等）。總得來說，大概就是“你知道題目考的是什么，但是就是不太會做”。這也是我在比賽過程中的真實感受。
不過最后成績還是不錯的，拿了省一。我算了一下自己的分數(shù)，大概是50-60分，頂多也就是對了五道題的樣子。我考完試都覺得可能完了，結(jié)果這個分數(shù)居然還能排在江蘇省一的中游，看來我運氣還是不錯的哈哈哈。
(資料圖片僅供參考)
時隔一個月，有些平臺上已經(jīng)有了第十四屆藍橋杯的題目，我打算記錄一下自己參賽的經(jīng)歷并寫下每道題的題解。PS: 本博客中編程題的代碼都是在Acwing平臺上提交且通過的代碼。
A：日期統(tǒng)計 暴力枚舉 解題思路第一道題是一個填空題，大致意思就是一個由100個數(shù)字組成的序列，統(tǒng)計符合"\(2023mmdd\)"格式的無重復子序列的個數(shù)，"\(2023mmdd\)"表示一個2023年的一個合法的日期，其中"\(mm\)"表示月份的兩位數(shù)字，"\(dd\)"表示天數(shù)的兩位數(shù)字。
我一開始有點不敢寫暴力，畢竟要八重循環(huán)呢！后來發(fā)現(xiàn)前四重循環(huán)在判斷年份的時候，由于年份確定為"2023"，故只需要判斷當前循環(huán)是否符合即可，如果不符合，就跳過這一整層的循環(huán)，比如說第一層循環(huán)，只需要判斷是否等于2就行，如果胡等于2，就跳過。這樣前面四重循環(huán)可以節(jié)省大量的運行時間，整個八重循環(huán)基本上就變成一個四重循環(huán)了，總共就100個數(shù)，所以可以在一秒左右的時間就跑出結(jié)果。
對于判重，我使用的是\(set\)，每出現(xiàn)一個合法日期，用 \(月份 × 100 + 天數(shù)\) 設為對應哈希值，放入\(set\)中。最后返回\(set\)的大小即答案。
答案： 235
個人戰(zhàn)況這道題做出來了，但是消耗了很多時間，一直不敢寫暴力，自己在考場上可能也有緊張的因素，而且我一直都喜歡睡懶覺，所以上午做題可能多少也影響到我的狀態(tài)了哈哈哈。幸好最后還是做出來了。
代碼#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]; //輸入數(shù)據(jù)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;//判斷月份和天數(shù)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 + 天數(shù)設為對應哈希值st.insert(res);}}}}}}cout << (int)st.size() << endl;return 0;} 題目大致意思就是給一個信息熵的公式，然后現(xiàn)在給你一個信息熵的值和字符串的長度，且字符串中只有0和1，由此逆推0出現(xiàn)的次數(shù)。
這道題給出的定義和公式看起來有點嚇人，然而字符串中只有0和1兩種字符，所以只要枚舉套公式求解即可。
答案：11027421
個人戰(zhàn)況這道題還挺簡單的，但是我被第一道題給影響到了，畢竟我第一道題都花了很多時間，然后一看第二個填空題，給了個看起來很復雜的公式，一下子不知道怎么去做，然后當時就跳過了這道題。雖然分值只有五分，但是還是很可惜的，沒能做這道簡單的填空題。
代碼#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出現(xiàn)的次數(shù)for(int i = 0; i < (N >> 1); i ++ )if(check(i)) {cout << i << endl;break;}return 0;} 題目大致意思就是，給出若干組 \(a\) 和 \(b\)，其中 \(a\) 是使用的金屬原料的數(shù)量，\(b\) 是消耗 \(a\) 個原料最多可以得到的新金屬的數(shù)量。假設每得到一個新金屬需要消耗 \(v\) 個原料，這道題要確定的就是 \(v\) 的范圍，即 \(v\) 的最小可能值和最大可能值。
這本質(zhì)上是一個數(shù)學題，通過找規(guī)律可以發(fā)現(xiàn)，\(v\) 的最大可能值，即所有 \(?a/b?\) 的最小值；\(v\) 的最小可能值，是所有 \(?a/(b+1)? + 1\) 的最小值。
此結(jié)論也可以通過推公式來得到：假設每得到一個新金屬需要消耗 \(v\) 個原料，消耗 \(a\) 的原料得到 \(b\) 個新金屬，但是無法得到 \(b + 1\) 個新金屬，所以 \(b \times v\le a< (b+1)\times v\)
由此可得：\(\frac{a}{b+1} < v\le \frac{a} \)
由于 \(v\) 是整數(shù)，所以最小值為 \(\frac{a}{b+1} + 1\)，最大值為 \(\frac{a}\) 。
個人戰(zhàn)況這道題應該是拿了全分的，不過考試的時候一直在找規(guī)律，處理整除操作上的細節(jié)，沒有直接從數(shù)學的角度去推導公式，所幸最后還是做出來了。
代碼#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;} 題目大致意思是給定 \(n\) 架飛機的最早降落時間 \(t\)，盤旋時間 \(d\) 以及降落所需時間 \(l\)，每架飛機從開始降落到降落結(jié)束過程中，其它飛機都不能降落，通俗得說就是這段時間里空中只有這一架飛機正在降落。求是否存在一種排列方案，使得所有飛機都可以降落到地面。
這道題本質(zhì)上就是一個求不相交區(qū)間的問題，我一開始想到的是純貪心，考試的時候，我通過直覺判斷用最晚降落時間\(t + d\)進行升序排序，這樣的容錯率感覺會更高，樣例應該是過了的。
但純貪心的思路是錯誤的，由于這道題的數(shù)據(jù)比較小，最多只有10，所以應當遞歸實現(xiàn)全排列枚舉，然后判斷是否存在一種排列能夠使得所有飛機降落成功即可。
對于每一層遞歸，只需要知道上一層的降落結(jié)束時刻 \(last\)，由于每架飛機有一個最早降落時間 \(t\)，所以當前一層遞歸的最早降落結(jié)束時刻應取 \(max(last, t) + l\)，\(l\) 為降落所需時間。為了使得容錯率更高，當最晚降落開始時間 \(t + d\) 大于等于 上一層的降落結(jié)束時刻，就可以將這架飛機作為下一個降落的飛機。
個人戰(zhàn)況我自己只想到貪心，估計只能過一半甚至都不到的樣例。
代碼#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大于等于上一層的降落結(jié)束時刻 st[i] = true; if(dfs(u + 1, max(last, t) + l)) return true; //當前層的最早降落結(jié)束時刻為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;} 逆向思維來考慮這道題，刪除最少的數(shù)字得到接龍數(shù)列，實際上就是求整個序列的最長接龍子序列，而這個問題和最長上升子序列本質(zhì)是一樣的，不同的是，兩個數(shù)字前后連接的方式不一樣。如果說最長上升子序列前后數(shù)字的連接方式是前一個數(shù)字比后一個數(shù)字小，那么接龍數(shù)列前后數(shù)字的連接方式就是前一個數(shù)字的末尾位與后一個數(shù)字的首位相同，這本質(zhì)上都是一樣的，只是連接方式不同而已。
想到最長上升子序列還不足以做出這道題，因為數(shù)據(jù)范圍達到了\(10^{5}\)，所以需要優(yōu)化成一維線性DP。
可以發(fā)現(xiàn)，每一位數(shù)字的范圍是 \(0 - 9\) ，只需要記錄以每一位數(shù)字結(jié)尾的最長接龍數(shù)列長度即可，這樣顯然可以省去原本最長上升子序列內(nèi)層的循環(huán)。
用 \(dp[i]\) 表示以數(shù)字 \(i\) 為末尾的最長接龍數(shù)列長度。對于每個數(shù)字，若其首位為 \(a\)，末位為 \(b\)，這個數(shù)字只有可能作為之前某個末位數(shù)字為 \(a\) 的數(shù)字后面，由此可得狀態(tài)轉(zhuǎn)移方程: \(dp[b] = max(dp[b], dp[a] + 1)\)
統(tǒng)計以每一位數(shù)字結(jié)尾的最長接龍數(shù)列長度的最大值，最后用原始序列長度減去這個最大值即答案。
個人戰(zhàn)況考試的時候只想到最長上升子序列，并沒有想到優(yōu)化方法，估計過了不到一半的樣例。
代碼#includeusing namespace std;int dp[10]; //dp[i]表示以數(shù)字i為末尾的最長接龍數(shù)列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;} 這道題比較考驗思維能力。我一開始一直將思維卡死在如何判斷一個島嶼連通塊是否處于一個環(huán)內(nèi)，也就是子島嶼的判斷上，實際上，并不需要糾結(jié)于如何判斷子島嶼。
很容易想到要使用 \(BFS\)，主要問題在于如何避免統(tǒng)計子島嶼。
只需要在外層加一層海洋，外層海洋可以涌入的地方，如果涌入的地方周圍有陸地，那么這塊陸地一定不在一個子島嶼中，反之，某個地方外層海洋無法涌入，一定是被某個環(huán)狀島嶼包圍所導致的，即位于某個子島嶼中。外層海洋無法涌入的地方，無需遍歷。
從 \((0, 0)\) 處進行外層海洋的\(BFS\)，由于島嶼是上下左右四個方向的，相較于其而言，外層海洋\(BFS\)時需要八個方向進行遍歷。在進行外層海洋\(BFS\)時，如果遍歷到周圍存在陸地，那么說明這個陸地所在的島嶼連通塊需要被統(tǒng)計，此時進行島嶼\(BFS\)。
總之，需要實現(xiàn)兩個\(BFS\)，并且在外層海洋\(BFS\)中，嵌套調(diào)用島嶼\(BFS\)。
個人戰(zhàn)況這道題很慘烈，我個人覺得自己做的 \(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 ++ ; //如果遇到外層海水領(lǐng)近的陸地 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;} 題目大致意思就是給定一個字符串，統(tǒng)計長度大于等于 \(k\) ，且首尾字符分別為 \(c_{1}\) 和 \(c_{2}\) 的子字符串個數(shù)。
很明顯可以用前綴和來求解。統(tǒng)計字符 \(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]\) 范圍內(nèi)的前綴和：
\(\begin{cases} res = res + pre[i - k + 1], & s[i]=c_{2} \\ res = res, & s[i] \ne c_{2}\end{cases}\)
記得開 \(long long\) 。
個人戰(zhàn)況這道題基本上五分鐘就做出來了，一下子就想到前綴和，應該是拿的全分。
代碼#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;} 題目大致意思就是，給定一個長度為 \(n\) 的序列，執(zhí)行 \(k\) 次操作，操作為：找到當前序列中最小的數(shù)，刪除它并將其累加到相鄰的兩個數(shù)中。最后得到 \(n - k\) 個數(shù)字，按照原始的相對順序輸出這些數(shù)字。
每次要取出最小數(shù)字，可以用小根堆進行模擬，存儲序列的值及其下標，關(guān)鍵之處在于每次執(zhí)行完刪除操作后，數(shù)字相鄰的下標位置會發(fā)生改變。
可以用雙鏈表的方式存儲相鄰位置的下標，前驅(qū)數(shù)組為 \(l[i]\) ，記錄的是下標 \(i\) 相鄰的左邊的下標；后繼數(shù)組為 \(r[i]\)，記錄的是下標 \(i\) 相鄰的右邊的下標。所以刪除操作即：\(l[r[i]] = l[i], r[l[i]] = r[i];\) ，\(i\) 為當前位置的下標。
采用了堆的數(shù)據(jù)結(jié)構(gòu)，無法在刪除數(shù)字的同時，直接將這個刪除的數(shù)字累加到相鄰位置的數(shù)字當中。所以，可以開一個數(shù)組 \(c[]\) 將累加值預先存起來，如果當前取出的最小值，累加值不是0，那么說明這個數(shù)字不應當作為當前的刪除數(shù)字，此時需要加上\(c[i]\)，重新入隊，并且將 \(c[i]\) 置0。
模擬直到最后堆中剩余 \(n - k\) 個數(shù)字，執(zhí)行完最后一步操作后，堆中的有些數(shù)字依然存在累加值，并且需要按照原始的相對順序輸出，所以最后要累加到 \(res[]\) 數(shù)組中。
個人戰(zhàn)況這道題也挺慘的，考試的時候，模擬了半天，結(jié)果發(fā)現(xiàn)思路不對，沒有想到用雙鏈表的方式去記錄相鄰下標位置。消耗了很多時間，最后兜兜轉(zhuǎn)轉(zhuǎn)還是寫了個暴力。
代碼#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的前驅(qū)下標 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{ //否則 當前最小值可以最為被選擇的數(shù)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;} 題目大致意思就是給定一個樹的結(jié)構(gòu)，有 \(n - 1\) 條無向邊，并且給了一個長度為 \(k\) 的序列，這個序列是訪問節(jié)點的順序?，F(xiàn)在可以跳過這個序列中的一個節(jié)點，分別求出跳過第 \(1、2、3...k\) 節(jié)點的最短路徑距離。
也就是說，需要求無向圖兩點之間的最短距離，可以通過求每兩個點的最近公共祖先，進而求出兩點間的最短距離。由于是無向圖且是樹的結(jié)構(gòu)，樹中的任何一個點都可以作為根節(jié)點，一般將節(jié)點 \(1\) 設為根節(jié)點。
假設此時需要求出節(jié)點 \(a\) 和節(jié)點 \(b\) 之間的最短距離，\(dist[a]\) 表示節(jié)點 \(a\) 到根節(jié)點的距離，\(dist[b]\) 表示節(jié)點 \(b\) 到根節(jié)點的距離，\(lca(a, b)\) 表示兩個節(jié)點的最近公共祖先，姑且先將其命名為 \(anc\) 。通過畫圖可以知道，兩點之間的最短距離就是 \(dist[a] + dist[b] - 2 * dist[anc]\) 。
在下圖中，比如要求節(jié)點 \(6\) 和節(jié)點 \(5\) 的最短距離，可以看出兩節(jié)點的最近公共祖先是節(jié)點 \(3\)，所以最近距離為 \(dist[5] + dist[6] - 2 * dist[3]\)。
我自己用的是 \(tarjan\) 算法求 \(LCA\)。由題意可知，需要存儲序列中相鄰兩個節(jié)點之間的詢問，以及一個節(jié)點跳過其序列中右邊相鄰的節(jié)點，與右邊相鄰節(jié)點的下一個節(jié)點之間的詢問。
然后先求出不跳過任何節(jié)點時的初始最短距離之和 \(sum\)，最后枚舉中間跳過的節(jié)點，求出所有最短路徑距離之和即可。假設跳過的節(jié)點為 \(i\)，那么需要減去節(jié)點 \(i\) 到 節(jié)點 \(i - 1\) 和 節(jié)點 \(i\) 到節(jié)點 \(i + 1\) 的最短路徑距離，再加上節(jié)點 \(i - 1\) 到節(jié)點 \(i + 1\) 的最短路徑。其中，跳過節(jié)點 \(1\) 和節(jié)點 \(k\) 需要特殊處理一下。
個人戰(zhàn)況這道題有點懊悔，自己 \(tarjan\) 求 \(LCA\) 的模板沒有背熟，考試的時候應該是寫錯了，而且這道題也可以用倍增法求\(LCA\)，然而我之前幾乎沒有寫過倍增。主要問題還有存儲詢問的方式，感覺自己的思維還是太死了，考試時沒有想到用 \(map\) 來存儲詢問以及相對應的 \(LCA\) 。
代碼#include#include#include 題目大致意思就是，給定一個樹的結(jié)構(gòu)，樹有 \(n\) 個節(jié)點，給定 \(m\) 對節(jié)點，找到一個編號最大的邊，使得去除這條邊之后，每一對節(jié)點不連通。
由于這是一個樹的結(jié)構(gòu)，節(jié)點與節(jié)點之間的路徑是唯一的。所以，假設每一對節(jié)點之間的路徑都走一遍，在 \(m\) 對節(jié)點所構(gòu)成的路徑網(wǎng)絡中，有一條邊經(jīng)過了 \(m\) 次，那么這條邊就是每一對節(jié)點之間路徑上都存在的邊。故去除這條邊之后，能夠使得每對節(jié)點不連通。樹中可能存在多條邊滿足這個條件，所以需要預先記錄邊的編號，并且最后返回編號最大的邊。
對于每條邊經(jīng)過的次數(shù)，采用樹上差分（邊差分）來處理。
邊差分公式：
\(\begin{cases}diff[a] = diff[a] + 1 \\diff[b] = diff[b] + 1 \\diff[lca(a, b)] = diff[lca(a,b)] - 2\end{cases}\)
可以根據(jù)一維差分公式對其進行推導，這里不多贅述。
然后用 \(dfs\) 在樹上自底向上再求一下前綴和就可以了。在 \(dfs\) 過程中，如果存在經(jīng)過了 \(m\) 次的邊且編號比先前更大，則進行答案的更新。
個人戰(zhàn)況看到這道題的時候以及沒時間了，一點代碼也沒寫。不過即使有時間這題也做不出，之前沒有學習過樹上差分，我要學的東西還是很多啊......
代碼#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;} 在寫題解的過程中，我時刻在反思自己有些方法為什么當時沒有想到，以及我究竟能夠在有限的時間里解決多少問題。我并沒有在短短的四小時內(nèi)將自己的實力發(fā)揮到極致，不過把自己所會的東西都做好，還是非常不容易的，很明顯我沒有做到這一點，這也是我自己能力不足、缺乏經(jīng)驗所導致的。未來的比賽有很多，雖然這次藍橋杯拿到了省一，但是我并不覺得我證明了自己的實力有多強，事實上，我只是發(fā)揮得馬馬虎虎并且運氣還不錯而已。
我所在的學校在算法競賽這一方面很弱，這是難以忽略的事實。也許在學校里我個人還算是不錯的，但是看到別的學校，算法競賽氛圍真的很好，努力的學生很多，高手很多，而且老師也都很用心。我很羨慕。
我一直以來都想去到更高的平臺參加比賽，去參加ACM什么的。我身處的環(huán)境，基本上決定了我未來的道路會充滿挫折，但這不會阻擋我去飛向更高的天空。
Copyright @ 2015-2022 海外生活網(wǎng)版權(quán)所有 備案號： 滬ICP備2020036824號-21 聯(lián)系郵箱：562 66 29@qq.com