蓝桥杯第六届蓝桥杯大赛个人赛校内选拔（软件类）C++A组，B组，C组真题解析_蓝桥杯a组b组题目一样吗

题目链接

A组真题

题目结构

第一题

• 问题重现

  一个串的子串是指该串的一个连续的局部。如果不要求连续，则可称为它的子序列。
  比如对串： “abcdefg” 而言，“ab”,“abd”,“bdef” 等都是它的子序列。
  特别地，一个串本身，以及空串也是它的子序列。
  对两个串而言，可以有许多的共同的子序列，我们关心的是：它们所共同拥有的长度最大的子序列是多长。以下代码实现了这个问题的求解。请填写划线部分缺失的代码。

  inline max(int a, int b)
  {
  	return a>b?a:b;
  }
  
  int f(char* x, char* y)
  {
  	if(strlen(x)==0) return 0;
  	if(strlen(y)==0) return 0;
  
  	if(*x == *y) return f(x+1, y+1) + 1;
  
  	return max( ______________________ );
  }
  
  int main()
  {
  	printf("%d\n", f("ac","abcd")); //2
  	printf("%d\n", f("acebbcde1133","xya33bc11de")); //5
  	return 0;
  }
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22

• 解题思路
  这种类型的题想必我们在动态规划基础题中见过了，这里实际上就是用递归实现了，如果所比较字符相等的话，那么我们必然是继续往后比较，同时公共子序列长度$+1$，那如果不相等，我们依然要继续往后比较，那么这个时候我们比较的方式要么是串$x$往后移一位，要么是串$y$往后移一位。（两个串一起移一位在后面的操作中会判断，这里为了考虑全局情况所以只需要一个各移一次。） 所以，对于这两种方式，我们要取一个最优的，即是根据子序列长度来抉择的，故此题易解。

• 答案

  f(x+1,y),f(x,y+1)
  1

第二题

• 问题重现

  历史上有许多计算圆周率pai的公式，其中，格雷戈里和莱布尼茨发现了下面的公式：pai = 4*(1-1/3+1/5-1/7 …)
  参见下图
  这个公式简单而优美，但美中不足，它收敛的太慢了。
  如果我们四舍五入保留它的两位小数,那么：
  累积了1项和是：4.00
  累积了2项和是：2.67
  累积了3项和是：3.47
  …
  请你写出它累积了100项的和是多少（四舍五入到小数后两位）。
  注意:只填写该小数本身，不要填写任何多余的说明或解释文字。

• 解题思路
  实际上就是进行100次的四舍五入，那么对于四舍五入而言，C++中有函数round()供我们实现四舍五入，当然我们也可以自己写一个这样的函数，提取小数点第三位判断进位。

• 代码

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大

double func(double num){
    int temp = round(num*100.0);
    return (double)temp/100.0;
}
void solve(){
    double sum=0;
    rep(i,1,100){
        if(i%2){
            sum+=4.0/(i*2.0-1.0);
        }
        else{
            sum-=4.0/(i*2.0-1.0);
        }
        //意思是每进行一次就四舍五入。
        sum=func(sum);
    }
    cout<<sum<<endl;
}
int main(){
    solve();
    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

• 答案
  $3.15$

第三题

• 问题重现

  如果x的x次幂结果为10（参见下图），你能计算出x的近似值吗？
  
  显然，这个值是介于2和3之间的一个数字。
  请把x的值计算到小数后6位（四舍五入），并填写这个小数值。
  注意:只填写一个小数，不要写任何多余的符号或说明。

• 解题思路
  由于底数和指数都是同一个未知数，所以我们无法利用已知函数求解。我们知道，只需要精确$x$的值到小数点后六位，那么如果我们带入$x$的值不断比较那个值最优（根据偏离度来比较）不就可以得到我们的$x$值了吗？ 并且无需四舍五入了，因为我们在比较的时候就已经判断了。

• 代码

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大

void solve(){
    double minn=1,result;
    for(double x=2.0;x<=3.0;x+=0.000001){
        double temp = pow(x,x);
        if(fabs(temp-10.0)<minn){
            minn=fabs(temp-10.0);
            result=x;
        }
    }
    printf("%.6f\n",result);
}
int main(){
    solve();
    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

• 答案
  $2.506184$

第四题

• 问题重现

  今有7对数字：两个1，两个2，两个3，…两个7，把它们排成一行。
  要求，两个1间有1个其它数字，两个2间有2个其它数字，以此类推，两个7之间有7个其它数字。如下就是一个符合要求的排列：
  17126425374635
  当然，如果把它倒过来，也是符合要求的。
  请你找出另一种符合要求的排列法，并且这个排列法是以74开头的。
  注意:只填写这个14位的整数，不能填写任何多余的内容，比如说明注释等。

• 解题思路
  这个题目是要我们从多种排列中找到一个符合要求的排列，那么我们应该怎么去做呢？这种题型都可以采用回溯法来进行搜索，因为在回溯的过程中我们可以一直利用条件来进行判断并逐渐向正确结果靠拢。 我们可以开设两个辅助数组来进行记录判断，$vis$数组我们可以用来判断这个数字是否已经被确定，即两个位置是否都已放置，$arr$数组我们可以用来记录$i$在$arr[i]$这个位置上。通过这个，我们设置好起始出发位置和终止位置，由于题目一开始就已经确定了$7,4$是在第一个和第二个位置，所以我们起始位置是第$3$个，这也代表着前两个位置已经确定了，那么最终位置我们自然也可以知道即是第$15$个，因为这代表着前$14$个位置已经确定了，也就是最终结果找到了。在回溯过程中，我们在对可设置点的状态进行递归后要还原此点的状态，避免干扰。具体看代码。

• 代码

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大

bool vis[8];//vis[i]表示i是否已经确定位置。
int arr[15];//arr[i]表示arr[i]在第i个位置。
void dfs(int index){
    if(index==15){
        //这代表前15的位置都已经确定了，即已经得到了结果，我们直接输出。
        rep(i,1,14){
            cout<<arr[i];
        }
        cout<<endl;
        exit(0);
    }
    //我们对这七个数一次填充试错。
    rep(i,1,7){
        if(arr[index]){
            //说明这个位置已经确定了，我们去搜索下一个。
            dfs(index+1);
        }
        //判断这个状态是否可以填充数值。
        if(index+i+1<=14&&!arr[index]&&!arr[index+i+1]&&!vis[i]){
            vis[i]=true;
            arr[index]=arr[index+i+1]=i;
            dfs(index+1);
            //还原状态，避免干扰。
            vis[i]=false;
            arr[index]=arr[index+i+1]=0;
        }
    }
}
void solve(){
    memset(vis,false,sizeof(vis));
    memset(arr,0,sizeof(arr));
    //设置初始条件。
    vis[7]=vis[4]=true;
    arr[1]=arr[9]=7;
    arr[2]=arr[7]=4;
    //由于12已经是我们确定好了的，所以我们从位置3开始进行搜索。
    dfs(3);
}
int main(){
    solve();
    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
57
58
59

• 答案
  $74151643752362$

第五题

• 问题重现

  勾股定理，西方称为毕达哥拉斯定理，它所对应的三角形现在称为：直角三角形。
  已知直角三角形的斜边是某个整数，并且要求另外两条边也必须是整数。
  求满足这个条件的不同直角三角形的个数。
  输入格式
  输入一个整数 n (0<n<10000000) 表示直角三角形斜边的长度。
  输出格式
  要求输出一个整数，表示满足条件的直角三角形个数。
  样例输入
  5
  样例输出
  1
  样例输入
  100
  样例输出
  2
  样例输入
  3
  样例输出
  0
  资源约定
  峰值内存消耗 < 256M
  CPU消耗 < 1000ms
  注意:请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
  所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
  main函数需要返回0
  只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
  所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
  提交时，注意选择所期望的编译器类型。

• 解题思路
  对于此题，我们可以直接暴力求解，模拟一条边的长度(小于$n$)。那么我们自然可以根据斜边长度给计算出来，最后我们要验证是否符合，即没有精度损失。这样统计符合要求的三角形数。值得注意的一点，为了避免重复以及减小时间复杂度，我们模拟的那一条边是从小到大的，那么另一条边是从大到小的，所以当模拟的那条边大于另一条边，那么我们就$break$退出循环。

• 代码

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大

ll n;
void solve(){
    ll ans=0;
    ll temp=n*n;
    for(ll i=1;;i++){
        ll j=sqrt(temp-i*i);
        //为了防止重复，当i>j的时候退出。
        if(i>j){
            break;
        }
        if(i*i+j*j==temp){
            ans++;
        }
    }
    cout<<ans<<endl;
}
int main(){
    while(cin>>n){
        solve();
    }
    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

第六题

• 问题重现

  你一定听说过“数独”游戏。
  如图，玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个同色九宫内的数字均含1-9，不重复。
  
  数独的答案都是唯一的，所以，多个解也称为无解。
  本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。但对会使用计算机编程的你来说，恐怕易如反掌了。
  本题的要求就是输入数独题目，程序输出数独的唯一解。我们保证所有已知数据的格式都是合法的，并且题目有唯一的解。
  输入格式
  输入9行，每行9个数字，0代表未知，其它数字为已知。
  输出格式
  输出9行，每行9个数字表示数独的解。
  样例输入
  005300000
  800000020
  070010500
  400005300
  010070006
  003200080
  060500009
  004000030
  000009700
  样例输出
  145327698
  839654127
  672918543
  496185372
  218473956
  753296481
  367542819
  984761235
  521839764
  样例输入
  800000000
  003600000
  070090200
  050007000
  000045700
  000100030
  001000068
  008500010
  090000400
  样例输出
  812753649
  943682175
  675491283
  154237896
  369845721
  287169534
  521974368
  438526917
  796318452
  资源约定
  峰值内存消耗 < 256M
  CPU消耗 < 2000ms
  注意:
  请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
  所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
  main函数需要返回0
  只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
  所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
  提交时，注意选择所期望的编译器类型。

• 解题思路

  这道题和第四题一样，都可以采用回溯法来解决。但这一道题相对比较难。我们来分析一下，首先对于数独来说，它的每一行每一列以及同色九宫格都是1~9的排列，那么，我们可以根据这个条件不断、去搜索试错，直到找到符合要求的解法。 我们可以将这个数独划分为$9\times 9$的矩阵，然后我们按行从左往右开始dfs搜索，这样的话，假设我们搜索到了$(x,y)$这个位置，那么说明在之前的都已经确定好了数。故我们很容易就清楚起始搜索点是$(0,0)$，终止搜索点是$(8,8)$。而我们如何判断呢？主要是对于那些值未知的点，我们要将$1$~$9$的数都代入，同时模拟继续dfs后要还原状态，必须保证各种搜索路径之间不互相干扰。具体见代码。

• 代码

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大

string num[9];
bool check(int x,int y,int value){
    //先判断同行同列是否有相同的值。
    rep(i,0,8){
        if(num[x][i]-'0'==value)
            return false;
        if(num[i][y]-'0'==value)
            return false;
    }
    //还需判断同色九宫格是否满足条件。
    //获取边界坐标。
    int temp_x=x/3*3;//获取行。
    int temp_y=y/3*3;//获取列。
    rep(i,temp_x,temp_x+2){
        rep(j,temp_y,temp_y+2){
            if(num[i][j]-'0'==value)
                return false;
        }
    }
    return true;
}
//接下来开始dfs搜索。我们要知道，若点上不为0，说明已经确定了。
void dfs(int x,int y){
    //我们搜索按行从左到右，所以我们从(0,0)开始，到达(9,0)的时候说明前面的都已经确定了，即数独已完成。
    if(x>8){
        //已经完成，直接打印。
        rep(i,0,8){
            cout<<num[i]<<endl;
        }
        cout<<endl;
        return;
    }
    //判断该点是否已经确定。
    if(num[x][y]!='0'){
        dfs(x+(y+1)/9,(y+1)%9);//这里注意理解，考虑到坐标变化进位。
    }
    else{
        //我们就需要对这个点从1~9赋值尝试。
        rep(i,1,9){
            if(check(x,y,i)){
                num[x][y]='0'+i;
                dfs(x+(y+1)/9,(y+1)%9);
                //变为0，恢复状态。
                num[x][y]='0';
            }
        }
    }
}
void solve(){
    dfs(0,0);
}
int main(){
    rep(i,0,8){
        cin>>num[i];
    }
    solve();
    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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

第七题

• 问题重现

  G将军有一支训练有素的军队，这个军队除开G将军外，每名士兵都有一个直接上级（可能是其他士兵，也可能是G将军）。现在G将军将接受一个特别的任务，需要派遣一部分士兵（至少一个）组成一个敢死队，为了增加敢死队队员的独立性，要求如果一名士兵在敢死队中，他的直接上级不能在敢死队中。
  请问，G将军有多少种派出敢死队的方法。注意，G将军也可以作为一个士兵进入敢死队。
  输入格式
  输入的第一行包含一个整数n，表示包括G将军在内的军队的人数。军队的士兵从1至n编号，G将军编号为1。
  接下来n-1个数，分别表示编号为2, 3, …, n的士兵的直接上级编号，编号i的士兵的直接上级的编号小于i。
  输出格式
  输出一个整数，表示派出敢死队的方案数。由于数目可能很大，你只需要输出这个数除10007的余数即可。
  样例输入
  3
  1 1
  样例输出
  4
  样例说明
  这四种方式分别是：
  1.选1；
  2.选2；
  3.选3；
  4.选2, 3。
  样例输入
  7
  1 1 2 2 3 3
  样例输出
  40
  数据规模与约定
  对于20%的数据，n ≤ 20；
  对于40%的数据，n ≤ 100；
  对于100%的数据，1 ≤ n ≤ 100000。
  资源约定
  峰值内存消耗 < 256M
  CPU消耗 < 2000ms
  注意
  请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
  所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
  main函数需要返回0
  只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
  所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
  提交时，注意选择所期望的编译器类型。

• 解题思路
  还是一样的回溯题。这套题好多可以用回溯算法解决，还是和上面的题一样的思路，注意还原状态。这里说一下核心的一点就是我们统计方案数不要盲目统计，可以细分，例如对于只选一个人成员的方案数，然后2个，3个·····n个这样再加起来就是总方案数。

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5+10;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大

//这道题也同样类似于递归回溯。
bool vis[maxn];//vis[i]表示i的上级也在队伍中。
int superior[maxn];//superior[i]代表i的上级。
ll ans;//方案数
int n;//成员数。
bool check(int i){
    if(vis[superior[i]]){
        return false;
    }
    else{
        return true;
    }
}
void dfs(int sum,int need,int index){
    //num为我们搜索到这的时候已经选的成员数，need为我们需要的成员数，而index即为我们上次选取的成员编号。
    if(sum==need){
        //说明足够了。
        ans++;
        return;
    }
    //那么没有的话，我们就要从之后的成员中选取，因为我们选取成员是按顺序来的，这样避免了重复的情况。
    rep(i,index+1,n){
        //检查是否可行。
        if(check(i)){
            vis[i]=true;
            //选取之后就sum+1，继续搜索。
            dfs(sum+1,need,i);
            //还原状态。
            vis[i]=false;
        }
    }
}
void solve(){
    ans=0;
    //我们知道，我们选的成员最少1个，最多n个，那么我们将这些取值的所有可能统计起来就是方案数。
    rep(i,1,n){
        memset(vis,false,sizeof(vis));
        dfs(0,i,0);
    }
    cout<<ans<<endl;
}
int main(){
    while(cin>>n){
        rep(i,2,n){
            cin>>superior[i];
        }
        superior[1]=1;//将军的上级可以看做是他自己。
        solve();
    }
    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
57
58
59
60
61
62
63
64
65
66
67
68

B组真题（和A组只有前两题有区别，这里列写不同的题，剩余五题同A组后五题。）

第一题

• 问题重现

  输入一个字符串，求它包含多少个单词.单词间以-一个或者多个空格分开.
  第一个单词前，最后一个单词后也可能有0到多个空格.
  比如: " abc xyz"包含两个单词，"ab c xyz"包含3个单词.
  如下的程序解决了这个问题，请填写划线部分缺失的代码.

int get_word_num(char* buf)
{
	int n = 0;   
	int tag = 1; 
	char* p = buf;
	for(;*p!=0 && *p!=13 && *p!=10;p++){
		if(*p==' ' && tag==0) tag=1;
		if(________________ ) { n++; tag=0; }   //填空
		}
	return n;
	}

int main()
{
	char buf[1000];
	fgets(buf,1000,stdin);
	printf("%d\n", get_word_num(buf));
	return 0;
}

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

注意:只填写划线部分的代码，不要填写任何多余的内容。比如已经存在的小括号,注释或说明文字等.

• 解题思路

  首先我们要知道我们的程序目的是什么？统计单词的个数。那么在get_word_num这个函数中，我们易知$n$用来统计，而$tag$正如其单词意思一样作为标记变量来看。这个for循环必然是用来遍历字符串，在for循环内，其退出条件必然是检索完字符串。第一个if是用来改变标记的，这里的意思也就是说遇到了空格就变为$1$。而空格是分隔单词的标志，所以如果我们下次遇到字母的时候是不是就相当于遇到了单词，同时我们要改变$tag$标记，等到下次遇到空格说明一个单词结束，这是$tag$也自然变为$1$。故此题易解。
  ASCII码小知识：$0$代表null，即为空；$10$代表换行符，$13$代表回车。

• 答案
  if(*p!=' '&&tag==1)

第二题

• 问题重现

  1/1 + 1/2 + 1/3 + 1/4 + … 在数学上称为调和级数。
  它是发散的，也就是说，只要加上足够多的项，就可以得到任意大的数字。
  但是，它发散的很慢：
  前1项和达到 1.0
  前4项和才超过 2.0
  前83项的和才超过 5.0
  那么，请你计算一下，要加多少项，才能使得和达到或超过 15.0 呢？
  请填写这个整数。
  注意：只需要填写一个整数，不要填写任何多余的内容。比如说明文字。

• 解题思路
  这题没有什么思维性，直接暴力求解即可。

• 代码

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大

void solve(){
    double sum=0;
    int cnt=0;
    while(sum<15.0){
        sum+=1.0/(double(cnt)+1.0);
        cnt++;
    }
    cout<<cnt<<endl;
}
int main(){
    solve();
    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

• 答案
  $1835421$

C组真题（第二题和B组第二题相同。第七题和A组第七题相同。）

题目结构

第一题

• 问题重现

  二项式的系数规律，我国数学家很早就发现了。
  如下图，我国南宋数学家杨辉1261年所著的《详解九章算法》一书里就出现了。
  
  如下的程序，用来建立N行的杨辉三角形。请填写划线部分缺少的代码。
  注意：只填写划线部分的代码，不要填写任何多余的内容。

#define N 8
int main()
{
	int a[N][N];
	int i,j;

	for(i=0; i<N; i++){
	a[i][0] = 1;
	a[i][i] = 1;
	}

	for(i=1; i<N; i++){
	for(j=1; j<i; j++) ___________________________;
	}

	for(i=0; i<N; i++){
	for(j=0; j<=i; j++)  printf("%-5d", a[i][j]);
	printf("\n");
}

	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

• 解题思路
  简单的杨辉三角规律，在直角三角形边上的元素全为$1$,其他的元素$a[i][j]$等于$a[i-1][j-1]+a[i-1][j]$。
• 答案

a[i][j]=a[i-1][j-1]+a[i-1][j]
1

第三题

• 问题重现

  有如下的加法算式。其中每个汉字代表一个数字。
  请填写“让我怎能过大年” 所代表的整数。
  所有数字连在一起，中间不要空格。例如：“3125697”。当然，这个不是正确的答案。
  注意：只填写一个整数，不要填写任何多余的内容。
  

• 解题思路
  这道题用数学推导特别麻烦且情况特别多的，所以我们可以暴力模拟让我怎能过大年这个数，看其是否满足这个条件。
• 代码

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大
int num[7];
bool check(int *num){
    sort(num,num+7);
    if(num[0]==num[1]||num[1]==num[2]||num[2]==num[3]||num[3]==num[4]||num[4]==num[5]||num[5]==num[6]){
        return false;
    }
    return true;
}
void solve(){
    rep(i,1000000,9999999){
       num[0]=i/1000000%10;
       num[1]=i/100000%10;
       num[2]=i/10000%10;
       num[3]=i/1000%10;
       num[4]=i/100%10;
       num[5]=i/10%10;
       num[6]=i%10;
       //判断是否满足相等。
       if((num[0]*1000000+num[1]*100000+num[2]*10000+num[3]*1000+num[4]*100+num[5]*10+num[6])+
          (num[1]*100000+num[2]*10000+num[3]*1000+num[4]*100+num[5]*10+num[6])+
          (num[2]*10000+num[3]*1000+num[4]*100+num[5]*10+num[6])+
          (num[3]*1000+num[4]*100+num[5]*10+num[6])+
          (num[4]*100+num[5]*10+num[6])+
          (num[5]*10+num[6])+
          (num[6])==
          (num[3]*1000000+num[3]*100000+num[3]*10000+num[3]*1000+num[3]*100+num[3]*10+num[3])){
            if(check(num)){
                cout<<i<<endl;
                break;
            }
          }
    }
}
int main(){
    solve();
    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

• 答案
  $1572836$

第四题

• 问题重现

  1193是个素数，对它循环移位后发现：
  1931,9311,3119也都是素数，这样特征的数叫：循环素数。
  你能找出具有这样特征的5位数的循环素数吗？
  当然，这样的数字可能有很多，请写出其中最大的一个。
  注意：答案是个5位数，不要填写任何多余的内容。

• 解题思路
  直接暴力求解，自己写一个判断素数的函数以及一个组合循环数的函数即可完成此题。注意要从大到小遍历。

• 代码

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大

bool isPrimer(int num){
    int temp=sqrt(num);
    rep(i,2,temp){
        if(num%i==0){
            return false;
        }
    }
    return true;
}
bool is_LoopPrimer(int num){
    int nums[5];
    nums[0]=num/10000;
    nums[1]=num/1000%10;
    nums[2]=num/100%10;
    nums[3]=num/10%10;
    nums[4]=num%10;
    if(isPrimer(nums[1]*10000+nums[2]*1000+nums[3]*100+nums[4]*10+nums[0])&&
       isPrimer(nums[2]*10000+nums[3]*1000+nums[4]*100+nums[0]*10+nums[1])&&
       isPrimer(nums[3]*10000+nums[4]*1000+nums[0]*100+nums[1]*10+nums[2])&&
       isPrimer(nums[4]*10000+nums[0]*1000+nums[1]*100+nums[2]*10+nums[3])){
        return true;
    }
    return false;
}
void solve(){
    //从大到小开始判断。
    per(i,99999,10000){
        if(isPrimer(i)){
            if(is_LoopPrimer(i)){
                cout<<i<<endl;
                break;
            }
        }
    }
}
int main(){
    solve();
    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

• 答案
  $99371$

第五题

• 问题重现

  把一个整数的每个数位都平方后求和，又得到一个整数，我们称这个整数为：位平方和。
  对新得到的整数仍然可以继续这一运算过程。
  比如，给定整数为4，则一系列的运算结果为：
  16,37,58,89,…
  本题的要求是，已知一个整数x，求第n步的运算结果。
  数据格式要求：
  输入，两个整数x n，中间以空格分开。表示求x的第n步位平方和。其中，x，y都大于0，且小于100000。
  输出，一个整数，表示所求结果。
  例如，
  输入：
  4 3
  则程序应该输出：
  58
  再例如，
  输入：
  1314 10
  则程序应该输出：
  20
  资源约定：
  峰值内存消耗 < 256M
  CPU消耗 < 1000ms
  注意：
  请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
  所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
  main函数需要返回0
  只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
  所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
  提交时，注意选择所期望的编译器类型。

• 解题思路
  题意非常明显，我们的关键在于实现位平方和功能，在取位方面，我们可以利用栈来存储最后再合成位平方和数。

• 代码

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大

stack<int> s;//用于存放整数的每一位。
int x,n;
void bit_pow(){
    while(!s.empty()){
        s.pop();
    }
    while(x!=0){
        s.push(x%10);
        x/=10;
    }
    int temp;
    while(!s.empty()){
        temp=s.top();
        s.pop();
        x+=temp*temp;
    }
}
void solve(){
    rep(i,1,n){
        bit_pow();
    }
    cout<<x<<endl;
}
int main(){
    while(cin>>x>>n){
        solve();
    }
    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

第六题

• 问题重现

  形如：1/a 的分数称为单位分数。可以把1分解为若干个互不相同的单位分数之和。
  例如：
  1 = 1/2 + 1/3 + 1/9 + 1/18
  1 = 1/2 + 1/3 + 1/10 + 1/15
  1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231
  等等，类似这样的分解无穷无尽。
  我们增加一个约束条件：最大的分母必须不超过30
  请你求出分解为n项时的所有不同分解法。
  数据格式要求：
  输入一个整数n，表示要分解为n项（n<12）
  输出分解后的单位分数项，中间用一个空格分开。
  每种分解法占用一行，行间的顺序按照分母从小到大排序。
  例如，
  输入：
  4
  程序应该输出：
  1/2 1/3 1/8 1/24
  1/2 1/3 1/9 1/18
  1/2 1/3 1/10 1/15
  1/2 1/4 1/5 1/20
  1/2 1/4 1/6 1/12
  再例如，
  输入：
  5
  程序应该输出：
  1/2 1/3 1/12 1/21 1/28
  1/2 1/4 1/6 1/21 1/28
  1/2 1/4 1/7 1/14 1/28
  1/2 1/4 1/8 1/12 1/24
  1/2 1/4 1/9 1/12 1/18
  1/2 1/4 1/10 1/12 1/15
  1/2 1/5 1/6 1/12 1/20
  1/3 1/4 1/5 1/6 1/20
  资源约定：
  峰值内存消耗 < 256M
  CPU消耗 < 2000ms
  请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
  所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
  注意: main函数需要返回0
  注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
  注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
  提交时，注意选择所期望的编译器类型。

• 解题思路
  首先，这道题本身其实是有问题的，因为并没有明确条件，以及分母是否可以为负。同时对一些无解的$n$，也没有加以排除。抛开这些，这道题还是比较好的，比较创新，也不像那种模板题。回归正题，我们来看，我们要寻找$n$个分数，它们的和为$1$（分数不相同）。所以这实际上是一道抽象的搜索题。我们采用dfs进行搜索，对于此题来说，如果我们找到了一个分数就将其存入数组（由于分数的分子都为$1$，故我们只需存取分母，当然我们在计算的时候也要保证分数是最简形式）。 最重要就是我们要找到初始状态和终止状态，由于我们是寻找$n$个分数，故我们易知初始状态为$1$，终止状态为$n$。这个状态表示的是我们正在寻找的分数。为了避免重复杂乱，所以我们搜索分数的分母也是从小到大，同样，我们也要时刻记录每个状态剩余的值。所以我们实现的dfs有四个参数。 具体看代码，附有详细解释。
• 代码

/*
*blog:https://blog.csdn.net/hzf0701
*邮箱：unique_powerhouse@qq.com
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)

using namespace std;

typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大

int n,a[31];//n表示需要分解的分数，a[i]表示第i个分数的分母。
//gcd,便于分母之间相加运算，约分。
int gcd(int n,int m){
    int temp;
    while(n%m){
        temp=n%m;
        n=m;
        m=temp;
    }
    return m;
}
//dfs搜索
void dfs(int cur,int minn,int fz,int fm){
    //参数解释，cur代表当前填写的是第cur个分数，minn表示能填写的最小分母，
    //fz/fm表示当前剩余的值。

    if(n==cur){
        //说明我们已经填写到最后一个了，而fz/fm就是剩下的，
        //接下来我们要判断是否符合。
        if(fm%fz){
            //说明fz不为1或者fm=fz，这样都是不符合题意的。
            return;
        }
        a[n] =fm/fz;
        if(a[n]>30){
            //由于我们填分母是从小到大的，故最后一个的分母是最大的，我们只需要判断它是否越界即可。
            return;
        }
        //打印。
        rep(i,1,n-1){
            cout<<"1/"<<a[i]<<" ";
        }
        cout<<"1/"<<a[n]<<endl;
        return;
    }
    //当前填写的是第cur个，我们必须要确定它所能填写的最小分母。这里要设置max以避免打印相同的结果。
    minn=max(minn,fm/fz+1);

    //确定好了之后，我们开始搜索。
    for(int i=minn;;i++){
        //我们要与当前还没有填写的分数数与可剩余的做比较，如果fz/fm>=(n-cur+1)/i，即说明以当前分母没办法填完剩余的值。
        //相等排除是因为不能有重复分数。
        if(fz*i>=(n-cur+1)*fm){
            break;
        }
        //此时就填写。
        a[cur]=i;
        //fz/fm-1/i。
        int temp1,temp2,temp3;
        //注意这里不能真的更改fz和fm，如果更改了，会影响接下里for循环里的结果。
        temp1=gcd(fz,fm);
        temp2=fz*i-fm;
        temp3=fm*i;
        dfs(cur+1,i+1,temp2/temp1,temp3/temp1);
    }
    return;
}
void solve(){
    memset(a,1,sizeof(a));
    dfs(1,2,1,1);
}
int main(){
    while(cin>>n){
        solve();
    }
    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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84