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();
}
}
Subscribe to drone - 以终为始,慎终如始.
Get the latest posts delivered right to your inbox