贰猹の小窝

题解仅供参考

编程练习专题（各种杂题）

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

---

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

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

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

求 1-n 的奇数平方和

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

法二：预处理打表（核心代码如下）

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

打表被老师嘲讽了

这题挺坑的，还要在出发点相遇（题目没讲清楚吧）

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

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

注意分母为 1 的情况

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

即 a+b-gcd (a,b)

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

显然用埃氏筛轻松解决

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

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

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

• 有限小数：形如 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

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

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

这题就很有意思了

对 n=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 个子序列

#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");
    }
}

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

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

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]);
}

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

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

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]))

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

求 N！ 的位数

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

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

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

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

略（基本上每个板子都能过吧）

大数累乘求 N!

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

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

核心代码如下：

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

求每组大数和

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

求 R 的 n 次方根

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

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

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

（然后大数比较我写错了，找 BUG 找了半天）

普通查找即可（不需要二分就可以过）

#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);

}
}

继续我的大数打表行为 emmm

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

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

太丢脸了就不放代码了

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

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

• 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 是否满足上述结构即可