京東2017實習生招聘線上筆試程式設計題

總結：差點忘了京東今天也有筆試了，剛開始 1h20min 在做華為的題，很簡單，但是考慮的情況很多（實際很多資料中都沒有），第三道模拟題想的比較複雜，做了 40min ，一次 AC 。

一看手機才發現還有京東的筆試，進了網址發現隻有 40min ，在 25min 内迅速做完了選擇題（貌似沒有注意到什麼有錯的地方，也可能是做題太快，沒仔細看）。

程式設計題貌似是随機配置設定的吧，有幸分到兩道比較容易寫的題，趕在交卷前寫完了。。。

PS：貌似寫了題解的，筆試都挂了，反而沒參加筆試的網易有面試。。。

（估計是基礎題答的太差，程式設計題有各種低級錯誤）

官方題解

1. 異或

題目連結

題意

異或運算是常見的二進制運算，給出兩個n位二進制數a，b。a異或b的運算依次考慮二進制的每一位，若這一位相同，那麼這一位的異或結果就是0，不同就是1。

例如a=1100, b=0100。執行a異或b的運算，a的最高位是1，b的最高位是0，兩個數字不同是以最高位異或結果是1；a和b次高位都是1，是以次高位異或為0；最後兩位它們都是0，是以異或結果也都是0。那麼a異或b的答案就是1000。

現在輸入兩個n位二進制數，輸出它們異或結果的十進制答案。上述樣例中異或的二進制結果為1000，轉化成十進制就是8。

思路 - 模拟

從高為開始模拟異或，并結果計入十進制數中。

一眼看去，像是中文冒号，結果 WA ，果斷改成英文冒号 + 空格就 AC 了。

代碼

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n, ans;
char a[], b[];

int main() {
    while( == scanf("%d%s%s", &n, a, b)) {
        ans = ;
        for(int i = ; i < n; ++i) {
            ans = (ans << ) + (a[i] == b[i] ?  : );
        }
        printf("%d\n", ans);
    }
    return ;
}
           

2. 通過考試

題目連結

題意

小明同學要參加一場考試，考試一共有n道題目，小明必須做對至少60%的題目才能通過考試。考試結束後，小明估算出每題做對的機率，p1,p2,…,pn。你能幫他算出他通過考試的機率嗎？

思路 - DP

設 dp[i][j] 表示前 i 題做對j題的機率，則狀态轉移方程為：

dp[i][j]=dp[i−1][j]∗(1−p)+dp[i−1][j−1]∗p ，處理好邊界狀态更新就行了

讀完題後感覺特别熟悉，感覺做過。交完卷後想起來在 XDOJ 做過類似的，當時還對 機率DP 了解不夠，想了好久。

代碼

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
double p, dp[][], ans;

int main() {
    while( == scanf("%d", &n)) {
        dp[][] = ;
        for(int i = ; i <= n; ++i) {
            scanf("%lf", &p);
            p /= ;
            dp[i][] = dp[i - ][] * ( - p);
            for(int j = ; j <= i; ++j) {
                dp[i][j] = dp[i - ][j] * ( - p) + dp[i - ][j - ] * p;
            }
        }
        for(int i = ceil(n * ); i <= n; ++i) {
            ans += dp[n][i];
        }
        printf("%.5lf\n", ans);
    }
    return ;
}