微软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;
}