题目A 组队
【问题描述】
作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员， 组成球队的首发阵容。 每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1 号位至 5 号位的评分之和最大可能是多少？
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LqxJI2WQ-1645677075334)(C:\Users\Sorakun\AppData\Roaming\Typora\typora-user-images\image-20220221211858554.png)]
解：
我的做法是找出每一列的最大值然后加起来，答案是492。然后就错了！！！
492答案对应如下方案：
1号位 17号；2号位 20号；3号位 17号；4号位 17号；5号位 18号
不行的原因是每个人只能担任一个位置，这里的17号重复了3次
正确答案一共有三种，因为17号同时拥有三个位置的最大值，认选一种。答案应该是490
题B 年号字符
【问题描述】
小明用字母 A 对应数字 1，B 对应 2，以此类推，用 Z 对应 26。对于 27 以上的数字，小明用两位或更长位的字符串来对应，例如 AA 对应 27，AB 对 应 28，AZ 对应 52，LQ 对应 329。 请问 2019 对应的字符串是什么？
解：
以为就是很普通的10进制转26进制，结果我反应半天也没搞出来，网上一些答案的代码也是错的（只是刚好2019对应的是对）
正确的代码如下：
#include<iostream>
using namespace std;
void resolve(int p){
if(p>0){
if(p%26 == 0){
//如果可以整除 说明是Z
resolve((p-26)/26);
cout<<"Z";
}
else{//如果不能整除，模26的结果对应着是第几个字母
resolve(p/26);
cout<<char('A'+(p%26-1));
}
}
}
int main()
{
int p;
cin>>p;
resolve(p);
}
正确答案是：BYQ
题C 数列求值
【问题描述】
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求 第 20190324 项的最后 4 位数字。
解：
好不容易终于做对一道。
这么大的数，肯定超出long long了，不过这里也没必要使用高精度。这明显是斐波那契数列的变形，每一次求和对10000取模再进行下一步运算，这样每一步都取10000的模不会对结果造成影响。
计算使用的代码如下：
#include<iostream>
using namespace std;
int main()
{
int a,b,c;
a=1,b=1,c=1;
int ans;
int n;
cin>>n;
n=n-3;
while(n--){
ans=(a+b+c)%10000;
a=b;
b=c;
c=ans;
}
cout<<ans;
}
题D 数的分解
【问题描述】
把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包 含数字 2 和 4，一共有多少种不同的分解方法？ 注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和 1001+1000+18 被视为同一种。
解：
又做错了，做的太麻烦。
很显然就是多重循环枚举出来判断，但在枚举的过程中需要考虑如何尽可能地减少枚举的次数，由此：
-
假设枚举出来的三个数i,j,k始终满足i<j<k,避免重复枚举 -
i从1开始枚举到673结束，i是最小的，所以必须小于2019的三分之一 -
j从i+1开始枚举，到（2019-i)/2，这样保证k是比j大的 -
k直接用2019-i-j计算出来 -
得到三个数后判断是否满足要求，如果满足则次数+1
代码：
#include <iostream>
#include <cstdio>
using namespace std;
int ans = 0;
int is_24(int x) {
while (x) {
int t = x % 10;
if (t == 2 || t == 4)
return 1;
x /= 10;
}
return 0;
}
int main() {
for (int i = 1; i <= 673; i++)
for (int j = i + 1; j <= (2019 - i) / 2; j++) {
int k = 2019 - i - j;
if (i < j && j < k && !is_24(i) && !is_24(j) && !is_24(k)) {
//cout << i << ' ' << j << ' ' << k << endl;
ans++;
}
}
cout << ans << endl;
return 0;
}
题E 迷宫
【问题描述】
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。
解：
因为权重为0和1，所以可以直接用bfs搜出来。
当队伍非空，或者找到答案时，循环截止。每次从队首出队，分别从 下、上、左、右 进行扩展，注意要使用 vis 数组记录是否已经访问过了，还要记录更新结点遇到的方向。
code：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=35;
const int M=55;
char mi[N][M];
int visit[N][M];
int path[N][M];
int dx[]={1,0,0,-1};
int dy[]={0,-1,1,0};
string ss="DLRU";
string ans="";
void bfs(){
queue<PII> q;
visit[0][0]=1;
q.push({0,0});
while(!q.empty()){
PII p=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=p.first+dx[i],y=p.second+dy[i];
if(x>=0&&x<30&&y>=0&&y<50&&!visit[x][y]&&mi[x][y]=='0'){
visit[x][y]=1;
q.push({x,y});
path[x][y]=i;
}
}
}
int x=29,y=49;
while(x!=0||y!=0){
char k=path[x][y];
ans=ss[k]+ans;
x=x-dx[k];
y=y-dy[k];
}
}
int main() {
for(int i=0;i<30;i++){
cin>>mi[i];
}
bfs();
cout<<ans;
}
//01010101001011001001010110010110100100001000101010
//00001000100000101010010000100000001001100110100101
//01111011010010001000001101001011100011000000010000
//01000000001010100011010000101000001010101011001011
//00011111000000101000010010100010100000101100000000
//11001000110101000010101100011010011010101011110111
//00011011010101001001001010000001000101001110000000
//10100000101000100110101010111110011000010000111010
//00111000001010100001100010000001000101001100001001
//11000110100001110010001001010101010101010001101000
//00010000100100000101001010101110100010101010000101
//11100100101001001000010000010101010100100100010100
//00000010000000101011001111010001100000101010100011
//10101010011100001000011000010110011110110100001000
//10101010100001101010100101000010100000111011101001
//10000000101100010000101100101101001011100000000100
//10101001000000010100100001000100000100011110101001
//00101001010101101001010100011010101101110000110101
//11001010000100001100000010100101000001000111000010
//00001000110000110101101000000100101001001000011101
//10100101000101000000001110110010110101101010100001
//00101000010000110101010000100010001001000100010101
//10100001000110010001000010101001010101011111010010
//00000100101000000110010100101001000001000000000010
//11010000001001110111001001000011101001011011101000
//00000110100010001000100000001000011101000000110011
//10101000101000100010001111100010101001010000001000
//10000010100101001010110000000100101010001011101000
//0011110000100001000000011011100000001000000001011
//10000001100111010111010001000110111010101101111000
因为权重是0和1，所以可以直接用bfs，这里不是求最短路径长度，而是求路径，其实也就相当于把原来求最短路径的代码里，更新路径长度的代码改成更新如何到达当前点。
试题 F: 特别数的和
【问题描述】
小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到
40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
code：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
bool judge(int a){
while(a>=1){
int yu=a%10;
if(yu==2||yu==0||yu==1||yu==9){
return true;
}
a=a/10;
}
return false;
}
int main()
{
int n;
ll sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
if(judge(i)) sum+=i;
}
printf("%d",sum);
}
很简单的一道送分题，直接遍历把答案加起来就行，注意使用longlong
试题 G: 完全二叉树的权值
【问题描述】
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从
上到下、从左到右的顺序依次是 A1, A2, · · · A**N。
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点
权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
code:
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n,maxnum=-350000000,maxlayer,cnt=0,flag=0;
cin>>n;
for(int layer = 0; ;layer++){//枚举每一层（1<<layer 就是2^layer）
long long sum=0,a;
for(int i=0;i<(1<<layer);i++){
cin>>a;
sum += a;
if(++cnt>=n){//结束
flag=1;
break;
}
}
if(sum>maxnum)
maxnum = sum, maxlayer = layer + 1;
if(flag)
break;
}
cout<<maxlayer;
return 0;
}
依次遍历每一层，找出权重和最大的那一层即可，由完全二叉树的公式可以知道每一层有多少个结点。
试题 H: 等差数列
【问题描述】
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一
部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有
几项？
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a, int b){
return b==0 ? a : gcd(b,a%b);
}
int a[100005],n,ans;
int main() {
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
ans=a[1]-a[0];
for(int i=2 ;i<n; i++)
ans=gcd(ans,a[i]-a[i-1]);//公差即为最大公约数
if(a[n-1]-a[0] == 0)//公差为0
cout << n;
else
cout<<(a[n-1]-a[0])/ans+1;//项数
return 0;
}
核心点是，这些数的最大公约数就是他们的公差。
试题 I: 后缀表达式
【问题描述】
给定 N 个加号、M 个减号以及 N + M + 1 个整数 A1, A2, · · · , A**N+M+1，小
明想知道在所有由这 N 个加号、M 个减号以及 N + M + 1 个整数凑出的合法的
后缀表达式中，结果最大的是哪一个？
请你输出这个最大的结果。
例如使用1 2 3 + -，则 “2 3 + 1 -” 这个后缀表达式结果是 4，是最大的。
CODE:
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[200005],n,m;
int main(){
cin>>n>>m;
ll ans=0;
ll minnum=100000000;
bool flagp=true,flagm=true;
for(int i=0 ; i< n + m + 1;i++){//参与计算的数
cin>>a[i];
if(!m)//如果没有减号
ans+=a[i];//就是全部加起来
else{
if(a[i]<0) flagp=false;
if(a[i]>0) flagm=false;
if(abs(a[i])<minnum) minnum =abs(a[i]);
ans += abs(a[i]);
}
}
if(m&&(flagp||flagm))//有减号，全部是正数或者负数
ans=ans-minnum-minnum;
cout<<ans;
}
分为 如下几种情况：
-
如果全部是加号，那么直接把所有数加起来 -
当有减号的时候： a. 如果全部是正数，那么至少需要减一个数，就减最小的那个数（其它的数都可以负负得正） b. 如果有正有负，可以转化成所有数的绝对值的和。 c.如果全部是负数，除一个数以外其它全部都可以翻成正数。和情况a一致
|