最好的免费软件网站建设,昆山市做网站,用WordPress做网站入门课,电子商务的应用场景看一道比较难又有趣的题#xff1a; 下面是分析#xff1a;
我们不妨把属性值看成点#xff0c;一个装备可以看成一条边#xff08;只能选一个端点#xff09;不存在有装备属性值的当成一个点#xff0c;于是我们便形成了树或图#xff0c;如果是树的话#xff0c;有一…看一道比较难又有趣的题 下面是分析
我们不妨把属性值看成点一个装备可以看成一条边只能选一个端点不存在有装备属性值的当成一个点于是我们便形成了树或图如果是树的话有一个点不能选如果有n条边则都可以选。
因此我们从1的开始如果不能全选就不选最大的我们for出不能的最小值答案就是减1。
那如何判断边呢我们采用并查集或直接搜索。
下面是AC代码
#includebits/stdc.h
using namespace std;
int n,a[100100],x,y,m,max1;
vectorint tu[1000020];
int dfs(int x,int fa){max1max(x,max1);a[x]1;int f0;for(int i0;itu[x].size();i){if(fatu[x][i]) continue;if(a[tu[x][i]]1){f1;continue;}if(dfs(tu[x][i],x)1) f1;}return f;
}
int main(){cinn;for(int i1;in;i){scanf(%d%d,x,y);tu[x].push_back(y);tu[y].push_back(x);mmax(m,x);mmax(m,y);}int ansm1;for(int i1;im;i){if(a[i]1) continue;max10;if(dfs(i,0)1) continue;else ansmin(ans,max1);}coutans-1;
}
下面是用并查集实现
#includebits/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(){cinn;for(int i1;i10000;i){max1[i]i;b[i]0;fa[i]i;} for(int i1;in;i){scanf(%d%d,x,y);int x1find(x);int y1find(y);if(x1y1){b[x1]1;}else{fa[x1]y1;max1[y1]max(max1[x1],max1[y1]);b[y1](b[y1]||b[x1]);}mmmax(mm,x);mmmax(mm,y);}int ansmm1;for(int i1;imm;i){if(fa[i]i){if(b[i]0){ansmin(ans,max1[i]);}}}coutans-1;
}
再看个整体二分的题 2^24虽然可以但很慢于是我们考虑用整体二分的思想用0/1串存每一个字母来解决
他们对应的二进制异或和为0.
因此我们对前12个暴力枚举然后再对后面几个暴力枚举再看看原来集合里是否有相同的值有的话就记录个数用map存复杂度为2^2/n*logn取max即可。
下面是AC代码
#includebits/stdc.h
using namespace std;
int n,a[30],ans;
mapint,int mp1;
mapint,int mp2;
string s[30];
void dfs(int begin,int end,int tmp,int xuan,int biao){if(beginend){if(biao1){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 tttmp^a[begin];dfs(begin1,end,tt,xuan1,biao);dfs(begin1,end,tmp,xuan,biao);return;
}
int main(){while(cinn){ans0;mp1.clear();mp2.clear();memset(a,0,sizeof(a));for(int i1;in;i){cins[i];for(int j0;js[i].length();j){a[i]^1(s[i][j]-A);}}dfs(1,n/2,0,0,1);dfs(n/21,n,0,0,2);for(mapint,int::iterator itmp2.begin();it!mp2.end();it){if(mp1.count(it-first)!0) ansmax(ans,mp1[it-first]it-second);}if(mp1.count(0)!0) ansmax(ans,mp1[0]);if(mp2.count(0)!0) ansmax(ans,mp2[0]);printf(%d\n,ans);}
}
