<commit_before>--- 
layout: post 
title: 微软2017年预科生计划在线编程笔试2
date: 2017-04-14 
categories: blog 
tags: [hihocode] 
description: OJ练习
--- 

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

## 问题1

### 地址

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

### 思路

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

### 代码

```cpp
#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)的时候，说明生产的成本已经大于等于工作的成本了，这时候就要停止。

### 代码

```cpp
#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为止，因为这样可能会造成多余的步骤，最好的情况也是刚好没有造成多余的步骤）。然后再考虑下一对。

### 代码

```cpp
#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`

### 代码

```cpp
#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;  
}  
```<commit_msg>refresh<commit_after>--- 
layout: post 
title: 微软2017年预科生计划在线编程笔试2
date: 2017-04-14 
categories: blog 
tags: [hihocode] 
description: OJ练习
--- 

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

## 问题1

### 地址

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

### 思路

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

### 代码

```cpp
#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)`的时候，说明生产的成本已经大于等于工作的成本了，这时候就要停止。

### 代码

```cpp
#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`为止，因为这样可能会造成多余的步骤，最好的情况也是刚好没有造成多余的步骤）。然后再考虑下一对。

### 代码

```cpp
#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`

### 代码

```cpp
#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;  
}  
```
{'fraction_non_alphanumeric': 0.18040393013100436, 'fraction_numerical': 0.019787117903930132, 'mean_word_length': 2.058001251825579, 'pattern_counts': {'":': 0, '<': 205, '<?xml version=': 0, '>': 195, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4487021', 'n_tokens_mistral': 7145, 'n_tokens_neox': 7156, 'n_words': 1304}