网易互娱游戏研发工程师笔试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

https://www.cnblogs.com/Hugh-Locke/

#网易笔试##网易互娱##笔试题目#