微软2017年预科生计划在线编程笔试2

Posted by SkyHigh on April 14, 2017

微软2017年预科生计划在线编程笔试2

问题1

地址

http://hihocoder.com/contest/mstest2017april/problem/1

思路

找四条线,水平、竖直、左对角线、右对角线,然后每条线计算线上的个数,并计算attack pair:(n) * (n - 1) / 2,结果相加。

代码

#include <iostream>
#include <cstdio>  
#include <iostream>  
#include <string>  
#include <iterator>  
#include <algorithm>  
#include <vector>  
#include <cstring>  
#include <array>  
#include <queue>  
#include <set>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <map>  
using namespace std;


int row;

double solve(double p, double q) {
    p = p / 100.;
    q = q / 100.;
    // cout<<p<<" "<<q<<endl;
    double step = p;
    double res = p;
    double pre = 1.;
    int depth = 1;
    while(true) {
        pre *= (1 - step);
        step += q;
        depth++;
        res += pre * depth * min(step, 1.);
        if(step >= 1.) {
            break;
        }
    }
    return res;
}

 
int main()  
{  
    scanf("%d", &row);  
    unordered_map<int, int> mr;
    unordered_map<int, int> mc;
    unordered_map<int, int> mlr;
    unordered_map<int, int> mrl;
    int r, c;
    int res = 0;
    for(int i=0;i<row;i++) {
        cin>>r>>c;
        mr[r] += 1;
        mc[c] += 1;
        mrl[r + c] += 1;
        mlr[r - c] += 1;
    }
    for(auto p : mr) {
        int n = p.second;
        res += (n * (n - 1) / 2);
    }
    for(auto p : mc) {
        int n = p.second;
        res += (n * (n - 1) / 2);
    }
    for(auto p : mrl) {
        int n = p.second;
        res += (n * (n - 1) / 2);
    }
    for(auto p : mlr) {
        int n = p.second;
        res += (n * (n - 1) / 2);
    }
    printf("%d\n", res);
    return 0;  
}  

问题2

地址

http://hihocoder.com/contest/mstest2017april/problem/2

思路

首先,如果要造机器的话,前面先造好,再开始工作。不要一开始先工作一会儿再生产,或者一部分工作一部分生产。如果考虑时间成本的话,一开始完成任务需要N时间,生产需要Q时间,那么我相当于用1个Q去换取一半的N。那么当Q * k >= N / (2^k)的时候,说明生产的成本已经大于等于工作的成本了,这时候就要停止。

代码

#include <iostream>
#include <cstdio>  
#include <iostream>  
#include <string>  
#include <iterator>  
#include <algorithm>  
#include <vector>  
#include <cstring>  
#include <array>  
#include <queue>  
#include <set>
#include <cmath>
#include <unordered_set>
#include <map>  
#include <limits>
using namespace std;

typedef long long ll;

ll N, Q;

 
int main()  
{  
    scanf("%lld %lld", &N, &Q);  
    ll res = 1e16;
    ll k = 0;
    ll cur;
    ll h;
    while(true) {
        h = 1LL << k;
        if(h > N)
            break;
        if(N % h == 0) {
            cur = k * Q + N / h;
        }
        else {
            cur = k * Q + (N / h + 1);
        }
        res = min(res, cur);
        k++;
    }
    printf("%lld\n", res);
    return 0;  
}  

问题3

地址

http://hihocoder.com/contest/mstest2017april/problem/3

思路

每次考虑一个(A_i, B_i)对,如果A和B两者有一个比avg多,则先补充给另一方,直到其中一个达到avg(没必要全给过去,或者给到对方到达avg为止,因为这样可能会造成多余的步骤,最好的情况也是刚好没有造成多余的步骤)。然后再考虑下一对。

代码

#include <iostream>
#include <cstdio>  
#include <iostream>  
#include <string>  
#include <iterator>  
#include <algorithm>  
#include <vector>  
#include <cstring>  
#include <array>  
#include <queue>  
#include <set>
#include <cmath>
#include <unordered_set>
#include <map>  
#include <limits>
using namespace std;

typedef long long ll;

ll N;
ll avg;

ll solve(vector<ll>& A, vector<ll>& B) {
    ll move = 0;
    for(int i=0;i<N;i++) {
        ll delta = 0;
        if(A[i] > avg && B[i] < avg) {
            delta = min(avg - B[i], A[i] - avg);
            B[i] += delta;
            A[i] -= delta;
            move += delta;
        }
        else if(A[i] < avg && B[i] > avg) {
            delta = min(avg - A[i], B[i] - avg);
            A[i] += delta;
            B[i] -= delta;
            move += delta;
        }
        if(i < N-1) {
            delta = A[i] - avg;
            A[i+1] += delta;
            A[i] = avg;
            move += abs(delta);
            delta = B[i] - avg;
            B[i+1] += delta;
            B[i] = avg;
            move += abs(delta);
        }

    }
    return move;
}

 
int main()  
{  
    scanf("%lld", &N);  
    vector<ll> A;
    vector<ll> B;
    ll a, b;
    ll total = 0;
    for(int i=0;i<N;i++) {
        cin>>a>>b;
        total += a;
        total += b;
        A.push_back(a);
        B.push_back(b);
    }
    avg = total / (2LL * N);
    ll res = solve(A, B);
    printf("%lld\n", res);
    return 0;  
}  

问题4

地址

http://hihocoder.com/contest/mstest2017april/problem/4

思路

先建立一棵树,再从下往上来对树进行合并操作。对每个结点,判定:

  • 如果结点没有孩子,且IN[r]=0,则返回该结点的cost
  • 如果结点没有孩子,且IN[r]!=0,则返回-1
  • 如果结点有孩子:
    • 对结点的每个孩子判定,如果IN[child]!=0,则进行递归操作,合并该孩子结点的所有结点;
    • 这个时候已经合并完了该结点的所有孩子结点,如果这些孩子结点的IN=0 and IP!=0,则表示可用,如果不为IN!=0 or IP=0,则表示不可用,直接忽略。
    • 对该结点的问题进行01背包建模,求出到达该结点的最小cost
    • 更新该结点的C[r]=C[r] + min_cost
    • 让该结点的IN=0

代码

#include <iostream>
#include <cstdio>  
#include <iostream>  
#include <string>  
#include <iterator>  
#include <algorithm>  
#include <vector>  
#include <cstring>  
#include <array>  
#include <queue>  
#include <set>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <map>  
#include <limits>
using namespace std;

typedef long long ll;

int N;
int F[2010];
int IN[2010];
int IP[2010];
int C[2010];

int solve(unordered_map<int, vector<int> >& m, int r) {
    // 防止只有一个结点的情况,这样就考虑两种情况
    if(m.find(r) == m.end()) {
        if(IN[r] == 0)
            return C[r];
        else
            return -1;
    }
    vector<int>& childs = m[r];
    for(auto child : childs) {
        // 只有在IN不为0的情况下,这个孩子才需要进行递归查找能够得到IN[child]信息的最小的cost,否则不用
        // 因为IN=0的时候,直接可以找这个结点
        if(IN[child] != 0)
            solve(m, child);
    }

    // 下面就是用01背包来求解某个结点在得到IN[r]的信息量的前提下,cost最小
    int target = IN[r];
    int total_IP = 0, total_C = 0;
    for(auto child : childs) {
        if(IN[child] == 0 && IP[child] != 0) {
            total_IP += IP[child];
            total_C += C[child];
        }
    }
    int val = total_IP - target;
    // 该结点的孩子的IP和小于target,那么肯定无法到达该结点
    if(val < 0)
        return -1;
    // 该节点的孩子的IP和等于target,说明要kill掉所有的孩子,才能到达该结点
    if(val == 0)
        return total_C;
    int dp[val + 1];
    memset(dp, 0, sizeof(dp));
    for(auto child : childs) {
        if(IN[child] == 0 && IP[child] != 0) {
            for(int i=val;i>=IP[child];i--) {
                dp[i] = max(dp[i], dp[i - IP[child]] + C[child]);
            }
        }
    }
    // 该结点置零
    IN[r] = 0;
    // 将孩子产生的最小cost加到该结点
    C[r] += (total_C - dp[val]);
    // cout <<r<<" "<<total_C - dp[val]<<endl;
    return total_C - dp[val];
}

 
int main()  
{  
    scanf("%d", &N);  
    memset(F, 0, sizeof(F));
    memset(IN, 0, sizeof(F));
    memset(IP, 0, sizeof(F));
    memset(C, 0, sizeof(F));
    unordered_map<int, vector<int> > m;
    int f, in, ip, c;
    int root = 0;
    for(int i=1;i<=N;i++) {
        cin>>f>>in>>ip>>c;
        F[i] = f;
        IN[i] = in;
        IP[i] = ip;
        C[i] = c;
        m[f].push_back(i);
        if(f == 0)
            root = i;
    }
    int res = solve(m, root);
    if(res < 0)
        printf("%d\n", res);
    else
        printf("%d\n", C[root]);

    return 0;  
}