题目大概是,有一段DNA,包含两种字符,A和T,科学家可以通过两种方式修改这种DNA,第一种是替换DNA上两个核酸的位置。第二种是直接把字符修改为另一种字符
输入两行,第一行是原始的DNA,第二行是目标DNA,保证长度是相同的
求最少的修改次数
样例输入:
ATTTAA
TTAATT
输出:3
这个题目看起来好像有点复杂,仔细一想其实很简单,就两个字符,不一样的时候可以交换,也可以更改。显然长度是一致的,没有改变长度的操作,所以很直接,如果可以交换直接交换,如果不能交换则修改。交换减少的不一样字符的数目为2,修改减少不一致的数目为1。
再来看交换,如果把A换成T,肯定有一个T被换成了A,如果把已经配对的T换成了A,那么相当于没换,因为不一样的数目没变。所以肯定是两者之间的互换。但是什么时候就不能交换了呢,显然就是所有的T已经被A交换完了,或者A被T交换完了。
如果已经有一种字符被交换完了,那么剩下的字符就只能修改了。所以统计不一样的字符数目,分开统计A不一样的时候,和T不一样的时候。交换的数目显然就是两个数中较小的数目。更改的数目就是多的数交换之后剩下的数目。所以总的修改次数,就是只管多的那个不一样的字符。
上面的例子中,两个DNA不相同的字符的索引有0,2,3,4,5。与原串的A不一样的字符索引是0,4,5。与原串的T不一样的字符索引是2,3。显然把0,4和2,3交换之后,剩下的5进行替换即可。所以就是统计与原串中A和T不一样的字符的数目,两者多的就是总的修改次数。
origin=input()
target=input()
ori={'A':0,'T':0}
for o,t in zip(origin,target):
if o!=t:
ori[o]+=1
print(max(ori['A'],ori['T']))
int main()
{
string origin, target;
cin >> origin;
cin >> target;
int a[2] = { 0,0 };
for (int i = 0; i < origin.size(); i++)
if (origin[i] != target[i])
a[origin[i] == 'A'] += 1;
cout << (a[0]>a[1]? a[0]:a[1]);
return 0;
}
这个问题,有人比较疑惑为什么自己不是使用max,也能正确提交,我分析之后,发现可能是大家使用这个公式 ( A + T + a b s ( A − T ) ) / / 2 = m a x ( A , T ) \left( A+T+abs(A-T)\right)//2=max(A,T) (A+T+abs(A−T))//2=max(A,T),具体是怎么计算的,大家看公式自己理解。
有一个抽奖箱,n张中奖券,m张不中奖券,A和B轮流抽奖,如果抽中奖券就结束。但是B每抽一次后,没抽中的话会把抽奖箱中的一张票给扔掉。如果所有的奖票都抽光了,则B获胜。A先抽,求A获胜的概率,保留4位小数
输入: n和m输出A获胜的概率
样例输入:
2 3
输出 0.6000
对于输出的0.5000的解释是,A第一次抽中的概率是2/5=0.4,第二次抽中的概率是A和B都没有抽中,概率是3/5 * 2/4这个时候剩下2张中奖券和一张不中奖券需要丢掉一张,有两种情况,丢掉一张中奖券,概率是2/3,则A下次获胜的概率是1/2,如果丢掉不中奖券,A下次获胜的概率是1。这个事件发生的概率等于 3/5 * 2/4 * (2/3 * 1/2 + 1/3 *1)。然后两次之和就是0.6000。
一回合,最多用掉三张奖券,肯定有两张是不中奖券,还有一张是丢的,可以是中奖券也可以是不中奖券。我们用掉三张之后,相当于问题分成了两种情况,n-1,m-2和n,m-3这两个子问题。而且子问题和原来的问题具有一致性,所以比较容易的写出递归代码。但是同样的问题,会出现重复计算,那么可能会想到给递归加备忘录,这就是整个算法的思路。
能否考虑自底向上的动态规划,当然可以,但是没有必要,因为处理的情况比较多。还是递归的代码处理起来简洁。而且n和m,有很多子问题是不需要计算的。如果自底向上,不好判断哪些需要计算,哪些不需要。所以选择自顶向下的计算更好一些。
处理返回情况了,当m<2的时候,因为不够一回合减两张不中奖券了,就已经可以返回了,同理n<1也可以返回了。所有的情况,因为没有下一次,所以a必须获胜,直接返回n/(n+m)。但是当m=2的时候,n=1,这个时候A也没有下次了,获胜的概率是n/(n+m)。
如果n还很多,但是m只有两张了,这个时候,显然a没抽中的话,只有m也没抽中才可以获胜,这个时候
A获胜的概率就是抽中,n/(n+2)加上A没抽中,B也没抽中的概率,就是
1
/
(
(
m
+
n
)
∗
(
m
+
n
−
1
)
)
1/((m+n)*(m+n-1))
1/((m+n)∗(m+n−1))。两者之和。
其实这里还可以用丢掉的奖券不影响A下次获胜的概率这一条规则简化一下代码,但是我笔试的时候没有考虑那么多。
n,m=[int(i) for i in input().split(' ')]
dp=[[0]*(m+1) for i in range(n+1)]
def func(n, m):
summ=m+n
if dp[n][m]:return dp[n][m]
elif m<2 or n<1 or (m==2 and n==1):
dp[n][m]=n/summ
elif m==2:
dp[n][m]=n/summ+2/(summ*summ-summ)
else:
cb=func(n, m - 3)*(m-2)/(summ-2) # 丢掉不中奖券后A获胜的概率
cr=func(n - 1, m - 2)*n/(summ-2) # 丢掉中奖券后A获胜的概率
dp[n][m]= n/summ+(cb+cr)*(m*m-m)/(summ*summ-summ) # A这次就获胜的概率+A之和获胜的概率
return dp[n][m]
print('%.4f'%func(n,m))
double f(int n, int m, vector<vector<double>> probability)
{
double sum = m + n;
if (probability[n][m])return probability[n][m];
if (m < 2 || n < 1 || (m == 2 && n == 1))probability[n][m] = n / sum;
else {
if(m==2)probability[n][m] = n / sum + 2 / (sum * sum - sum);
else {
double cb = f(n, m - 3, probability) * (m - 2) / (sum - 2); // 丢掉不中奖券后A获胜的概率
double cr = f(n - 1, m - 2, probability) * n / (sum - 2); // 丢掉中奖券后A获胜的概率
probability[n][m] = n / sum + (cb + cr) * (m * m - m) / (sum * sum - sum);
}
}
return probability[n][m];
}
int main()
{
int n, m;
cin >> n >> m;
vector<vector<double>> probability(n + 1, vector<double>(m + 1, 0));
cout << setiosflags(ios::fixed) << setprecision(4)<< f(n, m,probability);
}
由于我自己提交试用的是python,C++代码没有经过在线提交,如果发现bug,欢迎指出。