1084. Broken Keyboard (20)-PAT甲级试题

On a broken keyboard, some of the keys are worn out. So when you type some sentences, the characters corresponding to those keys will not appear on screen.

Now given a string that you are supposed to type, and the string that you actually type out, please list those keys which are for sure worn out.

Input Specification:

Each input file contains one test case. For each case, the 1st line contains the original string, and the 2nd line contains the typed-out string. Each string contains no more than 80 characters which are either English letters [A-Z] (case insensitive), digital numbers [0-9], or “_” (representing the space). It is guaranteed that both strings are non-empty.

Output Specification:

For each test case, print in one line the keys that are worn out, in the order of being detected. The English letters must be capitalized. Each worn out key must be printed once only. It is guaranteed that there is at least one worn out key.

Sample Input:
7_This_is_a_test
hssaes
Sample Output:
7TI

题目大意:旧键盘上坏了几个键,于是在敲一段文字的时候,对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字,请你列出肯定坏掉的那些键~

分析:用string的find函数~遍历字符串s1,当当前字符s1[i]不在s2中,它的大写也不在ans中时,将当前字符的大写放入ans中,最后输出ans字符串即可~
ps:感谢github上的@xiaorong61给我发的pull request中strchr()函数带来的灵感~让我想到了曾经用过的string的find函数~

1049. 数列的片段和(20)-PAT乙级真题

给定一个正数数列,我们可以从中截取任意的连续的几个数,称为片段。例如,给定数列{0.1, 0.2, 0.3, 0.4},我们有(0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 这10个片段。
给定正整数数列,求出全部片段包含的所有的数之和。如本例中10个片段总和是0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0。
输入格式:
输入第一行给出一个不超过105的正整数N,表示数列中数的个数,第二行给出N个不超过1.0的正数,是数列中的数,其间以空格分隔。
输出格式:
在一行中输出该序列所有片段包含的数之和,精确到小数点后2位。
输入样例:
4
0.1 0.2 0.3 0.4
输出样例:
5.00

分析:将数列中的每个数字读取到temp中,假设我们选取的片段中包括temp,且这个片段的首尾指针分别为p和q,那么对于p,有i种选择,即12…i,对于q,有n-i+1种选择,即i, i+1, … n,所以p和q组合形成的首尾片段有i * (n-i+1)种,因为每个里面都会出现temp,所以temp引起的总和为temp * i * (n – i + 1);遍历完所有数字,将每个temp引起的总和都累加到sum中,最后输出sum的值~

【Update 2020-6-18】PS:题目更新了测试样例,导致之前的代码测试点2(第3个测试点)无法通过,研究到凌晨四点找错误原因…后来找到了给PAT这道题提反馈改测试用例的这位同学写的关于这道题的博客:https://blog.zhengrh.com/post/about-double/,感谢他让我找到了错误的原因,大概意思是:N比较大时,double类型的值多次累加导致的精度误差,因为输入为十进制小数,存储到double中时,计算机内部使用二进制表示,且计算机的字长有限,有的十进制浮点数使用二进制无法精确表示只能无限接近,在字长的限制下不可避免会产生舍入误差,这些细微的误差在N较大时多次累加会产生较大误差,所以建议不要使用double类型进行多次累加的精确计算,而是转为能够精确存储的整型。尝试把输入的double类型的值扩大1000倍后转为long long整型累加,同时使用long long类型保存sum的值,输出时除以1000.0转为浮点型再输出(相当于把小数点向后移动3位后再计算,避免double类型的小数部分存储不精确,多次累加后对结果产生影响)
但我觉得乘以1000也未必严谨,可能测试样例最小只有小数点后三位,如果测试样例变成小数点后四位、五位、六位,乘以1000相当于直接在小数点后三位处截断,而原本第四五六位经过多次累加进位后依然可能会引起精度问题,但如果乘以10000就会超出long long的值,我认为最精确的应该是截取到所有小数中最大的位数的那一位。。可能我的想法有疏漏,经过测试,测试样例确实没有超过小数点后三位,虽然修改为乘以1000后代码已经AC,但如果对测试样例稍加修改,可能又会导致不AC了…所以这道题先打个问号吧,我猜可能将来题目样例还会被修改…

打印十字图-蓝桥杯历届试题

问题描述
小明为某机构设计了一个十字型的徽标(并非红十字会啊),如下所示:

对方同时也需要在电脑dos窗口中以字符的形式输出该标志,并能任意控制层数。 

输入格式
一个正整数 n (n<30) 表示要求打印图形的层数。

输出格式
对应包围层数的该标志。

样例输入1
1

样例输出1

样例输入2
3

样例输出2

提示
请仔细观察样例,尤其要注意句点的数量和输出位置。 

P1001 蓝桥杯算法提高-用字符串处理大数乘法

继续阅读P1001 蓝桥杯算法提高-用字符串处理大数乘法

学霸的迷宫-蓝桥杯算法提高-广搜 bfs 经典问题

用广度优先搜索解决。bfs。100分。

 

排列数(输出0~9的全排列)-蓝桥杯算法提高

问题描述
  0、1、2三个数字的全排列有六种,按照字母序排列如下:
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个(第1个为0123456789)。
输入格式
  一行,包含一个整数n
输出格式
  一行,包含一组10个数字的全排列
样例输入
1
样例输出
0123456789
数据规模和约定
  0 < n <= 10!
分析:啊我才发现有一个超好用的库函数……完全不用自己实现全排列。。竟然自己还那么笨的用下面的深度优先搜索的办法……next_permutation函数。。在algorithm里面,代码如下:

下面是那个笨方法。。。
假设有10个位置,需要在10个位置上依次放置0~9这十个数字。
1.先走到第一个位置,此时放置一个当前可以放置的数字当中最小的那个数字。
2.在走到第二个位置,放置一个当前可以放置的数字当中最小的那个数字。

3.到第10个位置时候,所有的数字已经放置完毕,属于第一个全排列。
4.收回第10个位置上的数字,此时还是只可以放置9,那么再到第9个位置面前,收回位置上的数字。
5.在第9个位置处,我们此时可以放置的数字有9,那么第10个位置放8.属于第二个全排列。
6.收回第10、9、8位置的数字,此时可以在第8个位置放置8.

用一个数组标记当前的数字是否已经被使用过了。
int book[10]; //一开始的时候没有被使用,初始化值为0.使用过了之后标记为1.
int a[10]; // 表示这10个需要放置数字的位置。
深度优先搜索: