微软2016校园招聘4月在线笔试

算法 2016-04-10

1. Font Size

二分字体大小即可。

#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<set>
#include<queue>
#include<bitset>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long UL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) ((int)(x.size()))
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N = 1e3 + 7;
const int M = 1e4 + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const LL LINF = 1e17 + 7;
const double Pi = acos(-1.);
const double EPS = 1e-8;
int n, w, h, p, a[N];
bool check(LL S) {
    LL sum = 0;
    LL perLine = w / S;
    if (perLine == 0)
        return false;
    for (int i = 0; i < n; ++i) {
        LL li = (a[i] - 1LL) / perLine + 1LL;
        sum += li;
    }
    LL perPage = h / S;
    return sum <= perPage * p;
}
int main() {
    int TASK;
    scanf("%d", &TASK);
    while (TASK--) {
        scanf("%d%d%d%d", &n, &p, &w, &h);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        int L = 1, R = INF;
        while (L + 1 < R) {
            int MID = (L + R) >> 1;
            check(MID) ? L = MID : R = MID;
        }
        int ans = check(R) ? R : L;
        printf("%d\n", ans);
    }
    return 0;
}

2. 403 Forbidden

字典树

#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<set>
#include<queue>
#include<bitset>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long UL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) ((int)(x.size()))
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N = 1e3 + 7;
const int M = 1e4 + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const LL LINF = 1e17 + 7;
const double Pi = acos(-1.);
const double EPS = 1e-8;
int n, m;
char str[N];
struct Node {
    int st, time;
    Node *nxt[2];
    Node() {
        clear();
    }
    void clear() {
        st = 0;
        time = INF;
        nxt[0] = nxt[1] = NULL;
    }
}*rt;
Node* newNode(int st = 0) {
    Node *ret = (Node *) malloc(sizeof(Node));
    ret->st = st;
    ret->time = INF;
    ret->nxt[0] = ret->nxt[1] = NULL;
    return ret;
}
void insert(Node *nd, int x, int p, int st, int time) {
    for (int i = 31; i >= 32 - p; --i) {
        int y = ((x >> i) & 1);
        if (nd->nxt[y] == NULL)
            nd->nxt[y] = newNode();
        nd = nd->nxt[y];
    }
    if (nd->st == 0) {
        nd->st = st;
        nd->time = time;
    }
}
int check(Node *nd, int x) {
    int ret = rt->st, time = rt->time;
    for (int i = 31; i >= 0; --i) {
        int y = ((x >> i) & 1);
        if (nd->nxt[y] == NULL)
            break;
        nd = nd->nxt[y];
        if (nd->st != 0 && nd->time < time) {
            time = nd->time;
            ret = nd->st;
        }
    }
    if (time == INF)
        return 0;
    return ret;
}
void P(int x) {
    for (int i = 31; i >= 0; --i) {
        if ((i + 1) % 8 == 0)
            putchar(' ');
        printf("%d", (x >> i) & 1);
    }
    puts("");
}
int main() {
    scanf("%d %d", &n, &m);
    rt = newNode();
    for (int i = 0; i < n; ++i) {
        scanf(" %s", str);
        int st = (str[0] == 'a' ? 1 : -1);
        scanf(" %s", str);
        int x = 0, y = 0, p = 32;
        for (int j = 0; str[j]; ++j)
            if (str[j] == '/') {
                p = 0;
                while (str[++j])
                    p = p * 10 + (str[j] - '0');
                break;
            } else if ('0' <= str[j] && str[j] <= '9') {
                y = 0;
                while ('0' <= str[j] && str[j] <= '9') {
                    y = (y * 10 + (str[j] - '0'));
                    ++j;
                }
                --j;
                x = ((x << 8) | y);
            }
        insert(rt, x, p, st, i);
    }
    for (int i = 0; i < m; ++i) {
        scanf(" %s", str);
        int x = 0, y = 0;
        for (int j = 0; str[j]; ++j)
            if ('0' <= str[j] && str[j] <= '9') {
                y = 0;
                while ('0' <= str[j] && str[j] <= '9') {
                    y = y * 10 + (str[j] - '0');
                    ++j;
                }
                --j;
                x = ((x << 8) | y);
            }
        int ret = check(rt, x);
        puts(~ret ? "YES" : "NO");
    }
    return 0;
}

3. Demo Day

f[i][j]表示从(1,1)到(i,j)最少操作次数。 f[i][j]=min(f[k][j]+cost((k,j)→(i,j))+(a[i+1][j]!='b'),f[i][k]+cost((i,k)→(i,j))+(a[i][j+1]!='b'))

#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<set>
#include<queue>
#include<bitset>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long UL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) ((int)(x.size()))
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N = 1e2 + 7;
const int M = 1e6 + 7;
const int INF = 1e6 + 7;
const int MOD = 1e9 + 7;
const LL LINF = 1e17 + 7;
const double Pi = acos(-1.);
const double EPS = 1e-8;
int n, m, a[N][N], f[N][N], col[N][N], row[N][N];
char nxtChar() {
    char ch = getchar();
    while (!(ch == '.' || ch == 'b'))
        ch = getchar();
    return ch;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            a[i][j] = (nxtChar() == '.');
        }
//  for (int i = 1; i <= n; ++i) {
//      for (int j = 1; j <= m; ++j)
//          printf("%d ", a[i][j]);
//      puts("");
//  }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            row[i][j] = row[i][j - 1] + (a[i][j] ^ 1);
        }
    for (int j = 1; j <= m; ++j)
        for (int i = 1; i <= n; ++i) {
            col[j][i] = col[j][i - 1] + (a[i][j] ^ 1);
        }
    for (int j = 1; j <= m; ++j) {
        f[1][j] = row[1][j] + a[1][j + 1];
    }
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            f[i][j] = INF;
            for (int k = 1; k < i; ++k) {
                f[i][j] = min(f[i][j],
                        f[k][j] + col[j][i] - col[j][k] + a[i + 1][j]);
            }
            for (int k = 1; k < j; ++k) {
                f[i][j] = min(f[i][j],
                        f[i][k] + row[i][j] - row[i][k] + a[i][j + 1]);
            }
        }
    printf("%d", f[n][m]);
    return 0;
}

4. Building in Sandbox

放置方块的时候，判断6个方向相邻位置是否有方块。 方块的是否裸露，则反过来做，每次挖掉方块然后更新方块的状态，即是否暴露在外面。

#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<set>
#include<queue>
#include<bitset>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long UL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) ((int)(x.size()))
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N = 1e2 + 7;
const int M = 1e6 + 7;
const int INF = 2e5 + 7;
const int MOD = 1e9 + 7;
const LL LINF = 1e17 + 7;
const double Pi = acos(-1.);
const double EPS = 1e-8;
const int dx[] = { 0, 0, 0, 0, -1, 1 };
const int dy[] = { 0, 0, -1, 1, 0, 0 };
const int dz[] = { -1, 1, 0, 0, 0, 0 };
queue<int> que;
int n, p[M];
int v[N][N][N], f[N][N][N];
void init() {
    memset(f, 0, sizeof(f));
    memset(v, 0, sizeof(v));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            v[i][j][0] = 1;
        }
}
bool chk(int x) {
    return 0 <= x && x < N;
}
int F(int x, int y, int z) {
    return (z << 16) | (y << 8) | (x);
}
void D(int S, int &x, int &y, int &z) {
    x = (S & 255);
    y = ((S >> 8) & 255);
    z = ((S >> 16) & 255);
}
void bfs(int x, int y, int z) {
    int xx, yy, zz;
    while (!que.empty())
        que.pop();
    f[x][y][z] = true;
    que.push(F(x, y, z));
    while (!que.empty()) {
        D(que.front(), x, y, z);
        que.pop();
        for (int j = 0; j < 6; ++j) {
            xx = x + dx[j];
            yy = y + dy[j];
            zz = z + dz[j];
            if (chk(xx) && chk(yy) && chk(zz) && !v[xx][yy][zz]
                    && !f[xx][yy][zz]) {
                f[xx][yy][zz] = true;
                que.push(F(xx, yy, zz));
            }
        }
    }
}
bool place() {
    bool ret = true;
    for (int i = 0; i < n; ++i) {
        int x, y, z, xx, yy, zz;
        scanf("%d%d%d", &x, &y, &z);
        if (v[x][y][z] > 0)
            ret = false;
        bool flag = false;
        for (int j = 0; j < 6; ++j) {
            xx = x + dx[j];
            yy = y + dy[j];
            zz = z + dz[j];
            if (chk(xx) && chk(yy) && chk(zz) && v[xx][yy][zz] > 0) {
                flag = true;
                break;
            }
        }
        if (!flag) {
//          printf("p %d %d %d\n", x, y, z);
            ret = false;
        }
        ++v[x][y][z];
        p[i] = F(x, y, z);
    }
    return ret;
}
bool access() {
    for (int i = n - 1; i >= 0; --i) {
        int x, y, z, xx, yy, zz;
        D(p[i], x, y, z);
        bool flag = false;
        for (int j = 0; j < 6; ++j) {
            xx = x + dx[j];
            yy = y + dy[j];
            zz = z + dz[j];
            if (chk(xx) && chk(yy) && chk(zz) && f[xx][yy][zz]) {
                flag = true;
                break;
            }
        }
        if (!flag) {
//          printf("a %d %d %d\n", x, y, z);
            return false;
        }
        --v[x][y][z];
        if (!v[x][y][z])
            bfs(x, y, z);
    }
    return true;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        init();
        bool ans = place();
        if (ans) {
            bfs(N - 1, N - 1, N - 1);
            ans = access();
        }
        puts(ans ? "Yes" : "No");
    }
    return 0;
}

本文由 mcginn 创作，采用 知识共享署名 3.0，可自由转载、引用，但需署名作者且注明文章出处。

赏个馒头吧