文章目录

标题：三角形面积标题：阅兵方阵标题：找假币标题：约瑟夫环标题：自描述序列

标题：三角形面积

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

求该三角形的面积。

注意，要提交的是一个小数形式表示的浮点数。 要求精确到小数后3位，如不足3位，需要补零。

给出了三角形三点的坐标，可以有几种方法求面积。 我感觉最好的方法是第一种

叉积公式，向量$AB=(x_1,y_1)$，向量$AC=(x_2,y_2)$ $S=AB\cdot AC=|x_1{y}_2-x_2{y}_1|/2$海伦公式 $p=(a+b+c)/2$ $S=\sqrt{p(p-a)(p-b)(p-c)}$将其填补成一个矩形，减去三个直角三角形的面积即可。

答案为8.795

叉积公式

#include <stdio.h> #include <math.h> int main() { double x1 = 5.1 - 2.3, y1 = 7.2 - 2.5; double x2 = 6.4 - 2.3, y2 = 3.1 - 2.5; double s = fabs(x1 * y2 - x2 * y1) / 2; printf("%.3lf\n", s); return 0; }

标题：阅兵方阵

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种队形了）

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

这道题是要求最小的并且满足由12对数的平方相加得到的数字。 这道题用一个循环即可，第二个数b可以直接根据a来表示。

标题：找假币

在8枚硬币中，有1枚假币，假币外观与真币一模一样，只是重量略轻或略重一点。 给你一架天平，要求最多称3次，就找出假币，并且知道它是重一些还是轻一些。 下面的代码给出一个解决方案，仔细分析逻辑，填写划线位置缺少的代码。

#include <stdio.h> int balance(int a, int b) { if(a<b) return -1; if(a>b) return 1; return 0; } void judge(char* data, int a, int b, int std) { switch(balance(data[a],data[std])){ case -1: printf("%d light\n", a); break; case 0: printf("%d heavy\n", b); break; case 1: printf("err!\n", b); } } // data 中8个元素，有一个假币，或轻或重 void f(char* data) { switch( ____________________________________ ){ // 填空 case -1: switch(balance(data[0]+data[4],data[3]+data[1])){ case -1: judge(data,0,3,1); break; case 0: judge(data,2,5,0); break; case 1: judge(data,1,4,0); } break; case 0: judge(data,6,7,0); break; case 1: switch(balance(data[0]+data[4],data[3]+data[1])){ case -1: judge(data,4,1,0); break; case 0: judge(data,5,2,0); break; case 1: judge(data,3,0,1); } break; } } int main() { int n; char buf[100]; scanf("%d", &n); gets(buf); int i; for(i=0; i<n; i++){ gets(buf); f(buf); } return 0; }

请注意：只需要填写划线部分缺少的内容，不要抄写已有的代码或符号。

这道题用到了树状数组中的基本操作，关于位运算。 答案是：balance(data[0] + data[1] + data[2], data[3] + data[4] + data[5)

标题：约瑟夫环

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 不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

可以用数学策略来解约瑟夫环问题。

对于这个做法的详解：https://blog.csdn.net/weixin_43772166/article/details/102508491

标题：自描述序列

小明在研究一个序列，叫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)的值吗？

输入

一个整数n。

对于30%的数据，1 <= n <= 1000000 对于70%的数据，1 <= n <= 1000000000 对于100%的数据，1 <= n <= 2000000000000000

输出

一个整数G(n)

【样例输入】 13

【样例输出】 6

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

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

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

提交程序时，注意选择所期望的语言类型和编译器类型。

如果我们直接打表g()的话，可以通过30%的数据，数据再多就会溢出

#include<stdio.h> int g[100000005]; int main() { g[1]=1; g[2]=2; int n; int num=2; for(int i=2;i<=105000;i++)//遍历每个g[i] for(int j=1;j<=g[i];j++)//g[i]表示i的个数 g[num++]=i; //printf("%d\n",num); scanf("%d",&n); printf("%d\n",g[n]); return 0; }

第一种方法是记录n——>g(n)。我们想到多个连续的g()是相等的，所以我们可以反过来记录g(n)——>n的关系。只需记录相等的g(n)中最大的n。