微软10.10日笔试前三题

ms实习生，投了简历，，竟然让笔试了。面试机会估计不会有的，，所以大家放心，不和你们抢饭碗

1.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, a, b, x;
    while(scanf("%d", &n) != EOF) {
        a = 0;
        b = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            if (x & 1) ++a; else ++b;
        }
        printf("%d\n", n - (min(a, b) << 1));
    }
    return 0;
} 

#include <bits/stdc++.h>
using namespace std;

char a[100010];
char b[210][2];
int dp[100010][2][26];

int n, m;
bool conflict(char aa, char bb) {
    for (int i = 0; i < m; i++) {
        if (b[i][0] == aa && b[i][1] == bb) return true;
        if (b[i][0] == bb && b[i][1] == aa) return true;
    }
    return false;
}

int main()
{
    while(scanf("%d", &n) != EOF) {
        memset(dp, 0, sizeof(dp));
        getchar();
        for (int i = 1; i <= n; i++) {
            scanf("%c", &a[i]);
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            getchar();
            scanf("%c%c", &b[i][0], &b[i][1]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 26; j++) {
                dp[i][0][j] = dp[i-1][0][j];
                if (!conflict(a[i], j + 'a')) {
                    dp[i][1][a[i] - 'a'] = max(dp[i][1][a[i] - 'a'], dp[i-1][0][j] + 1);
                }
            }
            if (i != 1) {
                dp[i][0][a[i-1] - 'a'] = max(dp[i][0][a[i-1] - 'a'], dp[i-1][1][a[i-1] - 'a']);
            }
            if (i != 1 && !conflict(a[i], a[i-1])) {
                dp[i][1][a[i] - 'a'] = max(dp[i][1][a[i] - 'a'], dp[i-1][1][a[i-1] - 'a'] + 1);
            }
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans = max(ans, dp[n][0][i]);
        }
        ans = max(ans, dp[n][1][a[n] - 'a']);
        printf("%d\n", n - ans);
    }
    return 0;
}

3.

 #include <bits/stdc++.h>
using namespace std;

const int N = 10010;
const int M = 110;
int n, m, k;
struct Node {
    int time;
    int sn;
    int pw;
    int index;
    bool operator < (const Node &node) const {
        if (time > node.time) return true;
        if (time < node.time) return false;
        return (sn > node.sn);
    }
    Node() {}
    Node(int a1, int a2, int a3, int a4): time(a1), sn(a2), pw(a3), index(a4) {}
};
int s[N], t[N], p[N];
int o[N][M];
int w[N][M];
int ans[N];
int earliest[M];

int main()
{
    while(scanf("%d%d%d", &n, &m, &k) != EOF) {
        priority_queue<Node> Q;
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d", &s[i], &t[i], &p[i]);
            for (int j = 0; j < p[i]; j++) {
                scanf("%d%d", &o[i][j], &w[i][j]);
            }
            Q.push(Node(t[i] + k, s[i], -1, i));
        }
        for (int i = 0; i < m; i++) {
            earliest[i] = 0;
        }
        while(!Q.empty()) {
            Node now = Q.top();
            Q.pop();
            if (now.pw == p[now.index] - 1) {
                ans[now.index] = now.time - k;
                continue;
            }
            now.pw++;
            now.time = max(now.time, earliest[o[now.index][now.pw]]) + w[now.index][now.pw] + k;
            earliest[o[now.index][now.pw]] = now.time - k;
            Q.push(now);
        }
        for (int i = 0; i < n; i++) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}