容桂网站设计制作,网站建设中数据字典,wordpress配置七牛,织梦做的网站打开不是#xff08;一、DNA序列修正#xff09;
问题描述 在生物学中#xff0c;DNA序列的相似性常被用来研究物种间的亲缘关系。现在我们有两条 DNA序列#xff0c;每条序列由 A、C、G、T 四种字符组成#xff0c;长度相同。但是现在我们记录的 DNA序列存在错误#xff0c;为了… 一、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
#includebits/stdc.h
using namespace std; // 使用std命名空间以便直接使用cout、cin等而不是std::cout、std::cin// 映射表将字符映射到对应的整数值A-0, C-1, G-2, T-3
mapchar, intmp{{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 或者 CGif (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-Gfor (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 的石头上由于16-7所以下一步你会移动到编号为 16 7 23 的石头上。 现在会有多次询问你需要对每个询问输出从1号石头出发到达指定编号石头的最少步数如果无法到达则输出-1。 输入格式 输入包含一个整数 t,(1 t 100)表示有t个询问。接下来t行每行一个整数 n(1 ≤ n ≤ 1e6)表示目标石头的编号。 输出格式 对于每个询问输出一行表示从1号石头到达目标石头的最少步数。如果无法到达输出 -1。 解法一
此题的解决方案可以进行数学化和形式化的优化。首先题目所述的情况可以被看做是一个单向图的遍历问题其中节点由数字标号的石头组成初始节点为标号为 1 的石头。在此图中从当前节点 n 移动到下一个节点 nx 的路径是唯一的其中 x 是 n 的各位数字之和。
鉴于每次遍历只存在一个可能的路径求解最短路径的问题实际上变成了确定目标节点是否能够在此唯一路径上被访问到。只需依次模拟每一步遍历过程如果能够在某一步到达目标节点那么这一步就是到达目标节点的最短路径长度。但是如果在某一步遍历时跳过了目标节点那么目标节点将无法访问因为无法向较小的节点移动。
对于多次查询我们可以预处理一段范围内的所有可能访问到的节点并将这些节点存储在数组中。在这种情况下数组的索引即为到达该节点所需的步数。每当一个新的查询到来只需检查目标数字是否存在于数组中。如果存在数组中的索引就是到达目标的最短步数否则目标节点将无法被访问。
#includebits/stdc.husing namespace std;
#define ll long longconst ll MAX 1e6;// 设置最大值为1000000
vectorll 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 中倒数第二个元素的值然后将该值与计算该元素各个数字的和相加并将结果赋值给变量 nextif (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则 aif(i) ai 1其中 f(i) 表示 i 的十进制数
位和。预处理除 a 即可询问 O(1) 回答。
时间复杂度 O(n T)。
*/std::vectorint a(1000000 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 1000000; i) {if (a[i] -1)continue;int x i f(i);if (x 1000000)break; // 1000000 的位置一定是不会询问的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;
}
今天就先到这了 看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注
你们的点赞就是博主更新最大的动力 有问题可以评论或者私信呢秒回哦。
