题目结构
| 题目 | 类型 | 分值 |
|---|---|---|
| 第一题 | 结果填空 | 15分 |
| 第二题 | 结果填空 | 31分 |
| 第三题 | 代码填空 | 21分 |
| 第四题 | 程序设计 | 47分 |
| 第五题 | 程序设计 | 79分 |
| 第六题 | 程序设计 | 107分 |
第一题 哥德巴赫分解
-
问题描述
哥德巴赫猜想认为：不小于4的偶数都可以表示为两个素数的和。
你不需要去证明这个定理，但可以通过计算机对有限数量的偶数进行分解，验证是否可行。
实际上，一般一个偶数会有多种不同的分解方案，我们关心包含较小素数的那个方案。
对于给定数值范围，我们想知道这些包含较小素数方案中最大的素数是多少。
比如，100以内，这个数是19，它由98的分解贡献。
你需要求的是10000以内，这个数是多少？输出
输出一个整数表示答案
-
解题思路
首先我们需要用埃氏筛筛选出 10000 10000 10000以内的素数，然后按题意从小到大枚举其中的一个素数，然后利用差来确定另一个值是否是素数即可。需要注意的就是要保存较小素数方案中的最大素数。
-
代码
/**
*@filename:哥德巴赫分解
*@author: pursuit
*@csdn:unique_pursuit
*@email: 2825841950@qq.com
*@created: 2021-04-30 13:57
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10000 + 5;
const int mod = 1e9+7;
int isprimer[maxn],primer[maxn];
int ans=0;
void init(){
memset(isprimer,true,sizeof(isprimer));
for(int i=2;i<10000;i++){
if(isprimer[i]){
primer[++primer[0]]=i;
for(int j=i+i;j<10000;j+=i){
isprimer[j]=false;
}
}
}
}
void cal(int x){
for(int i=1;i<=primer[0];i++){
int t=x-primer[i];
if(t>0&&isprimer[t]){
ans=max(ans,primer[i]);
return;
}
}
}
void solve(){
init();
for(int i=4;i<10000;i+=2)cal(i);
cout<<ans<<endl;//173
}
int main(){
solve();
return 0;
}
-
答案
173 173 173
第二题 数字划分
-
问题描述
w星球的长老交给小明一个任务：1,2,3…16 这16个数字分为两组。
要求：这两组数字的和相同，并且，两组数字的平方和也相同，并且，两组数字的立方和也相同。
请你利用计算机的强大搜索能力解决这个问题。
并提交1所在的那个分组的所有数字。
这些数字要从小到大排列，两个数字间用一个空格分开。
即类似：1 4 5 8 … 这样的答案。输出
按格式输出答案
提示
笨笨有话说：只要一个组的成员确定了，另一个组的成员也就确定了。枚举一个组的成员就可以了。
凭直觉，两个组的成员数目不会差太多吧。
歪歪有话说：既然求 1 所在的那个组，那只要枚举剩余的成员就可以了。
貌似都是8个成员的可能性很大啊。 -
解题思路
d f s dfs dfs枚举，理清题意即可。
-
代码
/**
*@filename:数字划分
*@author: pursuit
*@csdn:unique_pursuit
*@email: 2825841950@qq.com
*@created: 2021-05-07 18:46
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;
//先将所有数的和、平方和、立方和求出来，再枚举判断即可。
int ans1,ans2,ans3,result;
bool vis[20];
vector<int> a(1,1);//存储结果数组。
void dfs(int cur,int s1,int s2,int s3){
//当前填写的数下限，s1为当前的和，s2为当前的平方和，s3为当前的立方和。
if(s1*2>ans1||s2*2>ans2||s3*2>ans3)return;
if(s1*2==ans1&&s2*2==ans2&&s3*2==ans3){
for(int i=0;i<a.size();i++){
//1 4 6 7 10 11 13 16
cout<<a[i]<<" ";
}
cout<<endl;
result++;
}
for(int i=cur;i<=16;i++){
if(!vis[i]){
vis[i]=true;
a.push_back(i);
dfs(i+1,s1+i,s2+i*i,s3+i*i*i);
vis[i]=false;
a.pop_back();
}
}
//cout<<s1<<" "<<s2<<" "<<s3<<endl;
}
void solve(){
//dfs枚举。当大于和的一般的时候立即退出。
dfs(2,1,1,1);
cout<<result<<endl;
}
int main(){
for(int i=1;i<=16;i++){
ans1+=i;
ans2+=i*i;
ans3+=i*i*i;
}
solve();
return 0;
}
-
答案
1 4 6 7 10 11 13 16
第三题 表达式计算
- 问题描述
虽然我们学了许久的程序设计，但对于简单的四则混合运算式，如果让我们完全白手起家地编程来解析，还是有点棘手。
这里，我们简化一下问题，假设只有加法和乘法，并且没有括号来改变优先级。
再假设参加运算的都是正整数。在这么多的限制条件下，表达式的解析似乎简单了许多。
下面的代码解决了这个问题。请仔细阅读源码，并填写划线部分缺少的代码。#include <stdio.h> int f3(const char* s, int begin, int end) { int sum = 0; int i; for(i=begin; i<end; i++){ if(s[i]==' ') continue; sum = sum * 10 + (s[i]-'0'); } return sum; } int f2(const char* s, int begin, int end) { //这一步实际上就是累加，需要注意的就是是否有乘号。 int p = begin; int pro = 1;//pro实际上就是存储乘法结果。那么我们需要知道的就是f3是字符串转化函数。 while(1){ int p0 = p; while(p!=end && s[p]!='*') p++; //pro *= _______________________________; //填空 //得到的p0~p就是数值。 pro *=f3(s,p0,p); //填空 if(p==end) break; p++; } printf("f2: pro=%d\n", pro); return pro; } int f(const char* s) { //f函数中的参数即为表达式。只有加法和乘法。 int p = 0; int sum = 0; while(1){ int p0 = p; while(s[p]!=0 && s[p]!='+') p++;//这里的p0是起始位置，p则是结束位置，寻找的则是加号。 sum += f2(s,p0,p);//这里计算加号左边的值。 if(s[p]==0) break; p++; } return sum; } int main() { int x = f("12+18+5*4*3+10"); printf("%d\n", x); return 0; }
-
解题思路
已贴详细注释于上述代码中。
-
答案
f3(s,p0,p)
第四题 小数第n位
-
问题描述
我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。
本题的任务是：在上面的约定下，求整数除法小数点后的第n位开始的3位数输入
输出存在多组测试数据，对于每组测试数据：
输入一行包含三个整数：a b n，用空格分开。a是被除数，b是除数，n是所求的小数后位置
0 < a , b , n < 1000000000 0<a,b,n<1000000000 0<a,b,n<1000000000输出
对于每组测试数据：输出3位数字，表示：a除以b，小数后第n位开始的3位数字。
样例输入
1 8 1 1 8 3 282866 999000 6样例输出
125 500 914 -
解题思路
利用竖式除法的思想去处理这道题，特殊的就是我们需要取出当前的小数，这种我们可以通过 × 10 \times 10 ×10来得到，我们用数组存储小数，存储的方式就是不断进位。 那么需要注意的是，小数分为有限小数，无限循环小数，无限不循环小数。其中无限循环小数我们如果找到了循环节，那么就可以得出结果了，而若是有限小数，同样简单。关键是在于无限不循环小数，我们需要先处理前 n − 1 n-1 n−1个小数，最后输出后三位小数即可。具体看代码。
-
代码
/**
*@filename:小数第n位
*@author: pursuit
*@csdn:unique_pursuit
*@email: 2825841950@qq.com
*@created: 2021-05-07 19:33
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100 + 5;
const int mod = 1e9+7;
//此题我们可以用数组来存储小数，存储的方法是不断进位。小数分为有限小数，无限循环小数，无限不循环小数。
int sz[maxn];//用于存储小数。
int bcs,cs,n;
//先判断是什么类型的。
void work(){
int rem=bcs,cnt=0;
do{
sz[cnt++]=10*rem/cs;
rem=rem*10%cs;
}while(rem!=bcs&&rem!=0&&cnt<maxn);
if(rem==0){
//有限小数。输出小数点后的第n为开始的3个数。
printf("%d%d%d\n",sz[n],sz[n+1],sz[n+2]);
}
else if(rem==bcs){
//无限循环小数，循环节为cnt。
printf("%d%d%d\n",sz[n%cnt],sz[(n+1)%cnt],sz[(n+2)%cnt]);
}
else{
//无限小数。
while(n--){
bcs=bcs*10%cs;
}
for(int i=0;i<3;i++){
printf("%d",bcs*10/cs);
bcs=bcs*10%cs;
}
printf("\n");
}
}
void solve(){
bcs%=cs;
n--;
work();
}
int main(){
scanf("%d%d%d",&bcs,&cs,&n);
solve();
return 0;
}
第五题 分考场
-
问题描述
n个人参加某项特殊考试。
为了公平，要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。输入
第一行，一个整数n(1<n<100)，表示参加考试的人数。
第二行，一个整数m，表示接下来有m行数据
以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识（编号从1开始）。输出
一行一个整数，表示最少分几个考场。
样例输入
5 8 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5样例输出
4 -
解题思路
相当于无向图的染色问题。处理这道题我们首先要建立几个辅助数组: g [ i ] [ j ] g[i][j] g[i][j],参考人员 i i i和 j j j的关系，若为 1 1 1则认识，反之不认识。 f [ i ] [ j ] f[i][j] f[i][j]，第 i i i个考场第 j j j个人的编号，这个数组辅助我们判断第 i i i个考场能不能加入一个新参考人员。 c n t [ i ] cnt[i] cnt[i]，第 i i i个考场的人数。 那么我们利用 d f s dfs dfs枚举每个参考人员的放置情况，即新开一个考场或者加入已有的考场，而加入已有的考场的前提条件就是该人不能与现有考场中的人认识，按照这思想去进行即可。
-
代码
/**
*@filename:分考场
*@author: pursuit
*@csdn:unique_pursuit
*@email: 2825841950@qq.com
*@created: 2021-05-07 20:12
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100 + 5;
const int mod = 1e9+7;
int n,m,u,v;
int g[maxn][maxn];//参考人员的关系。
int f[maxn][maxn],cnt[maxn];//f[i][j]表示第i个考场第j个人的编号。cnt[i]表示的是第i个考场的人数。
int minn=maxn;
void dfs(int idx,int ans){
//idx为当前正在排的人，ans则为有ans个考场。
if(ans>=minn)return;//剪枝。
if(idx==n+1){
//说明前n个人已经排完了。
minn=min(ans,minn);
return;
}
//开始为这idx分考场。
for(int i=1;i<=ans;i++){
int len=cnt[i];//获得该考场的人数。
bool flag=false;
for(int j=1;j<=len;j++){
if(g[idx][f[i][j]]){
//说明认识，我们不能放入该考场。
flag=true;
break;
}
}
if(!flag){
//说明可以放入该考场。
f[i][++cnt[i]]=idx;
dfs(idx+1,ans);
cnt[i]--;//回溯。
}
}
f[ans+1][++cnt[ans+1]]=idx;
dfs(idx+1,ans+1);
cnt[ans+1]--;//回溯。
}
void solve(){
dfs(1,0);
cout<<minn<<endl;
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>u>>v;
g[u][v]=g[v][u]=1;//代表有关联。
}
solve();
return 0;
}
第六题 合根植物
-
问题描述
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？输入
第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：5 * 4 的小格子，编号：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20输出
输出一个整数表示答案
样例输入
5 4 16 2 3 1 5 5 9 4 8 7 8 9 10 10 11 11 12 10 14 12 16 14 18 17 18 15 19 19 20 9 13 13 17样例输出
5提示
-
解题思路
呃呃呃，这题放第六题未免有点不太合适，并查集模板题，累计有多少独立的集合即可。
-
代码
/**
*@filename:合根植物
*@author: pursuit
*@csdn:unique_pursuit
*@email: 2825841950@qq.com
*@created: 2021-05-07 20:38
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000000 + 5;
const int mod = 1e9+7;
int n,m,k,father[maxn];
int u,v;
void solve(){
}
int find(int x){
int r=x;
while(r!=father[r])r=father[r];
int i=x,j;
while(father[i]!=r){
j=father[i];
father[i]=r;
i=j;
}
return r;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n*m;i++)father[i]=i;
for(int i=1;i<=k;i++){
cin>>u>>v;
u=find(u),v=find(v);
if(u!=v){
father[u]=v;
}
}
int cnt=0;
for(int i=1;i<=n*m;i++){
if(father[i]==i)cnt++;
}
cout<<cnt<<endl;
solve();
return 0;
}
转载：https://blog.csdn.net/hzf0701/article/details/116503310