蓝桥杯校内模拟赛

今天药忘吃喽~ 2023-07-13 03:07 30阅读 0赞

### 蓝桥杯校内模拟赛 ###

*   *   *  A 约数
         *  B 内存
         *  C 数位为9
         *  D 树的叶子节点
         *  E 字符串
         *  F 数组
         *  G　逆序数
         *  H bfs
         *  I 数列
         *  J 晚会

### A 约数 ###

1200000有多少个约数（只计算正约数）。

#include<bits/stdc++.h>
    using namespace std;
    
    int main(){ 
    	int ans = 0 ,i,n=1200000;
    	for( i=1;i*i<n;++i){ 
    		if(n%i==0)ans+=2;
    	}
    	if(i*i==n)ans+=1;
    	printf("%d",ans);//96
    }

### B 内存 ###

在计算机存储中，15.125GB是多少MB？

#include<bits/stdc++.h>
    using namespace std;
    
    int main(){ 
    	double d = 15.125;
    	printf("%.2lf",d*1024);//15488
    }

### C 数位为9 ###

在1至2019中，有多少个数的数位中包含数字9？  
　　注意，有的数中的数位中包含多个9，这个数只算一次。例如，1999这个数包含数字9，在计算只是算一个数。

#include<bits/stdc++.h>
    using namespace std;
    
    int main(){ 
    	int n=2019,ans=0,f,j;
    	for(int i=9;i<=n;++i){ 
    		f=0;
            j=i;
    		while(j){ 
    			if(j%10==9){ 
    				f=1;
    				break;
    			}
    			j/=10;
    		}
    		if(f)ans++;
    	}
    	printf("%d",ans);//544
    }

### D 树的叶子节点 ###

一棵包含有2019个结点的树，最多包含多少个叶结点？

>  n 0 = n 2 + 1 n\_0=n\_2+1 n0=n2\+1 ,所以 n 0 = \[ n / 2 \] ( 向 上 取 整 ) = 1010 n\_0=\[n/2\](向上取整)=1010 n0=\[n/2\](向上取整)=1010  
> 一般的m叉树 n 0 = 1 + ∑ i = 2 m ( i − 1 ) n i n\_0=1+\\sum\\limits\_\{i=2\}^\{m\}(i-1)n\_i n0=1\+i=2∑m(i−1)ni，  
>  m a x ( n 0 ) = 1 + n m ∗ ( m − 1 ) ⇒ n 0 = 2018 max(n\_0)=1+n\_m\*(m-1)\\Rightarrow n\_0=2018 max(n0)=1\+nm∗(m−1)⇒n0=2018

### E 字符串 ###

#include<bits/stdc++.h>
    using namespace std;
    string s;
    int i=0;
    
    /** * @brief 判断字符是否为元音字母 a, e, i, o, u */
    bool judeg(char c){ 
    	return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';
    }
    
    /** * @brief 判断辅音段的个数 */
    int f1(){ 
    	int ans=0;
    	for(;i<s.size();++i)if(judeg(s[i])==false)ans++; else break;
    	return ans;
    }
    
    /** * @brief 判断元音段的个数 */
    int f2(){ 
    	int ans=0;
    	for(;i<s.size();++i)if(judeg(s[i])==true)ans++; else break;
    	return ans;
    }
    
    int main(){ 
    	cin>>s;
    	if(f1()>0&&f2()>0&&f1()>0&&f2()>0&&i==s.size())printf("yes\n");
    	else printf("no\n");//短路性质
    	
    }

### F 数组 ###

在数列 a\[1\], a\[2\], …, a\[n\] 中，如果对于下标 i, j, k 满足 0<i<j<k<n+1 且 a\[i\]<a\[j\]<a\[k\]，则称 a\[i\], a\[j\], a\[k\] 为一组递增三元组，a\[j\]为递增三元组的中心。  
　　给定一个数列，请问数列中有多少个元素可能是递增三元组的中心。（n<1000)

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e3+3;
    int n;
    int a[N];
    
    /** * @brief 求数组a[N] 在区间[b,n)的最大值 */
    int Max(int b){ 
    	int ans = a[b];
    	for(int i=b;i<n;++i)if(a[i]>ans)ans=a[i];
    	return ans;
    }
    
    int main(){ 
    	scanf("%d",&n);
    	for(int i=0;i<n;++i)scanf("%d",&a[i]);
    	int Min=a[0],ans=0;
    	for(int i=1;i<n-1;++i){ 
    		if(Min<a[i]&&a[i]<Max(i+1))ans++;
    		if(Min>a[i])a[i]=Min;
    	}
    	printf("%d\n",ans);
    }

O(n)优化

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e3+3;
    int n;
    int a[N];
    int leftMin[N];//leftMin[i]=min(a[0]~a[i])
    int rightMax[N];//rightMax[i]=max(a[i]~a[n-1])
    // 该问题等价于 leftMin[i]<a[i]<rightMax[i]
    
    int main(){ 
    	scanf("%d",&n);
    	for(int i=0;i<n;++i)scanf("%d",&a[i]);
        leftMin[0]=a[0];
        rightMax[n-1]=a[n-1];
        for(int i=1;i<n-1;++i)leftMin[i]=min(leftMin[i-1],a[i]);
        for(int i=n-2;i>0;--i)rightMax[i]=max(rightMax[i+1],a[i]);
        int ans=0;
        for(int i=1;i<n-1;++i)if(a[i]>leftMin[i]&&a[i]<rightMax[i])ans++;
        printf("%d",ans);   
    }

### G　逆序数 ###

一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如1135是一个数位递增的数，而1024不是一个数位递增的数。  
　　给定正整数 n，请问在整数 1 至 n 中有多少个数位递增的数？

#include<bits/stdc++.h>
    using namespace std;
    
    int a[10],m;
    
    /** * @brief 判断一个正整数d是否满足任何一个数位不大于右边相邻的数位。 */
    bool judge(int d){ 
    	m = 0;
    	while(d){ 
    		a[m++]=d%10;
    		d/=10;
    	}
    	for(int i=m-1;i>0;--i){ 
    		if(a[i]>a[i-1])return false;
    	}
    	return true;
    }
    
    int main(){ 
    	int n,ans=0;
    	scanf("%d",&n);
    	for(int i=1;i<=n;++i){ 
    		if(judge(i))ans++;
    	}
    	printf("%d\n",ans);
    	return 0;
    }

### H bfs ###

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。  
　　小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。  
　　这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。  
　　请告诉小明，k 个月后空地上哪些地方有草。

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e3+3;
    int n,m,k;
    char g[N][N];
    int pos[4][2]={ { 1,0},{ -1,0},{ 0,1},{ 0,-1}};//移动方向
    struct Node
    { 
    	int x,y;
    	Node(int x,int y):x(x),y(y){ }
    	Node(){ }
    };
    
    queue<Node> pre;//初始访问
    queue<Node> _next;//下次访问
    
    void bfs(){ 
    	int xx,yy;
    	Node node; 
    	for(int i=0;i<k;++i){ 
    		
    		while(!pre.empty()){ 
    			node=pre.front();
    			pre.pop();
    			for(int j=0;j<4;++j){ 
    				xx = node.x+pos[j][0];
    				yy = node.y+pos[j][1];
    				if(xx>=0&&xx<n&&yy>=0&&yy<=m&&g[xx][yy]=='.'){ 
    					g[xx][yy]='g';
    					_next.push(Node(xx,yy));
    				}
    			}
    		}
    		while(!_next.empty()){ 
    			pre.push(_next.front());
    			_next.pop();
    		}
    	}
    }
    
    int main(){ 
    	std::ios::sync_with_stdio(false);
    	cin.tie(0);//关闭输入同步流
    	cin>>n>>m;
    	for(int i=0;i<n;++i){ 
    		for(int j=0;j<m;++j){ 
    			cin>>g[i][j];
    			if(g[i][j]=='g')pre.push(Node(i,j));
    		}
    	}
    	cin>>k;
    	bfs();
    	for(int i=0;i<n;++i){ 
    		for(int j=0;j<m;++j)cout<<g[i][j];
    		cout<<"\n";
    	}
    	return 0;
    }

### I 数列 ###

小明想知道，满足以下条件的正整数序列的数量：  
　　1. 第一项为 n；  
　　2. 第二项不超过 n；  
　　3. 从第三项开始，每一项小于前两项的差的绝对值。  
　　请计算，对于给定的 n，有多少种满足条件的序列。  
　　输出答案除以10000的余数。  
　　1 <= n <= 1000

#include<bits/stdc++.h>
    using namespace std;
    
    
    /* 　1. 第一项为 n； 　2. 第二项不超过 n； 　3. 从第三项开始，每一项小于前两项的差的绝对值 */
    
    int ans=0;
    const int MOD =1e4;
    void mod(int &d){ 
    	if(d>MOD)d-=MOD;
    }
    
    //该方法可能只有一部分
    void recursion(int a,int b){ 
    	int z = abs(a-b);
    	ans++;mod(ans);
    	for(int i=1;i<z;++i){ 
    		recursion(b,i);
    	}
    }
    
    int main(){ 
    	int n;
    	scanf("%d",&n);
    	for(int i=1;i<=n;++i)recursion(4,i);
    	printf("%d\n",ans);
    }

### J 晚会 ###

小明要组织一台晚会，总共准备了 n 个节目。然后晚会的时间有限，他只能最终选择其中的 m 个节目。  
　　这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。  
　　小明发现，观众对于晚上的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。  
　　小明给每个节目定义了一个好看值，请你帮助小明选择出 m 个节目，满足他的要求。  
　　1 <= n <= 100000，0 <= 节目的好看值 <= 100000。