1.握手问题
题目描述：
解题思路1（组合数学）
按照题目描述来说，会议有五十人，如果不加任何限制条件，这五十个人两两握手的次数是：
t o t a l = 49 + 48 + 47 + . . . . . . . . + 1 total=49+48+47+........+1total=49+48+47+........+1
利用高斯求和的得出：t o t a l = 50 ∗ 49 / 2 total=5049/2total=50∗49/2
如果加上限制条件的话，题目给定的其中有七个人不会相互握手，需要用上面总的不加限制的减去七个人相互握手的次数。
c n t = 6 + 5 + . . . . . . + 1 = 7 ∗ 6 / 2 cnt=6+5+......+1=76/2cnt=6+5+......+1=7∗6/2
上述两式作差即可
编写代码：
include
using namespace std;
int main()
{
int total = 50 49 / 2;
int cnt = 7 6 / 2;
cout << total - cnt << endl;
return 0;
}
1
2
3
4
5
6
7
8
9
解题思路2（暴力枚举）
将每个人握手的情况枚举出来即可。
include
using namespace std;
int main()
{
int ans = 0;
for (int i = 1;i <= 50;i++)
{
for (int j = i + 1;j <= 50;j++)
{
//排除掉七人的情况
if (!(i >= 1 && i <= 7 && j >= 1 && j <= 7))
{
ans++;
}
}
}
cout << ans << endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2.小球反弹
问题描述：
做题思路
这道题我们肯定不能直接做的，这道题给定了d x : d y dx:dydx:dy的值说明这道题我们应该分解来做，将小球的反弹的路径分解为x方向和y方向来做。
我们首先假设x方向上经过了p个来回，y方向上经历了q个来回，因为是分解的缘故，所以两个分解方向上的时间是相同的。
所以可以得出两个等式：
d x ∗ t = 2 p x dxt=2pxdx∗t=2px（由于这里一半的路程是x，所以一个来回的路程是2x，乘以来回就是总路程）
d y ∗ t = 2 q x dyt=2qxdy∗t=2qx
将这两个式子进行比例
d x d y = p x q y \frac{dx}{dy}=\frac{px}{qy}
dy
dx
=
qy
px
得到这个式子之后我们可以利用gcd对这个式子的左边进行约分。
可以得出：p = d x ∗ y p=dxyp=dx∗y和q = d y ∗ x q=dyxq=dy∗x
算出q或者p之后可以利用公式计算t：t = 2 p x / d x t=2px/dxt=2px/dx
最后得出总路程：总路程 = t ∗ ( s q r t ( 1 5 2 + 1 7 2 ) ) 总路程=t*(sqrt(15^2+17^2))总路程=t∗(sqrt(15
2
+17
2
))
编写代码：
//求最大公约数
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
//给出x方向和y方向的速度
int dx = 15, dy = 17;
//给出x方向和y方向上的距离
int x = 343720, y = 233333;
//求出多少来回
int q = dy x, p = dx y;
//求最大公约数
int g = gcd(p, q);
p /= g, q /= g;
//计算时间
int t = 2 * p * x / dx;
//求路程
double ans = t * sqrt(15 * 15 + 17 * 17);
printf("%.2lf\n", ans);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
3.好数
问题描述：
数据量：
算法思路（暴力解法）—不会超时
遍历1到n的数，然后写一个check函数判断每个数是否是好数，这里的时间复杂度是n ∗ l o g n n*lognn∗logn
编写代码：
include
using namespace std;
int N,count;
bool Check(int n)
{
int i=1;
while(n!=0)
{
int tail=n%10;
if(i%2==1)
{
if(tail%2!=1)return false;
}
else
{
if(tail%2!=0)return false;
}
i++;
n/=10;
}
return true;
}
int main()
{
// 请在此输入您的代码
cin>>N;
for(int i=1;i<N;i++)
{
if(Check(i))
{
count++;
}
}
cout<<count<<endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
4.R格式
题目描述：
