UVA 7263 – Today Is a Rainy Day
- 2020 年 4 月 9 日
- 筆記
Description: PDF題面:Today is a rainy day Today is a rainy day. The temperature is apparently lower than yesterday. Winter is coming. It always leaves people feeling fatigued and tired. Lee hasn』t prepared for winter yet. As he wakes up this morning, he looks out of the window. Yesterday』s shining sunlight can no longer be seen. It is dark outside. The sky looks so heavy that it may collapse down at any moment. Lee gets out of his bed, shakes his head slightly to make himself more awake. But it』s of no use for him. Then he goes to the restroom and washes up. Lee has a class in fifteen minutes. If he sets out immediately, he may gets to the classroom on time. But he is not in the mood to do so. He decides to skip class and does something more interesting to train his mind. He takes out a draft paper and writes a list of digits using a dice. It is obvious that the digits are all between 1 and 6. And then he applies two kind of modifications to the digits. The first kind is to modify one digit into another. The second kind is to modify one kind of digits into another. For example, he can modify 「12123」 to 「12121」 using the first kind of modification, or modify 「12123」 to 「13133」 using the second kind of modification. In the process of modification, all digits should be in {1, 2, 3, 4, 5, 6}; After a few modifications, he feels tired but pleased. He』s got a list of digits which is very different from the original one. Thinking of the next thing to do, Lee becomes a little excited. He is going to figure out the least number of modifications to transform the final list back to the original one using the same rules. Lee made it in a very short time. Can you do this like him? Input There are up to 100 test cases. For each test case, there are two lines containing two lists of digits, representing the original list and the final list in order. The digits are all between 1 and 6. It is guaranteed that two lists are of same length. The length will not be greater than 110. Output For each test case, output one integer, the answer. Sample Input 22345611 12345611 2234562221 1234561221 2234562211 1234561111 22345622112 12345611111 654321654321654321654321 123456123456123456123456 Sample Output 1 2 3 3 11
Problem solving: 這道題的意思就是給你兩個只有1~6這六個數字組成的字元串，有一種操作是把一個字元串中的一類字元串都換成另一個。比如說這個字元串裡面的1全部換成2，第二種操作就是單獨的換一個。都是可以任意換的，問你最少換幾次，能使第二個字元串和第一個字元串相等。
一開始信誓旦旦的跟隊友說這是一道dp的題，然後心安理得的訓練賽的時候跳過。 後來補題的時候發現，哦，原來是BFS，啊！怎麼能這麼寫，太妙了吧。（好了不BB了，我們開始討論這個解題思路
首先我們要知道因為這裡要求的步數是最小的，所以我們要儘可能地使用更換一類的操作，才會使總操作數最小。關於這個的證明，網上搜出來的題解大多沒有具體說，因為這個確實是屬於「一想就是這樣的啊」的結論。但是我們想一下，如果現在有兩個串分別是」123456「和」123455「，這個時候當然是一次，並且這一次無論是哪種操作，結果都是一樣的。但是如果這個串是」123444「和」123333「，如果你一個一個換，需要四次，但是如果你先把'3'全部換成'4'，再對那個剩下的變成4的3的處理其實就跟上一種情況說的一樣了。其實總結一句話說就是，只要換一個能解決的換一類都能解決。（僅是個人理解）
並且這個字元串中只是由1~6這六個字元串組成的，所以我們考慮每一種第二類變化的話，會有將近6^6種變化。所以我們可以通過使用一個六位的字元串來標示出來這將近6^6種變化以及變換所需要的次數計算出來並存起來，這就用到了BFS。然後枚舉每一種情亂，再看剩下會有哪些不同的數再採用一個變的那種變化，取最小值即可。
網上大部分題解說到這就丟程式碼了。可能高智商比較好明白，但是我整整想了一天才搞明白。 '通過使用一個六位的字元串來標示出來這將近6^6種變化以及變換所需要的次數計算出來並存起來'這句話就是重點，我門這個算出來的是每一位數字變化之後的情況，所以我們初始情況下首先定義一個」123456「的字元串進行bfs。這裡再說下去，會更加抽象和不好理解，我給程式碼加上了我認為的完全清晰的注釋。可以一邊看程式碼一邊看注釋理解這句話。
Code:
// 註：下面注釋中無特別說明的均表示變化一類的那種變化 #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; const int INF = 0x3f3f3f3f; string x, y; map<string, int> ma; // 記錄從」123456「變化到每種情況所需要的次數 queue<string> que; //BFS需要用到 string pre[maxn]; //存下來每一種可以變化到的情況，方便以後遍歷 int pos = 0; void init() //預處理出來每一種變化情況 { string a, b; ma["123456"] = 1; //標記123456已經出現過，避免死循環 que.push("123456"); pre[++pos] = "123456"; //存入string數組 while (!que.empty()) { string mid = que.front(), Mid = "000000"; que.pop(); for (int i = 0; i < 6; i++) //這個雙重for循環就是模擬的把所有的i+1換成j+1 { for (int j = 0; j < 6; j++) { if (i == j) //如果這兩個相等，就沒必要換下去了 continue; for (int k = 0; k < 6; k++) //只有6個字元，所以這裡循環6次就行 { if (mid[k] == '1' + i) //如果當前情況下，出現了一個跟i+1的值相等的數就需要變化成j+1 Mid[k] = '1' + j; else Mid[k] = mid[k]; //如果不是i+1，不需要變化 } if (!ma[Mid]) //如果ma[mid]為0，說明這種情況還沒記錄過 { ma[Mid] = ma[mid] + 1; //Mid這種情況是mid變化了一次過來的，所以變化次數加一 que.push(Mid); pre[++pos] = Mid; //存進字元串數組 } } } } } int solve() { int ans = INF, l = x.size(); //因為答案是一個最小值，要取min，所以初始化為一個極大值 for (int i = 1; i <= pos; i++) //遍歷每一種可以變化到的情況 { int cnt = ma[pre[i]] - 1; //這種情況下的答案初始化為已經變化了的次數，因為我們計算變化次數的時候123456也算了一次，所以要減一 for (int j = 0; j < l; j++) //遍歷需要變換的字元串的每一個字元，判斷它與當前這種變換的情況下的結果需要再進行幾次第一次變化才可以相等 { if (pre[i][y[j] - '0' - 1] != x[j]) //這一步真的是關鍵，pre[i]代表的是當前遍歷到的這種變化情況下123456每一個字元所對應的變化到的字元，因為我們一開始就是初始化的123456，所以pre[i][y[j] - '0' - 1]代表的就是123456這六個字元在這一次變化下的結果。這個理解了就很簡單了 cnt++; //如果pre[i][y[j] - '0' - 1]與x[j]不等，當前情況答案加一，因為需要一次第一種變化 } ans = min(ans, cnt); //答案每次更新為最小值 } return ans; } int main() { init(); //預處理 while (cin >> x >> y) { cout << solve() << endl; } }
可能看完了你還不是很明白，其實理解的關鍵就在於BFS預處理得到的結果以及pre[i][y[j] - '0' - 1] != x[j])的理解。 這裡我在說一遍（沒用的話也沒事，如果幫到了你我很榮幸）：BFS中從123456開始搜索，每次得到的情況都是其中一個數字變化成另外一個數字的情況。例如，pre字元串數組中會有223456，323456，111111等。代表的就是對應位置上的數字經過了ma[pre[i]]次變化之後變成的數字。初始狀態下字元串為123456，正好跟下標是對應的，所以我們可以直接用pre[i][S[i]-'0'-1]來表示當前pre[i]的情況下變化成的數字，在跟之前的字元串的這個位置的字元進行比較，如果不等，就再來一次只變化一個的操作，答案加一。
