微软苏州校招笔试题解

前言

本来向人人好友求了内推，结果没想到还要笔试，略坑。人家江神只是三月份注册过简历，直接就收到了在线面试，看来找工作就是该早作准备啊……于是为了这次笔试简单刷了刷hihoCoder，无意中撞上了岛娘、7k+等神犇出的题目，简直吓尿！
好在紧张了半天之后发现实际上笔试题还都是挺简单的水题。考虑到博客新搬迁文章不多，简单写个题解凑凑文章数吧。这些题目在hihoCoder上面虽然已经不能再提交，但还是可见的，因此这篇文章应该也不会违反什么保密规定。

题目1 : Lost in the City

简单的旋转矩形并枚举位置即可，数据量太小就是个水模拟。但是这题需要注意一点，如果存在多个可能的位置，都需要输出，因为没仔细读题WA了一发。
直接贴代码：

int n, m;
char mp[210][210];
char cur[4][4];
char bak[4][4];

void Rotate()
{
    rep(i, 3) {
        rep(j, 3) {
            bak[j][2 - i] = cur[i][j];
        }
    }
    memcpy(cur, bak, sizeof(cur));
}

bool match( int row, int col ) {
    rep(i, 3) {
        rep(j, 3) {
            if ( mp[row + i][col + j] != cur[i][j] ) return false;
        }
    }
    return true;
}

int main()
{
    //std::ios::sync_with_stdio(false);
#ifdef FUCK
    freopen( "in.txt", "r", stdin );
    //freopen( "out.txt", "w", stdout );
#endif
    while ( scanf("%d %d", &n, &m) != EOF )
    {
        rep(i, n) scanf("%s", mp[i]);
        rep(i, 3) scanf("%s", cur[i]);
        rep(i, n - 2) {
            rep(j, m - 2)  {
                rep(k, 4) {
                    if ( match(i, j) ) {
                        printf("%d %d\n", i + 2, j + 2);
                        break;
                    }
                    Rotate();
                }
            }
        }
    }
}

题目2 : HIHO Drinking Game

一眼就能看出是裸的二分查找求最小值。题目中的游戏规则虽然看起来很复杂，但是实际上只要照着题意模拟一遍即可，敲完直接过了样例，交上去1A。
代码如下：

int n, k;
int nums[100010];

bool judge( int T )
{
    int cup = 0;
    int hi = 0, ho = 0;
    rep(i, n) {
        cup += T;
        if ( cup <= nums[i] ) {
            hi++;
            cup = 0;
        } else {
            ho++;
            cup -= nums[i];
        }
    }
    return ho > hi;
}

int main()
{
    //std::ios::sync_with_stdio(false);
#ifdef FUCK
    freopen( "in.txt", "r", stdin );
    //freopen( "out.txt", "w", stdout );
#endif
    while ( scanf("%d %d", &n, &k) != EOF )
    {
        rep(i, n) scanf("%d", &nums[i]);
        int low = 0, high = 100000, ans = -1;
        while ( low < high ) {
            int mid = (low + high) / 2;
            if ( judge(mid) ) {
                ans = mid;
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        printf("%d\n", ans);
    }
}

题目3 : Divided Product

这题就有点坑了。初步看上去像是个数论的结论题，猜测可能需要应用某种DP或者母函数一类的东西，可惜这些我都不会。看着过的人越来越多，再看看数据规模，忽然意识到不对，这里面的数据规模太小了，不可能存在需要module 1,000,000,007的情况！于是再仔细想想，终于明白了——TMD这种看起来巨难，但是数据规模不大的数论题，根本就是让你直接打表啊！！！于是快速敲了个DFS搜索整数拆分，然后判断一遍是否能被M整除，再输出成数组的形式，贴进程序里直接提交，一发就过了。
只贴打表代码了：

int N;
bool num[101];
int ans[110][60];

void DFS( int n, int prev_pos ) {
    if ( n < 0 ) return;
    if ( n == 0 ) {
        LL prod = 1;
        rep(i, 101) {
            if ( num[i] ) {
                prod *= i;
            }
        }
        REP(m, 1, 51) if ( prod % m == 0 ) ans[N][m]++;
    }
    REP(i, prev_pos, 101) {
        if ( !num[i] && n >= i ) {
            num[i] = true;
            DFS(n - i, i + 1);
            num[i] = false;
        }
    }
}

int main()
{
    //std::ios::sync_with_stdio(false);
#ifdef FUCK
    freopen( "in.txt", "r", stdin );
    freopen( "out.txt", "w", stdout );
#endif
    REP(i, 1, 101) {
        N = i;
        CLR(num, 0);
        DFS(i, 1);
    }
    putchar('{');
    rep(i, 101) {
        putchar('{');
        rep(j, 51) {
            printf("%d,", ans[i][j]);
        }
        putchar('}');
        putchar(',');
    }
    putchar('}');
}