备战蓝桥杯---搜索（进阶3）

看一道比较难又有趣的题：

下面是分析：

我们不妨把属性值看成点，一个装备可以看成一条边（只能选一个端点）不存在有装备属性值的当成一个点，于是我们便形成了树或图，如果是树的话，有一个点不能选，如果有>=n条边，则都可以选。

因此，我们从1的开始，如果不能全选就不选最大的，我们for出不能的最小值，答案就是减1。

那如何判断边呢，我们采用并查集或直接搜索。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[100100],x,y,m,max1;
vector<int> tu[1000020];
int dfs(int x,int fa){
    max1=max(x,max1);
    a[x]=1;
    int f=0;
    for(int i=0;i<tu[x].size();i++){
        if(fa==tu[x][i]) continue;
        if(a[tu[x][i]]==1){
            f=1;
            continue;
        }
        if(dfs(tu[x][i],x)==1) f=1;
    }
    return f;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        tu[x].push_back(y);
        tu[y].push_back(x);
        m=max(m,x);
        m=max(m,y);
    }
    int ans=m+1;
    for(int i=1;i<=m;i++){
        if(a[i]==1) continue;
        max1=0;
        if(dfs(i,0)==1) continue;
        else ans=min(ans,max1);
    }
    cout<<ans-1;
}

下面是用并查集实现：

#include<bits/stdc++.h>
using namespace std;
int n,fa[10010],x,y,m,max1[10010],b[10010],mm;
int find(int x){
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
int main(){
    cin>>n;
    for(int i=1;i<=10000;i++){
        max1[i]=i;
        b[i]=0;
        fa[i]=i;
    } 
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        int x1=find(x);
        int y1=find(y);
        if(x1==y1){
            b[x1]=1;
        }
        else{
            fa[x1]=y1;
            max1[y1]=max(max1[x1],max1[y1]);
            b[y1]=(b[y1]||b[x1]);
        }
        mm=max(mm,x);
        mm=max(mm,y);
    }
    int ans=mm+1;
    for(int i=1;i<=mm;i++){
        if(fa[i]==i){
            if(b[i]==0){
                ans=min(ans,max1[i]);
            }
        }
    }
    cout<<ans-1;
}

再看个整体二分的题：

2^24虽然可以但很慢，于是我们考虑用整体二分的思想+用0/1串存每一个字母来解决：

他们对应的二进制异或和为0.

因此，我们对前12个暴力枚举，然后再对后面几个暴力枚举，再看看原来集合里是否有相同的值，有的话就记录个数，用map存，复杂度为2^2/n*logn，取max即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[30],ans;
map<int,int> mp1;
map<int,int> mp2;
string s[30];
void dfs(int begin,int end,int tmp,int xuan,int biao){
	if(begin>end){
		if(biao==1){
		if(mp1.count(tmp)==0) mp1[tmp]=xuan;
		else{
			mp1[tmp]=max(mp1[tmp],xuan);
		}}
		else{
			if(mp2.count(tmp)==0) mp2[tmp]=xuan;
		else{
			mp2[tmp]=max(mp2[tmp],xuan);
		}	
		}
		return;
	}
	int tt=tmp^a[begin];
	dfs(begin+1,end,tt,xuan+1,biao);
	dfs(begin+1,end,tmp,xuan,biao);
	return;
}
int main(){
	while(cin>>n){
		ans=0;
		mp1.clear();
		mp2.clear();
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			cin>>s[i];
			for(int j=0;j<s[i].length();j++){
				a[i]^=1<<(s[i][j]-'A');
			}
		}
		dfs(1,n/2,0,0,1);
		dfs(n/2+1,n,0,0,2);
		for(map<int,int>::iterator it=mp2.begin();it!=mp2.end();it++){
			if(mp1.count(it->first)!=0) ans=max(ans,mp1[it->first]+it->second);
		}
		if(mp1.count(0)!=0) ans=max(ans,mp1[0]);
		if(mp2.count(0)!=0) ans=max(ans,mp2[0]);
		printf("%d\n",ans);
	}
}