蓝桥杯15届B组题解
蓝桥杯15届B组省赛题解（一）
好数
题目描述
一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位 · · · ）上的数字是奇数，偶数位（十位、千位、十万位 · · · ）上的数字是偶数，我们就称之为“好数”。给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。
输入格式
一个整数 N。
输出格式
一个整数代表答案。
样例输入
24
样例输出
7
解题思路
判断从 1 到 n 的每一个数是否为好数。 它的个位百位万位要为奇数 它的十位千位十万位要为偶数 判断从1到n的每一个数是否为好数。\\ 它的个位百位万位要为奇数\\ 它的十位千位十万位要为偶数 判断从1到n的每一个数是否为好数。它的个位百位万位要为奇数它的十位千位十万位要为偶数
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int sum=0;
//从1到n进行遍历
for(int i=1;i<=n;i++)
{
//找到不符合好数的条件
bool find =false;
int t = i;
int cnt=1;
while(t>0)
{
//偶数奇数，轮流检测 ，0，1，0
cnt=1-cnt;
//1表示是奇数，2表示偶数
int re = t%2;
//从低位一位一位进行的检测
t/=10;
if((!cnt&&re)||(cnt&&!re))
{
}
else
{
find =true;
break;
}
}
if(!find)
{
sum++;
}
}
cout<<sum;
}
R 格式
题目描述
小蓝最近在研究一种浮点数的表示方法：R 格式。对于一个大于 0 的浮点数 d，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R格式整数的做法是：
-
将浮点数乘以 2n;
-
四舍五入到最接近的整数。
输入格式
一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮点数。
输出格式
输出一行表示答案：d 用 R 格式表示出来的值。
样例输入
2 3.14
样例输出
13
做题思路
由于1 ≤ n ≤ 1000
1<=d<=1024
n
个
2
相乘，可以暂定
2
3
=
8
<
=
10
,
可以理解为
1000
/
3
=
333
个
10
相乘得到的位数显然
d
o
u
b
l
e
是无法满足这么大的位数的
,
这时候就要考虑大数处理。
用个
i
n
t
[
4000
]
的数组
a
表示每个位即可。
n个2相乘，可以暂定2^3=8<=10,可以理解为1000/3=333个10\\相乘得到的位数 显然double是无法满足这么大的位数的,这时候就要考虑大数处理。\\用个int[4000]的数组a表示每个位即可。
n个2相乘，可以暂定23=8<=10,可以理解为1000/3=333个10相乘得到的位数显然double是无法满足这么大的位数的,这时候就要考虑大数处理。用个int[4000]的数组a表示每个位即可。
大数的运算，一般是从小位到高位依次进行运算。
为了方便运算，将d当作字符串进行读入，并对它进行处理，先反转，方便从小位拿到高位。
再把"."的索引（假设它的位置为pos）拿到，并将它删除（方便进行运算）
然后就将字符串从低位到高位按照低位到高位一个个存储进数组a中
遍历n次
{
对每个位进行*2操作
从低位到高位依次检查是否要进位。
}
原始数据1.23
翻转32.1
.的索引位置是2
处理后321
因为我是将数组按照1-n,从个位到高位依次存储,显然此时索引位置对应着2。【代码使用这种】
如果我是将数组按照0-n,从个位到高位依次存储,显然此时索引位置对应着1。
索引位置就是判断是否要进位的位置。
最后进行四舍五入操作后。
从高位依次输出到小数点位前面一位即可。
提示
【样例说明】
3.14 × 22 = 12.56，四舍五入后为 13。
【评测用例规模与约定】
对于 50% 的评测用例：1 ≤ n ≤ 10，1 ≤ 将 d 视为字符串时的长度 ≤ 15。
对于 100% 的评测用例：1 ≤ n ≤ 1000，1 ≤ 将 d 视为字符串时的长度≤ 1024；保证 d 是小数，即包含小数点。
#include <bits/stdc++.h>
using namespace std;
const int N= 2e3+10;
int a[N] ;
int main()
{
//对数据进行预处理
int n;
string s;
cin>>n>>s;
reverse(s.begin(),s.end());
int pos = s.find(".");
s.erase(pos,1);
int l = s.length();
for(int i=0;i<l;i++) a[i+1]=s[i]-'0';
//进行2的n的幂次运算
for(int i=0;i<n;i++)
{
for(int j=1;j<=l;j++) a[j]*=2;
for(int j=1;j<=l;j++)
{
if(a[j]>=10)
{
a[j+1]++;
a[j]%=10;
if(j==l)l++;
}
}
}
//进行四舍五入运算
if(a[pos]>=5)a[pos+1] ++;
for(int j=pos+1;j<=l;j++)
{
if(a[j]>=10)
{
a[j+1]++;
a[j]%=10;
if(j==l)l++;
}
}
for(int i=l;i>=pos+1;i--) cout<<a[i] ;
return 0;
}
宝石组合
题目描述
在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 Hi，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美程度 S 可以用以下公式来衡量：
其中 LCM 表示的是最小公倍数函数。小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 S 值相同，优先选择按照 H 值升序排列后字典序最小的方案。
输入格式
第一行包含一个整数 N 表示宝石个数。第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。
输出格式
输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。
样例输入
5
1 2 3 4 9
样例输出
1 2 3
提示
【评测用例规模与约定】
对于 30% 的评测用例：3 ≤ N ≤ 100，1 ≤ Hi ≤ 1000。
对于 60% 的评测用例：3 ≤ N ≤ 2000。
对于 100% 的评测用例：3 ≤ N ≤ 105，1 ≤ Hi ≤ 105。
解题思路
根据整数唯一分解定理，可以把这目标的三个数分解成若干个素数的乘积。找公倍数实则就是从这几个数的，相同素数的幂次的最大值。
例如
4
=
2
2
,
而
6
=
2
1
1
∗
3
1
那么它们的公倍数就是
2
2
∗
3
1
=
12
例如4=2^2,而6=2^11*3^1\\ 那么它们的公倍数就是2^2*3^1=12
例如4=22,而6=211∗31那么它们的公倍数就是22∗31=12
就可以把题目所要求的条件理解为,对于某个构成这三个数共同的素数p
相同素数相乘幂就是+，向除，幂就是-
p
a
+
p
b
+
p
c
+
M
a
x
(
P
a
,
p
c
,
p
b
)
−
M
a
x
(
p
a
,
b
)
−
M
a
x
(
p
a
,
p
c
)
−
M
a
x
(
p
b
,
p
c
)
p_a+p_b+p_c+Max(P_a,p_c,p_b)-Max(p_a,_b)-Max(p_a,p_c)-Max(p_b,p_c)
pa+pb+pc+Max(Pa,pc,pb)−Max(pa,b)−Max(pa,pc)−Max(pb,pc)
根据上面的式子，为了它的值更大，希望要更p大的，Max(a,b,c)更大的。
提示分析
H i < = 1 0 5 , 意味着，只需要把小于或等于 1 0 5 的数的因式找到就行 H^i<=10^5,意味着，只需要把小于或等于10^5的数的因式找到就行 Hi<=105,意味着，只需要把小于或等于105的数的因式找到就行
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector< vector<int> > a(N,vector<int>());
int main()
{
//首先把构成某个数的因式全部提取出来
for(int i=1;i<=N;i++)
{
for(int j=i;j<=N;j+=i)
{
a[j].push_back(i);
}
}
int n;
cin>>n;
vector<int> b(n);
vector< vector<int> > mxb(N,vector<int>());
for(int i=0;i<n;i++) cin>>b[i];
//先进行排序，保证字典序
sort(b.begin(),b.end());
//从小数到大数依次将包含这个因式的数存入该因数
for(auto c:b)
{
for(auto ct:a[c])
{
mxb[ct].push_back(c);
}
}
//从大因数，到小因数，若满足有三个数同时拥有它，这三个数就是希望要找的三个数
for(int i=1e5;i>0;i--)
{
if(mxb[i].size()>2)
{
for(int j=0;j<3;j++)
cout<<mxb[i][j]<<" ";
return 0; // 直接结束程序
}
}
}