大家好，我是小单同学，欢迎交流指正~ 

  今天上午蓝桥杯圆满落幕，准备了几个月的比赛也终于打完了。今年填空题变成了两道，同学们反映今年难度上升很大，小单也感觉今年难度较大hh，空了两道题。现在给大家分享一下本菜鸡的解题报告，供大家交流。仅供参考哈。

目录

 ​大家好，我是小单同学，欢迎交流指正~ ​

🎁试题 A: 排列字母

🍞代码详解

 🎁试题 B: 特殊时间

🍞代码详解

 🎁试题 C: 纸张尺寸

🍞代码详解

 🎁试题 D: 求和

🍞代码详解

🎁试题 E: 数位排序

 🍞代码详解

 🎁试题 F: 选数异或

🎁试题 G: 消除游戏 

🎁试题 H: 重新排序

 🎁试题 I: 技能升级

总结：

 小单同学要去补专业课了QAQ,拜拜~

🎁试题 A: 排列字母

【问题描述】 小蓝要把一个字符串中的字母按其在字母表中的顺序排列。 例如，LANQIAO 排列后为 AAILNOQ。 又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY 。 请问对于以下字符串，排列之后字符串是什么？ WHERETHEREISAWILLTHEREISAWAY

   这道题无需多言，排个序的事，做这道题之前，我还是很自信的hh。

🍞代码详解

#include#include #include#include#includeusing namespace std;int main(){char a[28];for(int i=0;i>a[i];sort(a,a+28);for(int i=0;i<28;++i){cout<<a[i];}return 0;}

 🎁试题 B: 特殊时间

【问题描述】 2022 年 2 月 22 日 22:20 是一个很有意义的时间，年份为 2022，由 3 个 2 和 1 个 0 组成，如果将月和日写成 4 位，为 0222，也是由 3 个 2 和 1 个 0 组 成，如果将时间中的时和分写成 4 位，还是由 3 个 2 和 1 个 0 组成。 小蓝对这样的时间很感兴趣，他还找到了其它类似的例子，比如 111 年 10 月 11 日 01:11，2202 年 2 月 22 日 22:02 等等。 请问，总共有多少个时间是这种年份写成 4 位、月日写成 4 位、时间写成 4 位后由 3 个一种数字和 1 个另一种数字组成。注意 1111 年 11 月 11 日 11:11 不算，因为它里面没有两种数字。

  考试的时候这道题我没做出来，少考虑了很多种情况。刚才研究了一下，我们只需要考虑3个1和3个2的情况即可。因为3个数不可能为0，大于2的话月份就没有合法状态。我这里想出来一种全排列的解法，用两个数组分别初始化为a={1,1,1,0}；b={2,2,2,0},每次全排列之前把最后一个数变成1-9中可能的选择，然后全排列检查月份和日子是否合法，以及小时和分钟是否合法，因为年份一定是合法的，每个年份都有四种选择，我们统计出来中间四位和后面四位的所有合法状态，让他们相乘，4*中间四位合法状态*后面四位合法状态。就是每一种情况的所有取法。 不知道对不对，仅供参考；

🍞代码详解

#include#include#includeusing namespace std;int d[]={0,31,28,31,30,31,30,31,31,30,31,30,31};bool check_month(int a[]){int month = a[0]*10+a[1];int day = a[2]*10 + a[3];if(month > 12 || month <1)return false;if(dayd[month])return false;return true;}bool check_hour(int a[]){int hour = a[0]*10+a[1];int second = a[2]*10+a[3];if(hour24)return false;if(second >=60)return false;return true;}int main(){int a[4]={1,1,1,0};int ans=0;for(int i=0;i<=9;i++){a[3] = i;int month=0,hour=0;if(i==1)continue;do{if(check_month(a))month++;if(check_hour(a))hour++;}while(next_permutation(a,a+4));ans+=4*month*hour;a[0] = 1;a[1] = 1;a[2] = 1;a[3] = 0;} a[0] = 2;a[1] = 2;a[2] = 2;a[3] = 0;for(int i=0;i<=9;i++){a[3] = i;int month=0,hour=0;if(i==2)continue;do{if(check_month(a))month++;if(check_hour(a))hour++;}while(next_permutation(a,a+4));ans+=4*month*hour;a[0] = 2;a[1] = 2;a[2] = 2;a[3] = 0;} cout<<ans;return 0;}

 🎁试题 C: 纸张尺寸

【问题描述】 在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm × 841mm，将 A0 纸 沿长边对折后为 A1 纸，大小为 841mm × 594mm，在对折的过程中长度直接取 下整（实际裁剪时可能有损耗）。将 A1 纸沿长边对折后为 A2 纸，依此类推。 输入纸张的名称，请输出纸张的大小。

【输入格式】 输入一行包含一个字符串表示纸张的名称，该名称一定是 A0、A1、A2、 A3、A4、A5、A6、A7、A8、A9 之一。

【输出格式】 输出两行，每行包含一个整数，依次表示长边和短边的长度。

【样例输入 1】 A0

【样例输出 1】 1189 841

  这道题也蛮友好哈，模拟即可，先处理掉字符A，后面的数字就是循环的个数，每次选一个大的数/2，（题意说下取整就行）， 最后先输出较大的数，再输出较小的数。

🍞代码详解

#include#include#includeusing namespace std;int main(){getchar();int a;cin >> a;int x=1189,y=841;while(a--){if(x>y)x/=2;else y/=2;}cout<<max(x,y)<<endl<<min(x,y);return 0;}

 🎁试题 D: 求和

【问题描述】 给定 n 个整数 a1, a2, · · · , an ，求它们两两相乘再相加的和，即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an−2 · an−1 + an−2 · an + an−1 · an.

【输入格式】 输入的第一行包含一个整数 n 。 第二行包含 n 个整数 a1, a2, · · · an。

【输出格式】 输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。

【样例输入】 4 1 3 6 9

【样例输出】 117

【评测用例规模与约定】 对于 30% 的数据，1 ≤ n ≤ 1000，1 ≤ ai ≤ 100。 对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ ai ≤ 1000。

  乍一看没啥思路，先想暴力，两层循环枚举所有的数两两相乘，但是此题n为1e5*2，如果时间复杂度为O(n^2)，会TLE；

  所以 来分析一波，可以发现，S=A m*A m+1+A m*A m+2+......+Am*An;

  整理可得S=An*(A1+A2+...+An-1);就是每一个数乘以它前一项的前缀和。这样可以把时间复杂度优化到O（n），应该可以，不知道对不对， 仅供参考；

🍞代码详解

#include#includeusing namespace std;typedef long long LL;const int N=200010;int s[N];int a[N];int n;int main(){cin >> n;LL ans=0;for(int i=1;i=1;i--){ans+=a[i]*s[i-1];}printf("%lld",ans);return 0;}

🎁试题 E: 数位排序

【问题描述】 小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。当 两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时， 将数值小的排在前面。 例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位 之和 13。 又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。 给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元 素是多少？

【输入格式】 输入第一行包含一个正整数 n。 第二行包含一个正整数 m。

【输出格式】 输出一行包含一个整数，表示答案。

【样例输入】 13 5

【样例输出】 3

【样例说明】 1 到 13 的排序为：1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9。第 5 个数为 3。 【评测用例规模与约定】 对于 30% 的评测用例，1 ≤ m ≤ n ≤ 300。

对于 50% 的评测用例，1 ≤ m ≤ n ≤ 1000。

对于所有评测用例，1 ≤ m ≤ n ≤ 10^6。

  m，n的规模为10^6，应该选择O（nlogn）以内的算法，应该是快排加自定义规则。定义一个结构体，里面两个变量分别是该数字的数为和还有该数字原版的值，重载一下小于号，然后按数位和为第一优先级排序，数值为第二优先级排序。（后来才想到直接用pair就行了，当时考试的时候重载运算不知道为什么传两个参数就是不可以，还debug了半个多小时，麻了）

 🍞代码详解

#include#include#includeusing namespace std;const int N=1e6+5;struct A{int n1;int s1;bool operator s1;if(a.s1==s1)return a.n1>n1;} }a[N];int main(){int num1,num2;cin >> num1 >> num2;for(int i=1;i<=num1;++i){a[i].n1 = i;int k=a[i].n1;int sum=0;while(k){sum+=k%10;k/=10;}a[i].s1=sum;}sort(a+1,a+num1+1);cout << a[num2].n1;}

 🎁试题 F: 选数异或

【问题描述】 给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查 询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。

【输入格式】 输入的第一行包含三个整数 n, m, x 。 第二行包含 n 个整数 A1, A2, · · · , An 。 接下来 m 行，每行包含两个整数 li ,ri 表示询问区间 [li ,ri ] 。

【输出格式】 对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出 no。

【样例输入】 4 4 1 1 2 3 4 1 4 1 2 2 3 3 3

【样例输出】 yes no yes no 试题 F: 选数异或 8 第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 C 组 【样例说明】 显然整个数列中只有 2, 3 的异或为 1。

【评测用例规模与约定】 对于 20% 的评测用例，1 ≤ n, m ≤ 100； 对于 40% 的评测用例，1 ≤ n, m ≤ 1000； 对于所有评测用例，1 ≤ n, m ≤ 100000 ，0 ≤ x < 2 20 ，1 ≤ li ≤ ri ≤ n ， 0 ≤ Ai < 2 20。

  没想出来。。。写的暴力骗分，两层循环枚举区间，O（n^2),应该可以拿到百分之40把，等大佬更新题解学习一下吧。

🎁试题 G: 消除游戏 

【问题描述】 在一个字符串 S 中，如果 S i = S i−1 且 S i , S i+1 ，则称 S i 和 S i+1 为边缘 字符。如果 S i , S i−1 且 S i = S i+1，则 S i−1 和 S i 也称为边缘字符。其它的字符 都不是边缘字符。 对于一个给定的串 S，一次操作可以一次性删除该串中的所有边缘字符 （操作后可能产生新的边缘字符）。 请问经过 2 64 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则 输出 EMPTY。

【输入格式】 输入一行包含一个字符串 S 。

【输出格式】 输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。

【样例输入 1】 edda 【样例输出 1】 EMPTY

【样例输入 2】 sdfhhhhcvhhxcxnnnnshh 【样例输出 2】 s 

【评测用例规模与约定】 对于 25% 的评测用例，|S | ≤ 103 ，其中 |S | 表示 S 的长度； 对于 50% 的评测用例，|S | ≤ 104 ； 对于 75% 的评测用例，|S | ≤ 105 ； 对于所有评测用例，|S | ≤ 106，S 中仅含小写字母。

  这题和下一题都没做。我写异或数列那道暴力的时候，数组下标写错了，第一考试可能有点紧张？D了四十多分钟硬是没搞出来，后来才发现，我那个悔恨 啊，导致后来时间就来不及了，心也开始浮躁了，不然可以再写两道的（想不出来写暴力也行 啊！懊恼中！）。

🎁试题 H: 重新排序

【问题描述】 给定一个数组 A 和一些查询 Li , Ri，求数组中第 Li 至第 Ri 个元素之和。 小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可 以增加多少?

【输入格式】 输入第一行包含一个整数 n。 第二行包含 n 个整数 A1, A2, · · · , An，相邻两个整数之间用一个空格分隔。 第三行包含一个整数 m 表示查询的数目。 接下来 m 行，每行包含两个整数 Li、Ri ，相邻两个整数之间用一个空格分 隔。 【

输出格式】 输出一行包含一个整数表示答案。

【样例输入】 5 1 2 3 4 5 2 1 3 2 5

【样例输出】 4

 🎁试题 I: 技能升级

【问题描述】 小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技 能。其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数 都会减少 Bi。⌈ Ai Bi ⌉ (上取整) 次之后，再升级该技能将不会改变攻击力。 现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。请 你计算小蓝最多可以提高多少点攻击力？

【输入格式】 输入第一行包含两个整数 N 和 M。 以下 N 行每行包含两个整数 Ai 和 Bi。 【输出格式】 输出一行包含一个整数表示答案。

【样例输入】 3 6 10 5 9 2 8 1

【样例输出】 47 【评测用例规模与约定】 对于 40% 的评测用例，1 ≤ N, M ≤ 1000； 对于 60% 的评测用例，1 ≤ N ≤ 10^4 , 1 ≤ M ≤ 10^7； 对于所有评测用例，1 ≤ N ≤ 10^5，1 ≤ M ≤ 2 × 10^9，1 ≤ Ai , Bi ≤ 10^6。

就剩半小时了，又写的暴力。（懊恼+99999，数据友好的话也许能拿60的分？）

#include#include#include#includeusing namespace std;int n,m;const int N=1e5+5;int c[N],cnt[N];#define x first#define y secondtypedef pair<int,pair > PII;pair<int,pair > a[N];int main(){cin >> n >> m;//m是可以升级的次数int ans=0;for(int i=1;i<=n;++i){scanf("%d%d",&a[i].x,&a[i].y.x);if(a[i].x%a[i].y.x==0)a[i].y.y=a[i].x/a[i].y.x;else a[i].y.y = a[i].x/a[i].y.x + 1;}sort(a+1,a+n+1,greater() );for(int i=1;i=a[1].y.y)a[1].x=0;sort(a+1,a+n+1,greater());}cout<<ans;return 0;}

最后一题还是暴力，有一个条件还放错位置了，放到循环里面了，应该放到循环外面的。（懊恼+9999999）

总结：

  小单第一次打蓝桥杯，。虽然这次成绩可能不太理想，考试的时候是真的有点紧张嘞，之前学的算法全想不起来用，一看没时间了，就想着，暴力，暴力，暴力。最主要的是暴力还写错了一道，我哭。所以下次再有类似的比赛一定要沉下心来，不能慌，会就是会不会就是不会，不要太把得失放在心上。也要更细心一点，不能再出现这种一个数组下标写错，Debug了将近四十分钟的情况。不过也 没什么啦，通过这次比赛我开阔了眼界，认识到了自己的不足，也学到了很多的知识。接下来继续努力学习新知识，坚持每天一道算法题，并且定期总结和复盘。希望各位同学都能取到好的成绩，没取到好成绩的同学也不要灰心（比如我），和本菜鸡一起努力吧！

 小单同学要去补专业课了QAQ,拜拜~