猫史档案馆

*因已经退出了考试系统，故我不能查看原题了。下面的题面是回忆性的。

Problem 1 1031GCC01 求阶乘的和

题目描述给你一个数n，求 Σ(k=1→n) n!，也就是求1!+2!+3!+...+n!。

看到题面，千万不要直接for(int i=1;i<=n;i++)ans+=jiecheng(i);

你确定这样不会超时？n是<=100，这样复杂度又O(N^2)，马上爆掉（虽然我没试过

为了优化，您可以使用如下代码：

#include<iostream>
using namespace std;
long long n,ans=0,now=1;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		now*=i;
		ans+=now;
	}
	cout<<ans;
	return 0;
}

变量now保存当前阶乘的值，且不用每次更新。注意n，ans，now最好long long，数据有点大。

测试结果：AC-全部通过

Problem 2 1031GCC02 输出范围内所有只含有偶数数字的数字

题目描述给你两个数n，m（n<=m) ，输出在这两个数之间所有仅包含偶数数字的数字。

掉坑记录：不是偶数而是只包含偶数数字的数字，如2026是，而3026不是（因为3是奇数

正解：

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,last=-1;
bool check(int i){
	while(i!=0){
		if((i%10)%2!=0){
			return false;
		}
		i/=10;
	}
	return true;
}
int main(){
	cin>>n>>m;
	for(int i=n;i<=m;i++){
		if(i%2==0&&check(i)){
			if(last!=-1)
				printf("%d,",last);
			last=i;
		}
	}
	printf("%d",last);
	return 0;
}

测试结果 AC-全部通过

Problem 3 1031GCC03 统计数字出现的个数

题目描述给你一个数字n，求从1~n区间对于每一个数所有数字出现的个数总数。

。。。此题过水，直接放代码：

#include<iostream>
using namespace std;
int n;
long long cnt[15]={};
void fun(int num){
	while(num>0){
		cnt[num%10]++;
		num/=10;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		fun(i);
	}
	for(int i=0;i<10;i++){
		cout<<i<<","<<cnt[i]<<"\n";
	}
	return 0;
}

测试结果 AC-全部通过

Problem 4 1031GCC04 求最大公共子串

题目描述给你两个字符串s1与s2，求它们的最长公共子串。

🕳1：s1和s2长度是否相等？题目里并没有说（原题也没有），后来发现两个字符串一定是相等的。

🕳2：本来看到这题马上就想到dp，但发现字符串长度不超过100，那么喵以下也能过。于是：

#include<iostream>
using namespace std;
string a,b;
string ans;int len;
int main(){
	cin>>a>>b;
	for(int i=0;i<a.length();i++){
		for(int j=1;j<a.length()-i;j++){
			if(b.find(a.substr(i,j))!=-1){
				if(a.substr(i,j).length()>len){
					len=a.substr(i,j).length();
					ans=a.substr(i,j);
				}
			}
		}
	}
	cout<<ans<<endl<<len;
	return 0;
}

自己随手乱写了两个长度为100多的字符串，输进去，也没有爆掉。

测试结果 AC-全部通过

Problem 5 1031GCC05 数字操作

题目描述给你连个数字n和k，对于每一操作可以有n+1，n-1，n×2，问最少几次操作后n能变成k？

坑坑坑！🕳！

思考：用dfs肯定超时。所以用bfs。

第一次尝试：

发现×2的操作会导致效率降低，剪枝：

if(t.num<k)
    q.push({t.cishu+1,t.num*2});

第二次尝试：

发现+1与-1的操作会喵循环，添加bk记录数组，bk[i]表示第i个数是否被使用过。

if(bk[t.num]){
    q.pop();
    continue;
}
bk[t.num]=1;

第三次尝试：

样例成功过了，但作喵试了试极限：n=1，k=1000000（数据说明：0<n<1000001，0<k<1000001）

此时记得n到1000324时RE了。

找原因找了10min。。。。。。正当要放弃之时：

bool bk[100010]={};

而：

if(bk[t.num])

！！！数组越界！！！

于是：

bool bk[1000100]={};

后边多加一个零就完事了。

测试结果 AC-全部通过

Problem 6 1031GCC06 回形取数

题目描述给你n和m，表示一个矩阵的长和宽，且这个矩阵横排排列，为1，2，3...如：

当n=3，m=4时，

此矩阵为：

1 2 3

4 5 6

7 8 9

接着，请你以“回形”遍历这个矩阵。顺序如下（数字表示第几步）：

1 8 7

2 9 6

3 4 5

输出结果为：

1,4,7,8,9,6,3,2

看到这题，，，又是一道模拟题。。。有点复杂。

不过多想一会也能想出来吧。。。上代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool first_time=1;
bool vis[30][30]={};
int getnum(int x,int y){
	return (x-1)*n+y;
}
void dfs(int x,int y,char w){
	if(vis[x][y])return;
	vis[x][y]=1;
	if(first_time){
		cout<<getnum(x,y);
		first_time=0;
	}else
		cout<<","<<getnum(x,y);
	if(w=='s'){
		if(vis[x-1][y]){
			dfs(x,y-1,'z');
		}else{
			dfs(x-1,y,'s');
		}
	}else if(w=='x'){
		if(vis[x+1][y]){
			dfs(x,y+1,'y');
		}else{
			dfs(x+1,y,'x');
		}
	}else if(w=='z'){
		if(vis[x][y-1]){
			dfs(x+1,y,'x');
		}else{
			dfs(x,y-1,'z');
		}
	}else if(w=='y'){
		if(vis[x][y+1]){
			dfs(x-1,y,'s');
		}else{
			dfs(x,y+1,'y');
		}
	}
}
int main(){
	cin>>m>>n;
	for(int i=0;i<=n+1;i++){
		vis[0][i]=vis[m+1][i]=1;
	}
	for(int i=0;i<=m+1;i++){
		vis[i][0]=vis[i][n+1]=1;
	}
	dfs(1,1,'x');
	return 0;
}

测试结果 AC-全部通过

-----------------------------------------------------------------------------------------------------------------------------

总而言之，这次蓝桥杯初级组的题目难度不是很大，个人认为还有一定的难度提升空间，不然1=也太好拿了（

猫史档案馆

【蓝桥杯】【题解】【初级组】【C++】【与NOC擦边？】

回复