1 月 23日算法练习

模拟

既约分数

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

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

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

3. 代码

#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、题目描述

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

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

3. 代码

#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.

3. 代码

#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

2. 思路分析：贪心，枚举。操作次数最少说明交换操作尽可能多。遍历第一条 DNA，判断是否配对，如果不配对，遍历第二条 DNA 后面位置看是否能进行交换来满足。如果不能交换就进行替换。

3. 代码

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

无尽的石头

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

3. 代码

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