2018第九届蓝桥杯大赛国赛（软件类）试题 A组

1.三角形面积

已知三角形三个顶点在直角坐标系下的坐标分别为：
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)

求该三角形的面积。

注意，要提交的是一个小数形式表示的浮点数。
要求精确到小数后3位，如不足3位，需要补零。
——————————————————————————————————————————————————————————
方法1：直接套公式
A、B、C 的坐标分别为 A(x1，y1)、B(x2，y2)、C(x3、y3)，则
S=(x1y2-x1y3+x2y3-x2y1+x3y1-x2y2)
这个我相信没几个人能在考场上想到，所以还是老实的用下面的吧
方法2：
求出 ac 的长，再求出 b 到线段 ac 的垂直距离，用 底 * 高 / 2 求面积。

答案：8.795

2.阅兵方阵

x国要参加同盟阅兵活动。
主办方要求每个加盟国派出的士兵恰好能组成 2 个方阵。
x国发现弱小的 y国派出了130人的队伍，他们的士兵在行进中可以变换2种队形：
130 = 81 + 49 = 9^2 + 7^2
130 = 121 + 9 = 11^2 + 3^2

x国君很受刺激，觉得x国面积是y国的6倍，理应变出更多队形。
于是他发 施令：
我们要派出一支队伍，在行进中要变出 12 种队形！！！

手下人可惨了，要忙着计算至少多少人才能组成 12 种不同的双方阵。
请你利用计算机的优势来计算一下，至少需要多少士兵。

（ps: 不要失去信心，1105人就能组成4种队形了）

注意，需要提交的是一个整数，表示至少需要士兵数目，不要填写任何多余的内容。

约瑟夫环

n 个人的编 是 1~n，如果他们依编 按顺时针排成一个圆圈，从编 是1的人开始顺时针 数。
（ 数是从1 起）当 到 k 的时候，这个人就退出游戏圈。下一个人重新从1开始 数。
求最后剩下的人的编 。这就是著名的约瑟夫环问题。

本题目就是已知 n，k 的情况下，求最后剩下的人的编 。

题目的输入是一行，2个空格分开的整数n, k
要求输出一个整数，表示最后剩下的人的编 。

约定：0 < n,k < 1百万

例如输入：
10 3

程序应该输出：
4

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。
——————————————————————————————————————————————————————
我是用的数组模拟， 上有用数学计算的最优解版本

自描述序列

小明在研究一个序列，叫Golomb自描述序列，不妨将其记作{G(n)}。这个序列有2个很有趣的性质:

1. 对于任意正整数n，n在整个序列中恰好出现G(n)次。
2. 这个序列是不下降的。

以下是{G(n)}的前几项：

n 1 2 3 4 5 6 7 8 9 10 11 12 13
G(n) 1 2 2 3 3 4 4 4 5 5 5 6 6

给定一个整数n，你能帮小明算出G(n)的值吗br> 【输入】
一个整数n。
对于30%的数据，1 <= n <= 1000000
对于70%的数据，1 <= n <= 1000000000
对于100%的数据，1 <= n <= 2000000000000000
【输出】
一个整数G(n)
【样例输入】
13
【样例输出】
6
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
———————————————————————————————————————————————————

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33847 人正在系统学习中