真題卷001——算法備賽

藍橋杯2024年C/C++B組國賽卷

1.合法密碼

問題描述

小藍正在開發自己的OJ網站。他要求用戶的密碼必須符合一下條件：

長度大于等于8小于等于16
必須包含至少一個數字字符和至少一個符號字符

請計算一下字符串，有多少個子串可以當作合法密碼。字符串為：

kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th

原題鏈接

思路分析

這題打卡題還是簡單的，直接按題意暴力枚舉判斷即可。題目要求子串需要包含一個符號字符，而原字符中符號只有'#'，只需判斷枚舉的子串是否包含'#'即可。

代碼

#include <bits/stdc++.h>
using namespace std;
bool check(string k){bool isNum=false,isSymbol=false;for(int i=0;i<k.size();i++){if(k[i]=='#') isSymbol=true;else if(k[i]>='0'&&k[i]<='9') isNum=true;}return isNum&&isSymbol;
}
int main()
{string s;     s="kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th";int n=s.size();int ans=0;for(int i=0;i<=n-8;i++){for(int j=8;j<=16;j++){if(n-i>=j){string sub=s.substr(i,j);if(check(sub)) ans++;}else break;}}cout<<ans;return 0;
}

2.選數概率

問題描述

一個數組中有a個1，b個2，和c個3.
$設p_{i,j}表示從數組中隨機取兩個數，其中一個數為i，另一個數為j的概率。比如p_{1,2}=\frac{ab}{C_{(a+b+c)}^2}。$

$當a,b,c等于多少時，滿足p_{1,2}=\frac{517}{2091},p_{2,3}=\frac{2632}{10455},p_{1,3}=\frac{308}{2091}，且a+b+c最小。題目保證最小的解是唯一的。$

你需要提交一個a,b,c格式的字符串，例如a=12,b=34,c=54，那么你需要提交的字符串為12,34,56。

原題鏈接

思路分析
$題目意思就是\frac{ab}{n}=\frac{517}{2091},\frac{bc}{n}=\frac{2632}{10455},\frac{ac}{n}=\frac{308}{2091}，求a，b，c的分別為多少時，a+b+c最小。$
首先通分，將三個分數的分母都化為一個值，設三個分子分別為s1,s2,s3.
$可以得到\frac{ab}{bc}=\frac{a}{c}=\frac{s1}{s2}，\frac{ac}{bc}=\frac{a}{b}=\frac{s3}{s2}$
進而可得a:b:c=s3:s2:(s2s3)/s1化簡得:a:b:c=s1s3:s1s2:s2s3，求出滿足這個比值的最小的三個整數即可。設s1s3，s1s2，s2s3的公因數為d，對應的a，b，c就是s1*s3/d，s1*s2/d，s2*s3/d，要使a，b，c盡量小，d就要盡量大，求出最大公因數即可。

代碼

#include <bits/stdc++.h>
using namespace std;
int main()
{int s1=517*5;int s2=2632;int s3=308*5;int d=gcd(s1*s3,gcd(s2*s3,s1*s2));cout<<s1*s3/d<<','<<s1*s2/d<<','<<s2*s3/d;return 0;
}

3.螞蟻開會

問題描述

二維平面上有n只螞蟻，每只螞蟻有一條線段作為活動范圍，第i只螞蟻的活動范圍的線段的兩個端點為(x1,y1),(x2,y2)。現在考慮在這些線段的交點處設置會議中心，它們決定在所有交點為整點（x偏移量和y偏移量都是整數）的地方設置會議中心，問需要設置多少個會議中心？

數據規模

n<=500
0<=x1,x2,y1,y2<=10000
任意螞蟻的活動范圍不會退化為一個點，不保證任意兩條線段之間的交點數量有限

原題鏈接

思路分析

本題如果考慮直接求交點的方法，計算會非常繁瑣，而且注意數據規模提示最后一個信息，說明兩條線段可能重合，那么求交點就更難了。

重新仔細思考一下，其實可以考慮枚舉整點的方式來統計是交點的整點數量。具體思路如下：

根據每條直線，通過gcd將所有在該線段上的整點都添加進map
統計map集合，所有出現兩次以上的整點數量就是答案

根據數據規模信息，map可以存儲點的進制哈希值。

時間復雜度O(nk)k為線段上整點的平均數，最壞的情況數量級在5*10^6左右。

代碼

#include<bits/stdc++.h>
using namespace std;
int N = 10001;
int main() {ios::sync_with_stdio(0);cin.tie(0);int n; cin >> n;unordered_map<int, int>mp;for (int i = 0; i < n; i++) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;int xMin = min(x1, x2), xMax = max(x1, x2);int yMin = min(y1, y2), yMax = max(y1, y2);int d = gcd(xMax - xMin, yMax - yMin);int dx = (x2 - x1) / d, dy = (y2 - y1) / d;int x = x1, y = y1;for (int i = 0; i <= d; i++) {mp[x * N + y]++;x += dx;y += dy;}}int ans = 0;for (auto& [k, v] : mp) {if (v >= 2) ans++;}cout << ans;
}

4.立定跳遠

問題描述

在運動會上，小明從數軸的原點開始向正方向立定跳遠。項目設置了 n個檢查點a1,a2,…, an 且 ai > ai-1 > 0。小明必須先后跳躍到每個檢查點上且只能跳躍到檢查點上。同時，小明可以自行再增加 m 個檢查點讓自己跳得更輕松。小明單次跳躍的最遠距離達到L，并且學會一個爆發技能可以在運動會時使用一次，使用時可以在該次跳躍時的最遠距離變為 2L。小明想知道，L的最小值是多少可以完成這個項目?

原題鏈接

思路分析

首先看到題目，是求最優值的問題，這類題常用的解法有1.動態規劃，2.貪心，3.暴力模擬，4.二分答案+貪心判斷。

在由構造過程推出答案不好做的時候，從答案倒推過程是個不錯的選擇，本題就是如此。由題給信息可知，增設的檢查點越多，L就可以越小，反之，L越小，需要增設的檢查點就要更多。問題具有單調性，可以二分猜答案x，再根據x貪心地判斷該x需要的最少檢查點是否大于m。最后那個最小的x就是正確答案。

現在考慮子問題，已知x，求最小的增設檢查點數量。

枚舉每個間距di（已知的相鄰檢查點間距離），如果di大于x，那肯定需要增設檢查點，增設的數量最少的方案就是每隔x放一個，為：(di-1)/x，單次跳躍最遠距離可以變為一次2*x，也就是可以少放置一個檢查點。最小增設檢查點數量就是cnt-1(cnt為實際放置的最少數量)，這個值為負數也沒關系，最后只是拿來與m做比較。

代碼

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int>d;
bool check(int x){int cnt=0;for(int di:d){if(di>x){cnt+=(di-1)/x;}}if(cnt-1<=m) return true;return false;
}
int solve(){cin>>n>>m;d.resize(n);int l=1,r=0;int pre=0,next;for(int i=0;i<n;i++){cin>>next;d[i]=next-pre;pre=next;r=max(d[i],r);}while(l<r){int mid=(l+r)/2;if(check(mid)) r=mid;else l=mid+1;}return r;
}
int main()
{cout<<solve();return 0;
}

5.最小字符串

問題描述

給定一個長度為 N 且只包含小寫字母的字符串 S，和 M個小寫字母 c1,c2,…,c。

現在你要把 M 個小寫字母全部插入到字符串 S 中，每個小寫字母都可以插入到任意位置。請問能得到的字典序最小的字符串是什么?

原題鏈接

思路分析

字符串的字典序大小取決于靠前的字符的大小，越靠前的字符越小，字符串的字典序就越小。

先將M個字符統計到一個頻數字典中，再貪心地枚舉s中的每個字符ch，若能使當前的ch變得更小，那整個字符串的字典序就能更小。

依次將ch與頻數字典中最小的字符t比較,只要t更小，就將s(s是t的頻數)個t都插入到ch的位置。

注意：在插入s后，s的長度會改變，枚舉指針i要調整。

代碼

#include<bits/stdc++.h>
using namespace std;
int main()
{int n, m; cin >> n >> m;string s; cin >> s;vector<int>d(26);for (int i = 0; i < m; i++) {char ch; cin >> ch;d[ch - 'a']++;}int cnt = -1;while (cnt < 26) if (d[++cnt] != 0) break;for (int i = 0; i < s.size(); i++) {if (s[i] > 'a' + cnt) {s.insert(i, d[cnt], 'a' + cnt);i += d[cnt] - 1;while (cnt < 26) if (d[++cnt] != 0) break;if (cnt == 26) break;}}while (cnt < 26) {  //處理數據殘留if (d[cnt] != 0) {s.insert(s.size(), d[cnt], 'a' + cnt);}cnt++;}cout << s;return 0;
}

6.數位翻轉

藍橋杯2024年國賽題

問題描述

小明創造了一個函數f(x)用來翻轉x的二進制的數位（無前導0）。比如f(11)=13，小明隨機出了一個長度為n的整數數組{a1,a2,,...an}，他想知道在這個數組中最多選m個不相交的區間，將這些區間內的二進制數位翻轉（將ai變為f(ai)）后，整個數組的最大和是多少？

原題鏈接

思路分析

首先將數組中的所有數都預處理，計算出一個d數組，d[i]存儲的是f[ai]-ai。

原問題轉化一個子問題：從d[i]中選最多m個不相交的區間，這些區間內所有數的和最大為多少？該問題的值再加上sum(sum為a數組的總和)就是原問題答案。

現在來思考這個子問題：如果貪心或者模擬來求具體是哪幾個區間是不容易的，因為區間不能重疊，要考慮的細節很多。可以使用動態規劃來解決。

定義dp[i][j]表示前 i 個數取最多 j 個不相交的區間的最大總和。枚舉到i時，計算dp[i][j],有兩種選擇：

不選最后一個下標i的后綴區間，dp[i][j]=dp[i-1][j]
選最后一個下標i的后綴區間，dp[i][j]=max(dp[k-1][j-1]+suffix(k,i) ，suffix(k,i)表示d的子數組[k,i]的區間和。

狀態轉移方程為：dp[i][j]=max(dp[i-1][j],max(dp[k-1][j-1]+suffix(k,i)))。

時間復雜度O(mn^2)。

代碼

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll getDiff(int x) {int p = x;int tr = 0;while (x) {tr <<= 1;if (x & 1) tr |= 1;x >>= 1;}return tr - p;
}int main()
{int n, m;cin >> n >> m;vector<ll>d(n + 1);vector<vector<ll>>dp(n + 1, vector<ll>(m+1));  //dp[i][j]表示前i個數取最多j個不相交的區間的最大總和ll sum = 0;for (int i = 1; i <= n; i++) {int t; cin >> t;sum += t;d[i] = getDiff(t);}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) dp[i][j] = dp[i - 1][j];  //不選從i開始的后綴子數組for (int j = 1; j <= m; j++) {ll suffix = 0;for (int k = i; k >= 1; k--) {suffix += d[k];dp[i][j] = max(dp[i][j], dp[k - 1][j - 1] + suffix);  //選從i開始的后綴子數組}}}cout << sum + dp[n][m];return 0;
}

7.數星星

問題描述

小明正在一棵樹上數星星，這棵樹有n個節點1,2,3...,n。他定義樹上的一個子圖G是一顆星星需要滿足以下所有條件：

G是一課樹。
G中存在某個節點，其度數為|VG|-1。其中|VG|表示這個子圖含有的節點數。

當且僅當兩顆星星包含的節點集合不完全相同，兩顆星星不相同。小明想知道這棵樹上有多少顆不同的星星包含的節點數在[L,R]范圍內。答案對1e9+7取余

原題鏈接

思路分析

本題看似是一道圖論題，實際只是借用了圖的概念的排列組合的數學題。

直觀圖

在這里插入圖片描述

由題意可知，子圖G是一棵星星，其實就是說G是一棵所有葉子都是根節點的孩子的樹，如上圖，子圖[1,2,3,4]，子圖[1,3,5]都是星星。

首先統計每個節點的鄰接節點數量（具體是哪些節點不用關系），edges[i]存儲了節點i的鄰接點的數量（也就是以i為根節點，它的孩子節點的數量）。依次枚舉節點，統計以它為根節點的星星中（子節點數量為n），子節點數在[L-1,R-1]范圍內的星星數量。這就是一個組合的問題，答案為:
$C_n^{L-1}+...+C_n^{min(n,R-1)}$

$單個計算C_n^x=\frac{n!}{x!*(n-x)!}$

因為需要多次計算組合數，暴力計算是要超時的，可以預處理計算出所有的x！的結果，C(n,x)就能在O(1)的時間復雜度內計算出結果。

在計算過程中需要不斷對mod取余，而除法是不能直接除，這里可以用逆元處理。

前置知識：

逆元：給定整數a，m，滿足gcd(a,m)=1(a與m互質)，ax%m=1的一個解為a模m的逆元，記為a^-1。

注：求解x/y%m的值可以轉化為x*y^-1%m的值，（y^-1為y模m的逆元）。

費馬小定理：當m是質數時，對于任意的a（a不能被m整除），其逆元為a^m-2%m。

注：求解a^m-2可以通過快快速冪求解。

更多詳情請讀者查閱資料。

根據前置知識可以得出求解C(n,x)的計算公式：
${C_n^x} \% mod=\frac{n!}{x!*(n-x)!}\%mod=fac[n]*inv[n-k]*inv[k]\%mod$
其中fac[x]表示x！，inv[x]表示x！模mod的逆元。

自此其實還沒完（只能通過16個測試用例），仔細想想，當L<=2<=R時，統計節點數為2的星星數量時是有重復統計的，直觀圖中子圖[1,2]，和子圖[2,1]是同一個子圖。解決方法就是節點為1（星星數為原圖中節點的數量）和2（星星數為原圖邊的數量）的星星數提前計算出來，枚舉時只統計節點數大于等于max(3,L)的星星,具體實現見代碼。

代碼

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
vector<int>fac;  //預處理階乘
vector<int>inv;  //預處理階乘的逆元
int pow(int x, int n) {  //快速冪求解(x^n)%mint s = 1;while (n) {if (n & 1) {s = (ll)x * s % mod;}x = (ll)x * x % mod;n >>= 1;}return s;
}
void init(int n) {  //初始化fac.resize(n + 1);inv.resize(n + 1);fac[0] = inv[0] = 1;//階乘的初始化for (int i = 1; i <= n; i++) {fac[i] = (ll)fac[i - 1] * i % mod;inv[i] = pow(fac[i], mod - 2);  //費馬小定理求解階乘的逆元}
}
int cal(int n, int x) {  //求解C(n,x)的值return (ll)((ll)fac[n] * inv[x] % mod) * inv[n - x] % mod;
}
int main()
{int n; cin >> n;init(n);vector<int>edges(n+1);for (int i = 1; i < n; i++) {int u, v; cin >> u >> v;edges[u]++;edges[v]++;}int L, R; cin >> L >> R;int ans = 0;int sum1=n,sum2=n-1;  //節點為1的星星數量為n，節點為2的星星數量為n-1for (int i = 1; i <= n; i++) {int s = edges[i];if (s < max(L-1,2)) continue;  //子節點數量不合格直接退出for (int j = max(L-1,2); j < R; j++) {  //從至少j=2開始遍歷，j小于2的星星統計會有重復計算，先預處理好ans = (ans + cal(s, j)) % mod;if (j >= s) break;}}if(L==1) ans=(ans+sum1)%mod;if(L<=2&&2<=R) ans=(ans+sum2)%mod;cout << ans;return 0;
}

8.套手鐲

問題描述

小藍在 LQ 集市上發現一個套手鐲的游戲，在一個大小為10⁸ * 10⁸矩形平面上擺放著 N 個圓形的手鐲。

玩家可以將一個大小為 w*h 的矩形方框放置在這個平面上(玩家只可以沿著水平/垂直方向放置方框，即可以將方框旋轉 90度，但不可以旋轉至其他角度)，位于這個矩形方框內部的手鐲就是玩家獲得的獎勵。可以將這個矩形平面看作是一個二維坐標系，左下角的坐標為(0,0)。手鐲和方框的厚度可以忽略不計，允許多個手鐲重疊放置。小藍想要嘗試一次，請問他最多可以獲得多少手鐲?

示例：
在這里插入圖片描述

數據規模

1<=N<=10⁵，1<=w,h,x,y,r<=10⁸，1<=min(w,h)<=200.

原題鏈接

思路分析

一個圓形如何判斷它是否在矩形中內，只要它最高點，最低點，最左點，最右點在矩形內即可，所以對于一個圓形，我們主要關注的就是它的四個邊界點（題目要是改成其他形狀也是如此）。

先將圓的四個邊界點作為一個整體（可以自定義數據結構，也可以使用pair,為方便后面排序，可直接使用pair）裝入一個數據容器，將矩形方框作為滑窗讓其裝入盡量多的圓。滑動的過程可以枚舉底線，讓矩形在底線上水平左右滑動。具體滑動時要將盡可能多的圓包含在矩形中，為方便計算，將圓按照右邊界點大小排序，固定底線，每次將當前枚舉到的圓的右邊界作為矩形的右邊界，來統計裝入的圓的數量最多為多少。

圖示過程：
在這里插入圖片描述

在單次水平滑動過程中需要用一個容器來維護矩形范圍內的圓的左邊界，常用的是隊列，因為左邊界不保證有序，可以用優先隊列來存儲，頭節點維護的是最小的左邊界，圓的左邊界超出矩形的左邊界都需要剔除（詳見代碼）。

因為矩形可以旋轉90度，交換矩形的長寬然后再重復滑動過程就行。

代碼

#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
int n,w,h;
vector<pair<pii,pii>>c;
int getCnt(int bottom){   priority_queue<int,vector<int>,greater<int>>pq;  //維護矩形內的圓，頭節點記錄左邊界最小的圓的左邊界值int cnt=0;for(int i=0;i<n;i++){auto cur=c[i];if(cur.s.s<bottom||cur.s.f>bottom+h) continue;  //y坐標不合格pq.push(cur.f.s);  //左邊界x坐標入隊while(!pq.empty()&&pq.top()<cur.f.f-w) pq.pop();  //左邊界不在矩形范圍內的圓刪除隊列cnt=max(cnt,(int)pq.size());}return cnt;
}
int main()
{ios::sync_with_stdio(0); cin.tie(0);cin>>n>>w>>h;c.resize(n);for(int i=0;i<n;i++){int x,y,r; cin>>x>>y>>r;c[i].f.f=x+r;c[i].f.s=x-r;c[i].s.f=y+r;c[i].s.s=y-r;}sort(c.begin(),c.end());int ans=0;for(int i=0;i<n;i++){ans=max(ans,getCnt(c[i].s.s));}swap(w,h);  //將方框旋轉90度for(int i=0;i<n;i++){ans=max(ans,getCnt(c[i].s.s));}cout<<ans;return 0;
}

9.跳石頭

問題描述

小明正在和朋友們玩跳石頭的小游戲，一共有塊石頭按 1到 n 順序排成一排，第讠塊石頭上寫有正整數權值 C。如果某一時刻小明在第 j塊石頭，那么他可以選擇跳向第j + c 塊石頭(前提j+ ci<n )或者跳向第 2j塊石頭(前提 2j<n)，沒有可跳躍的目標時游戲結束。

假如小明選擇從第 x 塊石頭開始跳躍，如果某塊石頭有可能被小明經過("經過"指存在某一時刻小明在這個石頭處)，則將這塊石頭的權值納入得分集合 S，那么小明從第 x 塊石頭開始跳躍的得分為|S|(|S|表示S中不同元素的數量)。

比如如果小明從第 x 塊石頭出發，所有可能經過的石頭上的權值分別為 5,3,5,2,3，那么 S=[ 5,3,2 ] 得分為|S|=3。小明可以任選一塊石頭開始跳躍，請求出小明最多能獲得的分數。

原題鏈接

思路分析

這是一個常見的跨步問題，可以用動態規劃求解，記錄原數組到nums，從下標 i 出發，可能到達i+nums[i]和i*2的位置，可以定義dp[i]記錄從i出發可能到達的節點權值集合，要求解dp[i]就得先知道dp[i+nums[i]]或dp[i*2],可以采用記憶化搜索的方式求解，也可以從后往前遍歷，先求解出后面的dp值。

代碼

#include<bits/stdc++.h>
using namespace std;
int main()
{int n; cin>>n;vector<int>nums(n+1);vector<unordered_set<int>>dp(n+1);for(int i=1;i<=n;i++) cin>>nums[i];int ans=0;for(int i=n;i>=1;i--){int to1=i+nums[i];int to2=i*2;if(to1<=n){dp[i].insert(dp[to1].begin(),dp[to1].end());}if(to2<=n){dp[i].insert(dp[to2].begin(),dp[to2].end());}dp[i].insert(nums[i]);ans=max((int)dp[i].size(),ans);}cout<<ans;return 0;
}

10.最長回文前后綴

問題描述

小明特別喜歡回文串，然而回文串太少見了，因此他定義：字符串的相同長度的，不相交的前綴和后綴是"回文前后綴"，當且僅當這個前綴和后綴拼起來是個回文串。對于一個給定的字符串 S，小明希望對其進行改造使得L(S)(S的最長前后綴長度)盡可能大。改造允許將字符串中一個任意長度的子串刪除。比如刪除S=abcdebijbba 中的子串 S[3,5]后S變成了 abbijbba 。

小明想知道改造后的新字符串 S’的最長回文前后綴”的長度L(S')最大是多少?

原題鏈接

思路分析

在判斷一個字符串是否是回文串時，常用雙指針往中心靠攏的方式來枚舉判斷，在本題中，我么也可以先這樣統計出最小的回文前后綴的長度ans，第一個不相同的位置為l,r。
在這里插入圖片描述

此時，如果不進行刪除，那答案就是ans，如果進行刪除，那肯定是刪除以L為開頭的前綴子串或者刪除以R為結尾的后綴子串，只有這樣才能使ans更大。因為只能刪除一次，那直接暴力枚舉刪除具體那個子串就好，當然也不用真的刪除，只是模擬一下，計算出值就行。

因為需要兩次模擬操作，可以定義一個函數來實現代碼復用。

代碼

#include<bits/stdc++.h>
using namespace std;
int getMax(string str){int l=0,r=str.size()-1;int cnt=0;while(l<r){if(str[l]==str[r]){  //刪除[0,l-1]int lt=l,rt=r;while(lt<rt&&str[lt]==str[rt]) lt++,rt--;cnt=max(lt-l,cnt);}l++;}return cnt;
}
int main()
{ios::sync_with_stdio(0); cin.tie(0);string s; cin>>s;int n=s.size();int l=0,r=n-1;int ans=0;while(l<r&&s[l]==s[r]) l++,r--;ans=l;string t=s.substr(l,r-l+1);string rt=t; reverse(t.begin(),t.end());ans+=max(getMax(t),getMax(rt));cout<<ans;return 0;
}