题解仅供参考

编程练习专题(各种杂题)

题外话:我得重新整个实用的大数板子了


A

题解

就是个裸的辗转相除法,没什么坑,int就能过

B

题目大意

就是求一堆数里的素数(这题貌似用最简单的判断素数方法就能过)

优化

可以对前1e7个数用筛法判断存表(不过这题确实没必要)

C

题目大意

求1-n的奇数平方和

题解

法一:用公式解决(注意n(n+1)(n+2)会超长整数范围)

法二:预处理打表(核心代码如下)

1
2
3
4
5
long long pow2[100001];
pow2[1]=1;
for(int i=1;i<=100000;i+=2){
pow2[i]=i*i+pow2[i-2];
}

题外话

打表被老师嘲讽了

D

题解

这题挺坑的,还要在出发点相遇(题目没讲清楚吧)

具体的解法是,假设输入的数是a/b c/d

化简 a/b 和 c/d 得到新的 a,b,c,d,答案为 lcm(a,c)/gcd(b,d)

注意分母为1的情况

E

题解

这题是个纯数学题,看平均分后有多少刀是重复的

即 a+b-gcd(a,b)

F

题目大意

求最大质因数是第几个素数

题解

显然用埃氏筛轻松解决

G

题解

显然 c 是 b 的倍数且满足 gcd(a,c)==b 即可

循环 c 累加 b,找到最小的 c 后直接 break

H

题解

根据题目可知,一共有三种形式的小数需要我们去转换成分数,分别为:

  • 有限小数:形如 0.2,0.33

  • 纯循环小数:形如 0.333333333…

  • 非纯循环小数:形如 0.32477777… ,0.24367676767…

显然,无限不循环小数不可能转换为分数(中学知识),而对于上面两种循环小数,我们不妨分情况来讨论。

1、纯循环小数

0.33333… * 10 = 3.33333…

(10 - 1) * 0.33333… = 3

即 9 * 0.33333… = 3

所以 0.33333… = 3/9 = 1/3

再举一个例子

0.474747… * 100 = 47.474747…

(100 - 1) * 0.474747… = 47

即 99 * 0.474747… = 47

所以 0.474747… = 47/99

由上述两个例子我们可以发现,纯循环小数化成分数过后其分子就为所循环单元化成的数,分母则全由9组成,位数和循环数的位数相同。

2、非纯循环小数

0.4777777… * 10 = 4.7777…

0.477777… * 100 = 47.77777…

(100 - 10) * 0.4777777… = 43

所以 0.4777777… = 43/90

再举一个例子

0.323565656… * 1000 = 323.56565656…

0.323565656… * 100000= 32356.565656…

(10000 - 1000) * 0.32356565656… = 32033

所以 0.32356565656… = 32033/99000

由上述两个例子我们可以发现,非纯循环小数化成分数过后其分子为 非循环部分与第一个循环部分 组成的数减去非循环部分的数,分母则为9与0组成的数,9的位数和循环部分数的位数相同,0的位数则和非循环部分数的位数相同

PS:对于有限小数,不妨看作是非纯循环小数的一种特例子,即0.3 = 0.30000000

I

题目大意

输出[1,2,…,n]的第i个子序列

自序列的顺序按字典序排序

题解

这题就很有意思了

对 n=1 而言,子序列为

[1]

对 n=2 而言,子序列为

[1],[1,2]

[2],[2,1]

对 n=3 而言,子序列为

[1],[1,2],[1,2,3],[1,3],[1,3,2]

[2],[2,1],[2,1,3],[2,3],[2,3,1]

[3],[3,1],[3,1,2],[3,2],[3,2,1]

……

显然可以发现,长度为 n 的序列的子序列 S(n) 满足这样一个关系式:S(n)=n*(S(n-1)+1)

如果按上面的写的话,将 S(n) 个数分为 n 组,每组有 S(n-1)+1 个

那么第 i 个子序列的开头就很明显了,为 x1=i/(S(n-1)+1)+1

假如 n=3,i=9 ,求出的第9个子序列的第一个数为 x1=2

接下来对第 x1 行处理,去除第一个数,新的序列为

[1],[1,3]

[3],[3,1]

即为序列 [1,3] 的子序列

所求即为第 i%(S(n-1)+1)-1 个子序列

以此类推

代码

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
#include <bits/stdc++.h>
using namespace std;
long long s[21]={0};
bool t[21]={0};
int main(){
s[1]=1;
for(int i=2;i<=20;i++)
s[i]=i*(s[i-1]+1);

int n;
long long m;
while(~scanf("%d %lld",&n,&m)){
memset(t,false,sizeof(t));
long long k,num=n;
while(m>0){
m--;
k=m/(s[--num]+1);
m=m%(s[num]+1);
int number=0,i;
for(i=1;i<=n;i++){
if(!t[i])number++;
if(number==k+1)break;
}
printf("%d",i);
t[i]=true;
if(m>0)printf(" ");
}
printf("\n");
}
}

J

题目大意

其实就是最大上升子序列和

题解

DP题一道,dp[i]记录从1-i的最大子序列和,不断维护最大值即可,核心代码如下

1
2
3
4
5
6
7
8
9
10
int maxx=-1;
for(int i=1;i<=n;i++)
{
int maxs=-1;
for(int j=0;j<i;j++)
if(num[i]>num[j])
maxs=max(maxs,dp[j]);
dp[i]=maxs+num[i];
maxx=max(maxx,dp[i]);
}

K

题解

01背包问题,不过这题反向记录不被录取的最小概率会比较好算

dp[i]记录的是 i 万美元下不被录取的最小概率,核心代码如下

1
2
3
4
5
6
7
8
long long i,j;
for(i=0;i<10005;i++)
dp[i]=1;
for(i=1;i<=m;i++)
scanf("%lld %lf",&a[i],&b[i]);
for(i=1;i<=m;i++)
for(j=n;j>=a[i];j--)
dp[j]=min(dp[j],dp[j-a[i]]*(1-b[i]))

L

题解

数塔(数字三角形)什么的已经很老套了,这里就不讲了(不过递归会超时)

M

题目大意

求 N! 的位数

题解

求位数我们其实比较容易想到的是 log10(i)+1

log10(N!) = log10(12L*N) = log10(1) + log10(2) + L + log10(N)

最后对和取整+1即为答案

N

题目大意

就是个大数加法板子。。。

题解

略(基本上每个板子都能过吧)

O

题目大意

大数累乘求 N!

题解

10000!足足有近36000位,所以考虑了下压位处理

这题卡了空间没卡时间,打表反而会 MLE,每次运算求解就可

核心代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
memset(a,0,sizeof(a));
a[0]=1;
for(int i=1;i<=n;i++){
int k=0;
for(int j=0;j<10000;j++){
a[j]=i*a[j]+k;
k=a[j]/10000;
a[j]%=10000;
}
}

int i;
for(i = 10000; ; i--)
if(a[i] != 0)
break;
printf("%d",a[i]);
i--;
for( ; i != -1; i--)
printf("%04d",a[i]);
printf("\n");

PS:注意 0! =1

P

题目大意

求每组大数和

题解

还是个大数板子题,不过注意这题有个单独的数据 0 比较恶心

Q

题目大意

求 R 的 n 次方根

题解

对整数部分和小数部分分别运算,注意最后输出格式(小数的乘法确实难搞)

R

题目大意

求区间内的菲波那契数的个数

题解

这题我采用的是先打表后查找的方式,菲波那契数的第500项位数就超过100位了

(然后大数比较我写错了,找BUG找了半天)

普通查找即可(不需要二分就可以过)

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

int fb[1006][504] ={0};
int a1[504],b1[504];

bool min_fb_a1(int m){
int i,j;
for(i = 200; ; i--)
if(fb[m][i] != 0)break;
for(j = 200; ; j--)
if(a1[j] != 0)break;
if(i<j)return true;
if(i>j)return false;
for( ; i != -1; i--)
if(fb[m][i] < a1[i])
return true;
else if(fb[m][i] > a1[i])
return false;
return false;
}

bool min_deng_fb_b1(int m){
int i,j;
for(i = 200; ; i--)
if(fb[m][i] != 0)break;
for(j = 200; ; j--)
if(b1[j] != 0)break;
if(i<j)return true;
if(i>j)return false;
for( ; i != -1; i--)
if(fb[m][i] < b1[i])
return true;
else if(fb[m][i] > b1[i])
return false;
return true;
}

int main()
{
int i, j, k;
string a,b;
fb[1][0] = 1;
fb[2][0] = 1;
for(i = 3; i <= 500; i++){
k = 0;
for(j = 0; j <= 200; j++){
fb[i][j] = fb[i-1][j]+fb[i-2][j]+k;
k = fb[i][j]/10;
fb[i][j] = fb[i][j]%10;
}
}
while(cin>>a>>b){
if(a=="0"&&b=="0")break;
memset(a1,0,sizeof(a1));
memset(b1,0,sizeof(b1));
for(i=a.length()-1;i>=0;i--)a1[a.length()-1-i]=int(a[i])-48;
for(i=b.length()-1;i>=0;i--)b1[b.length()-1-i]=int(b[i])-48;

int start,end;
for(start=1;start<=500;start++)
if(!min_fb_a1(start))break;
if(start!=1)start--;
for(end=start;end<=500;end++)
if(!min_deng_fb_b1(end))break;
end--;

printf("%d\n",end-start);

}
}

S

题解

继续我的大数打表行为emmm

T

题解

跟大数加法没太大区别,只不过变成头尾补0了

U

题解

这题我的解法跟别人可能不太一样。。。我直接让组合出的数做为下标存到布尔数组里,再枚举数组值为 true 的下标(暴力不需要考虑重复)

太丢脸了就不放代码了

V

题目大意

已知树的前根中根遍历,求后根遍历

题解

这题也是老题了,熟悉这三种遍历方式的自然知道怎么判断树的根节点(不需要构建树)

W

题目大意

  • 1,2是友谊数

  • 如果 a,b (可相同)是友谊数,那么 ab+a+b 也是友谊数

求 n 是不是友谊数

题解

这是道数学题。可以发现公式

n+1 = ab+a+b+1 = (a+1)(b+1)

又因为所有友谊数都是由 1,2 衍生,可以知道 n+1 可以表示成 pow(2,x)*pow(3,y) 的形式

判断 n 是否满足上述结构即可