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

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

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