19 条题解
-
2
hfz LV 8 @ 2016-09-22 00:13:11
哦啦啦，终于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;
}
-
2
这题也可以用Dfs，但要在重复访问节点时返回。我因为递归层数限制调了很久。
思路：若 A 能直接生成 B，代价为 w，则连无向边 A～B，边权为 w。用搜索方法建图之后，跑一遍 Kruskal 即可。
提示：
- 由于边很少，所以不必判重。即：A、B之间可以保留多条权值不同的边（反正 Kruskal 会进行排序）。
- 当 n>1 时，S集合内的某些元素可能可以相互生成，但代价不计。有两种方法处理。1. 在这些元素之间连接代价为 0 的边；或 2. 先把这些元素在并查集中联通。 -
1
调了一个半小时，思路大概是先用bfs生成树，然后以价值为权建图找MST；
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #define LL longlong #define FOUP(a,b,s) for(int s=a;s<=b;s++) #define FDOW(a,b,s) for(int s=a;s>=b;s++) #define R(a) scanf("%d",&a) #define RV scanf("%d%d%d",&x,&y,&z); #define WI(a) printf("%d\n",a) #define WLL(a) printf("%lld ",a) #define INF 0x7fffffff/2 #define M 1005 #define N 100005 using namespace std; int cnt,ans,maxn,maxl,l=1,r,n; int h[N],vis[N],q[N],num[15],num0,fa[N]; struct edge { int a,b,v; }w[N*100]; bool cmp(edge a,edge b) { return a.v<b.v; } int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void add(int a,int b,int v) { w[++cnt].a=a;w[cnt].b=b;w[cnt].v=v; } int number(int a[],int a0) { int sum=0; for(int i=a0;i;i--)sum=sum*10+a[i]; return sum; } void init() { R(n); for(int i=1;i<=n;i++) { int x; R(x); q[++r]=x; vis[x]=1; maxn=max(maxn,x); } FOUP(1,n-1,i)add(q[i],q[i+1],0); maxl=int(log10(maxn))+1; maxn=1; FOUP(1,maxl,i)maxn*=10; } int calc1(int a,int b) { return ((a&b)+(a^b))*2; } int calc2(int a,int b,int c) { return a+(b&c)+(b^c); } void get1(int num[],int num0) { int a=number(num,num0); FOUP(1,num0-1,i) FOUP(i+1,num0,j) if(num[i]!=num[j]) { swap(num[i],num[j]); int to=number(num,num0); int f=calc1(num[i],num[j]); add(a,to,f); add(to,a,f); swap(num[i],num[j]); if(!vis[to]) { q[++r]=to; vis[to]=1; } } } void get2(int num[],int num0) { if(num0==1)return; int tp[15]={0},tp0; int a=number(num,num0); FOUP(1,num0,i) { if(num[i]<=num[i-1]&&num[i]>=num[i+1]) { for(int j=1;j<i;j++)tp[j]=num[j]; for(int j=i;j<=num0;j++)tp[j]=num[j+1]; tp0=num0-1; int to=number(tp,tp0); int f=calc2(num[i],num[i-1],num[i+1]); add(a,to,f); add(to,a,f); if(!vis[to]) { q[++r]=to; vis[to]=1; } } } } void get3(int num[],int num0) { if(num0==maxl)return; int tp[15]={0},tp0; int a=number(num,num0); FOUP(1,num0+1,i) { if(num[i]<=num[i-1]) { for(int j=num0+1;j>i;j--)tp[j]=num[j-1]; for(int j=1;j<i;j++)tp[j]=num[j]; tp0=num0+1; FOUP(num[i],num[i-1],j) { tp[i]=j; int to=number(tp,tp0); int f=calc2(j,num[i],num[i-1]); add(a,to,f); add(to,a,f); if(!vis[to]) { q[++r]=to; vis[to]=1; } } } } } void kruskal() { FOUP(1,maxn,i)fa[i]=i; sort(w+1,w+cnt+1,cmp); FOUP(1,cnt,i) { int f1=find(w[i].a); int f2=find(w[i].b); if(f1!=f2) { ans+=w[i].v; fa[f1]=f2; } } } void solve() { int num0; while(l<=r) { int a=q[l]; num0=0; memset(num,0,sizeof(num)); while(a) { num[++num0]=a%10; a/=10; } num[0]=num[num0]; num[num0+1]=num[1]; get1(num,num0); get2(num,num0); get3(num,num0); l++; } kruskal(); WI(ans); } int main() { init(); solve(); return 0; } -
0
用bfs+Mst
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <cmath> #include <map> #include <vector> #define inf 0x7fffffff/2 #define vti vector<int> using namespace std; struct node { vector<int> k; int cost; friend bool operator <(node a,node b) { return a.cost>b.cost; } }; int n,lim,cnt,ans; map<vti,bool> book; priority_queue<node> q; void change(vti p) { for (int i = 0;i < p.size();i++) { for (int j = i+1;j < p.size();j++) { swap(p[i],p[j]); if (!book[p]) q.push((node){p,((p[i]&p[j])+(p[i]^p[j]))*2}); swap(p[i],p[j]); } } } void add(vti p) { if (p.size()>=lim) return; for (int i = 0;i < p.size();i++) { for (int j = 1;j <= 9;j++) { vti v=p; if (i==0) { if (p[p.size()-1]<=j&&j<=p[i]) { int cost=j+(p[p.size()-1]&p[i])+(p[p.size()-1]^p[i]); v.insert(v.begin(),j); if (!book[v]) q.push((node){v,cost}); } } else { if (p[i-1]<=j&&j<=p[i]) { int cost=j+(p[i-1]&p[i])+(p[i-1]^p[i]); v.insert(v.begin()+i,j); if (!book[v]) q.push((node){v,cost}); } } } } for (int j = 1;j <= 9;j++) { vti v=p; if (p[p.size()-1]<=j&&j<=p[0]) { int cost=j+(p[p.size()-1]&p[0])+(p[p.size()-1]^p[0]); v.push_back(j); if (!book[v]) q.push((node){v,cost}); } } } void delt(vti p) { if (p.size()==1) return; if (p.size()==2&&p[0]!=p[1]) return; if (p.size()==2&&p[0]==p[1]) { vti t; int cost=2*p[0]; t.push_back(p[0]); if (!book[t]) q.push((node){t,cost}); return; } for (int i = 0;i < p.size();i++) { vti v=p; if (i==0) { if (p[p.size()-1]<=p[0]&&p[0]<=p[1]) { int cost=p[0]+(p[p.size()-1]&p[1])+(p[p.size()-1]^p[1]); v.erase(v.begin()); if (!book[v]) q.push((node){v,cost}); } } else if (i==p.size()-1) { if (p[i-1]<=p[i]&&p[i]<=p[0]) { int cost=p[i]+(p[i-1]&p[0])+(p[i-1]^p[0]); v.erase(v.end()-1); if (!book[v]) q.push((node){v,cost}); } } else { if (p[i-1]<=p[i]&&p[i]<=p[i+1]) { int cost=p[i]+(p[i-1]&p[i+1])+(p[i-1]^p[i+1]); v.erase(v.begin()+i); if (!book[v]) q.push((node){v,cost}); } } } } void bfs() { while (!q.empty()) { node h=q.top(); q.pop(); if (h.k.size()>lim) continue; if (book[h.k]) continue; book[h.k]=1; ans+=h.cost; change(h.k); add(h.k); delt(h.k); } } int main() { scanf("%d",&n); vti t; for (int i = 1;i <= n;i++) { t.clear(); char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') { t.push_back(ch-'0'); ch=getchar(); } q.push((node){t,0}); lim=max(lim,(int)t.size()); } bfs(); printf("%d",ans); return 0; } -
0
fengyuchen LV 10 @ 2009-07-25 16:25:14
一个下午总算0msAC了，爽
-
0
用链表胡乱搞了47行。。
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
编译通过...
├ 测试数据 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... -
0
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
hfz
LV 8
@ 2016-09-22 00:13:11
- 1