/ ALGORITHM

2017 微软预科生笔试

Contest Information

source: It’s from the HihoCoder

昨天刚做了 2018 的笔试，想起来之前做过 2017 的题目，顺便写一下题解。

Problem A : Queen Attack

$N$个皇后在一个无限大的棋盘上, 处于同一行，同一列或同一对角线上的两个皇后可以互相攻击。给出 $N$ 个皇后的位置，请问有多少对皇后可以互相攻击？

数据范围：
For $80\%$ of the data, $1 <= N <= 1000$
For $100\%$ of the data, $1 <= N <= 100000, 0 <= R_i, C_i <= 1000000000$

Input

5                                                                                  
1 1  
2 2  
3 3   
1 3
3 1

Output

10

Solution

转化一下题意就是，每个皇后都有 4 种属性（行号，列号，两个斜对角），若两个皇后的某一种属性值相同，则她们就可以互相攻击。所以我们统计一下每个属性值的皇后数即可。

AC code

#include<bits/stdc++.h>

using namespace std;

int N;

struct Node{
    int x, y;
    Node(){}
    Node(int x, int y):x(x), y(y){}
};                                                                                 

vector<Node> nodes;
bool enter[100005][4];
map<int,int> M[4];
int ans[4][100005];


void init()
{
    nodes.clear(); 
    for(int i=0; i<4; i++) M[i].clear();
    memset(enter,0,sizeof(enter));
    memset(ans, 0, sizeof(ans));
}

int cal(int id, int type)
{
    switch(type)
    {
    case 0:
        return nodes[id].y;
    case 1:
        return nodes[id].x;
    case 2:
        return nodes[id].y-nodes[id].x;
    case 3:
        return nodes[id].y+nodes[id].x;
    default:
        return 0;
    }
}
void solve()
{
    init();
    for(int m=0;m<4;m++)
    {
        for(int i=0; i<N; i++)
        {
            int index = cal(i,m);
            if( M[m].find(index) == M[m].end() ){
                M[m][index] = M[m].size()+1;
            }
            // cout << m << ": " << index << ": " << M[m][index] << endl;
            ans[m][M[m][index]]++;
        }
    }
    long long sum = 0;
    for(int m=0;m<4;m++)
    {
        for(int i=0; i<N; i++)
        {
            // cout << m << ": " << ans[m][i] << endl;
            sum += 1LL*ans[m][i]*(ans[m][i]-1)/2;
        }
    }
    printf("%lld\n", sum);
    
}

int main()
{
    while(~scanf("%d", &N))
    {
        int x, y;
        for(int i=0; i<N; i++){
            scanf("%d %d", &x, &y);
            nodes.push_back(Node(x, y));
        }
        solve();        
    }
}

Problem B : Diligent Robots

需要完成 $N$ 个任务, 每完成一个任务需要花费机器人一个小时，刚开始只有一个机器人，每个机器人花 $Q$ 小时可以制作一个新的机器人。请问完成 $N$ 个任务最少需要多少个小时？

数据范围：
For $70\%$ of the data, $1 <= N <= 1000000$
For $100\%$ of the data, $1 <= N <= 1000000000000, 1 <= Q <= 1000$

Input

10 1

Output

5

Solution

上来我们先判断一下什么时候两个机器人会比一个机器人更省时间：$N > Q + \frac N2 \rightarrow Q < \frac N2 $；
再比较两个机器人和三个机器人花费的时间：$(Q + \frac N2) - (Q + \frac{(N-Q)}{3}) = \frac{Q}{3} - \frac N6$；
所以当 $Q < \frac N2$ 时，优先选择两个机器人。同理可以计算出当 $ Q < \frac N4$ 时，四个机器人更省时间。所以对于给定的 $N$，我们可以计算出最少花费的时间为: $x \times Q + \frac{N}{2^x}$, $(x = \left \lfloor log_2^{\frac NQ} \right \rfloor)$

AC code

#include<bits/stdc++.h>

using namespace std;

long long N, Q;
vector<long long> base;

void init()
{
    long long num = 2LL;
    while(num<=1E12)
    {
        base.push_back(num);
        num*=2LL;
    }
}                                                                                  

int main()
{
    init();
    while(~scanf("%lld%lld", &N, &Q))
    {
        if( N/Q <= 2){printf("%lld\n", N);continue;}
        int index = lower_bound(base.begin(), base.end(), N/Q)-base.begin();
        long long ans = 1LL*index*Q + ceil(1.0*N/base[index-1]);
        printf("%lld\n", ans);
    }
}

Problem C : A Box of Coins

小 Hi 有一个大箱子，里面有 $2\times N$ 个小格子，刚开始每个小格子里都有一些硬币。每次花费一秒的时间，可以将一个格子里的一个硬币移动到这个格子旁边的格子里。请问最少花费多少时间，才能使得每个格子里的硬币数相等。（保证硬币总数是 $2\times N$ 的倍数）。

数据范围：$2 <= N <= 100000, 0 <= A_i, B_i <= 2000000000$

Input

2
3 4
6 7

Output

4

Solution

记录每个格子的信息为该格子的硬币数与目标数 ($\frac{Total}{2\times N}$) 的差值，从左往右遍历每一列格子，每次判断 $A_i, B_i$ 是否能移动硬币，然后再将剩余的值累加到下一列继续判断。这样保证了同一列的格子优先交换，使得移动次数最优。

AC code

#include <bits/stdc++.h>

using namespace std;

int N;
long long ans, Coins[100005][2];

int main()
{                                                                                  
    while(~scanf("%d", &N))
    {
        long long sum = 0;
        for(int i=1;i<=N;i++) {
            scanf("%d%d", &Coins[i][0], &Coins[i][1]);
            sum += Coins[i][0];
            sum += Coins[i][1];
        }
        long long avg = sum/2/N;

        ans = 0;
        Coins[0][0] = Coins[0][1] = 0;
        for(int i=1;i<=N;i++)
        {
            ans += abs(Coins[0][0]);
            ans += abs(Coins[0][1]);

            Coins[0][0] += Coins[i][0]-avg;
            Coins[0][1] += Coins[i][1]-avg;

            if( Coins[0][0]>0 && Coins[0][1]<0) {
                long long tmp = min(Coins[0][0], abs(Coins[0][1]));
                Coins[0][0] -= tmp, Coins[0][1] += tmp, ans += tmp;
            }
            if( Coins[0][1]>0 && Coins[0][0]<0) {
                long long tmp = min(Coins[0][1], abs(Coins[0][0]));
                Coins[0][1] -= tmp, Coins[0][0] += tmp, ans += tmp;
            }
        }
        printf("%lld\n", ans);
    }
}

Problem D : EL SUENO

小 Hi 在玩一个刺杀游戏，需要刺杀 $N$ 个高价值 NPC。除了 EL SUENO 之外，每个 NPC 都有一个上级 NPC。击杀一个 NPC 需要花费 $C$ 点刺杀能力，在击杀一个 NPC 前，需要搜集 $IN$ 点关于他的信息，击杀之后可以获得他的上级的 $IP$ 点信息。（如果一个 NPC 没有下属，那么击杀他不需要任何信息）

数据范围：
For $30\%$ of the data, $1 <= N <= 10, 0 <= IN_i, IP_i <= 100$
For $60\%$ of the data, $1 <= N <= 100, 0 <= IN_i, IP_i <= 1000$
For $100\%$ of the data, $1 <= N <= 2000, 0 <= F_i <= N, 0 <= IN_i, IP_i <= 20000, 1 <= C_i <= 1000$

Input

6
2 1 2 2                                                                            
0 4 0 2
2 0 2 5
2 0 2 6
1 0 1 2
1 0 1 3

Output

11

Solution

先解决一个小问题：对于每一个有下属的 NPC，刺杀他需要获得关于他的 $IN$ 点信息，他有 $x$ 个下属，杀死每个下属需要 $C$ 点花费，但能获得其上司的 $IP$ 个信息，求刺杀他的最小花费。这样就变成了一道很明显的 $01$ 背包 问题（需要注意背包最大容量的设定）。那么原问题就变成从叶子节点层层递归上去求解 $01$ 背包。

AC code

#include <bits/stdc++.h>

#define MaxN 2005
#define MaxM MaxN*10
#define INF 0x3f3f3f3f

using namespace std;

int N,fa[MaxN],need[MaxN],give[MaxN],cost[MaxN];

struct Edge 
{
    int u,v,next;
}edge[MaxM];
int cont, head[MaxN];

inline void add(int u, int v){
    edge[cont].u = u, edge[cont].v = v, edge[cont].next = head[u], head[u] = cont++;
}                                                                                  

int DP[40005];
int dfs(int u)
{
    if( need[u]==0 ) return cost[u]; 
    vector<int> C,W;
    int mx = 0;
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v = edge[i].v;
        if( v==fa[u] ) continue;
        int c = dfs(v), w = give[v];   
        C.push_back(c), W.push_back(w);
        mx = max(mx, w);
    }
    int n = C.size(), V = need[u]+mx;
    for(int i=1;i<=V;i++) DP[i] = INF;
    DP[0] = 0;
    for(int i=0; i<n; i++)
    {
        for(int v=V;v>=W[i];v--)
        {
            DP[v] = min(DP[v], DP[v-W[i]]+C[i]);
        }
    }
    int ans = INF;
    for(int v=need[u];v<=V;v++) ans = min(ans, DP[v]);
    return ans+cost[u]; 
} 

int root;
void solve()
{
    int ans = dfs(root);
    if(ans>=INF) ans = -1;
    printf("%d\n", ans);
}


void init()
{
    cont = 0;
    memset(head,-1,sizeof(head));
}

int main()
{
    while(~scanf("%d", &N))
    {
        init();
        for(int i=1;i<=N;i++)
        {
            scanf("%d%d%d%d", &fa[i], &need[i], &give[i], &cost[i]);
            if(fa[i]==0) {
                root = i;
                continue;
            }
            add(i, fa[i]); add(fa[i], i);
        }
        solve();
    }
}