小a與星際探索vector向量

小a與星際探索

題目描述：

連結：

https://ac.nowcoder.com/acm/contest/317/C

來源：牛客網

小a正在玩一款星際探索遊戲，小a需要駕駛着飛船從1号星球出發前往n号星球。其中每個星球有一個能量指數pi。星球i 能到達 星球j 當且僅當pi>pj。同時小a的飛船還有一個耐久度t，初始時為1号點的能量指數，若小a前往星球j，那麼飛船的耐久度會變為t⊕pj(即t異或pj，關于其定義請自行百度)小a想知道到達n号星球時耐久度最大為多少。注意：對于每個位置來說，從它出發可以到達的位置僅與兩者的能量指數p有關，與下标無關。

輸入：

第一行一個整數n，表示星球數
接下來一行有n個整數，第i個整數表示pi
           

輸出：

一個整數表示到達n号星球時最大的耐久度
若不能到達n号星球或到達時的最大耐久度為0則輸出−1
           

說明：

小a有兩種方法到達3号星球
第一種：
1→2→3，最終耐久度為457⊕456⊕23=22
第二種：
1→3，最終耐久度為457⊕23=478

1⩽n,∀pi⩽3000
           

代碼：

#include<bits/stdc++.h>

using namespace std;

const int N=3005;
int main()
{
	int n,p[N];//求異或最大（本題隻能異或比自己目前異或的數小的數，不影響異或選出來的所有的數。）上三角矩陣，最大獨立集（任何一個數不能被其他的數異或出來），求法高斯消元。 
	cin>>n;
	for(int i=0;i<n;i++)cin>>p[i];
	if(n==1)cout<<(p[0]?p[0]:-1)<<endl;
	else if(p[0]<=p[n-1])cout<<-1<<endl;
	else
	{
		vector<int>sets;
		for(int i=1;i<=n-1;i++)
		{
			if(p[i]<p[0]&&p[i]>p[n-1])
			{
				sets.push_back(p[i]);//因為隻能到達比目前星球能量指數小的星球，初始星球能量指數為p[0]，最終要求到第n個星球（能量指數為p[n-1]），是以中間的星球能量指數一定在p[0]到p[n-1]之間。
			}
		}
		if(sets.size())//這裡高斯消元的過程。
		{
			for(int i=14,k=0;i>=0;i--)//尋找第I位為1的數，讓其下标為K； 
			{
				for(int j=k;j<sets.size();j++)
				{
					if(sets[j]>>i&1)
					{
						swap(sets[j],sets[k]);
						break;
					}
				}
				if(sets[k]>>i&1)//檢查後面的數，如果該位上也為1，則讓其變為0 
				{
					for(int j=k+1;j<sets.size();j++)
					{
						if(sets[j]>>i&1)
						{
							sets[j]^=sets[k];
						}
					}
					k++;
				}
			}
		}
		int res=p[0]^p[n-1];//答案肯定包括第一個能量和最後一個能量。
		if(sets.size())//掃一遍求答案即可。
		{
			for(int i=14,k=0;i>=0;i--)
			{
				if(sets[k]>>i&1)
				{
					if(!(res>>i&1))res^=sets[k]; 
					k++;
				}
			}
		}
		if(!res)res=-1;
		cout<<res<<endl;
	}
	return 0;
}
           

2月14日。