网易互娱游戏研发工程师笔试4.11
第一题
把所有不为0的点取出来形成一个(距离，点值)的二元组，按照第一维度排序取出来直接模拟即可
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define LL long long
#define PLI pair<long long,int>
const int maxn = 510;
const int mod = 1e9 + 7;
int N,M,S,x,y;
LL L;
int MAP[maxn][maxn];
vector<PLI>P;
int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d%lld",&N,&L); P.clear();
for(int i = 1; i <= N ; i ++){
for(int j = 1; j <= N ; j ++){
scanf("%d",&MAP[i][j]);
}
}
scanf("%d%d",&x,&y);
x++;y++;
for(LL i = 1; i <= N ; i ++){
for(LL j = 1; j <= N; j ++){
if(!MAP[i][j]) continue;
P.push_back(mp((i-x)*(i-x)+(j-y)*(j-y),MAP[i][j]));
}
}
sort(P.begin(),P.end());
for(int i = 0 ; i < P.size(); i ++){
if(L * L >= P[i].fi) L += P[i].se;
else{break;}
}
cout << L << endl;
}
return 0;
}
第二题 并查集基础题，增加一维belong数组表示该点属于哪个集合即可
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define LL long long
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
int N,M,S;
int fa[maxn],num[maxn],belong[maxn];
void init(){
for(int i = 1 ; i <= N; i ++){
belong[i] = fa[i] = i;
num[i] = 1;
}
}
int find(int x){
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void Union(int a,int b){
a = find(a);
b = find(b);
if(a == b) return;
num[a] += num[b];
fa[b] = a;
}
int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M); init();
int cnt = N;
for(int i = 1; i <= M ; i ++){
int op; scanf("%d",&op);
if(op == 1){
int x,y; scanf("%d%d",&x,&y);
Union(belong[x],belong[y]);
}else if(op == 2){
int x; scanf("%d",&x);
num[find(belong[x])]--;
belong[x] = ++cnt;
fa[cnt] = cnt; num[cnt] = 1;
}else{
int x; scanf("%d",&x);
printf("%d\n",num[find(belong[x])]);
}
}
}
return 0;
}
第三题 状压dp
dp[i]表示前j位数字匹配完i这个状态的最小权，j是i中1的个数
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define LL long long
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
int N,M,S;
int a[maxn],V[maxn],P[maxn];
LL dp[1<<20];
const LL INF = 1e18;
int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(int i = 0; i < N ; i ++){
scanf("%d",&a[i]);
a[i]--;
P[a[i]] = i;
}
for(int i = 0; i < N ; i ++) scanf("%d",&V[i]);
dp[0] = 0;
int st = (1<<N) - 1;
for(int i = 1; i <= st;i ++) dp[i] = INF;
for(int i = 0;i < st; i ++){
int num = 0;
for(int j = 0; j < N; j ++) num += (i & (1 << j))>0;
for(int j = 0 ; j < N ; j ++){ //B[num]位置为j
if(i&(1<<j)) continue;
if(a[num] == j) continue;
dp[i|(1<<j)] = min(dp[i|(1<<j)],dp[i]+V[j]*abs(P[j]-num));
}
}
printf("%lld\n",dp[st]);
}
return 0;
}
不明白的可以在评论区指出
安利我的blog
#网易笔试##网易互娱##笔试题目#