网易互娱开发11号3道笔试题题解

1. 大刀

求所有点到（X,Y）的距离，排序，然后遍历，判定是否可达有无补品，增加刀长

#include <bits/stdc++.h>

//freopen("temp.in","r",stdin);#include "utils.cpp"
using namespace std;
#define UF(i,start,end) for(auto i=start;i<end;i++)
#define DF(i,start,end) for(auto i=start;i>=end;i--)
int ri(){int a;scanf("%d",&a);return a;}//读取整数并返回
string rs(){string s;cin>>s;return s;}
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecll;
typedef vector<bool> vecb;
typedef vector<string> vecs;
typedef vector<vector<int>> vveci;

template<typename T> ostream& operator<<(ostream& os,const vector<T>& v){
for(auto t:v)
os<<t<<" ";
os<<endl;
return os;
}
template <typename T>
ostream &print(ostream &os,const T &t){
return os<<t<<endl;
}
template <typename T,typename... Args>
ostream &print(ostream &os,const T &t,const Args&... rest){
os << t <<" ";
return print(os,rest...);
}
template <typename T,typename... Args>
void PR(const T &t,const Args&... rest){
print(cout,t,rest...);
}

struct Pos{
int x,y;
int d2;//d^2
Pos(int x_,int y_,int d2_):x(x_),y(y_),d2(d2_){}
friend bool operator< (Pos p1,Pos p2){
return p1.d2<p2.d2;
}
};
int X,Y;
int dis(int i,int j){
return pow(X-i,2)+pow(Y-j,2);
}
int main(){
//PR(get_next("ababc"));
freopen("temp.in","r",stdin);
//freopen("temp.out", "w", stdout);
//test();
string s1,s2;
int T;
int M,L;

cin>>T;
while(T--){
cin>>M>>L;
vveci V(M,veci(M,0));
UF(i,0,M){
UF(j,0,M){
cin>>V[i][j];
}
}
cin>>X>>Y;//第i行
//从靠近X,Y的
veci Q(M*M,0);//将（X，Y）能抵达的区域按距离排序
vector<Pos> V2;
UF(i,0,M){
UF(j,0,M){
V2.push_back(Pos(i,j,dis(i,j)));
}
}
sort(V2.begin(),V2.end());//从低到高排序
UF(i,0,M*M){
if(V2[i].d2<=pow(L,2)){
L+=V[V2[i].x][V2[i].y];
}
}
PR(L);
}

//cout<<setprecision(2)<<ans<<endl; 设置输出总位数
//cout<<fixed<<setprecision(2)<<ans<<endl; 设置小数点后两位输出
return 0;

}

2.并查集集合操作

将X独立出来时，如果X是集合的祖先，需要从集合中再选一个当祖先

#include <bits/stdc++.h>

//freopen("temp.in","r",stdin);#include "utils.cpp"
using namespace std;
#define UF(i,start,end) for(auto i=start;i<end;i++)
#define DF(i,start,end) for(auto i=start;i>=end;i--)
int ri(){int a;scanf("%d",&a);return a;}//读取整数并返回
string rs(){string s;cin>>s;return s;}
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecll;
typedef vector<bool> vecb;
typedef vector<string> vecs;
typedef vector<vector<int>> vveci;

template<typename T> ostream& operator<<(ostream& os,const vector<T>& v){
for(auto t:v)
os<<t<<" ";
os<<endl;
return os;
}
template <typename T>
ostream &print(ostream &os,const T &t){
return os<<t<<endl;
}
template <typename T,typename... Args>
ostream &print(ostream &os,const T &t,const Args&... rest){
os << t <<" ";
return print(os,rest...);
}
template <typename T,typename... Args>
void PR(const T &t,const Args&... rest){
print(cout,t,rest...);
}

//并查集
const int MAX_SIZE = 10005;
int f[MAX_SIZE];//祖先节点
int find_root(int v){
if(f[v]==v) return v;
int z = find_root(f[v]);//找父亲的祖先
f[v] = z;
return z;
}
int N,M;
void my_print(){
UF(i,1,N+1){
cout<<f[i]<<" ";
}
cout<<endl;
}
int main(){
//PR(get_next("ababc"));
freopen("temp.in","r",stdin);
//freopen("temp.out", "w", stdout);
//test();
string s1,s2;
int T;

int X,Y;
cin>>T;
while(T--){
memset(f,-1,sizeof f);//能初始化成功吗?

cin>>N>>M;
int OP;
UF(i,1,N+1) f[i]=i;
UF(i,0,M){
cin>>OP;
if(OP==1){
cin>>X>>Y;
int a = find_root(X),b = find_root(Y);
if(a!=b){
f[b] = a;//令Y的祖先认X的祖先为祖先
}
//my_print();
}else{
cin>>X;
if(OP==2){
//如果X是祖先，就让它的子孙重新认一个
int new_z=-1;
UF(i,1,N+1){
if(i!=X and find_root(i)==X){
new_z = i;
}
}
UF(i,1,N+1){
if(i!=X and find_root(i)==X) f[i]=new_z;
}
f[X]=X;
//my_print();
}else{
int ans = 0;
X = find_root(X);
UF(i,1,N+1){
if(find_root(i)==X) ans++;
}
PR(ans);
}
}
}

}

//cout<<setprecision(2)<<ans<<endl; 设置输出总位数
//cout<<fixed<<setprecision(2)<<ans<<endl; 设置小数点后两位输出
return 0;

}

3. 最小错序排列.. 搜索--剪枝

#include <bits/stdc++.h>

//freopen("temp.in","r",stdin);#include "utils.cpp"
using namespace std;
#define UF(i,start,end) for(auto i=start;i<end;i++)
#define DF(i,start,end) for(auto i=start;i>=end;i--)
int ri(){int a;scanf("%d",&a);return a;}//读取整数并返回
string rs(){string s;cin>>s;return s;}
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecll;
typedef vector<bool> vecb;
typedef vector<string> vecs;
typedef vector<vector<int>> vveci;

template<typename T> ostream& operator<<(ostream& os,const vector<T>& v){
for(auto t:v)
os<<t<<" ";
os<<endl;
return os;
}
template <typename T>
ostream &print(ostream &os,const T &t){
return os<<t<<endl;
}
template <typename T,typename... Args>
ostream &print(ostream &os,const T &t,const Args&... rest){
os << t <<" ";
return print(os,rest...);
}
template <typename T,typename... Args>
void PR(const T &t,const Args&... rest){
print(cout,t,rest...);
}

const int MAX_SIZE = 105;

veci A(MAX_SIZE),V(MAX_SIZE);
vecb visited(MAX_SIZE);

veci M(MAX_SIZE);//M[i]表示[i,n) 剩余最小权值和
int n;
int ans;

//搜索--剪枝
void f(int k,int val){
if(k==n){
if(val<ans){
ans=val;
}
return ;
}
if(val+M[k]>=ans) return ;//这里是重点，如果当前错序值 + 后面元素的最小错序权值>=目前最优解返回
UF(i,0,n){
if(visited[i]) continue;
if(i==k) continue;
visited[i]=true;
f(k+1,val+V[A[k]-1]*abs(k-i));
visited[i]=false;
}
}

int main(){
//freopen("temp.in","r",stdin);

int T;
cin>>T;
while(T--){
cin>>n;
A.assign(n,0),V.assign(n,0),M.assign(n,0);
visited.assign(n,false);

UF(i,0,n) cin>>A[i];
UF(i,0,n) cin>>V[i];

M[n-1] = V[A[n-1]-1];
DF(i,n-2,0){
M[i]=M[i+1]+V[A[i]-1];//[i,n)元素的最小权值和(假设那些元素都乱序1位)
}

ans = INT_MAX;
f(0,0);
PR(ans);
}

//cout<<setprecision(2)<<ans<<endl; 设置输出总位数
//cout<<fixed<<setprecision(2)<<ans<<endl; 设置小数点后两位输出
return 0;

}

#网易互娱2020春招笔试#