devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

24.第12届蓝桥杯省赛真题题解

作者：不正经 | 2024-03-17 13:11:20

赞

踩

24.第12届蓝桥杯省赛真题题解

A.空间（100%）

计算机存储单位计算

1TB=2^10 GB

1GB=2^10 MB

1MB=2^10 KB

1KB=2&10 B

1B=8 bit(bit位二进制的最小的存储单位)

#include <iostream>
#include <cmath>

using namespace std;
//2^28B  2^2

int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cout<<(int)pow(2,26)<<endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

B.卡片（100%）

#include <iostream>
#include <cmath>

using namespace std;
const int N=20;
int cnt[N];
int main(){ 
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n=2021;
	for(int i=0;i<=9;i++){
		cnt[i]=n;
	}
	bool flag=false;
	int x;
	for(x=1;;x++){
		int t=x;
		while(t){
			//123
			int num=t%10;
			if(--cnt[num]<0){
				flag=true;
				break;
			}
			t=t/10;
		}
		if(flag) break;
	}
	cout<<x-1<<endl;
	return 0;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

C.直线（100%）

根据y=kx+b 俩个点确定唯一的一个（k,b）对 放在set中去重加 输出个数
#include <iostream>
#include <cmath>
#include <set>
using namespace std;

int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    set<pair<double,double>> st;
    for(int x1=0;x1<=19;x1++){
        for(int y1=0;y1<=20;y1++){
            for(int x2=x1+1;x2<=19;x2++){
                for(int y2=0;y2<=20;y2++){
                    double k=(y2-y1)*1.0/(x2-x1);
                    double b=(y1 * x2 - y2 * x1) *1.0/ (x2 - x1);
                    st.insert({k,b});
                }
            }
        }
    }
    cout<<st.size()+20<<endl;
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

D.物品摆放（100%）

枚举3个位置的值

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

#include <iostream>
#include <vector>
#define int long long 
using namespace std;
int n=2021041820210418,ans;
vector<int> vec;
signed main(){ 
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	for(int i=1;i*i<=n;i++){
		if(n%i==0){//是因子 16
			vec.push_back(i);//2
			if(i!=n/i) vec.push_back(n/i);//8
		}
	}
	for(int i=0;i<vec.size();i++){
		for(int j=0;j<vec.size();j++){
			for(int k=0;k<vec.size();k++){
				if(vec[i]*vec[j]*vec[k]==n){
					ans++;
				}
			}
		}
	} 
	cout<<ans<<endl;
	return 0;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

E.路径（100%）

Dijkstra(单源最短路)

时间复杂度O(n^2)

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

不用邻接表邻接矩阵版本

#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
const int N=2021;
int n=2021,mindis[N],st=1,t=2021;
bool vis[N];
int gcd(int a,int b){
    return b==0? a:gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
void dijkstra(int s){
    mindis[s]=0;
    for(int i=1;i<=n;i++){
        int mi=INT_MAX,miId=0;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&mi>mindis[j]){
                mi=mindis[j];
                miId=j;
            }
        }
        vis[miId]=1;
        for(int i=1;i<=n;i++){
            if(miId-i!=0&&abs(miId-i)<=21&&!vis[i]){
                int id=i,w=lcm(miId,id);
                if(mi+w<mindis[id]){
                    mindis[id]=mi+w;
                }
            }
        }
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    for(int i=1;i<=n;i++) mindis[i]=INT_MAX;
    dijkstra(st);
    cout<<mindis[t]<<endl;
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

邻接表版本

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#define int long long

using namespace std;
const int N=3e3+10,INF=INT_MAX;
vector<pair<int,int>> g[N];
int n=2021,mindis[N],st=1,t=2021;
bool vis[N];
//mindis[i]-->起点到i点的最短路 
//6 12 
int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
void dijkstra(int s){
	mindis[s]=0;
	for(int i=1;i<=n;i++){
		int mi=INT_MAX,miId=0;
		//在集合中找到未被标记过的最小值，即起点到该点的最短路 
		for(int j=1;j<=n;j++){
			if(!vis[j]&&mi>mindis[j]){
				mi=mindis[j];
				miId=j;
			}
		}
		vis[miId]=1;
		//以miId位中转点,访问miId未被标记过的邻接点，更新集合 
		for(int j=0;j<g[miId].size();j++){
			int id=g[miId][j].first,w=g[miId][j].second;
			if(!vis[id]&&mindis[id]>mi+w){
				mindis[id]=mi+w;
			}
		}
	}
} 
signed main(){ 
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j&&abs(i-j)<=21){
                //无向图，双向连边
				g[i].push_back({j,lcm(i,j)});g[j].push_back({i,lcm(i,j)});
			}
		}
	}
	fill(mindis+1,mindis+n+1,INF);
	dijkstra(st);
	cout<<mindis[t];
	return 0;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56

Floyd(多元最短路)

三层for循环 时间复杂度O(n^3)
#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#define int long long

using namespace std;
const int N=3e3+10,INF=INT_MAX;
int n=2021,mindis[N][N],st=1,t=2021;
bool vis[N];
//mindis[i][j]-->起点i到j点的最短路 
//6 12 
int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
void floyd(){
    //枚举中转站
	for(int k=1;k<=n;k++){
        //枚举起点
		for(int i=1;i<=n;i++){
            //枚举终点
			for(int j=1;j<=n;j++){
                //判断是否又连边
				if(mindis[i][k]!=INF&&mindis[k][j]!=INF){
                    //判断是否需要更新mindis集合
					if(mindis[i][k]+mindis[k][j]<mindis[i][j]){
						mindis[i][j]=mindis[i][k]+mindis[k][j];
					}
				}
			}
		}
	}
}
signed main(){ 
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	fill(mindis[0],mindis[0]+N*N,INF);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j&&abs(i-j)<=21){
				mindis[i][j]=mindis[j][i]=lcm(i,j);
			}
		}
	}
	floyd();
	cout<<mindis[st][t]<<endl;
	return 0;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

F.时间显示（100%）

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int HH,MM,SS,x1,x2;
const int DAY=24*60*60,H=60*60,M=60;
//1618708103123
//449641:08:23
signed main(){ 
	std::ios::sync_with_stdio(false);
    	cin.tie(0);cout.tie(0);
	int n;cin>>n;//1618708103123
	n=n/1000;//46863
	HH=n/H%24;//13
	x1=n%H;//63
	MM=x1/M;//1
	x2=x1%M;//3
    SS=x2;
    printf("%02ld:%02ld:%02ld\n",HH,MM,SS);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

G.砝码称重（10%）

搜索+回溯

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <set>
#define int long long

using namespace std;
const int N=1e5+10;
int a[N],n; 
bool vis[N];
set<int> st; 
void dfs(int sum,int depth){
	//3
	//1 4 6
	//insert   d 1 sum 1
	//insert 1 d 2 sum 5
	//insert 5 d 3 sum 10
	//insert 10d 4 sum  
	if(depth>=2) st.insert(sum);
	if(depth==n+1) return;
	
	
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			dfs(sum+a[i],depth+1);
			dfs(abs(sum-a[i]),depth+1);
			vis[i]=0;
		}
	}
}
signed main(){ 
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(0,1);
	if(st.find(0)!=st.end()) st.erase(0);
	cout<<st.size()<<endl;
	return 0;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

H.杨辉三角（40%）

#include <iostream>
#define int long long
using namespace std;
const int N=1e3+10;
int a[N][N];
int n=1e2+10,ans;
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    for(int i=1;i<=n;i++){
        a[i][1]=1;
        a[i][i]=1;
    }
    for(int i=3;i<=n;i++){
        for(int j=2;j<=i-1;j++){
            a[i][j]=a[i-1][j]+a[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(a[i][j]==t){
                cout<<++ans<<endl;
                return 0;
            }
            ans++;
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

I.双向排序（60%）

#include <iostream>
#include <algorithm>
//#define int long long
using namespace std;
const int N=1e5+10;
int a[N],n,m;
bool cmp(int l,int r){
    return l>r;
}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        a[i]=i;
    }
    int sign,k;
    while(m--){
        cin>>sign>>k;
        if(sign==0){//从1到k降序
            sort(a+1,a+k+1,cmp);
        }
        else{//从k到n升序
            sort(a+k,a+n+1);
        }
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

J.括号序列（100%）

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
const int N = 5e3 + 10, mod = 1e9 + 7; // 定义常量N和mod，mod用于计算结果的模数
int n; // 输入的字符串长度
string str; // 存储输入的括号序列
int f[N][N]; // 动态规划数组，f[i][j]表示前i个字符中有j个左括号待匹配时的方案数量
 
// calc函数用于计算结果
int calc() {
    memset(f, 0, sizeof(f)); // 初始化动态规划数组
    f[0][0] = 1; // 初始状态设为1，表示没有任何括号的情况只有一种可能
    for (int i = 1; i <= n; i++) { // 遍历输入的括号序列
        if (str[i] == '(') { // 如果当前字符是左括号
            for (int j = 1; j <= n; j++) { // 遍历所有可能的未匹配的左括号数量
                f[i][j] = f[i - 1][j - 1]; // 状态转移，因为遇到左括号，需要匹配的左括号数量减少1
            }
        }
        else { // 如果当前字符是右括号
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod; // 状态转移，如果之前没有未匹配的左括号，只能添加一个左括号，否则可以不添加或添加一个左括号
            for (int j = 1; j <= n; j++) { // 遍历所有可能的未匹配的左括号数量
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod; // 状态转移，因为遇到右括号，需要匹配的左括号数量增加1，或者添加一个右括号来消除一个未匹配的左括号
            }
        }
    }
    for (int i = 0; i <= n; i++) { // 遍历所有可能的未匹配的左括号数量
        if (f[n][i]) { // 如果存在合法的方案
            return f[n][i]; // 返回方案数量
        }
    }
    return -1; // 如果没有合法的方案，返回-1
}
 
signed main() {
    cin >> str; // 输入括号序列
    n = str.size(); // 计算括号序列的长度
    str = " " + str; // 在字符串前添加一个空格，便于索引操作
    int l = calc(); // 调用calc函数计算结果
    reverse(str.begin() + 1, str.end()); // 反转括号序列
    for (int i = 1; i <= n; i++) { // 将括号序列中的左括号和右括号互换
        if (str[i] == '(') str[i] = ')';
        else str[i] = '(';
    }
    int r = calc(); // 再次调用calc函数计算结果
    printf("%lld\n", l * r % mod); // 输出结果，即两次计算结果的乘积对mod取模
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/256194
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号