蓝桥杯15届B组题解

蓝桥杯15届B组省赛题解（一）

好数

标题描述

一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位 · · · ）上的数字是奇数，偶数位（十位、千位、十万位 · · · ）上的数字是偶数，我们就称之为“好数”。给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。
输入格式

一个整数 N。
输特别式

一个整数代表答案。
样例输入

1. 24

复制代码

样例输出

1. 7

复制代码

解题思路

                                         判断从                            1                            到                            n                            的每一个数是否为好数。                                     它的个位百位万位要为奇数                                     它的十位千位十万位要为偶数                                  判断从1到n的每一个数是否为好数。\\ 它的个位百位万位要为奇数\\ 它的十位千位十万位要为偶数                     判断从1到n的每一个数是否为好数。它的个位百位万位要为奇数它的十位千位十万位要为偶数

1. #include<bits/stdc++.h>
2. using namespace std;
4. int main()
5. {
6.         int n;
7.         cin>>n;
8.         int sum=0;
9.     //从1到n进行遍历
10.         for(int i=1;i<=n;i++)
11.         {
12.         //找到不符合好数的条件
13.                 bool find =false;
14.                 int t = i;
15.                 int cnt=1;
16.                 while(t>0)
17.                 {
18.             //偶数奇数，轮流检测 ，0，1，0
19.                         cnt=1-cnt;
20.            
21.             //1表示是奇数，2表示偶数
22.                         int re = t%2;
23.             //从低位一位一位进行的检测
24.                         t/=10;
25.                         if((!cnt&&re)||(cnt&&!re))
26.                         {
27.                                
28.                         }
29.                         else
30.                         {
31.                                 find =true;
32.                                 break;
33.                         }
35.                 }
36.                 if(!find)
37.                 {
38.                         sum++;
39.                 }
40.         }
41.         cout<<sum;
42. }

复制代码

R 格式

标题描述

小蓝近来在研究一种浮点数的表示方法：R 格式。对于一个大于 0 的浮点数 d，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R格式整数的做法是：

• 将浮点数乘以 2n;
  
• 四舍五入到最接近的整数。
  

输入格式

一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮点数。
输特别式

输出一行表示答案：d 用 R 格式表示出来的值。
样例输入

1. 2 3.14

复制代码

样例输出

1. 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中

1. 遍历n次
3. {
5. ​        对每个位进行*2操作
7. ​        从低位到高位依次检查是否要进位。
9. }

复制代码

原始数据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 是小数，即包含小数点。

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N= 2e3+10;
4. int a[N] ;
5. int main()
6. {
7.   //对数据进行预处理
8.   int n;
9.   string s;
10.   cin>>n>>s;
11.   reverse(s.begin(),s.end());
12.   int pos = s.find(".");
13.   s.erase(pos,1);
14.   int l = s.length();
15.   for(int i=0;i<l;i++) a[i+1]=s[i]-'0';
16.   //进行2的n的幂次运算
17.   for(int i=0;i<n;i++)
18.   {
19.           for(int j=1;j<=l;j++) a[j]*=2;
20.           for(int j=1;j<=l;j++)
21.           {
22.                   if(a[j]>=10)       
23.                   {
24.                           a[j+1]++;
25.                         a[j]%=10;
26.                         if(j==l)l++;
27.                 }
28.         }
29.   }
30.   //进行四舍五入运算
31.   if(a[pos]>=5)a[pos+1] ++;
32.   for(int j=pos+1;j<=l;j++)
33.           {
34.                   if(a[j]>=10)       
35.                   {
36.                           a[j+1]++;
37.                         a[j]%=10;
38.                         if(j==l)l++;
39.                 }
40.         }
41.   for(int i=l;i>=pos+1;i--) cout<<a[i] ;
43.   return 0;
44. }

复制代码

宝石组合

标题描述

在一个神秘的丛林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐蔽在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和外形，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特别本领，可以发出不同强度的闪光。小蓝共找到了N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 Hi，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美水平 S 可以用以下公式来权衡：

[img]https://i-blog.csdnimg.cn/direct/d2bad213
0d35425da4b3e31ac7
4fbdf3.png[/img]

其中 LCM 表示的是最小公倍数函数。小蓝想要使得三枚宝石组合后的精美水平 S 尽可能的高，请你帮他找出精美水平最高的方案。如果存在多个方案 S 值雷同，优先选择按照 H 值升序排列后字典序最小的方案。
输入格式

第一行包含一个整数 N 表示宝石个数。第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。
输特别式

输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。
样例输入

1. 5
2. 1 2 3
3. 4 9

复制代码

样例输出

1. 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的数的因式找到就行

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N = 1e5+10;
5. vector< vector<int> > a(N,vector<int>());
6. int main()
7. {
8.     //首先把构成某个数的因式全部提取出来
9.     for(int i=1;i<=N;i++)
10.     {
11.         for(int j=i;j<=N;j+=i)
12.         {
13.             a[j].push_back(i);
14.         }
15.     }
16.     int n;
17.     cin>>n;         
18.     vector<int> b(n);
19.     vector< vector<int> > mxb(N,vector<int>());
20.     for(int i=0;i<n;i++) cin>>b[i];
21.     //先进行排序，保证字典序
22.     sort(b.begin(),b.end());
23.     //从小数到大数依次将包含这个因式的数存入该因数
24.     for(auto c:b)
25.     {
26.         for(auto ct:a[c])
27.         {
28.             mxb[ct].push_back(c);
29.         }
30.     }
31.     //从大因数，到小因数，若满足有三个数同时拥有它，这三个数就是希望要找的三个数
32.     for(int i=1e5;i>0;i--)
33.     {
34.         if(mxb[i].size()>2)
35.         {
36.             for(int j=0;j<3;j++)
37.                 cout<<mxb[i][j]<<" ";
38.             return 0;  // 直接结束程序
39.         }
40.     }
41. }

复制代码

[code][/code]
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。