以难度顺序排列
文章目录
1.摸鱼王的2468复读机分析代码
2.签到题分析代码
3.阶乘分析代码
4.ff爱组合数分析代码
5.合并滑稽分析错误代码AC代码
6.约数的个数分析代码
7.猜猜在哪里描述分析代码
1.摸鱼王的2468复读机
分析
有规律的，除去第一位2的0次方个位数为1，其余以2 , 4，8 , 6为循环
代码
#include<iostream>
using namespace std
;
int main() {
long long n
;
cin
>>n
;
int ans
;
if(n
==0)
ans
= 1;
else {
switch(n
%4) {
case 0: ans
= 6;
break;
case 1: ans
= 2;
break;
case 2: ans
= 4;
break;
case 3: ans
= 8;
break;
}
}
cout
<<ans
<<endl
;
return 0;
}
2.签到题
分析
其实输出结果就是printf中的表达式，随便尝试一下就可以发现规律就是1，-1重复的循环，所以唯一的问题就是n过大，会超时
代码
#include<iostream>
using namespace std
;
int main() {
long long n
;
scanf("%lld",&n
);
if(n
%2==0)
cout
<<-1<<endl
;
else
cout
<<1<<endl
;
return 0;
}
3.阶乘
分析
对于所有数，能够相乘得出10的倍数才能使结果的末位增加0，所以5成为一个非常重要的数字，对于每一个5，都需要一个2和它配对相乘才能得出10，所以所有2的倍数（2,4,6,8）都能够担此重任，把所有数分成5个一组，而对于阶乘而言，每一个5之前都会有至少两个2的倍数，所以一定够用。 需要注意的地方在于一些比较特殊的数字，例如25=5 * 5，这个数字能够拆分成为两个5，所以可以增加两个0，而50 = 2 * 5* 5也可以增加两个0，125 = 5 * 5 * 5，可以增加三个0，所以对于每一个数n!末尾的0应该表示为f(n) = n/5 + f(n/5)，并且循环嵌套。
代码
#include<iostream>
using namespace std
;
int main() {
int n
;
int count
=0;
cin
>>n
;
while(n
) {
n
/= 5;
count
+= n
;
}
cout
<<count
<<endl
;
return 0;
}
4.ff爱组合数
分析
问题其实已经给出了公式，最复杂的部分就是怎么解决时间复杂度和答案溢出的问题，直接两个for循环嵌套就可以解决，然后计算结果的时候多多mod取余，以防溢出，虽然题目中好像没有这种情况。
代码
#include<iostream>
#include<string.h>
using namespace std
;
const long long MOD
= 1e9 + 9;
long long num
[2002][2002];
void fun();
int main() {
int T
;
memset(num
,0,sizeof(num
));
cin
>> T
;
fun();
while (T
--) {
int n
, m
;
cin
>> n
>> m
;
cout
<< num
[n
][m
]<< endl
;
}
}
void fun() {
for (int i
= 0; i
<= 2001; i
++) {
num
[0][i
] = 0;
num
[i
][0] = 1;
}
for (int i
= 1; i
<= 2001; i
++) {
for(int j
= 1; j
<= i
; j
++) {
num
[i
][j
] = (num
[i
-1][j
]%MOD
+ num
[i
-1][j
-1]%MOD
) % MOD
;
}
}
}
5.合并滑稽
分析
是一道贪心策略的题目，我觉得贪心没有固定的解题模式，就是一种理解方式。 本题的意图就是不断把一组数排序，然后取最小的两个数相加得出一个新的数放入数列中，之前的两个数抛去，并将相加的结果累加得出答案。 根据分析，其实用最简单的数组就能写，但是数据最大开到了10000，我算了一下，时间复杂度大概是10的8次方，亿级别以上基本不可能过，但是学校的平台上数据水了竟然过了。 所以必须使用优先队列，这里涉及STL内容（以后总结的话会更新）。首先将每个元素压入小根堆，在循环的时候不断的取头上的值，取两个作为最优值（a,b），最后再弹掉。结果就是不断累加两个元素（a,b）,最后再把此次的和再压入小根堆。
错误代码
这是会超时的代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std
;
int num
[10005];
int main() {
int n
;
cin
>> n
;
for (int i
= 0; i
< n
; i
++) {
cin
>> num
[i
];
}
long long mx
= 0;
while (n
> 1) {
sort(num
, num
+n
);
num
[0] += num
[1];
mx
+= num
[0];
n
--;
for (int i
= 1; i
< n
; i
++) {
num
[i
] = num
[i
+1];
}
}
cout
<<mx
<<endl
;
return 0;
}
AC代码
#include<queue>
#include<iostream>
#include<stdio.h>
using namespace std
;
priority_queue
<int,vector
<int>,greater
<int> >q
;
int main(){
int n
,x
;
int ans
=0;
cin
>>n
;
for(int i
=1;i
<=n
;i
++){
cin
>>x
;
q
.push(x
);
}
while(q
.size()>=2){
int a
=q
.top();
q
.pop();
int b
=q
.top();
q
.pop();
ans
+= a
+b
;
q
.push(a
+b
);
}
printf("%d\n",ans
);
return 0;
}
6.约数的个数
分析
这道题的意图就是求出1-N中所有数的约数个数，并依次相乘一个常数，最后求出相加的和，且为了防止数字过大溢出要约1e15,。 求约数可以使用数论中提到的方法–筛法求解，
代码
在这里插入代码片
7.猜猜在哪里
描述
有一个很有意思的魔术
桌子上有从左到右编号为1到n的n顶不透明的帽子，一开始只有1号帽子下面有一只兔子，魔术师会依次交换其中的m对帽子，也就是说每次把从左往右的第x个帽子和第y个帽子交换，其中x, y不相同，帽子下的兔子也会跟着帽子移动。
由于魔术师神奇的手法，作为观众的你没有看到魔术师的部分交换操作，但你按顺序记下了一部分不一定连续的交换操作。对于每个你没看到的交换操作，我们假设魔术师会等概率地选择两个位置不同的帽子交换，请问所有操作结束以后，兔子在从左到到右第1, 2, …, n号帽子底下的概率分别是多少？
分析
代码
