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个需要放置数字的位置。
深度优先搜索: