蓝桥杯小白打卡第三天

1209. 带分数

问题描述

100 可以表示为带分数的形式：100 = 3 + 69258 / 714

还可以表示为：100 = 82 + 3546 / 197

注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。

类似这样的带分数，100 有 11 种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。

数据范围

1 ≤ N < 10^6

输入输出样例

输入样例 1

100

输出样例 1

11

输入样例 2

105

输出样例 2

6

题目代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
//每个数字只出现一次1-9
bool st[10],backup[10];


//题目是要求n=a+b/c，能有多少种数，我们可以将题目修改为c*n=a*c+b,有多少种数（尽量避免除法），此时存在可能9位数，此时会出现超出int范围的情况，
//所以到时候，要讲c*n和a*c转换为long long的形式
int n,a,b,c,ans;

//因为我们要求的是c*n=a*c+b，此时n是已知条件，那么我们可以把a和c都列举出来后直接出b
//那么我们接下来就要开始进行列举a的函数
//由于a是一个完整的整数，a一定不会超过N，所以我们递归的出口就是判断当前a的大小是否已经超过了N

void check(int a,int c);
void dfs_c(int u,int a,int c);
void dfs_a(int u,int a);
void dfs_a(int u,int a){
    //u代表此时已经记录了几个数字
    //a代表此时a的大小
    if(a>n) return;
    if(a) dfs_c(u,a,0);
    for(int i=1;i<=9;i++){
        if(!st[i]){
        
            st[i]=true;
            dfs_a(u+1,a*10+i);
            st[i]=false;
        }
    }
}
void dfs_c(int u,int a,int c){
    if(u>9) return;
    check(a,c);
    for(int i=1;i<=9;i++){
        if(!st[i]){
            st[i]=true;
            dfs_c(u+1,a,c*10+i);
            st[i]=false;
        }
    }

}
void check(int a,int c){
    //计算出b的值
    long long b=(long long)c*n-a*c;
    memcpy(backup, st, sizeof st);
    while(b){
        int tem=b%10;
        if(!tem||backup[tem]){
            return;
        }
        backup[tem]=true;
        b/=10;
    }
    
    for(int i=1;i<=9;i++){
        if(!backup[i]){
           
            return;  
        } 
    }
    ans++;
   
    return;
}

int main(){
    cin>>n;
    dfs_a(1,0);
    cout<<ans;
    return 0;
}

790. 数的三次方根

问题描述

给定一个浮点数 n，求它的三次方根。

输入格式

共一行，包含一个浮点数 n。

输出格式

共一行，包含一个浮点数，表示问题的解。注意，结果保留 6 位小数。

数据范围

$-10000\le n\le 10000$

输入输出样例

输入样例

1000.00

输出样例

10.000000

题目代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;




int main(){
    double n;//保存浮点数
    cin>>n;
    double l=-10000,r=10000;
    while(r-l>1e-8){//要把限制条件写在这里，不然会超时
        double mid =(l+r)/2;
        if(mid*mid*mid>=n){
            r=mid;
        }
        else l=mid;
    }
    
    printf("%lf",l);
    
    
    return 0;
}

730. 机器人跳跃问题(今日头条题目）

问题描述

机器人正在玩一个古老的基于 DOS 的游戏。游戏中有 $N+1$ 座建筑——从 $0$ 到 $N$ 编号，从左到右排列。编号为 $0$ 的建筑高度为 $0$ 个单位，编号为 $i$ 的建筑高度为 $H(i)$ 个单位。

起初，机器人在编号为 $0$ 的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第 $k$ 个建筑，且它现在的能量值是 $E$，下一步它将跳到第 $k+1$ 个建筑。

• 如果 $H(k+1)>E$，那么机器人就失去 $H(k+1)-E$ 的能量值。
• 否则它将得到 $E-H(k+1)$ 的能量值。

游戏目标是到达第 $N$ 个建筑，在这个过程中能量值不能为负数个单位。现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式

• 第一行输入整数 $N$。
• 第二行是 $N$ 个空格分隔的整数，$H(1),H(2),\cdots ,H(N)$ 代表建筑物的高度。

输出格式

输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围

$1\le N,H(i)\le 10^5$

输入输出样例

输入样例 1

5
3 4 3 2 4

输出样例 1

4

输入样例 2

3
4 4 4

输出样例 2

4

输入样例 3

3
1 6 4

输出样例 3

3

题目思路

面对这种要求最小的能量值的问题，我们可以考虑到使用 二分 dfs dp 贪心的方法来做
在这里我们可以使用二分的方法来解决这个问题
由于题目给出了能量值的区间，那么我们就通过二分，逐渐缩小我们可以完成问题的能量区间值，最终得到满足的答案
由于H(k)>e时我们会失去H(k)-e的能量，那么我们的最终值是2e-H(k)
如果是h（k）<e，我们会得到e-H(k)的能量，那么我们的最终值是2e-H(k)

题目代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N=1e5+10;
int h[N],n;

bool check(int mid){
    for(int i=1;i<=n;i++){
        mid=2*mid-h[i];
        if (mid >= 1e5) return true;//这里添加原因：mid每次*2会爆内存，所以如果已经满足了，就直接返回true，从而顺便提前剪枝
        if(mid<0) return false;
    }
    return true;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);//完成值的输入
    
    //接下来对区间进行二分
    int l=0,r=1e5;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    
    
    return 0;
}