2020-03-24 360笔试题

1、DNA编辑。大概题意是：
输入两条特殊的DNA，每个都只由A、T组成，两条DNA长度相同。
编辑时有两种操作：
第一种：可以把A改成T，也可以把T改成A；
第二种：在本条DNA内把A、T互换，
问把第一条DNA改成第二条DNA一毛一样，需要的操作次数。
比如：
样例输入：
ATTTAA
TTAATT
输出：3
解释：需要3次，第一次把ATTAA中的A改成T ---->TTTTAA，然后两条DNA长这样：
TT TT AA
TT AA TT
下面是互换操作：
第一次互换：TT T T A A （第二条：TTAATT）
第二次互换：TT A T TA （第二条：TTAATT）

思路：
遍历两条DNA，记录同样下标，第一条中为A，第二条中为T的个数countAT，
记录同样下标，第一条中为T，第二条中为A的个数countTA，
取这两个的最大值。
（这个是100%ac的放心食用）

if __name__ == "__main__":
    # ATTTAA
    # TTAATT
    dna1 = input()
    dna2 = input()
    countAT,countTA = 0,0
    for i in range(len(dna1)):
        if dna1[i] == 'A' and dna2[i] =='T':
            countAT +=1
        elif dna1[i] == 'T' and dna2[i] =='A':
            countTA += 1
    if countAT > countTA:
        print(countAT)
    else:
        print(countTA)

大神代码7行搞定Orz
https://blog.csdn.net/m0_38065572/article/details/105082562

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']))

2、中奖
A、B俩人抽奖。n张中奖票，m张不中奖票。A、B轮流抽，有人抽中就结束。抽过的奖票就丢掉。B每次抽之后，要再抽一次，再抽的这张如果中了，不算B胜利。
如果A先抽，求A胜利的概率。
输入两个数字n、m，n是中奖票的数量，m是不中奖票数量，要求输出A获胜的概率，4位小数。
输入样例：2 3
输出：0.6000

（还没找到用dp做的大佬的题解，我暂时不太会dp，先看懂这个，等会了dp再更）

大佬的题解，思路懂了但是range范围还没懂明天继续。。

大佬题解：https://www.nowcoder.com/discuss/390708?type=all&order=time&pos=&page=1

image.png

照着写了py版本：

if __name__ == "__main__":
    sum = 0
    n,m = map(int,input().split())
    for i in range(int((m+n)/2)):
        res = float(n/(m+n-2*i))
        for j in range(2*i):
            res *= float((m - j)/(n+m-j))
        print('i = %.4f, res = %.4f' %(i,res))
        sum += res
    print("%.4f" %sum)

太长不看预警

大佬的思路是这样的：

for i in range(int((m+n)/2))

这里的i是轮次，
比如i=0，就是第一轮A中奖；i=1，第二轮A中奖
至于为什么是(m+n)/2 我也在想为什么不是/3 ……

res = float(n/(m+n-2*i))

res是在第i+1轮时，A中奖的概率。比如i=1时，res就是在A在第二轮抽中奖的概率，就是A在第一轮不中奖且B在第一轮不中奖且A在第二轮中奖！
那有小伙伴就要问了（也是昨天困扰我的问题），因为每轮B如果抽的不是奖票，会再抽走一张。那为什么可以简单粗暴用 $\frac{n}{m+n-2i}$ 来表示，这式子看起来是中奖票的数量除以本轮还剩票的数量，但本轮还剩的为什么是所有减去2i，明明B每轮如果第一次没抽中，要再抽一张，就是要抽两张，那每轮A和B一共耗费了3张奖票呀？

接下来举个例子

假如2张奖票，3张非奖票，那么

A第一轮中奖概率是2/5
A在第二轮抽中奖的概率，就是A在第一轮不中奖且B在第一轮不中奖且A在第二轮中奖：(3/5) * (2/4)* (A在第二轮中奖)
A在第二轮中奖有2种情况

B第一轮丢了一张中奖票的情况下A在第二轮中奖：
2/3 * 1/2
B第一轮丢了一张非奖票的情况下A在第二轮中奖
1/3 * 2/2
把两种情况加起来2/3 * 1/2 +1/3 * 2/2 = 2/3 ！
2/3 就是中奖票数量/本轮还剩所有票数量

接下来是不推一下不死心的推导

奖票 $n$ ，
如果B上一轮丢的是奖票： $\frac{n}{m+n-2i}$ ，
A本轮中奖概率： $\frac{n}{m+n-2i}* \frac{n-1}{m+n-2i-1}$
如果B上一轮丢的不是奖票： $\frac{m-2i}{m+n-2i}$
A本轮中奖概率：
$\frac{m-2i}{m+n-2i}* \frac{n}{m+n-2i-1}$
那么A本轮中奖概率：
$\frac{n}{m+n-2i}* \frac{n-1}{m+n-2i-1}+ \frac{m-2i}{m+n-2i}* \frac{n}{m+n-2i-1}$
= $\frac{n(n-1)+(m-2i)n}{(m+n-2i)(m+n-2i-1)}$
= $\frac{n(n-1+m-2i)}{(m+n-2i)(m+n-2i-1)}$

= $\frac{n}{m+n-2i}$

好这个式子就结束了

for j in range(2*i):

res *= float((m - j)/(n+m-j))

通过上面的推导我们知道了A在本轮中奖的概率，那还差前面几轮的概率这个题就妥了，即A在前面轮不中奖且B在前面轮也不中奖（这样游戏才能继续，A才能在本轮中奖），j就是来求大家在前面都不中奖概率的。
比如i=1的时候，游戏是第二轮，j=0,1 两个res乘起来，意思是A、B在第一轮不中奖的概率相乘。因为A、B都是人没什么区别，所以直接res就自乘了，也可以理解成前面操作了几次都没中奖的概率。j=0,1就是操作了两次。
m - j：是操作了j+1次之后，非奖票的数量（比如j=0，就是第一次的时候，非奖票有m张，j=1就是第二次的时候，非奖票有m-1张）
n+m-j ：是操作了j+1次之后，所有奖票的数量（比如j=0，就是第一次的时候，所有奖票的有n+m张，j=1就是第二次的时候，非奖票有n+m-1张，因为第一次的时候已经抽走1张啦）

如果i=2，就是游戏进行到第三轮了，j=0,1,2,3 就是第一轮A不中奖，第一轮B不中奖，第二轮A不中奖、第二轮B不中奖。

sum += res

把每个i得到的res相加，意思就是A在所有可能的轮次中奖的概率之和。

PS.关于大佬代码现在我还没想通的是i的范围，想通了我再来更。。。