19 条题解
-
2
hfz LV 8 @ 8 年前
哦啦啦,终于A了,粘一发C++程序
c++
#include"bits/stdc++.h"
#define LL long long
using namespace std;
const int INF=0x7f7f7f7f;
const int MAXN=100005;
struct Eg{
int x,y,w;
bool operator<(const Eg tmp)const{return w<tmp.w;}
}e[MAXN*100];
int n,cnt=0,maxl;
int a[MAXN];
int fa[MAXN];
int vis[MAXN];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void Init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){int t,l=0;
scanf("%d",&a[i]);t=a[i];
while(t){t/=10;l++;}if(l>maxl)maxl=l;
for(int j=1;j<=i-1;++j){
e[++cnt].x=a[i];e[cnt].y=a[j];e[cnt].w=0;
}
}
}
void bfs(){
queue<int> Q;int x[10];
for(int i=1;i<=n;i++)Q.push(a[i]),vis[a[i]]=1;
while(!Q.empty()){int i=Q.front(),t=i,l=0;Q.pop();
memset(x,0,sizeof(x));
while(t){t/=10;l++;}
t=i;
for(int j=l;j>=1;j--){int k=t%10;t/=10;x[j]=k;}
x[0]=x[l];x[l+1]=x[1];
for(int j=1;j<=l-1;j++)
for(int k=j+1;k<=l;k++){int w=((x[j]&x[k])+(x[j]^x[k]))*2,tmp=0;
swap(x[j],x[k]);
for(int bot=1;bot<=l;bot++)tmp=tmp*10+x[bot];
swap(x[j],x[k]);
e[++cnt].x=i;e[cnt].y=tmp;e[cnt].w=w;
if(vis[tmp]) continue;vis[tmp]=1;Q.push(tmp);
}
if(l>1){
for(int j=1;j<=l;j++){
if(x[j-1]<=x[j]&&x[j]<=x[j+1]){int w=x[j]+(x[j-1]&x[j+1])+(x[j-1]^x[j+1]),tmp=0;
for(int bot=1;bot<=l;bot++)if(bot!=j)tmp=tmp*10+x[bot];
e[++cnt].x=i;e[cnt].y=tmp;e[cnt].w=w;
if(vis[tmp])continue;vis[tmp]=1;Q.push(tmp);
}
}
}
if(l<maxl){
for(int j=0;j<=l;j++){
for(int num=x[j];num<=x[j+1];num++){int w=num+(x[j]&x[j+1])+(x[j]^x[j+1]),tmp=0;
for(int bot=1;bot<=l;bot++){
if(bot==j+1)tmp=tmp*10+num;
tmp=tmp*10+x[bot];
}
if (j==l) tmp=tmp*10+num;
e[++cnt].x=i;e[cnt].y=tmp;e[cnt].w=w;
if(vis[tmp])continue;vis[tmp]=1;Q.push(tmp);
}
}
}
}
}
void Work(){int ans=0;
bfs();sort(e+1,e+cnt+1);
for(int i=1;i<=MAXN;i++)fa[i]=i;
for(int i=1;i<=cnt;i++){int x=find(e[i].x),y=find(e[i].y);
if(x!=y) ans+=e[i].w,fa[x]=y;
}
printf("%d\n",ans);
}
int main(){
Init();
Work();
return 0;
}
-
28 年前@
这题也可以用Dfs,但要在重复访问节点时返回。我因为递归层数限制调了很久。
思路:若 A 能直接生成 B,代价为 w,则连无向边 A~B,边权为 w。用搜索方法建图之后,跑一遍 Kruskal 即可。
提示:
- 由于边很少,所以不必判重。即:A、B之间可以保留多条权值不同的边(反正 Kruskal 会进行排序)。
- 当 n>1 时,S集合内的某些元素可能可以相互生成,但代价不计。有两种方法处理。1. 在这些元素之间连接代价为 0 的边;或 2. 先把这些元素在并查集中联通。 -
16 年前@
调了一个半小时,思路大概是先用bfs生成树,然后以价值为权建图找MST;
-
06 年前@
用bfs+Mst
-
07 年前@
灰常好的题
就是码量有些大 -
011 年前@
200行左右....注意一开始的那些数字之间也要连边权为0的边...傻×忘记连了导致WA了7,8次!
-
015 年前@
pascal 170行……
膜拜 47行…… -
015 年前@
把教主的题解贴给大家看看
教主的难题(problem) BFS,MST
对于一开始只有一个数字的情况,如果A能生成B那么A向B连一条边,由于所有生成规则都是可逆的,且代价相同,所以连出的是无向边。BFS出所有能生成的数字,并构图,最后即变成了最小生成树的模型,一开始的数为最小生成树的根,生成树上的边为生成数字的过程。由于图比较稀疏,所以用Kruskal就可以。
对于多个数字的情况,只要一开始在这些数字之间连条权为0的边即可。范围较小,并且图比较一般,不一定要加什么优化。 -
015 年前@
一个下午总算0msAC了,爽
-
016 年前@
用链表胡乱搞了47行。。
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
016 年前@
愚昧害死人啊!
insert中,居然num[1]~num[L]打成num[L]~num[1]!白交2次! -
016 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 25ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:25ms
就比CODE能力...膜拜std写进3KB,我整整5KB... -
016 年前@
哈。。
1AC。。。
秒杀。。。 -
016 年前@
program p1422;
var p1,p2,wh,h,i1,r,j1,k1,wh1,wh2,wh0,max,i,j,k,m,n:longint;
f:array[0..300000]of longint;
ok:array[0..100000]of boolean;
p:array[0..300000]of longint;
a,b,c:array[0..300000]of longint;
num:array[0..8]of longint;
s,s0,s1,s2,s3:string;
ch:char;
procedure swap(i,j:longint);
var mm:longint;
begin
mm:=a[i];a[i]:=a[j];a[j]:=mm;
mm:=b[i];b[i]:=b[j];b[j]:=mm;
mm:=c[i];c[i]:=c[j];c[j]:=mm;
end;
procedure work(p,r:longint);
var i,j:longint;
begin
if p -
016 年前@
220行,累死我了...
-
016 年前@
就是像题解中写的一样
BFS+MST
BFS时要注意全部的边都要存~是存的下的~
因为~有平行边~同样两个数可能有不同的转化方法~权值不同 -
016 年前@
我是第二个AC的!!!!!!!!!!!!!!!!!!!!!!!
377行啊!!!!!!!!!!!!!!!!!!!!!!!!!! -
016 年前@
占座……
-
016 年前@
herself是何方大牛?
- 1