1 月 23日算法练习

发布时间:2024年01月23日

模拟

既约分数

1、题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
如果一个分数的分子和分母的最大公约数是 1,这个分数称为既约分数。
例如 1/7 , 3/4 , 1/8 都是既约分数。
请问,有多少个既约分数,分子和分母都是 1 到 2020 之间的整数(包括 1和 2020)?

运行限制
最大运行时间:2s
最大运行内存: 128M

  1. 题目分析:
    题目类型:枚举
    解题思路:分别枚举分子分母在 1-2020 范围,判断是否最大公约数为 1,如果是就是既约分数,计数

  2. 代码

#include<iostream>
#include<algorithm>

using namespace std;

int my_gcd(int a,int b){
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

int main(){
    int ans = 0;
    for(int i=1;i<=2020;i++){
        for(int j=1;j<=2020;j++){
            if(my_gcd(i,j) == 1)ans++;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

改进:质数筛等数学方法。

数的分解

1、题目描述
在这里插入图片描述

  1. 题目分析:
    题目类型:枚举
    解题思路:分别枚举三个数,如果他们满足和为 2019 的条件和不包含 2 和 4则计数,最后答案除以 6 则为最终答案。因为排列组合同个答案有 6 次呈现。

优化 1:用数组来进行不包含 2 和 4 的判断。
优化 2:添加 i<j<k 的约束保证只有一种答案
优化 3:利用 i 和 j 的枚举来计算 k

  1. 代码
#include<iostream>
using namespace std;


int flag[2020];

int check(int i){
    while(i){
        if(i%10==2||i%10==4)return 0;
        i/=10;
    }
    return 1;
}

signed main(){
    int res = 0;

    for(int i=1;i<=2019;i++)if(check(i))flag[i]=1;
    
    for(int i=1;i<=2019;i++){
        for(int j=i+1;j<2019-i-j;j++){
            if(flag[i]&&flag[j]&&flag[2019-i-j])res++;
        }
    }
    cout<<res<<'\n';
    return 0;
}

改进:数位 dp

小蓝和小桥的挑战

在这里插入图片描述
2. 题目分析:
题目类型:枚举
解题思路:先求 0 的个数z,在求 z 的过程中求总和 sum,如果 sum 为 0,则答案为 z+1,否则则为 z。调整过程是先把为 0 的+1,然后如果总和为 0 把一个正整数+1.

  1. 代码
#include<iostream>

using namespace std;

int tmp,t,n;

signed main(){
    cin>>t;
    while(t--){
        cin>>n;
        int sum = 0,z = 0;
        for(int i=1;i<=n;i++){
            cin>>tmp;
            if(tmp == 0){z++;tmp++;}
            sum+=tmp;
        }
        
        if(sum==0)cout<<z+1<<'\n';
        else cout<<z<<'\n';
    }
    
    return 0;
}

DNA序列修正

  1. 题目
    在这里插入图片描述
  • 样例输出为 2
  1. 思路分析:贪心,枚举。操作次数最少说明交换操作尽可能多。遍历第一条 DNA,判断是否配对,如果不配对,遍历第二条 DNA 后面位置看是否能进行交换来满足。如果不能交换就进行替换。

  2. 代码

#include<iostream>
#include<map>

using namespace std;

map<char,int> mp{
    {'A',0},
    {'C',1},
    {'G',2},
    {'T',3}
};


signed main(){
    int N;cin>>N;
    string a,b;
    cin>>a>>b;
    int cnt = 0;
    for(int i = 0;i<N;i++){
        if(mp[a[i]]+mp[b[i]]!=3){
            for(int j = i+1;j<N;j++){
                if(mp[a[i]]+mp[b[j]]==3&&mp[a[j]]+mp[b[i]]==3){
                    swap(b[i],b[j]);
                    break;
                }
            }
            cnt++;
        }
    }
    cout<<cnt;
}

无尽的石头

在这里插入图片描述

  1. 解题思路:模拟
    读题可知行走路径是唯一的,先求出路径存在数组中,然后再查询。

  2. 代码

#include<iostream>
#include<vector>
#include<algorithm>//find

using namespace std;

#define ll long long
const ll MAX = 1e6;

vector<ll> stones;

ll sum_digits(ll digit){
    ll sum = 0;
    while(digit){
        sum += digit%10;
        digit/=10;
    }
    return sum;
}

void preprocess(){
    stones.push_back(1);
    while(true){
        ll next = *--stones.end() + sum_digits(*--stones.end());
        if(next<=MAX)stones.push_back(next);
        else break;
    }
}

int main(){
    preprocess();
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        auto it = find(stones.begin(), stones.end(), n);
        if(it!=stones.end())cout<<it - stones.begin()<<'\n';
        else cout<<-1<<'\n';
    }
    return 0;
}

文章来源:https://blog.csdn.net/qq_61735602/article/details/135769004
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。