特殊的密碼鎖

2022-09-22 18:28:31 字數 1335 閱讀 7631

標籤(空格分隔): 演算法競賽

總時間限制: 1000ms 記憶體限制: 1024kb

描述有一種特殊的二進位制密碼鎖,由n個相連的按鈕組成(n<30),按鈕有凹/凸兩種狀態,用手按按鈕會改變其狀態。

然而讓人頭疼的是,當你按一個按鈕時,跟它相鄰的兩個按鈕狀態也會反轉。當然,如果你按的是最左或者最右邊的按鈕,該按鈕只會影響到跟它相鄰的一個按鈕。

當前密碼鎖狀態已知,需要解決的問題是,你至少需要按多少次按鈕,才能將密碼鎖轉變為所期望的目標狀態。

輸入兩行,給出兩個由0、1組成的等長字串,表示當前/目標密碼鎖狀態,其中0代表凹,1代表凸。

輸出至少需要進行的按按鈕操作次數,如果無法實現轉變,則輸出impossible。

樣例輸入

011000

樣例輸出

1

#include 

#include

#include

#include

#define n 33

using

namespace

std;

void re(char *a,int i)

void act(char *a,int i,int length)

int main()

}if (temp[len-1]==aim[len-1]) flag=1;

}else

}if (temp[len-1]==aim[len-1]) flag=1;}}

if (flag)

else

printf("impossible\n");

return

0;}

這道題是熄燈問題的一個簡化。如果我們能遍歷所有可能的操作,我們一定可以從中找到一個答案。但是可能的組合太多了,有2^30種,計算複雜度會超了,只能想其他的辦法。還是遍歷,如果我們能縮小遍歷的範圍,或者給出更好的遍歷方法也可以。考慮到,如果採用從頭開始的遍歷方法,那麼,當前位置的鎖操作不操作,是由它前一個鎖的狀態決定的。因為如果我們從第i-1個鎖碼遍歷過來,來到第i個鎖碼,那麼現在,第i-1個鎖碼狀態如何,就只會由第i個鎖碼的狀態決定。

通過這個遞推關係,我們得知,只要確定了i=1 時的操作,後面的操作就都可以確定了。那麼,我們可不可以簡單的設定為“當i=1 時,如果碼相同就不反轉,如果碼不同就反轉”?不可以!比如說111111,目標碼000000,實際上按兩次就行了,但是按剛才的設定,會按3次。所以,我們要確定確定i=1 時的操作,就要分開考慮:按,以及不按。**中用一個兩次的for迴圈完成。

0023 特殊的方程

特殊的方程 難度級別 a 執行時間限制 1000ms 執行空間限制 51200kb 長度限制 2000000b 試題描述 剛入學的新生為了學習簡單的一元一次方程,設計了一個程式,可以自己進行方程設計。這裡只是解決一類非常簡單的一元一次方程,形如 x a b c 例如 x 900 456 234, x...

JSON中的特殊字元

使用json從後臺向前臺傳輸資料的時候,當資料本身含有一些特殊字元,會導致json資料的解析出錯。這個時候,就需要將json中的特殊字元過濾...

Linux中 的特殊用法

一 變數說明 表示在執行命令的一些引數 shell最後執行的後臺process的pid 2 最後執行的命令的結束 返回值 3 所有引數列表。...