前言

一年一度的🏀杯馬上就要開始了，為了取得更好的成績，好名字寫了下前年2023年藍橋杯的省賽真題，感覺題目還不錯（好難）為此來寫篇博客重溫一下這幾個題。也可以幫助一下第一次參加藍橋杯的新手小白更好沖擊省一。
2023年的題目感覺比我們2024年的題目難（還好我不是去年參加的），不過🏀杯聲名遠揚，打打暴力可能就能獲獎省一，從此成為同學眼中的“大神”。
只寫了5個題，剩下的再看看。。。

日期統計

題意：

直接上圖片吧，節省時間。
這題一看就非常簡單了，畢竟作為第一題肯定不會太難。寫出來第一題估計就能省三到省二區間了，大家也可以移步去看看。24年的第一題（更簡單）
我們直接暴力打表，六七層循環跑出來，但是要注意其中的細節，這題就是考細節了。
代碼就不展示了，好名字的代碼找不到了，反正就是這樣，然后再那樣，相信你們都懂。
最后得到的答案是235。
這題so easy ，必須確保拿下。

冶煉金屬

題意：

這是一個數學+二分的題目。我們可以知道
$75?20=3$
$75?21=3$
$75?22=3$
。。。看下來我們可以知道75除以一個區間的數字都是可以等于3，所以對于每一組數據，我們都有一個區間的值符合要求，那么我們可以求出來每一個數據的區間，最后對他們取∩，我們就可以得到最小值，再進行一次取∩我們可以得到最大值。這是二分答案的寫法。不會二分答案的同學，可以移步這里。
我看有人用數學的方法也可以寫，這里就不做演示了。
這個題在我去年打藍橋杯的時候就寫過博客，大家可以進我主頁看看。給朱波點點關注

int n;
vector<int>a,b;void Solve () {cin>>n;a.resize(n+1);b.resize(n+1);//vector容器的重構大小for (int i=1;i<=n;i++) {cin>>a[i]>>b[i];}int left =-1e9,right=1e9;for (int i=1;i<=n;i++) {int l = 1,r = 1e9;while (l<r) {int mid = l+r>>1;if (a[i]/mid<=b[i]) r = mid;else l = mid+1;}left = max(left,l);}for (int i=1;i<=n;i++) {int l = 1,r = 1e9;while (l<r) {int mid = l+r+1>>1;if (a[i]/mid>=b[i]) l = mid;else r = mid-1;}right = min(right,l);}//兩次二分cout<<left<<' '<<right;return ;
}

這題可以搞，easy。

島嶼個數

題意：

大眼一看主播就知道這是一個搜索題，不過子島嶼的存在讓主播有些許的頭疼，不過利用瞪眼法我們可以知道，如果一個島嶼外面的海洋是公共的海洋，那么這個島嶼就沒有被包圍，這個島嶼就不是子島嶼。
所以，我們可以先DFS一遍外海洋，全部標記一遍，再利用這類題的傳統解法。??我們題目給出的邊界之外全部都是海洋，所以我們可以自己處理一下，像這樣

然后附上代碼

char a[100][100];
int n,m;
int dx[]={0,0,1,-1,-1,1,-1,1},dy[]={1,-1,0,0,1,1,-1,-1};
int vis1[100][100],vis2[100][100];
int f = 0;
void dfs1 (int x,int y) {for (int i=0;i<8;i++) {int nx = x+dx[i],ny = y+dy[i];if (nx<0||nx>n+1||ny<0||ny>m+1||vis1[nx][ny]||a[nx][ny]=='1') continue;vis1[nx][ny] = 1;dfs1(nx,ny);}
}void dfs2 (int x,int y) {for (int i=0;i<4;i++) {int nx = x+dx[i],ny = y+dy[i];if (nx<0||nx>n+1||ny<0||ny>m+1||vis2[nx][ny]) continue;		if (vis1[nx][ny]==1) f =1;	if (a[nx][ny]=='1'){vis2[nx][ny] = 1;dfs2(nx,ny);}	}
}void Solve () {cin>>n>>m;memset(vis1,0,sizeof vis1);memset(vis2,0,sizeof vis2);for (int i=1;i<=n;i++) {for (int j=1;j<=m;j++) {cin>>a[i][j];}}for (int i=0;i<=n+1;i++) {for (int j=0;j<=m+1;j++) {if (i==0||i==n+1||j==0||j==m+1) a[i][j] = '0';}}vis1[0][0]=1;dfs1(0,0);int ans = 0;for (int i=1;i<=n;i++) {for (int j=1;j<=m;j++) {if (a[i][j]=='1' && vis2[i][j]==0) {vis2[i][j]=1;f = 0;dfs2 (i,j);if (f) {ans++;}}}}cout<<ans<<'\n';return ;
}

注意記得初始化，主播因為沒有初始化一開始，看了半天不知道哪里出錯了，這是個多實例！！！
這個題也不難，不過OI賽制下可能寫搜索題可能不太友好。說不定就差一個字母，這個題都沒分。

子串簡寫

題意：

這一題找有多少符合條件的子串，并且要求這個子串的長度不能小于k，這個子串的首尾兩個字母要和樣例給出的一樣，我們發現當我們在某處符合條件再往后找的時候，但凡出現字符b都是符合條件的。
舉個例子：

首字母為a，尾字母為b，長度為4）
adcb這個答案顯然為1
adcbb這個就是2
adcbbbbb這個就是5
aadcbbbbb這個就是10

我們可以看出，這顯然和前綴和有關，所以我們思考一下，就可以知道，這個和前綴和其實沒啥關系，但是和后綴和關系就大了，我們對串預處理一下，出現b的位置標為1，否則就是0。
然后用后綴和相加起來，我們可以輸出一下這個后綴和看下，以樣例為例

4 4 3 3 2 2 1 1

而后我們遍歷這個串，從出現a的位置往后找k位，用后綴和快速找到后面有多少b，就是這個位置往后有多少符合條件的解，最后全部加起來就是答案。

void Solve () {int k;cin>>k;string s;cin>>s;s = " "+s;int t = s.size();vector<int>x(t+2);char a,b;cin>>a>>b;for (int i=1;s[i];i++) {if (s[i]==b) x[i] = 1;else x[i] = 0;}for (int i=t-1;i>=1;i--) {x[i] = x[i+1]+x[i];}int ans = 0;for (int i=1;i<s.size()-k+1;i++) {if (s[i]==a) {ans+=x[i+k-1];}}cout<<ans<<'\n';return ;
}

這個題賽時可以全寫完，不難。

整數刪除

題意：

這一題真的是挺不容易的，難度我覺得在CF1400+，主要就是對于小根堆的處理。不知道大小根堆的人有難了。還是去看下大小根堆的介紹理解一下吧。
每次刪除一個最小數，我們很容易就能想到是小根堆的利用，但是本題會讓其他數字也發生變化，我們又不能對于小根堆里面的數字進行更改，怎么辦呢？
不能改我們就不改了嘛，我們用一個數組存一下每個位置改變的值，當要刪除這個數字的時候，看看你會不會被前面刪除的數字影響，就比如1,2,3我們先刪除1，那么下一個2就會受影響變成3。同時如果是2 1 3的話，我們刪除1，這時2的右領居和3的左領居就會發生變化，我們下次變化的時候就要進行調整。
所以我們要對于每一個數字的左右領居進行維護，然后用一個cnt數組記錄每個位置的變化情況。
最后對于小根堆不停的刪除最小的數字，當這個即將刪除的數字會被之前的刪除的數字影響，我們就push這個數字加上cnt的值放進小根堆里面。（小根堆還會自動排序，太好用了！）再進行判斷。
最后輸出就行了，看下代碼。

priority_queue<PII,vector<PII>,greater<PII>>q;//用pair開小根堆記錄這個值，和位置
void Solve () {int n,k;cin>>n>>k;vector<int>l(n+10),r(n+10);for (int i=1;i<=n;i++) {int x;cin>>x;q.push({x,i});l[i] = i-1;r[i] = i+1;}vector<int>cnt(n+10,0);   while (k--) {int x = q.top().fi;int id = q.top().se;q.pop();    if (cnt[id]) {q.push({x+cnt[id],id});k++;//重新放進去再進行判斷，所以k++cnt[id] = 0;}else {int le = l[id],ri = r[id];cnt[le] += x;cnt[ri] += x;r[le] = ri; l[ri] = le;//變化id這個位置的左右鄰居}}map<int,int>mp;while (q.size()) {int x = q.top().fi;int y = q.top().se;q.pop();mp[y] += (x+cnt[y]);}for (auto t : mp) cout<<t.se<<' ';    return ;
}

注意數組要開大一點，不然就會像我一樣WA好幾發（藍橋杯賽場就炸缸了）
感覺這一題挺好的，可以細細斟酌一下。

總結

藍橋杯不用想著把正解搞出來，其實暴力跑跑已經可以超過絕大部分人了（在弱省），好好備戰，補藥讓300塊打水漂。