前4题的讲解在这个视频，第五题的讲解在这个视频从第137分30秒开始。
第一题 三角形面积
题目描述
已知三角形三个顶点在直角坐标系下的坐标分别为：
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)
求该三角形的面积。
注意，要提交的是一个小数形式表示的浮点数。
要求精确到小数后3位，如不足3位，需要补零。
代码
#include <iostream>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
double cross(double x1, double y1, double x2, double y2)
{
return x1 * y2 - x2 * y1;
}
int main()
{
PDD pts[3];
for (int i = 0; i < 3; i ++ )
{
scanf("%lf%lf", &pts[i].first, &pts[i].second);
}
double l[3];
for (int i = 0, k = 0; i < 3; i ++ )
for (int j = i + 1; j < 3; j ++, k ++ )
{
double x1 = pts[i].first, y1 = pts[i].second;
double x2 = pts[j].first, y2 = pts[j].second;
double dx = x1 - x2, dy = y1 - y2;
l[k] = sqrt(dx * dx + dy * dy);
}
double a = l[0], b = l[1], c = l[2];
double p = (a + b + c) / 2;
cout << sqrt(p * (p - a) * (p - b) * (p - c)) << endl;
cout << 0.5 * cross(pts[1].x - pts[0].x, pts[1].y - pts[0].y, pts[2].x - pts[0].x, pts[2].y - pts[0].y) << endl;
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种队形了）
注意，需要提交的是一个整数，表示至少需要士兵数目，不要填写任何多余的内容。
代码
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
for (int i = 1; ; i ++ )
{
int cnt = 0;
for (int j = 1; j * j * 2 <= i; j ++ )
{
int k = i - j * j;
int t = sqrt(k);
if (t * t == k) cnt ++ ;
}
if (cnt >= 12)
{
cout << i << endl;
break;
}
}
return 0;
}
// ans: 160225
第三题 找假币
题目描述
在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:
switch(balance(data[6], data[7])){
case -1:
return judge(data,6,7,0);
case 0:
return -1;
case 1:
return judge(data,7,6,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;
}
请注意：只需要填写划线部分缺少的内容，不要抄写已有的代码或符号。
代码
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
int balance(int a, int b)
{
if(a<b) return -1;
if(a>b) return 1;
return 0;
}
int judge(char* data, int a, int b, int std)
{
switch(balance(data[a],data[std])){
case -1:
return a;
//printf("%d light\n", a);
break;
case 0:
return b;
//printf("%d heavy\n", b);
break;
case 1:
return -1;
//printf("err!\n", b);
}
return -1;
}
// data 中8个元素，有一个假币，或轻或重
int f(char* data, int as, int bs)
{
switch( balance(as, bs) ){ // 填空
case -1:
switch(balance(data[0]+data[4],data[3]+data[1])){
case -1:
return judge(data,0,3,1);
break;
case 0:
return judge(data,2,5,0);
break;
case 1:
return judge(data,1,4,0);
}
break;
case 0:
switch(balance(data[6], data[7])){
case -1:
return judge(data,6,7,0);
case 0:
return -1;
case 1:
return judge(data,7,6,0);
}
break;
case 1:
switch(balance(data[0]+data[4],data[3]+data[1])){
case -1:
return judge(data,4,1,0);
break;
case 0:
return judge(data,5,2,0);
break;
case 1:
return judge(data,3,0,1);
}
break;
}
return -1;
}
void out(vector<int> &a)
{
for (auto x : a) cout << x << ' ';
cout << endl;
}
bool check(vector<int> &a, vector<int> &b)
{
char buf[16][100] = {0};
for (int i = 0, k = 0; i < 16; i ++, k = (k + 1) % 8)
{
for (int j = 0; j < 8; j ++ ) buf[i][j] = '1';
if (i < 8) buf[i][k] = '0';
else buf[i][k] = '2';
}
for (int i = 0; i < 16; i ++ )
{
int as = 0, bs = 0;
for (auto x : a) as += buf[i][x];
for (auto x : b) bs += buf[i][x];
if (f(buf[i], as, bs) != i % 8) return false;
}
return true;
}
void dfs(int u, vector<int> &a, vector<int> &b)
{
if (u == 8)
{
if (a.size() != b.size()) return;
if (check(a, b))
{
out(a), out(b);
puts("");
}
return;
}
dfs(u + 1, a, b);
a.push_back(u);
dfs(u + 1, a, b);
a.pop_back();
b.push_back(u);
dfs(u + 1, a, b);
b.pop_back();
}
int main()
{
vector<int> a, b;
dfs(0, a, b);
return 0;
}
// 0 1 2, 3 4 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 [HTML_REMOVED]
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型。
代码
#include <iostream>
using namespace std;
const int N = 1000010;
int f[N];
int main()
{
int n, k;
cin >> n >> k;
f[1] = 0;
for (int i = 2; i <= n; i ++ ) f[i] = (f[i - 1] + k) % i;
cout << f[n] + 1 << endl;
return 0;
}
自描述序列
题目描述
小明在研究一个序列，叫Golomb自描述序列，不妨将其记作{G(n)}。这个序列有2个很有趣的性质:
- 对于任意正整数n，n在整个序列中恰好出现G(n)次。
- 这个序列是不下降的。
以下是{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 [HTML_REMOVED]
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型。
代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1000010;
int g[N];
int main()
{
LL n;
cin >> n;
g[1] = 1, g[2] = 2;
for (int i = 2, j = 2; j < N; i ++ )
{
for (int k = 0; k < g[i] && j < N; k ++ ) g[j ++ ] = i;
}
LL s = 0, t = 0;
for (int i = 1; i < N; i ++ )
{
s += i * (LL)g[i];
if (s >= n)
{
s -= i * (LL)g[i];
cout << t + (n - s + i - 1) / i << endl;
break;
}
t += g[i];
}
return 0;
}
这个约瑟夫环的解法太妙了！！
是的hh