A。

题意:给定两个字符串,把每一位都改变到第二个字符串中的相应位置,可以向上向下翻转,求最小的翻转次数。

思路:直接求出向上向下最小的步,求和就好了。

B。

题意:总共有n个数字,现在给你其中的k个数,现在让你填剩下的n-k个数,每个数的区间是1~p,问是否可以在填完之后,中位数大于等于 x,序列的总和小于等于y

思路:统计给定原序列中大于等于中位数的个数和小于中位数的个数,把剩下的数字的最大总分分配给大于等于中位数的数字和小于中位数的数字。小于中位数的填1,大于等于的填中位数。

C。

题意:有一个图,‘.’代表没有碎的冰, ‘X’代表碎了的冰,‘.’的冰走过之后会变成‘X’,‘X’的冰不能走,问是否可能到达终点 (ex,ey),并且(ex,ey)的状态是‘X’。

思路:直接从起始点开始bfs就好了。如果终点一开始就是‘X’,那就是判断是看能否到达一次,如果是‘.’ 拿就得到两次。

D。

题意:石头剪子布啊!现在有三种生物,分别是 石头,剪子,布,现在他们会互相攻击,石头会杀死剪子,剪子会杀死布,布会杀死石头,他们会等概率相遇。

给你石头剪子布的个数,求最后只剩下石头/剪子/布的概率。

思路:概率dp,d[i][j][k] 表示 当石头有i个,剪子有j个,布有k个时候的概率。

如果i存在,d[i][j][k] 可以由 d[i][j+1][k]转移得来。

如果j存在,d[i][j][k] 可以由 d[i][j][k+1]转移得来。

如果k存在,d[i][j][k] 可以由 d[i+1][j][k]转移得来。

注意他们是等概率相遇的。 那么在i,j,k的状态下,所有相遇的可能性是 1/(i*j+j*k+i*k), 那么i,j相遇的概率是(i*j)/(i*j+j*k+i*k)。

E。

题意:有一个无限长的序列,(1~n),现在有m次交换,求交换之后的逆序对数。

思路:对于任何位置的一个数,求他的逆序对数我们可以分为两部分。第一部分是发生过交换的数,第二部分是没有交换过的数。

求逆序对必然会想到树状数组,但是这个题的区间太大,直接用树状数组肯定不行,需要离散化,离散化的时候我觉得就比较巧妙了。

首先把所有的发生过交换的所有位置存起来,排序,去重,然后他们每个数所在的下标其实就是他们离散化后相对应的数值。

第一部分求的时候就是递推一下初始化。第二部分求的时候就是树状数组。

 

1年半没写啦

给博客续费了一波 好久没写了 等有时间再写一些 头条相对忙一些,自己看东西的时间短一些 公司一些工程实践也不方便在其他平台上分享 所以能写的东西真不多 &...

阅读全文

UVA 1595 – Symmetry(stl水题)

找出最左边的点 和 最右边的点。 通过这两个点 找出对称轴。 然后 枚举所有的点 看看有没有相应的对称的点存在即可。 #includ...

阅读全文

UVA 11136 – Hoax or what(set/multiset)

简单题。用set来做的话 还是比较简单的。 因为set是一个集合。 所以存在一个问题往集合内存 1  1两个相同的数的时候。会只能存上一个。 所以用一个数组来标记...

阅读全文

欢迎留言

*