題目結(jié)構(gòu)

題目類型分值

第一題	結(jié)果填空	15分
第二題	結(jié)果填空	47分
第三題	代碼填空	25分
第四題	程序設(shè)計(jì)	35分
第五題	程序設(shè)計(jì)	79分
第六題	程序設(shè)計(jì)	99分

---

第一題 36進(jìn)制

• 問題描述

  對于16進(jìn)制，我們使用字母A-F來表示10及以上的數(shù)字。
  如法炮制，一直用到字母Z，就可以表示36進(jìn)制。
  36進(jìn)制中，A表示10，Z表示35，AA表示370
  你能算出 MANY 表示的數(shù)字用10進(jìn)制表示是多少嗎?

  輸出

  輸出一個整數(shù)表示答案

• 解題思路

  36進(jìn)制。位權(quán)值為36。累加位權(quán)和即可。

• 代碼

/***@filename:36進(jìn)制*@author: pursuit*@CSDNBlog:unique_pursuit*@email: 2825841950@qq.com*@created: 2021-04-02 21:47 **/ #include <bits/stdc++.h>using namespace std;typedef long long ll; const int maxn = 100000 + 5; const int mod = 1e9+7;//36進(jìn)制。位權(quán)值為36. void solve(){//MANY//cout<<ll(('M'-'A'+10)*powl(36,3)+('A'-'A'+10)*powl(36,2)+('N'-'A'+10)*36+('Y'-'A'+10))<<endl;cout<<1040254<<endl; } int main(){solve();return 0; }

• 答案

  $1040254$

第二題 瓷磚樣式

• 問題描述

  小明家的一面裝飾墻原來是 $3\times 10$ 的小方格。
  現(xiàn)在手頭有一批剛好能蓋住$2$個小方格的長方形瓷磚。
  瓷磚只有兩種顏色：黃色和橙色。
  小明想知道，對于這么簡陋的原料，可以貼出多少種不同的花樣來。
  小明有個小小的強(qiáng)迫癥：忍受不了任何$2\times 2$的小格子是同一種顏色。
  （瓷磚不能切割，不能重疊，也不能只鋪一部分。另外，只考慮組合圖案，請忽略瓷磚的拼縫）
  顯然，對于 $2\times 3$ 個小格子來說，口算都可以知道：一共$10$種貼法。
  但對于 $3\times 10$ 的格子呢？肯定是個不小的數(shù)目，請你利用計(jì)算機(jī)的威力算出該數(shù)字。
  

  輸出

  輸出一個整數(shù)表示答案

• 解題思路

  對于這道題，我們很容易就想到利用$dfs$暴力去解決，那么我們需要注意的就是如何去表示整個方格以及如何判斷是否符合要求并判重。 對于表示整個方格，我們可以用字符串來表示，也可以用二維數(shù)值數(shù)組來表示，那么這樣我們就需要說明各自代表的是什么，該題黃色我表示為$1$，未填表示為$0$，橙色表示為$?1$。那么對于判斷是否符合要求，直接累加$2\times 2$的方格值即可，判斷是否模$4$為$0$。這很方便，我們也很容易證明，若方格值顏色相同，那么自然是模$4$為$0$的。再回到判重，我們可以將二維數(shù)值數(shù)組轉(zhuǎn)化為字符串放入$set$中，也可以將二維數(shù)組轉(zhuǎn)化為$1$個值，這里采用二進(jìn)制的權(quán)值，那么這樣我們總能保證不相同得到的和是不相同的。

• 代碼

/***@filename:瓷磚樣式*@author: pursuit*@csdn:unique_pursuit*@email: 2825841950@qq.com*@created: 2021-04-29 17:05 **/ #include <bits/stdc++.h>using namespace std;typedef long long ll; const int maxn = 1000 + 5; const int mod = 1e9+7;//對于這個題，我們可以直接用dfs模擬，那么方格表示我們可以用二維數(shù)組來實(shí)現(xiàn)。 //其中1表示黃色，0表示黃色，-1表示未填，注意用set判重，判重的方法我們可以采用倍增思想表示一個數(shù)。 int n,m;//n*m大小的方格。 int a[maxn][maxn]; set<int> t; bool judge(){//由于我們用值來表示，也就是說若存在2*2顏色相同的方格，那么其中的值一定模4為0。for(int i = 0; i < n-1; i++){for(int j = 0; j < m-1; j++){if((a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1])%4==0){return false;}}}return true; } void add(){int ans=0,temp=1;for(int i=0;i<n;i++){for(int j=0;j<m;j++){ans+=a[i][j]*temp;temp*=2;}}t.insert(ans); } void dfs(int step){//用step來抽象化二維坐標(biāo)。if(step == n*m){//由于下標(biāo)從0開始，說明已經(jīng)過完了n*m個坐標(biāo)。開始判斷。if(judge()){add();}return;}int x = step / m , y = step % m ;if(a[x][y]!=-1)dfs(step+1);else{//判斷是否能橫著放或者豎著放。if(x+1<n&&a[x+1][y]==-1){//說明能豎著放。a[x][y]=a[x+1][y]=1;dfs(step+1);a[x][y]=a[x+1][y]=0;dfs(step+1);a[x][y]=a[x+1][y]=-1;//復(fù)原。}//注意這里一定要兩邊都要抉擇。if(y+1<m&&a[x][y+1]==-1){//說明能橫著放。a[x][y]=a[x][y+1]=1;dfs(step+1);a[x][y]=a[x][y+1]=0;dfs(step+1);a[x][y]=a[x][y+1]=-1;//復(fù)原。}} } void solve(){//我們.要注意模擬。memset(a,-1,sizeof(a));dfs(0);cout<<t.size()<<endl;//101466 } int main(){cin>>n>>m;solve();return 0; }

• 答案

  $101466$

第三題 希爾伯特曲線

• 問題描述

  希爾伯特曲線是以下一系列分形曲線 Hn 的極限。我們可以把 Hn 看作一條覆蓋$2^n\times 2^n$ 方格矩陣的曲線，曲線上一共有 $2^n\times 2^n$ 個頂點(diǎn)(包括左下角起點(diǎn)和右下角終點(diǎn))，恰好覆蓋每個方格一次。

  Hn(n > 1)可以通過如下方法構(gòu)造：

• 將 Hn-1 順時針旋轉(zhuǎn)90度放在左下角
• 將 Hn-1 逆時針旋轉(zhuǎn)90度放在右下角
• 將2個 Hn-1 分別放在左上角和右上角
• 用3條單位線段把4部分連接起來

對于 Hn 上每一個頂點(diǎn) p ，我們定義 p 的坐標(biāo)是它覆蓋的小方格在矩陣中的坐標(biāo)(左下角是$$(1,1)$$，右上角是$$(2^n,2^n)$$，從左到右是X軸正方向，從下到上是Y軸正方向)，
定義 p 的序號是它在曲線上從起點(diǎn)開始數(shù)第幾個頂點(diǎn)(從1開始計(jì)數(shù))。

以下程序?qū)τ诮o定的$n(n<=30)$和p點(diǎn)坐標(biāo)$(x,y)$，輸出p點(diǎn)的序號。請仔細(xì)閱讀分析源碼，填寫劃線部分缺失的內(nèi)容。

#include <stdio.h>long long f(int n, int x, int y) {//n代表的是方格矩陣Hn，大小為2^n*2^nif (n == 0) return 1;//由于遞歸到了H0，那么自然為1.int m = 1 << (n - 1);//即m=2^(n-1)次方。if (x <= m && y <= m) {return f(n - 1, y, x);//這里表明，如果x和y是屬于左下角的子矩陣，那么我們就遞歸去尋找，由于左下角的子矩陣是順時針翻轉(zhuǎn)的，那么我們需要更改x和y}if (x > m && y <= m) {//同理，這里則是右下角的子矩陣。根據(jù)前面的分析，這道題其實(shí)就易解了。注意這個子矩陣是逆時針翻轉(zhuǎn)過來的。//如果沒有翻轉(zhuǎn)，坐標(biāo)是(x-m,y)，現(xiàn)在需要翻轉(zhuǎn)，則為(m-y+1,m-(x-m)+1)//return 3LL * m * m + f(n - 1, ________________ , m * 2 - x + 1); // 填空return 3LL * m * m + f(n - 1, m-y+1 , m * 2 - x + 1); // 填空}if (x <= m && y > m) {//這里為左上角的子矩陣，那么我們需要加上已經(jīng)過去了的m*m的序號。//這里坐標(biāo)我們是需要更改的，因?yàn)槲覀冞f歸到左上角的Hn-1矩陣了，那么坐標(biāo)自然要更改。return 1LL * m * m + f(n - 1, x, y - m);}if (x > m && y > m) {//這里為右上角的子矩陣，那么我們需要加上已經(jīng)過去了的2*m*m的序號。return 2LL * m * m + f(n - 1, x - m, y - m);} }int main() { int n, x, y;scanf("%d %d %d", &n, &x, &y); printf("%lld", f(n, x, y));//給定p點(diǎn)的坐標(biāo)，輸出p點(diǎn)的序號。return 0; }

• 解題思路

  題目分析已貼于代碼中，這道題主要就是理清題意即可。

• 答案

  m-y+1

第四題 發(fā)現(xiàn)環(huán)

• 問題重現(xiàn)

  小明的實(shí)驗(yàn)室有N臺電腦，編號1~N。原本這N臺電腦之間有N-1條數(shù)據(jù)鏈接相連，恰好構(gòu)成一個樹形網(wǎng)絡(luò)。
  在樹形網(wǎng)絡(luò)上，任意兩臺電腦之間有唯一的路徑相連。
  不過在最近一次維護(hù)網(wǎng)絡(luò)時，管理員誤操作使得某兩臺電腦之間增加了一條數(shù)據(jù)鏈接，于是網(wǎng)絡(luò)中出現(xiàn)了環(huán)路。
  環(huán)路上的電腦由于兩兩之間不再是只有一條路徑，使得這些電腦上的數(shù)據(jù)傳輸出現(xiàn)了BUG。
  為了恢復(fù)正常傳輸。小明需要找到所有在環(huán)路上的電腦，你能幫助他嗎？

  輸入

  第一行包含一個整數(shù)N。
  以下N行每行兩個整數(shù)a和b，表示a和b之間有一條數(shù)據(jù)鏈接相連。
  對于30%的數(shù)據(jù)，$1<=N<=1000$
  對于100%的數(shù)據(jù), $1<=N<=100000，1<=a,b<=N$
  輸入保證合法。

  輸出

  按從小到大的順序輸出在環(huán)路上的電腦的編號，中間由一個空格分隔。

  樣例輸入

  5 1 2 3 1 2 4 2 5 5 3

  樣例輸出

  1 2 3 5

• 解題思路

  • 拓?fù)渑判?/strong>

    我們都知道拓?fù)渑判驅(qū)嶋H上僅能適用于有向無環(huán)圖的，那這里如果我們要強(qiáng)行應(yīng)用在無向圖中，應(yīng)該要注意什么？首先，現(xiàn)在入度為$1$和$0$的都是起點(diǎn)，而不再是以入度為$0$作為標(biāo)志了，同樣，由于是無向圖，我們需要認(rèn)為一條邊上的兩個頂點(diǎn)入度都需要增加。知道了這樣，實(shí)際上我們就可以處理了，最后沒有入隊(duì)的即是存在環(huán)的。

  • 并查集處理連通+dfs查找環(huán)

    并查集處理這道題其實(shí)是非常方便的，我們怎么判斷出現(xiàn)環(huán)了呢？即是當(dāng)所加入的邊上的兩個頂點(diǎn)已經(jīng)連通在一起了，我們?nèi)绻俅芜B接就會出現(xiàn)環(huán)路。那么查找環(huán)也是一個問題，我們需要確定環(huán)路的起點(diǎn)和終點(diǎn)，而結(jié)束狀態(tài)則是起點(diǎn)已經(jīng)到達(dá)了終點(diǎn)，利用dfs的思想搜索路徑，值得注意的是，我們需要還原狀態(tài)，因?yàn)榭赡芪覀儺?dāng)前走的路徑并不是正確的，所以必須還原到上一個狀態(tài)。并且，當(dāng)我們已經(jīng)搜索完回路之后，我們需要標(biāo)記我們已經(jīng)找到了，避免重新開始而進(jìn)入死循環(huán)。

• 代碼

  • 拓?fù)渑判?/strong>

/***@filename:發(fā)現(xiàn)環(huán)(拓?fù)渑判?*@author: pursuit*@csdn:unique_pursuit*@email: 2825841950@qq.com*@created: 2021-04-29 19:32 **/ #include <bits/stdc++.h>using namespace std;typedef long long ll; const int maxn = 100000 + 5; const int mod = 1e9+7;//我們需要使用拓?fù)渑判蛉ソ鉀Q這道題。 int indegree[maxn];//indegree[i]表示的即是頂點(diǎn)i的入度有多少。 bool vis[maxn];//vis[i]表示頂點(diǎn)i是否已經(jīng)入隊(duì)。 int n,a,b; vector<int> g[maxn]; void solve(){//現(xiàn)在我們需要去判斷哪些點(diǎn)的入隊(duì)為0.queue<int> q;for(int i=1;i<=n;i++){if(indegree[i]==1){q.push(i);//由于是無向圖，所以我們默認(rèn)為1的為起點(diǎn)。vis[i]=true;}}while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<g[u].size();i++){if(indegree[g[u][i]]>1){indegree[g[u][i]]--;if(indegree[g[u][i]]==1){vis[g[u][i]]=true;q.push(g[u][i]);}}}}bool flag=false;for(int i=1;i<=n;i++){if(!vis[i]){//沒有入隊(duì)的說明if(!flag){//說明是第一次輸出。cout<<i;flag=true;}else{cout<<" "<<i;}}} } int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a>>b;indegree[a]++,indegree[b]++;g[a].push_back(b);g[b].push_back(a);}solve();return 0; }

• 并查集處理連通+dfs查找環(huán)

/***@filename:發(fā)現(xiàn)環(huán)*@author: pursuit*@csdn:unique_pursuit*@email: 2825841950@qq.com*@created: 2021-04-29 19:06 **/ #include <bits/stdc++.h>using namespace std;typedef long long ll; const int maxn = 100000 + 5; const int mod = 1e9+7;int n,a,b;//n臺電腦。 int father[maxn]; vector<int> ans;//存儲出現(xiàn)環(huán)路的電腦。 vector<int> g[maxn];//無向圖。 bool vis[maxn];//vis[i]表示i是否已經(jīng)進(jìn)入結(jié)果序列。 vector<int> result;//結(jié)果序列。 bool flag;//判斷是否找到回路。 int find(int x){int r=x;while(r!=father[r])r=father[r];int i=x,j;while(father[i]!=r){j=father[i];father[i]=r;i=j;}return r; } void dfs(int st,int ed){if(st==ed){//說明回路已經(jīng)搜索完成，此時直接退出。sort(result.begin(),result.end());for(int i=0;i<result.size();i++){printf("%d%c",result[i],i==result.size()-1?'\n':' ');}flag=true;return;}for(int i=0;i<g[st].size();i++){int u=g[st][i];if(!vis[u]&&!flag){result.push_back(u);vis[u]=true;dfs(u,ed);//回溯。result.pop_back();vis[u]=false;}}return; } int main(){scanf("%d",&n);int st,ed;for(int i=1;i<=n;i++)father[i]=i;for(int i=1;i<=n;i++){scanf("%d%d",&a,&b);g[a].push_back(b),g[b].push_back(a);int fa=find(a),fb=find(b);if(fa!=fb){father[fa]=fb;}else{//說明a和b已經(jīng)連接了，此時再次連接則會出現(xiàn)環(huán)路。所以我們可以記錄環(huán)路的起點(diǎn)和終點(diǎn)。st=a,ed=b;}}vis[st]=true;result.push_back(st);dfs(st,ed);return 0; }

第五題 對局匹配

• 問題描述

  小明喜歡在一個圍棋網(wǎng)站上找別人在線對弈。這個網(wǎng)站上所有注冊用戶都有一個積分，代表他的圍棋水平。
  小明發(fā)現(xiàn)網(wǎng)站的自動對局系統(tǒng)在匹配對手時，只會將積分差恰好是K的兩名用戶匹配在一起。
  如果兩人分差小于或大于$K$，系統(tǒng)都不會將他們匹配。
  現(xiàn)在小明知道這個網(wǎng)站總共有$N$名用戶，以及他們的積分分別是$A_1,A_2,...A_N$。
  小明想了解最多可能有多少名用戶同時在線尋找對手，但是系統(tǒng)卻一場對局都匹配不起來(任意兩名用戶積分差不等于K)？

  輸入

  第一行包含兩個個整數(shù)$N$和$K$。第二行包含$N$個整數(shù)$A_1,A_2,...A_N$。
  對于30%的數(shù)據(jù)，$1<=N<=10$
  對于100%的數(shù)據(jù)，$1<=N<=100000,0<=Ai<=100000,0<=K<=100000$

  輸出

  一個整數(shù)，代表答案。

  樣例輸入

  10 0 1 4 2 8 5 7 1 4 2 8

  樣例輸出

  6

• 解題思路

  • 動態(tài)規(guī)劃

    題目所求的即是讓我們盡可能找到多的人使他們?nèi)我庵g積分之差不等于$k$，我們用$cnt$數(shù)組來記錄積分的出現(xiàn)次數(shù)，那么我們就可以通過這個$k$來分組，然后枚舉$i+kj(i\in [0,k?1],j?k<=maxx)$，這樣，我們就存在著選與不選了，跟背包問題來分析即可。若選擇此時的$i+kj$，那么就不能繼承上一次的$i+k?(j?1)$了，而是需要加上$i+k?(j?2)$，而若不選擇，則就是繼承上一次的$i+(j?1)k$。最后，累加所有的最終狀態(tài)值即可得到答案。

  • 貪心+尺取法

    我們知道如果兩個人之間積分值相差為k，那么我們隨便取一個出來就可以湊出一個答案了。按照這思想尺取法遍歷所有積分，最后累加即可。

• 代碼

  • 動態(tài)規(guī)劃

/***@filename:對局匹配*@author: pursuit*@csdn:unique_pursuit*@email: 2825841950@qq.com*@created: 2021-04-29 20:19 **/ #include <bits/stdc++.h>using namespace std;typedef long long ll; const int maxn = 100000 + 5; const int mod = 1e9+7;int n,k,temp,maxx;//題目所問，即為任意兩名用戶的積分之差不等于K。 int cnt[maxn];//cnt[i]表示積分為i的出現(xiàn)次數(shù)。 int dp[maxn];//dp數(shù)組。有點(diǎn)像背包問題，我們讓相差為k分的人為為一組。 void solve(){int ans=0;if(!k){//說明k為0，此時我們只需要統(tǒng)計(jì)積分不相同的即可。for(int i=0;i<=maxx;i++){if(cnt[i])ans++;}}else{//dp，我們通過k將其分成0~k-1組。for(int i=0;i<k;i++){int j;for(j=i;j<=maxx;j+=k){//對j進(jìn)行情況分析。if(j-2*k>=0){//說明可以選擇j也可以不選擇。如果不選擇，那么就是繼承上一次的dp[j-k];dp[j]=max(dp[j-k],dp[j-2*k]+cnt[j]);//如果選擇，就是加上上一次的dp[j-2*k]。}else if(j-k>=0){//說明此時仍是選還是不選。dp[j]=max(dp[j-k],cnt[j]);}else{dp[j]=max(dp[j],cnt[j]);}}//由于退出的時候j已經(jīng)大于maxx了，所以我們需要減去k。ans+=dp[j-k];}}printf("%d\n",ans); } int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&temp);cnt[temp]++;maxx=max(maxx,temp);//保存當(dāng)前最大值。}solve();return 0; }

• 貪心+尺取法

/***@filename:對局匹配-貪心*@author: pursuit*@csdn:unique_pursuit*@email: 2825841950@qq.com*@created: 2021-04-29 20:52 **/ #include <bits/stdc++.h>using namespace std;typedef long long ll; const int maxn = 100000 + 5; const int mod = 1e9+7;//貪心+尺取法，我們知道如果兩個人之間積分值相差為k，那么我們隨便取一個出來就可以湊出一個答案了。 int n,k,a[maxn]; bool vis[maxn];//vis[i]判斷i是否已經(jīng)被確定了，即存在和別人積分值相差k。 void solve(){sort(a+1,a+n+1);int ans=0;int l=1,r=1;while(r<=n){if(l==r){r++;continue;}if(a[l]==a[r]-k&&!vis[l]&&!vis[r]){//說明沒有被確認(rèn)，我們?nèi)∫粋€湊答案。ans++;vis[l]=vis[r]=true;l++,r++;}else if(a[l]<a[r]-k&&!vis[l]&&!vis[r]){//說明湊不出，我們需要偏移，讓l靠近r。l++;}else if(a[l]>a[r]-k&&!vis[l]&&!vis[r]){//說明湊不出，且a[l]>a[r]，我們需要偏移，讓r大于它。r++;}else{//說明存在l和r有一個是被確認(rèn)的，我們需要移動被確認(rèn)的。if(vis[l])l++;else if(vis[r])r++;else if(vis[l]&&vis[r]){l++,r++;}}}for(int i=1;i<=n;i++){if(!vis[i]){//說明無法湊出，我們累加。ans++;}}printf("%d\n",ans); } int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}solve();return 0; }

第六題 觀光鐵路

• 問題描述

  跳蚤國正在大力發(fā)展旅游業(yè)，每個城市都被打造成了旅游景點(diǎn)。
  許多跳蚤想去其他城市旅游，但是由于跳得比較慢，它們的愿望難以實(shí)現(xiàn)。
  這時，小C聽說有一種叫做火車的交通工具，在鐵路上跑得很快，便抓住了商機(jī)，創(chuàng)立了一家鐵路公司，向跳蚤國王請示在每兩個城市之間都修建鐵路。
  然而，由于小C不會扳道岔，火車到一個城市以后只能保證不原路返回，而會隨機(jī)等概率地駛向與這個城市有鐵路連接的另外一個城市。
  跳蚤國王向廣大居民征求意見，結(jié)果跳蚤們不太滿意，因?yàn)檫@樣修建鐵路以后有可能只游覽了3個城市(含出發(fā)的城市)以后就回來了，它們希望多游覽幾個城市。
  于是跳蚤國王要求小C提供一個方案，使得每只跳蚤坐上火車后能多游覽幾個城市才回來。
  小C提供了一種方案給跳蚤國王。跳蚤國王想知道這個方案中每個城市的居民旅游的期望時間(設(shè)火車經(jīng)過每段鐵路的時間都為1)，請你來幫跳蚤國王。

  輸入

  輸入的第一行包含兩個正整數(shù)n、m，其中n表示城市的數(shù)量，m表示方案中的鐵路條數(shù)。
  接下來m行，每行包含兩個正整數(shù)u、v，表示方案中城市u和城市v之間有一條鐵路。
  保證方案中無重邊無自環(huán)，每兩個城市之間都能經(jīng)過鐵路直接或間接到達(dá)，且火車由任意一條鐵路到任意一個城市以后一定有路可走。
  4 <= k <= n <= 21，1 <= u, v <= n

  輸出

  輸出n行，第i行包含一個實(shí)數(shù)ti，表示方案中城市i的居民旅游的期望時間。
  你應(yīng)當(dāng)輸出足夠多的小數(shù)位數(shù)，以保證輸出的值和真實(shí)值之間的絕對或相對誤差不超過1e-9。

  樣例輸入

  4 5 1 2 2 3 3 4 4 1 1 3

  樣例輸出

  3.333333333333 5.000000000000 3.333333333333 5.000000000000

• 解題思路

  待補(bǔ)。貼出AC代碼供各位參考。

• 代碼

#include<iostream> using namespace std; const int MAX = 100; int num[MAX]; int n, m; int main() {cin >> n >> m;for (int i = 1; i <= m; i++){int u, v;cin >> u >> v;num[u]++;num[v]++;}for (int i = 1; i <= n; i++) {double p = m * 2.0 / num[i];printf("%.12f\n", p);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的第八届蓝桥杯（软件类）决赛C/C++B组真题题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。