2018.05.10快手筆試程式設計題總結

做題時到最後緊張了有兩個緻命失誤，導緻沒有AC

第一個失誤是第一題第33行temp寫成了a，導緻一直L不顯示

第二個失誤是第二題輸出”don’t be discouraged”寫成了”don`t be discouraged”,題目不能複制，拼寫時don’t中的符号搞錯，一點之差！！！！

第一題 數字轉化為文字輸出

• 由于輸出漢字較為麻煩，将萬，千，百，十，零改為W,Q,B,S,L
• 輸入整數a 範圍[0,99999]
• 示例1
  • 輸入 99999
  • 輸出 9W9Q9B9S9
• 示例2
  • 輸入 10203
  • 輸出 1WL2BL3
• 示例3
  • 輸入 11
  • 輸出 1L1

#include <iostream>
#include <string>
using namespace std;

int main()
{
    int a;
    cin >> a;
    if(a< || a>)
        return ;
    if(a == )
    {
        cout << "L" << endl;
        return ;
    }
    char arr[] = {'L', 'S', 'B', 'Q', 'W'};
    string res = "";
    bool flag = false;//判斷位上為0的前面是否有值
    //比如101，十位上的0前面有值(即個位上的1) flag = true
    //比如100，十位上的0前面沒有值 flag = false
    int i = ;
    while(a != )
    {
        int temp = a%;
        if(temp != )
        {
            flag = true;
            if(i != )
                res = arr[i] + res;
            char c = '0' + temp;
            res = c + res;
        }
        else if(temp ==  && i!= && flag)
        {
            res = arr[] + res;
            flag = false;
        }
        i++;
        a /= ;
    }
    cout << res << endl;
    return ;
}
           

第二題 博弈論

• 一堆石頭，A,B兩個人拿，每人每次隻能拿2的次幂(即1,2,4,8)，拿到最後一塊石頭的人獲勝，A先拿，給出石頭數n,求A
• 先輸入數字m,表示m組樣例，接下來m行，每行輸入一個石頭數n
• 輸出為m行，獲勝輸出lucky，失敗輸出don’t be discouraged
• 示例1

  • 輸入

    3

    8

    5

    3

  • 輸出

    lucky

    lucky

    don’t be discouraged

思路很簡單，判斷n是否是3的倍數，不是的話就A能赢，否則A就輸

A是先手，考慮A的必勝态。

注意，因為任何正整數都能寫成若幹個2的整數次方幂之和。

由于規定隻能取2的某個整數次方幂，隻要你留給對手的石頭數為3的倍數時，那麼A就必赢，因為留下3的倍數時，對手有兩種情況：

1. 如果輪到對方拿石頭時隻剩3個，對方要麼取1個，要麼取2個，剩下的A全取走，win！

2. 如果輪到對方拿石頭時還剩3*k個石頭，對手不管取多少，剩下的石頭數是3*x+1或者3*x+2。輪到A時，又可以構造一個3的倍數。 是以無論哪種情況，當留給對手為3*k的時候，A是必勝的。

題目說A先抓石頭，那麼當石頭數為3的倍數時，A就輸了。否則A就能利用先手優勢将留給對方的石頭數變成3的倍數，就必勝。

#include <iostream>

using namespace std;

int main()
{
    int m;
    cin >> m;
    for(int i=; i<m; i++)
    {
        int n;
        cin >> n;
        if(n% != )
            cout << "lucky" << endl;
        else
            cout << "don't be discouraged" << endl;
    }
    return ;
}
           

參考：

組合博弈遊戲