刚做了一道小题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

刚做了一道小题

刚做了一道小题# JobHunting - 待字闺中

s*t2013-01-27 08:01

1 楼

这么冷清？

p*22013-01-27 08:01

2 楼

有一个字符串，长度n，由k个字母组成 2<=k<=26, 都是大写字母
你可以替换任意一个字符为其他的字符，问如何以最少的次数替换，使得相邻的字母不
同。需要输出最少的次数和结果。
比如
n k
6 3
ABBACC
2
ABCACA
3 2
BBB
1
BAB

b*i2013-01-27 08:01

3 楼

木有免费的office

【在 s****t 的大作中提到】

: 这么冷清？

a*o2013-01-27 08:01

4 楼

k=2时候要处理一下?

【在 p*****2 的大作中提到】

: 有一个字符串，长度n，由k个字母组成 2<=k<=26, 都是大写字母
: 你可以替换任意一个字符为其他的字符，问如何以最少的次数替换，使得相邻的字母不
: 同。需要输出最少的次数和结果。
: 比如
: n k
: 6 3
: ABBACC
: 2
: ABCACA
: 3 2

c*a2013-01-27 08:01

5 楼

inspiron不值钱。

j*y2013-01-27 08:01

6 楼

感觉 k>= 3比较好弄。 k= 2稍微还要想想。下面是 k >= 3的思路
先看 A[i], A[i + 1], A[i + 2],
case 1: A[i], A[i + 1], A[i + 2] 相同，改变 A[i + 1], 然后看
A[i + 2], A[i + 3], A[i + 4]
case 2: A[i], A[i + 1] 相同，改变 A[i], 然后看 A[i + 2], A[i + 3], A[i + 4]
case 3: A[i + 1], A[i + 2]相同, 这个时候看 A[i + 1]，A[i + 2], A[i + 3];
case 4: A[i], A[i + 1], A[i + 2]都不相同，这个时候看A[i + 2], A[i + 3], A[i
+ 4]

【在 p*****2 的大作中提到】

s*t2013-01-27 08:01

7 楼

哦 3s
差点跳了

【在 b****i 的大作中提到】

: 木有免费的office

a*o2013-01-27 08:01

8 楼

k=2也好做,就俩情况ABABABA和BABABAB
数数一下就行了

4]
[i

【在 j*****y 的大作中提到】

: 感觉 k>= 3比较好弄。 k= 2稍微还要想想。下面是 k >= 3的思路
: 先看 A[i], A[i + 1], A[i + 2],
: case 1: A[i], A[i + 1], A[i + 2] 相同，改变 A[i + 1], 然后看
: A[i + 2], A[i + 3], A[i + 4]
: case 2: A[i], A[i + 1] 相同，改变 A[i], 然后看 A[i + 2], A[i + 3], A[i + 4]
: case 3: A[i + 1], A[i + 2]相同, 这个时候看 A[i + 1]，A[i + 2], A[i + 3];
: case 4: A[i], A[i + 1], A[i + 2]都不相同，这个时候看A[i + 2], A[i + 3], A[i
: + 4]