文章目录
1.握手问题
题目描述：
解题思路1（组合数学）
按照题目描述来说，会议有五十人，如果不加任何限制条件，这五十个人两两握手的次数是：
t
o
t
a
l
=
49
+
48
+
47
+
.
.
.
.
.
.
.
.
+
1
total=49+48+47+........+1
total=49+48+47+........+1
利用高斯求和的得出：
t
o
t
a
l
=
50
∗
49
/
2
total=50*49/2
total=50∗49/2
如果加上限制条件的话，题目给定的其中有七个人不会相互握手，需要用上面总的不加限制的减去七个人相互握手的次数。
c
n
t
=
6
+
5
+
.
.
.
.
.
.
+
1
=
7
∗
6
/
2
cnt=6+5+......+1=7*6/2
cnt=6+5+......+1=7∗6/2
上述两式作差即可
编写代码：
#include<iostream>
using namespace std;intmain(){int total =50*49/2;int cnt =7*6/2;
cout << total - cnt << endl;return0;}
解题思路2（暴力枚举）
将每个人握手的情况枚举出来即可。
#include<iostream>
using namespace std;intmain(){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;return0;}
2.小球反弹
问题描述：
做题思路
这道题我们肯定不能直接做的，这道题给定了
d
x
:
d
y
dx:dy
dx:dy的值说明这道题我们应该分解来做，将小球的反弹的路径分解为x方向和y方向来做。
我们首先假设x方向上经过了p个来回，y方向上经历了q个来回，因为是分解的缘故，所以两个分解方向上的时间是相同的。
所以可以得出两个等式：
d
x
∗
t
=
2
p
x
dx*t=2px
dx∗t=2px（由于这里一半的路程是x，所以一个来回的路程是2x，乘以来回就是总路程）
d
y
∗
t
=
2
q
x
dy*t=2qx
dy∗t=2qx
将这两个式子进行比例
d
x
d
y
=
p
x
q
y
\frac{dx}{dy}=\frac{px}{qy}
dydx=qypx
得到这个式子之后我们可以利用gcd对这个式子的左边进行约分。
可以得出：
p
=
d
x
∗
y
p=dx*y
p=dx∗y和
q
=
d
y
∗
x
q=dy*x
q=dy∗x
算出q或者p之后可以利用公式计算t：
t
=
2
p
x
/
d
x
t=2px/dx
t=2px/dx
最后得出总路程：
总路程
=
t
∗
(
s
q
r
t
(
1
5
2
+
1
7
2
)
)
总路程=t*(sqrt(15^2+17^2))
总路程=t∗(sqrt(152+172))
编写代码：
//求最大公约数intgcd(int a,int b){return b ==0? a :gcd(b, a % b);}intmain(){//给出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);return0;}
3.好数
问题描述：
数据量：
算法思路（暴力解法）—不会超时
遍历1到n的数，然后写一个check函数判断每个数是否是好数，这里的时间复杂度是
n
∗
l
o
g
n
n*logn
n∗logn
编写代码：
#include<iostream>
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;}intmain(){// 请在此输入您的代码
cin>>N;for(int i=1;i<N;i++){if(Check(i)){
count++;}}
cout<<count<<endl;return0;}
4.R格式
题目描述：
数据量：
可以看到这道题的数据量是很大的，涉及到了幂次，肯定不可能直接去算，这道题很显然是考察的是高精度算法（高精度*低精度）
算法思路
高精度模版题：
编写代码：
#include<iostream>#include<algorithm>#include<string>#include<cmath>
using namespace std;//数组模拟高精度：高精度*低精度constint N =2e3+10;
string s;int a[N];intmain(){int n;
cin >> n >> s;//反转操作reverse(s.begin(), s.end());//确定小数点的位置int pos = s.find(".");
s.erase(pos,1);//删除小数点，方便后续计算int len = s.size();for(int i =0;i < len;i++) a[i +1]= s[i]-'0';//高精度*低精度for(int i =1;i <= n;i++){//顺序扫描，均*2for(int j =1;j <= len;j++) a[j]*=2;//处理大于10的位数for(int j =1;j <= len;j++){if(a[j]>=10){
a[j +1]++;
a[j]%=10;if(j == len) len++;}}}//处理小数点后的第一位，进行四舍五入if(a[pos]>=5)a[pos +1]++;for(int i = pos +1;i <= len;i++){if(a[i]>=10){
a[i +1]++;
a[i]%=10;if(i == len)len++;}}//打印的时候倒序打印for(int i = len;i >= pos +1;i--) cout << a[i];return0;}
5.宝石组合
题目描述：
数据范围：
首先从数据量来看这道题是不能用暴力枚举的，因为暴力枚举三个数的时间复杂度是
O
(
N
3
)
O(N^3)
O(N3)了。
算法思路—唯一分解定理
首先我们要知道什么是唯一分解定理，简单来说唯一分解定理就是，任意一个大于1的正整数 ，都可以唯一地表示为若干个质数的乘积，且这些质数的顺序不影响分解的唯一性。
那么可以得出：
N
1
=
p
1
a
1
⋅
p
2
a
2
⋅
…
⋅
p
n
a
n
N_1 = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_n^{a_n}
N1=p1a1⋅p2a2⋅…⋅pnan
N
2
=
p
1
b
1
⋅
p
2
b
2
⋅
…
⋅
p
n
b
n
N_2 = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_n^{b_n}
N2=p1b1⋅p2b2⋅…⋅pnbn
从上面两个式子可以得出：
gcd
(
N
1
,
N
2
)
=
p
1
min
(
a
1
,
b
1
)
⋅
p
2
min
(
a
2
,
b
2
)
⋅
…
⋅
p
n
min
(
a
n
,
b
n
)
\gcd(N_1,N_2) = p_1^{\min(a_1,b_1)} \cdot p_2^{\min(a_2,b_2)} \cdot \ldots \cdot p_n^{\min(a_n,b_n)}
gcd(N1,N2)=p1min(a1,b1)⋅p2min(a2,b2)⋅…⋅pnmin(an,bn)
lcm
(
N
1
,
N
2
)
=
p
1
max
(
a
1
,
b
1
)
⋅
p
2
max
(
a
2
,
b
2
)
⋅
…
⋅
p
n
max
(
a
n
,
b
n
)
\operatorname{lcm}(N_1,N_2) = p_1^{\max(a_1,b_1)} \cdot p_2^{\max(a_2,b_2)} \cdot \ldots \cdot p_n^{\max(a_n,b_n)}
lcm(N1,N2)=p1max(a1,b1)⋅p2max(a2,b2)⋅…⋅pnmax(an,bn)
假设Ha，Hb，Hc的分解出来的相同的质数的幂次分别是x，y，z那么可以得出：
上面的式子可以转换为幂次是：
x
+
y
+
z
+
max
(
x
,
y
,
z
)
−
max
(
x
,
y
)
−
max
(
x
,
z
)
−
max
(
y
,
z
)
x+y+z+\max(x,y,z)-\max(x,y)-\max(x,z)-\max(y,z)
x+y+z+max(x,y,z)−max(x,y)−max(x,z)−max(y,z)
相当于我们只需要求出上面式子的最大值即可。
编写代码：
#include<iostream>#include<vector>#include<algorithm>
using namespace std;constint N =1e5+10;int a[N];//fac是存储因子的二维数组，s是求的最大值
vector<int> fac[N], s[N];intmain(){//遍历数组for(int i =1;i <=1e5;i++){for(int j = i;j <=1e5;j += i){//i是j的因子
fac[j].push_back(i);}}//输入n个数int n;cin >> n;for(int i =1;i <= n;i++)cin >> a[i];//保证字典序最小sort(a +1, a + n +1);for(int i =1;i <= n;i++){//处理i的每个因子for(int j =0;j < fac[a[i]].size();j++){//
s[fac[a[i]][j]].push_back(a[i]);}}for(int i =1e5;i >=0;i--){if(s[i].size()>=3){
cout << s[i][0]<<' '<< s[i][1]<<' '<< s[i][2]<< endl;break;}}return0;}
6.数字接龙
问题描述：
数据量：
根据数据量来看这道题考察的应该是DFS，但是在DFS中应该还涉及到回溯，因为当走到不满足条件的时候需要进行回溯。
算法思路----DFS
编写代码：
#include<iostream>#include<string>
using namespace std;constint N =20;int a[N][N];
bool vis[N][N];int n, k;//方向数组： 0 1 2 3 4 5 6 7int dx[8]={-1,-1,0,1,1,1,0,-1};int dy[8]={0,1,1,1,0,-1,-1,-1};
string res;voiddfs(int x,int y,int prev, string s,int dep){//当搜到终点的时候，且搜索深度是n的时候，意思就是每种情况都搜索完了if(x == n && y == n && dep == n * n){if(res.empty())res = s;return;}for(int i =0;i <8;i++){//生成邻接点int bx = x + dx[i];int by = y + dy[i];//过滤越界节点if(bx<1|| bx>n || by<1|| by>n)continue;//过滤访问过的节点if(vis[bx][by]== true)continue;//防止交叉搜索if(i ==1&& vis[x -1][y]&& vis[x][y +1])continue;if(i ==3&& vis[x +1][y]&& vis[x][y +1])continue;if(i ==5&& vis[x +1][y]&& vis[x][y -1])continue;if(i ==7&& vis[x -1][y]&& vis[x][y -1])continue;//保证路径数值为0 1 2 3 .....k-1if((a[bx][by]< k && a[bx][by]== prev +1)||(prev +1== k && a[bx][by]==0)){//可以搜索，将点标记为true
vis[bx][by]= true;dfs(bx, by, a[bx][by], s +to_string(i), dep +1);//最优性剪枝if(!res.empty())return;
vis[bx][by]= false;//回溯}}}intmain(){
cin >> n >> k;for(int i =1;i <= n;i++)for(int j =1;j <= n;j++)
cin >> a[i][j];
string emp;//标记起点
vis[1][1]= true;dfs(1,1,0, emp,1);if(res.empty())cout <<-1;else cout << res << endl;return0;}
7.拔河
问题描述：
数据量：
对于这种涉及到区间和的题来说，大概率都是用前缀和算法解决
算法思路
编写代码：
#include<iostream>#include<set>#include<climits>
using namespace std;#definelllonglongconstint N =1e3+10;int a[N], s[N];//前缀和和数组
multiset<int> ms;intmain(){int n;cin >> n;for(int i =1;i <= n;i++){
cin >> a[i];//前缀和
s[i]= s[i -1]+ a[i];}//用set去维护所有的区间和for(int i =1;i <= n;i++){for(int j =1;j <= n;j++){//维护区间和
ms.insert(s[j]- s[i -1]);}}int ans = LONG_MAX;for(int i =1;i <= n;i++){for(int j =1;j < i;j++){//枚举以i结尾的区间，因为这里i-1只会有一个人，所以应该是j-1int sum = s[i]- s[j -1];//找到与该区间和sum相似的区间和auto it = ms.lower_bound(sum);if(it != ms.end()){
ans =min(ans,abs(*it - sum));}if(it != ms.begin()){
it--;
ans =min(ans,abs(*it - sum));}}//删除以i开头且以j结尾的区间，防止后续查询区间的时候出现区间重叠/交叉问题for(int j = i;j <= n;j++) ms.erase(ms.find(s[j]- s[i -1]));}
cout << ans << endl;return0;}
本文转载自: https://blog.csdn.net/2301_79969994/article/details/142898129
版权归原作者 lyyyyrics 所有， 如有侵权，请联系我们删除。
版权归原作者 lyyyyrics 所有， 如有侵权，请联系我们删除。