模拟算法题练习(二）（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;
  // 输入 n, 表示DNA序列的长度
  
  string a, b;
  cin >> a >> b;
  // 输入 a, b, 表示两条DNA序列
  int cnt = 0;
  for (int i = 0; i < n; ++i)
  {
    if (mp[a[i]] + mp[b[i]] != 3)
    //判断相同位置处的 a, b的DNA中是否互补
    {
      // 从当前位置之后开始遍历 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;
    // 输入一个整数t, 表示有t个询问
    while (t--) {
        int n;cin >> n;
        // 输入 n, 表示目标石头的编号
        auto it = find(stones.begin(), stones.end(), n);
        // 在vector中查找石头编号n，如果找到，输出其在vector中的位置（从0开始计数）
        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'000'000大小以上的数组, 全部元素赋值为 -1
// 如果是无尽的石头, 则赋值为相应的值
//1 2 4 8 ......
void solve(const int& Case) {
    int n;std::cin >> n;
    // 输入 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 的个位数，并累加到 ret 上
            x /= 10;  // 这里 x % 10 得到了 x 的个位数
        }
        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;
    // 输入 T 个询问
    for (int i = 1; i <= T; i++)solve(i);
    return 0;
}