基础算法题——虫洞（简单版、vector）

虫洞（简单）

题目链接

解题步骤：

①、求出第 i 个星球作为中心子星系时，f[i] 的大小。
②、对每个 i 与 n - f[i] 异或后的结果相加，再对998244353取模即可得到答案。

问题关键点
求第 i 个星球 f[i] 的大小

个人解题思路：暴力
①、利用两个 vector 数组存储每个星球被哪些星球环绕的信息、将第 i 个星球看作第一类星球时，所有不同类型星球数。

vector <int> g[1010];	//记录路径
vector <int> v[1010];	//记录类型数 

②、将每个星球都看作是第一类星球，进行暴力枚举。并不断记录第 i 个星球的 f[i]。

AC代码

#include<iostream>
#include<vector>
#include<memory.h>
#define ll long long
using namespace std;
int n, x, w[1010], tmp[1010], f[1010];
const ll mod = 998244353;

vector <int> g[1010];	//记录路径
vector <int> v[1010];	//记录类型数 

//计算第x星球所有的类型数星球 
void dfs(int x, int lx){
	for(int i=0; i<g[x].size(); i++){
		v[lx].push_back(w[g[x][i]]);
		dfs(g[x][i], lx+1);
	}
	
	return;
}

int main(){
//	freopen("data.txt", "r", stdin);
	cin>>n>>x;
	
	for(int i=2; i<=n; i++){
		int a;
		cin>>a;
		g[a].push_back(i);
	}
	
	for(int i=1; i<=n; i++)
		cin>>w[i];
	
	//将每一个星球看作单独的个体，枚举 
	for(int i=1; i<=n; i++){
		dfs(i, 2);
		
		//开始组合 从第二个类型开始 
		for(int j=2; j<=n; j++){
			if(v[j].size()==0) break;
			
/*			printf("i:%d j:%d ", i, j);
			for(int k=0; k<v[j].size(); k++){
				printf("%d ", v[j][k]); 
			} 
			printf("\n");*/
			
			int flag=0;	//标志位 
			for(int k=0; k<v[j].size()&&flag==0; k++){
				for(int k2=k+1; k2<v[j].size()&&flag==0; k2++){
					int tmp = v[j][k]^v[j][k2];
					if(tmp==x){
						flag=1;
						f[i]++;
					}
				}
			}
		}
		for(int k=2; k<=n; k++){
			if(v[k].size()==0) break;
			v[k].clear();
		}
	}

//	for(int i=1; i<=n; i++)
//	cout<<f[i]<<" ";	
//	cout<<endl;
	
	ll ans=0;
	for(int i=1; i<=n; i++){
		ll tmp = i^(n-f[i]);
		ans = (ans+tmp%mod)%mod;
	}
		
	cout<<ans;
	
	return 0;
} 

总结

这道题因为 n 的数据范围较小，能够用暴力的方式解决。我们有时间不妨可以思考一下，当 n=1000000时，我们如何解决这道难题。