說明
試題 F: 刪邊問題 沒實現(xiàn)
試題 I: 拼數(shù)字 不會做
試題 J: 逃跑 不會做
試題 A: 子 2023
本題總分：5 分
【問題描述】
小藍在黑板上連續(xù)寫下從 1 到 2023 之間所有的整數(shù)，得到了一個數(shù)字序列：
S = 12345678910111213 . . . 20222023。
小藍想知道 S 中有多少種子序列恰好等于 2023？
提示，以下是 3 種滿足條件的子序列（用中括號標識出的數(shù)字是子序列包含的數(shù)字）：
1[2]34567891[0]111[2]1[3]14151617181920212223…
1[2]34567891[0]111[2]131415161718192021222[3]…
1[2]34567891[0]111213141516171819[2]021222[3]…
注意以下是不滿足條件的子序列，雖然包含了 2、0、2、3 四個數(shù)字，但是順序不對：
1[2]345678910111[2]131415161718192[0]21222[3]…
【答案提交】
這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個整數(shù)，在提交答案時只填寫這個整數(shù)，填寫多余的內(nèi)容將無法得分
【解釋】
動態(tài)規(guī)劃
當遇到字符 ‘2’ 的時候字符串 “2” 的數(shù)量+1，字符串 “202” 的數(shù)量加上字符串 “20” 的數(shù)量
當遇到字符 ‘0’ 的時候字符串 “20” 的數(shù)量加上字符串 “2” 的數(shù)量
當遇到字符 ‘3’ 的時候字符串 “2023” 的數(shù)量加上字符串 “202” 的數(shù)量
最后 “2023” 的數(shù)量就是答案
【代碼】
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int dp[4]={0};//分別代表"2"、"20"、"202"、"2023"的數(shù)量
string s;
for(int i=1;i<=2023;i++){//構(gòu)造string
s+=to_string(i);
}
for(int i=0;i<s.size();i++){//構(gòu)造string
if(s[i]=='2'){
dp[0]++;
dp[2]+=dp[1];
}else if(s[i]=='0'){
dp[1]+=dp[0];
}else if(s[i]=='3'){
dp[3]+=dp[2];
}
}
cout<<dp[3]<<endl;
}
【答案】
5484660609
試題 B: 雙子數(shù)
本題總分：5 分
【問題描述】
??若一個正整數(shù) x 可以被表示為 p2 × q2，其中 p、q 為質(zhì)數(shù)且 p , q，則 x 是一個 “雙子數(shù)”。請計算區(qū)間 [2333, 23333333333333] 內(nèi)有多少個 “雙子數(shù)”？
【答案提交】
??這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個整數(shù)，在提交答案時只填寫這個整數(shù)，填寫多余的內(nèi)容將無法得分。
【解釋】
先用歐拉篩求出10的7次方內(nèi)的素數(shù)，求出之后暴力枚舉兩個數(shù)即可
【代碼】
#include<bits/stdc++.h>
#define int __int128 //用__int128穩(wěn)一點
using namespace std;
int f[10000010]={1,1};
vector<int> v;
signed main(){
for(int i=2;i<=10000010;i++){//歐拉篩求素數(shù)
if(f[i]==0){//如果沒被標記過，那么i是質(zhì)數(shù)
v.push_back(i);
}
for(int j=0;j<v.size()&&v[j]*i<=10000010;j++){
f[v[j]*i]=1;//標記以i為最大因數(shù)的數(shù)為不是素數(shù)（除了1和本身）
if(i%v[j]==0){//如果p[j]是i的因數(shù)，那么后面的數(shù)都不是以i為最大因數(shù)的
break;
}
}
}
long long ans=0;
for(int i=0;i<v.size();i++){
for(int j=i+1;j<v.size();j++){
if(v[i]*v[i]*v[j]*v[j]<2333)continue;//小于那就不要，繼續(xù)
if(v[i]*v[i]*v[j]*v[j]>23333333333333)break;//大于直接退出
ans++;
}
}
cout<<ans<<endl;
}
【答案】
947293
試題 C: 班級活動
時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：10 分
【問題描述】
??小明的老師準備組織一次班級活動。班上一共有 n 名（n 為偶數(shù)）同學(xué)，老師想把所有的同學(xué)進行分組，每兩名同學(xué)一組。為了公平，老師給每名同學(xué)隨機分配了一個 n 以內(nèi)的正整數(shù)作為 id，第 i 名同學(xué)的 id 為 ai。
??老師希望通過更改若干名同學(xué)的 id 使得對于任意一名同學(xué) i，有且僅有另一名同學(xué) j 的 id 與其相同（ai = aj）。請問老師最少需要更改多少名同學(xué)的 id？
【輸入格式】
輸入共 2 行。
第一行為一個正整數(shù) n。
第二行為 n 個由空格隔開的整數(shù) a1, a2, …, an。
【輸出格式】
輸出共 1 行，一個整數(shù)。
【樣例輸入】
4
1 2 2 3
【樣例輸出】
1
【樣例說明】
僅需要把 a1 改為 3 或者把 a3 改為 1 即可。
【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，保證 n ≤ 103。
對于 100% 的數(shù)據(jù)，保證 n ≤ 105。
【解釋】
把題目捋清楚就很容易實現(xiàn)了
1、先用map存下每個數(shù)字的數(shù)量
2、數(shù)量大于等于2的那么就減去二，剩下的一定要轉(zhuǎn)換，存到sum1中，小于二的另外統(tǒng)計到sum2中
3、sum1>=sum2，那么答案是sum1，sum1<sum2，那么答案是sum1+(sum2-sum1)/2;
【代碼】
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n;
map<int,int> ma;
cin>>n;
for(int i=0;i<n;i++){
int a;
cin>>a;
ma[a]++;
}
int sum1=0,sum2=0;
for(auto it:ma){
if(it.second>=2){
sum1+=it.second-2;
}else{
sum2+=it.second;
}
}
if(sum1>=sum2){
cout<<sum1<<endl;
}else{
cout<<sum1+(sum2-sum1)/2<<endl;
}
}
試題 D: 合并數(shù)列
時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：10 分
【問題描述】
??小明發(fā)現(xiàn)有很多方案可以把一個很大的正整數(shù)拆成若干正整數(shù)的和。他采取了其中兩種方案，分別將他們列為兩個數(shù)組 {a1, a2, …, an} 和 {b1, b2, …, bm}。兩個數(shù)組的和相同。
??定義一次合并操作可以將某數(shù)組內(nèi)相鄰的兩個數(shù)合并為一個新數(shù)，新數(shù)的值是原來兩個數(shù)的和。小明想通過若干次合并操作將兩個數(shù)組變成一模一樣，即 n = m 且對于任意下標 i 滿足 ai = bi。請計算至少需要多少次合并操作可以完成小明的目標。
【輸入格式】
輸入共 3 行。
第一行為兩個正整數(shù) n, m。
第二行為 n 個由空格隔開的整數(shù) a1, a2, …, an。
第三行為 m 個由空格隔開的整數(shù) b1, b2, …, bm。
【輸出格式】
輸出共 1 行，一個整數(shù)。
【樣例輸入】
4 3
1 2 3 4
1 5 4
【樣例輸出】
1
【樣例說明】
只需要將 a2 和 a3 合并，數(shù)組 a 變?yōu)?{1, 5, 4}，即和 b 相同。
【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，保證 n, m ≤ 103。
對于 100% 的數(shù)據(jù)，保證 n, m ≤ 105，0 < ai, bi ≤ 105。
【解釋】
其實就是一個貪心題
1、對比兩個數(shù)組最左邊的數(shù)字，哪邊小就合并哪一邊
2、如果兩個數(shù)組最左邊的數(shù)字相等就出隊
【代碼】
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n,m;
deque<int> q1,q2;
cin>>n>>m;
for(int i=0;i<n;i++){
int a;
cin>>a;
q1.push_back(a);
}
for(int i=0;i<m;i++){
int a;
cin>>a;
q2.push_back(a);
}
int ans=0;//記錄答案
while(!q1.empty()){
if(q1.front()==q2.front()){//相等直接出隊
q1.pop_front();
q2.pop_front();
}else if(q1.front()>q2.front()){//q2小就合并q2前面兩個
q2[1]+=q2[0];
q2.pop_front();
ans++;//合并次數(shù)+1
}else{//q1小就合并q1前面兩個
q1[1]+=q1[0];
q1.pop_front();
ans++;//合并次數(shù)+1
}
}
cout<<ans<<endl;
}
試題 E: 數(shù)三角
時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：15 分
【問題描述】
小明在二維坐標系中放置了 n 個點，他想在其中選出一個包含三個點的子集，這三個點能組成三角形。然而這樣的方案太多了，他決定只選擇那些可以組成等腰三角形的方案。請幫他計算出一共有多少種選法可以組成等腰三角形？
【輸入格式】
輸入共 n + 1 行。
第一行為一個正整數(shù) n。
后面 n 行，每行兩個整數(shù) xi, yi 表示第 i 個點的坐標。
【輸出格式】
輸出共 1 行，一個整數(shù)。
【樣例輸入】
5
1 4
1 0
2 1
1 2
0 1
【樣例輸出】
4
【樣例說明】
一共有 4 種選法：{2, 3, 4}、{3, 4, 5}、{4, 5, 2}、{5, 2, 3}。
【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，保證 n ≤ 200。
對于 100% 的數(shù)據(jù)，保證 n ≤ 2000，0 ≤ xi, yi ≤ 109。
【解釋】
樣例應(yīng)該輸出5，比賽時勘誤了，{1, 3, 5}也是可以的
1、枚舉每個點，計算其它點與該點的距離，距離相同的兩條邊可以構(gòu)成等腰三角型
2、注意要考慮共線問題
3、其實這個方法不是很行，等邊三角形會被重復(fù)計算，正解是什么不是很清楚
【代碼】
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n;
cin>>n;
vector<vector<int>> v;
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
v.push_back({a,b});
}
int ans=0;//統(tǒng)計答案
for(int i=0;i<n;i++){
map<int,int> ma1;
map<pair<int,double>,int> ma2;
for(int j=0;j<n;j++){
int d=(v[i][0]-v[j][0])*(v[i][0]-v[j][0])+(v[i][1]-v[j][1])*(v[i][1]-v[j][1]);//距離的平方，就不開方了
double k=-1;
if(v[i][1]-v[j][1]!=0){
k=(double)(v[i][0]-v[j][0])/(v[i][1]-v[j][1]);//斜率
}
ans+=ma1[d];
ans-=ma2[{d,k}];//減去共線的數(shù)量
ma1[d]++;
ma2[{d,k}]++;
}
}
cout<<ans<<endl;
}
試題 F: 刪邊問題
時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：15 分
【問題描述】
給定一個包含 N 個結(jié)點 M 條邊的無向圖 G，結(jié)點編號 1 . . . N。其中每個
結(jié)點都有一個點權(quán) Wi。
你可以從 M 條邊中任選恰好一條邊刪除，如果剩下的圖恰好包含 2 個連通
分量，就稱這是一種合法的刪除方案。
對于一種合法的刪除方案，我們假設(shè) 2 個連通分量包含的點的權(quán)值之和分
別為 X 和 Y，請你找出一種使得 X 與 Y 的差值最小的方案。輸出 X 與 Y 的差
值。
【輸入格式】
第一行包含兩個整數(shù) N 和 M。
第二行包含 N 個整數(shù)，W1, W2, . . . WN。
以下 M 行每行包含 2 個整數(shù) U 和 V，代表結(jié)點 U 和 V 之間有一條邊。
【輸出格式】
一個整數(shù)代表最小的差值。如果不存在合法的刪除方案，輸出 ?1。
【樣例輸入】
4 4
10 20 30 40
1 2
2 1
2 3
4 3
【樣例輸出】
20
【樣例說明】
由于 1 和 2 之間實際有 2 條邊，所以合法的刪除方案有 2 種，分別是刪除(2, 3) 之間的邊和刪除 (3, 4) 之間的邊。
刪除 (2, 3) 之間的邊，剩下的圖包含 2 個連通分量：{1, 2} 和 {3, 4}，點權(quán)和分別是 30、70，差為 40。
刪除 (3, 4) 之間的邊，剩下的圖包含 2 個連通分量：{1, 2, 3} 和 {4}，點權(quán)和分別是 60、40，差為 20。
【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，1 ≤ N, M ≤ 10000。
對于另外 20% 的數(shù)據(jù)，每個結(jié)點的度數(shù)不超過 2。
對于 100% 的數(shù)據(jù)，1 ≤ N, M ≤ 200000，0 ≤ Wi ≤ 109，1 ≤ U, V ≤ N。
【解釋】
會縮點的話這題就不成問題了！但是我不會
提供點思路
1、用Tarjan算法將環(huán)縮成一個點，縮點后將會的到一棵樹
2、統(tǒng)計樹每個節(jié)點的字節(jié)點和(dfs一遍就可以實現(xiàn))
3、枚舉每個點，答案就是每個點的abs(總分數(shù)-節(jié)點分數(shù)-節(jié)點分數(shù))，取最小值
【代碼】
代碼就不寫了，不是很熟
試題 G: AB 路線
時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：20 分
【問題描述】
??有一個由 N × M 個方格組成的迷宮，每個方格寫有一個字母 A 或者 B。小藍站在迷宮左上角的方格，目標是走到右下角的方格。他每一步可以移動到上下左右相鄰的方格去。
??由于特殊的原因，小藍的路線必須先走 K 個 A 格子、再走 K 個 B 格子、再走 K 個 A 格子、再走 K 個 B 格子……如此反復(fù)交替。
??請你計算小藍最少需要走多少步，才能到達右下角方格？
??注意路線經(jīng)過的格子數(shù)不必一定是 K 的倍數(shù)，即最后一段 A 或 B 的格子可以不滿 K 個。起點保證是 A 格子。
例如 K = 3 時，以下 3 種路線是合法的：
AA
AAAB
AAABBBAAABBB
以下 3 種路線不合法：
ABABAB
ABBBAAABBB
AAABBBBBBAAA
【輸入格式】
第一行包含三個整數(shù) N、M 和 K。
以下 N 行，每行包含 M 個字符（A 或 B），代表格子類型。
【輸出格式】
一個整數(shù)，代表最少步數(shù)。如果無法到達右下角，輸出 ?1。
【樣例輸入】
4 4 2
AAAB
ABAB
BBAB
BAAA
【樣例輸出】
8
【樣例說明】
每一步方向如下：下右下右上右下下；路線序列：AABBAABBA。
【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，1 ≤ N, M ≤ 4。
對于另 20% 的數(shù)據(jù)，K = 1。
對于 100% 的數(shù)據(jù)，1 ≤ N, M ≤ 1000，1 ≤ K ≤ 10。
【解釋】
經(jīng)典的Dijkstra，熟練的話隨便做了，用一個數(shù)組統(tǒng)計最優(yōu)值，有更優(yōu)的值就更新即可
就不多解釋了，可以看看代碼
【代碼】
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
int ans[1010][1010][20];//記錄到達每個狀態(tài)的最小步數(shù)
string s[1010];//存地圖
priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> q;
int f[4][2]={0,1,1,0,-1,0,0,-1};//四個方向
signed main(){
cin>>n>>m>>k;
for(int i=0;i<n;i++){
cin>>s[i];
}
memset(ans,0x3f,sizeof ans);//初始化最大值
q.push({0,1,0,0});//{0,1,0,0}分別代表走了0步，第1個相同字母，橫坐標，縱坐標
ans[0][0][1]=0;
while(!q.empty()){
vector<int> v=q.top();
q.pop();
int px=v[2];//當前點的坐標
int py=v[3];
for(int i=0;i<4;i++){
int x=px+f[i][0];//下一個點的坐標
int y=py+f[i][1];
if(x>=0&&x<n&&y>=0&&y<m){//得符合條件
if(s[px][py]==s[x][y]){//字母相同的情況
if(v[1]==k)continue;//到k了就不能走了
if(ans[x][y][v[1]+1]>v[0]+1){//有更優(yōu)的，更新
ans[x][y][v[1]+1]=v[0]+1;
q.push({v[0]+1,v[1]+1,x,y});
}
} else{//字母不相同的情況
if(v[1]!=k)continue;//不到k不能走不同字母
if(ans[x][y][1]>v[0]+1){//有更優(yōu)的，更新
ans[x][y][1]=v[0]+1;
q.push({v[0]+1,1,x,y});
}
}
}
}
}
int mi=ans[0][0][0];
for(int i=1;i<=k;i++){
mi=min(mi,ans[n-1][m-1][i]);//記錄到達終點的最小值
}
if(mi==ans[0][0][0]){
cout<<-1<<endl;
}else{
cout<<mi<<endl;
}
}
試題 H: 抓娃娃
時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：20 分
【問題描述】
??小明拿了 n 條線段練習(xí)抓娃娃。他將所有線段鋪在數(shù)軸上，第 i 條線段的左端點在 li，右端點在 ri。小明用 m 個區(qū)間去框這些線段，第 i 個區(qū)間的范圍是 [Li, Ri]。如果一個線段有 至少一半 的長度被包含在某個區(qū)間內(nèi)，則將其視為被這個區(qū)間框住。請計算出每個區(qū)間框住了多少個線段？
【輸入格式】
輸入共 n + m + 1 行。
第一行為兩個正整數(shù) n, m。
后面 n 行，每行兩個整數(shù) li,ri。
后面 m 行，每行兩個整數(shù) Li, Ri。
【輸出格式】
輸出共 m 行，每行一個整數(shù)。
【樣例輸入】
3 2
1 2
1 3
3 4
1 4
2 3
【樣例輸出】
3
2
【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，保證 n, m ≤ 103。
對于 100% 的數(shù)據(jù)，保證 n, m ≤ 105，li < ri，0 < li,ri, Li, Ri ≤ 106，max{ri ?li} ≤ min{Ri ? Li}
【解釋】
題目勘誤了，樣例最后一行應(yīng)該是2 4，而不是2 3
1、其實題目保證了max{ri ?li} ≤ min{Ri ? Li}，那么如果占了區(qū)間一半的話，那么肯定包含了區(qū)間中點，我們就用這個原理做一個前綴和就好了
2、因為涉及了小數(shù)，給每個數(shù)字都乘以2先吧
【代碼】
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int arr[2000010];
signed main(){
cin>>n>>m;
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
arr[(a+b)]++;//實際是 (a+b)/2*2
}
for(int i=1;i<2000010;i++){
arr[i]+=arr[i-1];//前綴和
}
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a*=2;
b*=2;
cout<<arr[b]-arr[a-1]<<endl;//差分
}
}
試題 I: 拼數(shù)字
時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：25 分
【問題描述】
小藍要用 N 個數(shù)字 2 和 M 個數(shù)字 3 拼出一個 N + M 位的整數(shù)。請你計算
小藍能拼出的最大的 2023 的倍數(shù)是多少？
【輸入格式】
兩個整數(shù) N 和 M。
【輸出格式】
一個 N + M 位的整數(shù)，代表答案。如果拼不出 2023 的倍數(shù)，輸出 ?1。
【樣例輸入】
2 8
【樣例輸出】
2233333333
【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，1 ≤ N, M ≤ 12。
對于 40% 的數(shù)據(jù)，1 ≤ N, M ≤ 100。
對于 60% 的數(shù)據(jù)，1 ≤ N, M ≤ 10000。
對于 100% 的數(shù)據(jù)，1 ≤ N, M ≤ 1000000。
【解釋】
不會做啊啊啊，痛哭
【代碼】
不會寫文章來源：http://www.zghlxwxcb.cn/news/detail-478668.html
試題 J: 逃跑
時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：25 分
【問題描述】
??小明所在星系有 n 顆星球，編號為 1 到 n。這些星球通過 n ? 1 條無向邊連成一棵樹。根結(jié)點為編號為 1 的星球。
??為了在星際戰(zhàn)爭到來時逃到其他星系，小明在根結(jié)點設(shè)置了逃離用的傳送門。每個星球的人只需要一直往父結(jié)點星球移動就可以抵達根結(jié)點。為了方便各個星球的人去往根結(jié)點，小明將其中 m 個星球設(shè)置為了跳板星球。在從某個星球去往根結(jié)點的路徑上，當一個人經(jīng)過任意星球（包括起點星球）時，他可以嘗試直接跳躍到 其前往根結(jié)點路徑上的除當前星球以外的第一個跳板星球，其時間花費和走到父結(jié)點星球的時間花費相同，都是 1 單位時間。
??然而，因為技術(shù)問題，向跳板星球的跳躍并不一定成功，每一次跳躍都有p 的概率失敗，并轉(zhuǎn)而跳躍到當前星球的父結(jié)點星球（相當于直接走到父結(jié)點星球）；同時此跳板星球失效，將 不再視為跳板星球。
??為了衡量移動效率，小明想知道，如果一個人在這 n 顆星球中隨機選擇一顆出發(fā)前往根結(jié)點，其花費的最短時間的期望是多少單位時間？
【輸入格式】
輸入共 n + 1 行，第一行為兩個正整數(shù) n、m 和一個浮點數(shù) p。
后面 n ? 1 行，每行兩個正整數(shù) xi
, yi 表示第 i 條邊的兩個端點。
最后一行，共 m 個正整數(shù)表示所有跳板星球的編號。
【輸出格式】
一行，一個浮點數(shù)，表示答案（請保留兩位小數(shù)）。
【樣例輸入】
4 1 0.2
1 2
2 3
3 4
2
【樣例輸出】
1.30
【樣例說明】
從 1 號星球出發(fā)的時間花費為 0；
從 2 號星球出發(fā)的時間花費為 1；
從 3 號星球出發(fā)的時間花費為 2；
從 4 號星球出發(fā)的時間花費為 0.8 × 2 + 0.2 × 3 = 2.2。
所以期望時間為 (0+1+2+2.2)/4 = 1.3。
【評測用例規(guī)模與約定】
對于 30% 的數(shù)據(jù)，保證 1 ≤ n ≤ 2000。
對于 100% 的數(shù)據(jù)，保證 1 ≤ n ≤ 106，1 ≤ m ≤ n，0 < p < 1。
【解釋】
不會做啊啊啊，痛哭
【代碼】
不會寫
大佬有好思路可以提供一下，感謝！點個贊吧！文章來源地址http://www.zghlxwxcb.cn/news/detail-478668.html
到了這里，關(guān)于2023第十四屆藍橋杯國賽 C/C++ 大學(xué) B 組的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
