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

迈不过友情╰ 2022-12-08 15:45 98阅读 0赞

### 虫洞（简单） ###

[题目链接][Link 1]![题目1][1]  
![题目2][2]  
![题目3][3]  
![题目4][4]![题目6][6]  
![题目5][5]

--------------------

#### 解题步骤： ####

①、求出第 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时，我们如何解决这道难题。

[Link 1]: https://nanti.jisuanke.com/t/48484
[1]: /images/20221123/632601cee5714962b780935c655615a8.png
[2]: /images/20221123/4d87552946c847ce847f77501917bee0.png
[3]: /images/20221123/04a8dee7cedf4d77955a383a9787d852.png
[4]: https://img-blog.csdnimg.cn/20200920204750196.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70#pic_center
[6]: /images/20221123/dd2ae29e166a41c0a1eeac59b9bfc807.png
[5]: /images/20221123/32b68783c076438e8d57912d00bcaecf.png