模拟算法题练习(二）（DNA序列修正、无尽的石头)

（一、DNA序列修正）

问题描述
在生物学中，DNA序列的相似性常被用来研究物种间的亲缘关系。现在我们有两条 DNA序列，每条序列由 A、C、G、T 四种字符组成，长度相同。但是现在我们记录的 DNA序列存在错误，为了严格满足 DNA 序列的碱基互补配对即 A-T和C-G，我们需要依据第一条 DNA 序列对第二条 DNA 序列进行以下操作:
1.选择第二条 DNA 序列的任意两个位置，交换他们的字符,
2.选择第二条 DNA 序列任意一个位置，将其字符替换为 A、C、G、T 中的任何一个。
需要注意的是:每个位置上的碱基只能被操作一次!
你的任务是通过最小的操作次数，使第二条 DNA 序列和第一条DNA序列互补。并且已知初始两条 DNA 序列长度均为 N。
输入格式
第一行包含一个整数 N，(1 ≤ N ≤ 103)，表示 DNA 序列的长度。
接下来的两行，每行包含一个长度为 N 的字符串，表示两条 DNA序列。
输出格式
输出一个整数，表示让第二条 DNA 序列和第一条 DNA 序列互补所需的最小操作次数。

2 2 0 0 3 -1 0 1

样例输出:

2 1

解法一：

问题分析

给定两条 DNA 序列，我们需要将第二条 DNA 序列修改为与第一条 DNA 序列互补。碱基互补规则是 A 与 T 互补，C 与 G 互补。同时，任何一个位置只能操作一次。

方法实现

我们可以考虑贪心的思路，因为每次修改操作只能修正一个位置，就是操作和得分比是 1:1；如果我们考虑通过交换来同时修正两个位置，那么操作和得分比就是 1:2，我们应当尽可能多地使用该操作。那么整个过程就是：

从左到右扫描第一条 DNA 序列和第二条 DNA 序列的每一个位置，检查它们是否互补。
如果某个位置不互补，我们需要寻找第二条 DNA 序列中后续位置的碱基，看是否可以通过交换使这两个位置都互补。如果可以，我们就进行交换。
如果在后续位置找不到可以交换的碱基，说明这个位置只能通过替换来满足要求。因为每个位置只能修改一次，所以我们不能把不配对的碱基交换到当前位置作为中转站，则只能进行修改。
每次交换或替换，操作计数器增加 1。
最后输出操作计数器的值。

时间复杂度和空间复杂度分析

时间复杂度：O(N2)。在最坏情况下，我们可能需要为每个位置在之后的所有位置中查找可以交换的碱基。

空间复杂度：O(N)。主要是由于输入的两个字符串。

#define  _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std; // 使用std命名空间，以便直接使用cout、cin等，而不是std::cout、std::cin

// 映射表，将字符映射到对应的整数值，A->0, C->1, G->2, T->3
map<char, int>mp{
	{'A',0},
	{'C',1},
	{'G',2},
	{'T',3}
};

int 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)
		{
            // 从当前位置之后开始遍历 b 字符串
			for (int j = i + 1; j < n; ++j)
			{
                // 如果交换后可以使得两个字符组合为 "AT" 或者 "CG"
				if (mp[a[i]] + mp[b[j]] == 3 && mp[a[j]] + mp[b[i]] == 3)
				{
					swap(b[i], b[j]);
					break;
				}
			}
			cnt++;
		}
	}
	cout << cnt << endl;

	return 0;
}

解法二：

#include <bits/stdc++.h>

//需要注意的是:每个位置上的碱基只能被操作一次
// 对于操作二, 一定能一次让一个位置变正确
// 对于操作一, 有可能是两/一/零个位置变正确

// 尽量使用操作一, 使两个位置同时变正确

void solve(const int &Case) {
    int n;
    std::cin >> n;
    std::string s1, s2;
    std::cin >> s1 >> s2;
    // A-T C-G
    for (int i = 0; i < n; i++) { // 把序列一转成互补的序列
        if (s1[i] == 'A')s1[i] = 'T';
        else if (s1[i] == 'T')s1[i] = 'A';
        else if (s1[i] == 'C')s1[i] = 'G';
        else s1[i] = 'C';
    }
    int ans = 0;
    for (int i = 0; i < n; i++) { 
        if (s1[i] == s2[i])continue; // 如果当前位置已经正确, 则不需要动
        for (int j = 0; j < n; j++) {
            if (s1[i] == s2[j] && s1[j] == s2[i]) { // 如果一次操作能正确两个位置
                std::swap(s1[i], s1[j]);// 交换, 执行操作一
                break;
            }
        }
        ans++;
    }
    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T = 1;
    for (int i = 1; i <= T; i++)solve(i);
    return 0;
}

（二、无尽的石头）

用户登录

问题描述
在一个古老的迷宫中，有一道无尽的通道。通道上每隔一定的距离就会有一块神秘的石头，石头上刻着从1开始的连续整数。从1号石头开始，每块石头的编号都比前一块大 1。
石头上的数字有特殊的意义。如果你站在编号为几的石头上，并向前走，你将会瞬间移动到编号为几十的石头上，其中为几的各位数字之和。
例如，如果你站在编号为 16 的石头上，由于1+6-7，所以下一步你会移动到编号为 16 +7= 23 的石头上。
现在，会有多次询问，你需要对每个询问输出从1号石头出发，到达指定编号石头的最少步数，如果无法到达，则输出-1。
输入格式
输入包含一个整数 t,(1 <t< 100)，表示有t个询问。接下来t行，每行一个整数 n，(1 ≤ n ≤ 1e6)，表示目标石头的编号。
输出格式
对于每个询问，输出一行，表示从1号石头到达目标石头的最少步数。如果无法到达，输出 -1。

解法一：

此题的解决方案可以进行数学化和形式化的优化。首先，题目所述的情况可以被看做是一个单向图的遍历问题，其中节点由数字标号的石头组成，初始节点为标号为 1 的石头。在此图中，从当前节点 n 移动到下一个节点 n+x 的路径是唯一的，其中 x 是 n 的各位数字之和。

鉴于每次遍历只存在一个可能的路径，求解最短路径的问题实际上变成了确定目标节点是否能够在此唯一路径上被访问到。只需依次模拟每一步遍历过程，如果能够在某一步到达目标节点，那么这一步就是到达目标节点的最短路径长度。但是，如果在某一步遍历时跳过了目标节点，那么目标节点将无法访问，因为无法向较小的节点移动。

对于多次查询，我们可以预处理一段范围内的所有可能访问到的节点，并将这些节点存储在数组中。在这种情况下，数组的索引即为到达该节点所需的步数。每当一个新的查询到来，只需检查目标数字是否存在于数组中。如果存在，数组中的索引就是到达目标的最短步数；否则，目标节点将无法被访问。

#include<bits/stdc++.h>

using namespace std;
#define ll long long

const ll MAX = 1e6;// 设置最大值为1000000
vector<ll> stones;

ll sum_digits(ll n) {
    // 求各个数位数字之和
    ll sum = 0;
    while (n) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

void preprocess() {
    stones.push_back(1);// 向vector中添加数字1作为起始点  
    while (true) {
        ll next = *--stones.end() + sum_digits(*--stones.end());
        // 计算容器 stones 中倒数第二个元素的值，然后将该值与计算该元素各个数字的和相加，并将结果赋值给变量 next
        if (next <= MAX) {
            stones.push_back(next);
        }
        else {
            break;
        }
    }
}

int main() {
    preprocess(); // 预处理函数，生成 stones 数组
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        // 在vector中查找石头编号n，如果找到，输出其在vector中的位置（从0开始计数）
        auto it = find(stones.begin(), stones.end(), n);
        if (it != stones.end()) {
            cout << it - stones.begin() << endl;// 输出位置
        }
        else {
            cout << -1 << endl;
        }
    }
    return 0;
}

解法二：

#include <bits/stdc++.h>

/*
考虑 ai 表示从 1 走到 i 的步数，若走不到则是 ?1。一个明显的递推
方式便是，若 ai = 1，则 ai+f(i) = ai + 1，其中 f(i) 表示 i 的十进制数
位和。预处理除 a 即可询问 O(1) 回答。
时间复杂度 O(n + T)。
*/

std::vector<int> a(1'000'000 + 1, -1);

//1 2 4 8 ......

void solve(const int &Case) {
    int n;
    std::cin >> n;
    std::cout << a[n] << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    // 156423
    // 1 + 5 + 6 + 4 + 2 + 3
    // 3
    // 156432 / 10 = 15642
    // 15642 / 10 = 1564
    // ...
    auto f = [&](int x) { //求 x 的各个数位和的函数
        int ret = 0;
        while (x > 0) {
            ret += x % 10;// 取出当前的个位数
            x /= 10; //
        }
        return ret;
    };
    // i -> i + f(i)
    a[1] = 0;
    for (int i = 1; i <= 1'000'000; i++) {
        if (a[i] == -1)continue;
        int x = i + f(i);
        if (x > 1'000'000)break; // > 1'000'000 的位置一定是不会询问的
        a[x] = a[i] + 1; // a[i + f(i)] = a[i] + 1
    }
    int T = 1;
    std::cin >> T;
    for (int i = 1; i <= T; i++)solve(i);
    return 0;
}

今天就先到这了！！！