本文以洛谷平臺所提供的題目描述及評測數據為基礎進行講解。
前言:這是本人的藍橋杯試卷,大概排省一前40%的位置,實際上這屆題目偏難,我沒有做出太多的有效得分。我把當時的思路和現在學習的思路都復盤進來,希望給大家做個參考。
T1(5分)
題面描述
解析
根據題意,我們很快可以畫出左邊這張圖,這是一條可行的路徑。顯然是半徑r+弧長l
現在這個題面說“交替,不限次數”的使用兩種操作,那么這樣一下來可能把很多人又給嚇迷糊了。但是如果我們畫畫圖,按照右邊的圖去分析,我們會發現:不論怎么走,路徑長度是一樣的!這其實就有點考平面幾何的意思,你把水平路徑平移到x軸,圓弧路徑往右平移,這本質仍然是r+l。
第一個理論性的難題就過了。剩下的問題是,怎么求半徑和弧長?
半徑顯然用勾股定理,弧長我們要知道 l=r*θ,需要求這個角度。
考試的時候我發<cmath>沒有arctan這個函數,所以沒辦法,我自己手搓了一個二分法求arctan的值。回來我才知道求角度的函數是atan。遇事不決的時候,構造二分解方程是個不錯的選擇。
但是主播還是出錯了,原因在于:我把x和y看反了!我求的是半徑加藍色的弧長。。。怒虧五分
Code
#include <bits/stdc++.h>
#include <cmath>
#define eps 1e-6
using namespace std;
double x=233.0,y=666.0;
double l,r,sita;
double arctan(double y,double x);
int main() {r=sqrt(x*x+y*y);sita=arctan(y,x);//cout<<r<<' '<<sita<<endl;l=r*sita;cout<<(long long)(l+r)<<endl;return 0;
}
double arctan(double y,double x){double t1=0,t2=3.15/2,mid=(t1+t2)/2;while(fabs(t1-t2)>=eps){if(tan(mid)-y/x>eps){t2=mid;}else if(tan(mid)-y/x<-eps){t1=mid;}else{break;}mid=(t1+t2)/2; //cout<<t1<<' '<<t2<<' '<<tan(mid)<<' '<<y/x<<endl;}return mid;
}
T2(5分)
這題主播也是沒想明白,所以照搬(翻譯)的這個講解:
【藍橋杯】第十六屆C++B組省賽真題詳解_嗶哩嗶哩_bilibili
題面描述
解析
第一個條件就是說結果這是一個排序
第二個看起來很炸裂很復雜,但是實際上我們只要抓住兩條信息:
1.i可以等于j,那么先令i=j試試會怎么樣。測試代碼在第一段。
可以發現(不過確實很難往這方面想),1到1013的排列可以是亂的(A1012<=1013,A1013<=1013),從1014開始,Ai必須等于i本身。
2.既然i>=1014時,Ai等于i,那么令i<=1013,j>=1014,可以得到Ai*j<=i*j+2025,這個對于任意的j都成立。
對于任意的j都成立,而2025/1014和2025/2025向下取整都是1,那么Ai<=i+1。
也就是說,A1=1 2,A2=1 2 3,A3 = 1 2 3 4......但是數不能重復選擇。特殊的,A1013最高取1013,不能取1014,因為1014已經被A1014選走了。
所以實際上這是個選擇的問題,從A1開始選才不會亂,一直是乘下去,到最后是2^1012(而不是2^1013,因為上面解釋了,第1013個數實際上沒得選)
Code
#include <iostream>
#include <cmath>
using namespace std;
long long n=2025;
int main() {for(int i=1;i<=n;++i){cout<<i<<' '<<(int)sqrt(i*i+2025)<<endl;}return 0;
}
#include <iostream>
#define M 1000000007
using namespace std;
long long n=1012,res=1;
int main() {for(int i=1;i<=1012;++i){res=res*2%M;}cout<<res<<endl;return 0;
}
T3(10分)
題面描述
解析
這題我喜提0分,我在考試的時候是分奇偶討論的,好像是奇數還是偶數我推出來了全成立,剩下的有條件。
但是,這題比我想象的還更暴力無解:既然序列中的數字是連續遞增的整數,還可包括負數,那么我們構造的序列把前面和后面抵消掉,只剩下這個數字本身,就可以了,抵消的辦法就是把負數拉過來。比如3,我們構造-2 -1 0 1 2 3,-2到2抵消掉,只剩下3本身。
所以,對于大于1的數都成立,只有1不成立。
Code
注意,<bits/stdc++.h>不能用count,這本身是一個函數。
#include <iostream>
using namespace std;
long long n,x,count=0;
int main() {cin>>n;for(int i=1;i<=n;i++){cin>>x;if(x!=1)++count;}cout<<count;return 0;
}
T4(10分)
題面描述
解析
這其實就是一道很純粹的模擬題。
如果你做的是a=(b+c)/2;b=(a+c)/2;c=(a+b)/2;那么回家吧孩子,回家吧。值覆蓋都沒搞懂啊這是。
但是沒完,注意到k<=10^9,說明你的時間很可能會超。那就需要一個優化,手動推導就可以發現,a=b=c的時候直接break掉,可以省很多時間。
但是洛谷的數據莫名其妙有點抽風,,,見下,錯掉的全部是RE錯誤。我把if(a==b&&b==c)改成if(a==b&&b==c&&a==c)就過了。
Code
#include <iostream>
using namespace std;
long long T=0,k=0,a=0,b=0,c=0;
int main() {cin>>T;for(int i=1;i<=T;++i){cin>>a>>b>>c>>k;while(k!=0){if(a==b&&b==c&&a==c)break;long long ta=0,tb=0,tc=0;ta=(b+c)/2;tb=(a+c)/2;tc=(a+b)/2;a=ta;b=tb;c=tc;--k;}cout<<a<<' '<<b<<' '<<c<<endl;}return 0;
}
T5(15分)
題面描述
解析
這題開始上難度了,但是想要分析出來也并不難。
使得L達到最小值,那么有一個基本的出發點就是貪心。因為所有數字都是正的,那么后面的大于前面的,形成一個單調序列,才能夠讓L取最小。所以先把數組設為a,進行sort排序。
然后我們來計算每個a[i]^2-a[i-1]^2的值。構成一個數組b[i]。那么這題轉化為求b數組里面一個長度為m-1的子序列,使得和達到最小值。為什么是m-1,因為你選M個數,b數組只能得出m-1個值。那么顯然有暴力做法騙分。
但是,都分析到這一步子序列了,你就不能想著優化一下嗎!這個就是典型的前綴和的問題,我們構造一個前綴和數組c[i],那么求c[i+m-1]-c[i]的min就可以了,時間復雜度哐哐降!
Code
#include <iostream>
#include <algorithm>
using namespace std;
long long n,m;
long long a[100005]={0},b[100005]={0},c[100005]={0};
int main() {cin>>n>>m;for(int i=1;i<=n;++i){cin>>a[i];}sort(a+1,a+n+1);for(int i=2;i<=n;++i){b[i]=a[i]*a[i]-a[i-1]*a[i-1];c[i]=c[i-1]+b[i];}long long ans=c[m]-c[1];for(int i=1;i<=n-m+1;++i){//cout<<i+m-1<<' '<<i<<' '<<c[i+m-1]<<' '<<c[i]<<endl; if(c[i+m-1]-c[i]<ans)ans=c[i+m-1]-c[i];}cout<<ans;return 0;
}
/*可以拿下面的做測試,輸出應該為0。
6 2
1 2 3 4 4 5
*/
T6(15分)
略有遺憾的一題。
題面描述
解析
這是一篇非常有個人特色的題解。這是我省賽打的最后一道題,一開始用圖的dfsbfs我發現不給力,直接進行數學推導可能還會好一些,所以這篇題解傾向于數學和模擬。當時沒有完全正確,現在重新寫了一遍,知道了問題所在。
首先基礎的也是main函數里面的:把字符串翻譯成圖,用數組s去存儲。
除了數組s,我還開了一組數組a,這個是用來尋找'#'開頭和'#'結尾的。
我的基本思路是,要是碰見(1)..##..(2)..#.#.這樣的,我們直接定位到第三列和第五列,只要在中間去討論要不要補,而前面后面都是空白,那就沒有討論的必要。
所以我的bgn表示最開頭的#,fnl表示最尾巴的#,中間用一個循環,從bgn到fnl,從左向右檢測。
這個“檢測”的具體操作如下:
我們知道,一列分為四種情況:
(1)# (2). (3)# (4).
(1)#?(2). (3).? (4)#
我先進行"記憶化",定義一個lastpos,分別表示一些情況,你可以理解為方向:
lastpos=3,前面是(1),lastpos=2,前面是(4),lastpos=1,前面是(3),至于兩個點,不定義。
1.如果這一列都是#,也就是都是檢測器,那么ans就不用++了,"方向"改成3
2.如果這一列都是. ,也就是啥都沒有,那么ans必須++,然后"方向"不需要改變(在這里引入lastpos,也是為了防止中間有很多的. ,因為如果只看前一列,你是判斷不出前面的情況的)
3.如果這一列是情況(3),那么此時要討論前面的"方向"是什么:
如果lastpos=3,那么ans不需要++,你的lastpos=1,因為這一列的狀態不變。
如果lastpos=2,也就是上一個和這一個完全相反
也就是 .?# 或者 . . . . #這種中間全是點的(中間的已經被判斷出來并且ans++了,故等效于左邊)
? ? ? ? ? ?# .? ? ? ? ? #. . . .
那么加一個檢測器到右下角等效于這種情況:. #,現在你的lastpos就是3了,因為這列填滿了。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?# #
如果lastpos=1,那前面的情況和現在的情況是一樣的,那就不用動了,ans不用加,方向不用改。
4.如果這一列是情況(4),同理,你根據邏輯的對稱性也能推理出來。
那么現在我來說說我錯的點:lastpos=3和lastpos=2當時沒有討論清楚,我只有lastpos=1的討論
我給一個測試點:
..#.#..
.#.#.#.
如果只有lastpos=1,那么我需要補充四個點(除了最后一列都得補充)。但是實際只要補充兩個點。
因為我沒意識到,補充了點之后,這一列狀態就相當于lastpos=3了,也就是萬能墻了。
第二個錯的點就是,測試點全為...的時候要特判,不然我的邏輯答案是1(bgn=fnl,然后調到第二種情況ans++),洛谷會喜提19/20。
Code
#include<iostream>
#include<cmath>
using namespace std;
long long n;
string str1,str2;
char ch;
bool s[3][1000005]={0};
long long a[3][1000005]={0},topA=0,topB=0;
long long lastpos=0;
long long ans=0;
void fun();
int main()
{cin>>str1>>str2;n=str1.length();for(int i=1;i<=n;i++){ch=str1[i-1];if(ch=='#'){a[1][++topA]=i;s[1][i]=1;}}for(int i=1;i<=n;i++){ch=str2[i-1];if(ch=='#'){a[2][++topB]=i;s[2][i]=1;}}fun();cout<<ans;return 0;
}void fun()
{int bgn=min(a[1][1],a[2][1]),fnl=max(a[1][topA],a[2][topB]);//cout<<bgn<<' '<<fnl<<endl;if(topA==0&&topB==0) return;for(int i=bgn;i<=fnl;i++){if(s[1][i]==1&&s[2][i]==1){lastpos=3;}else if(s[1][i]==0&&s[2][i]==0){ans++;}else if(s[1][i]==1&&s[2][i]==0){if(lastpos==2){ans++;lastpos=3;}else{lastpos=1;}}else if(s[1][i]==0&&s[2][i]==1){if(lastpos==1){ans++;lastpos=3;}else{lastpos=2;}}}return ;
}
T7(20分)
題面描述
分析
我是對照著這篇來學習理解的
題解:P12136 [藍橋杯 2025 省 B] 生產車間 - 洛谷專欄
差不多關于這題的精神思想理解到位了,但是這一段的代碼實現我始終啃不下來,可能是背包題本身還不熟練吧。
這是我理解到的圖。這題的意思就是列舉每個點位所有的可能性。
T8(20分)
題面描述
解析
對于這題,我大概聽到9分鐘,就關掉視頻了,悟道了。大家也可以試試看能聽到多久你就明白了。
本題只有三種運算:加法、減法、異或,而異或等級最高。這個實際上是反邏輯的,計算機是先加減后異或。所以我在考試的時候搞了模擬,開一個數棧和一個符號棧去暴力,代碼特別長3^13次方也約等于10^6,只能騙前30%的點(不過6分也很香)。
那么本題的正解是什么呢?不可能是死算,那么我們能不能從樣例著手分析?
聰明的你從樣例其實就應該能發現了!對于一個空格,可以填+也可以填-,總有一個對應的方式,讓他們加起來和=0,只留下前面的數據。
所以,我們實際上留下來的是什么?
這個規律用我就不用文字表述啦(表達能力有限咳咳)
那么代碼怎么實現方便呢?每次都進行異或運算,顯然不合適。那么我們開一個數組a,a[i]=a[i-1]^輸入的數,就不用每次都來計算了,就很方便!
然后由于pow可能過大,要考慮模,而且每次都計算模冪非常麻煩,所以我們自己寫一個數組b存儲模冪運算結果。
Code
#include<iostream>
#define M 1000000007
using namespace std;
long long n,x,res=0;
long long a[100010]={0};
long long b[100010]={0};
void fun();
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>x;a[i]=a[i-1]^x;}b[0]=1;b[1]=3;for(int i=2;i<=n;i++){b[i]=(b[i-1]*3)%M;}for(int i=1;i<=n-1;i++){res=(res+a[i]*2*b[n-1-i])%M;}res=(res+a[n])%M;cout<<res<<endl;return 0;
}
綜上,藍橋杯不愧是數學杯。。。