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