A-字符串ST

題目

東東有一個字符串X，該串包含偶數(shù)個字符，一半是 S 字符，一半是 T 字符
東東可以對該字符串執(zhí)行 1010000 次操作：如果存在 ST 是該串的子串，則刪除掉最左邊的 ST。
即 TSTTSS?TTSS、SSSTTT?SSTT?ST?空

Input

(2 ≦ |X| ≦ 200,000)

Output

輸出最終串的長度

Sample Input

TSTTSS

Sample Output

4

思路

類似于括號匹配，利用棧。
當(dāng)前字符s[i]為’S’時，當(dāng)前字符入棧；棧不為空且當(dāng)前字符s[i]為’T’且棧頂字符st.top()為’S’時，彈出棧頂元素。最后輸出棧中元素個數(shù)。

總結(jié)

一開始沒有想到棧，自己使用兩個變量記錄下標(biāo)模擬了上述思路的過程，但是會wa。后來忽然想起棧，又重寫了代碼，但是re，發(fā)現(xiàn)是彈出棧頂元素時沒有判斷棧為空。

代碼

#include<iostream> #include<string> #include <stack> #include<algorithm> using namespace std;int main(){string s;cin>>s;stack<char> st;for(int i=0;i<s.length();i++){if(i==0)st.push(s[i]);else{if(!st.empty()&&st.top()=='S'&&s[i]=='T'){st.pop();}else{st.push(s[i]);}}}cout<<st.size();return 0; }

---

B-東東轉(zhuǎn)魔方

題目

東東有一個二階魔方，即2×2×2的一個立方體組。立方體由八個角組成。
魔方的每一塊都用三維坐標(biāo)(h, k, l)標(biāo)記，其中h, k, l∈{0,1}。六個面的每一個都有四個小面，每個小面都有一個正整數(shù)。
對于每一步，東東可以選擇一個特定的面，并把此面順時針或逆時針轉(zhuǎn)90度。
請你判斷，是否東東可以在一個步驟還原這個魔方（每個面沒有異色）。

Input

輸入的第一行包含一個整數(shù)N（N≤30），這是測試用例的數(shù)量。
對于每個測試用例， 第 1~4 個數(shù)描述魔方的頂面，這是常見的2×2面，由（0，0，1），（0，1，1），（1，0，1），（1，1，1）標(biāo)記。四個整數(shù)對應(yīng)于上述部分。

第 5~8 個數(shù)描述前面，即（1，0，1），（1，1，1），（1，0，0），（1，1，0）的公共面。四個整數(shù) 與上述各部分相對應(yīng)。

第 9~12 個數(shù)描述底面，即（1，0，0），（1，1，0），（0，0，0），（0，1，0）的公共面。四個整數(shù)與上述各部分相對應(yīng)。

第 13~16 個數(shù)描述背面，即（0，0，0），（0，1，0），（0，0，1），（0，1），（0，1，1）的公共面。四個整數(shù)與上述各部分相對應(yīng)。

第 17~20 個數(shù)描述左面，即（0，0，0），（0，0，1），（1，0，0），（1，0，1）的公共面。給出四個整數(shù)與上述各部分相對應(yīng)。

第 21~24 個數(shù)描述了右面，即（0，1，1），（0，1，0），（1，1，1），（1，1，0）的公共面。給出四個整數(shù)與上述各部分相對應(yīng)。

換句話說，每個測試用例包含24個整數(shù)a、b、c到x。你可以展開表面以獲得平面圖，如下所示。

+ - + - + - + - + - + - + | q | r | a | b | u | v |+ - + - + - + - + - + - + | s | t | c | d | w | x |+ - + - + - + - + - + - +| e | f |+ - + - +| g | h |+ - + - +| i | j |+ - + - +| k | l |+ - + - +| m | n |+ - + - +| o | p |+ - + - +

Ouput

對于每個測試用例，魔方如果可以至多 “只轉(zhuǎn)一步” 恢復(fù)，輸出YES，則輸出NO。

Sample Input

4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 6 6 6 6 1 1 1 1 2 2 2 2 3 3 3 3 5 5 5 5 4 4 4 4 1 4 1 4 2 1 2 1 3 2 3 2 4 3 4 3 5 5 5 5 6 6 6 6 1 3 1 3 2 4 2 4 3 1 3 1 4 2 4 2 5 5 5 5 6 6 6 6

Sample Output

YES YES YES NO

思路

使用cube[]數(shù)組記錄每個方格的顏色，題目中的a～x面分別對應(yīng)cube[1]～cube[24]。
按照題目描述擺放魔方確定上下左右前后面，可以分為四種情況：

• 上下面顏色相同，需要轉(zhuǎn)前后左右面；
• 前后面顏色相同，需要轉(zhuǎn)上下前后面；
• 左右面顏色相同，需要轉(zhuǎn)上下前后面；
• 其他。

對于前三種情況，每種情況中又可以分出兩種情況：

• 順時針轉(zhuǎn)90度；
• 逆時針轉(zhuǎn)90度（即順時針轉(zhuǎn)270度）。

在代碼中，用必要條件判斷進(jìn)入四種情況的哪一個，判斷分別是：

• 前面中靠上的2個方格顏色相同，靠下的2個方格顏色相同，且兩者顏色不同；
• 上面中靠前的2個方格顏色相同，靠后的2個方格顏色相同，且兩者顏色不同；
• 上面中靠左的2個方格顏色相同，靠右的2個方格顏色相同，且兩者顏色不同。
• 其他。

對于四種情況，再轉(zhuǎn)到其對應(yīng)的順/逆時針轉(zhuǎn)90度的函數(shù)或不轉(zhuǎn)的函數(shù)，看操作后是否還原成功。
判斷是否還原成功對著折好的魔方看就好了。

總結(jié)

我太懶了，懶得折魔方。一開始想用三維坐標(biāo)記錄顏色，寫著寫著發(fā)現(xiàn)一個小魔方塊有三面，也就是三個顏色，而我只用了一個坐標(biāo)來表示一個小魔方塊，就很尷尬。
折個魔方又不費(fèi)力，為什么不折一個呢。

代碼

#include <algorithm> #include <cstdio> using namespace std; int cube[26];bool solve1(){//上下前后轉(zhuǎn)for(int i=17;i<20;i++){//左面是否同色，右面是否同色if(cube[i]!=cube[i+1]||cube[i+4]!=cube[i+5])return false;}if(cube[5]==cube[7]&&cube[6]==cube[8]&&cube[9]==cube[11]&&cube[10]==cube[12]&&cube[13]==cube[15]&&cube[14]==cube[16]){if(cube[3]==cube[6]&&cube[7]==cube[10]&&cube[11]==cube[14]&&cube[15]==cube[2])return true;if(cube[1]==cube[16]&&cube[13]==cube[12]&&cube[9]==cube[8]&&cube[5]==cube[4])return true;}return false; } bool solve2(){//上下左右轉(zhuǎn)for(int i=5;i<8;i++){//前面是否同色，后面是否同色if(cube[i]!=cube[i+1]||cube[i+8]!=cube[i+9])return false;}if(cube[21]==cube[22]&&cube[23]==cube[24]&&cube[9]==cube[10]&&cube[11]==cube[12]&&cube[17]==cube[18]&&cube[19]==cube[20]){if(cube[2]==cube[23]&&cube[22]==cube[10]&&cube[11]==cube[19]&&cube[18]==cube[3])return true;if(cube[1]==cube[20]&&cube[17]==cube[9]&&cube[12]==cube[24]&&cube[21]==cube[4])return true;}return false; } bool solve3(){//前后左右轉(zhuǎn)for(int i=1;i<4;i++){if(cube[i]!=cube[i+1]||cube[i+8]!=cube[i+9])return false;}if(cube[21]==cube[23]&&cube[22]==cube[24]&&cube[15]==cube[16]&&cube[13]==cube[14]&&cube[18]==cube[20]&&cube[17]==cube[19]){if(cube[6]==cube[24]&&cube[21]==cube[14]&&cube[15]==cube[17]&&cube[20]==cube[7])return true;if(cube[5]==cube[19]&&cube[18]==cube[13]&&cube[16]==cube[22]&&cube[23]==cube[8])return true;}return false; } bool solve4(){//不轉(zhuǎn)for(int i=1;i<4;i++){for(int j=0;j<6;j++){if(cube[i+j*4]!=cube[i+j*4+1])return false;}}return true; }bool solve(){if(cube[1]==cube[3]&&cube[2]==cube[4]&&cube[1]!=cube[2])return solve1();if(cube[1]==cube[2]&&cube[3]==cube[4]&&cube[1]!=cube[3])return solve2();if(cube[5]==cube[6]&&cube[7]==cube[8]&&cube[5]!=cube[7])return solve3();return solve4(); }int main(){int n;scanf("%d",&n);while(n--){for(int i=1;i<=24;i++)scanf("%d",&cube[i]);if(solve())printf("YES\n");elseprintf("NO\n");}return 0; }

題目鏈接

總結(jié)

以上是生活随笔為你收集整理的程序设计思维 week10 限时大模拟-魔方的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。