/ Vijos / 题库 / 教主的难题 /

题解

19 条题解

  • 2
    @ 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;
    }

  • 2
    @ 8 年前

    这题也可以用Dfs，但要在重复访问节点时返回。我因为递归层数限制调了很久。
    思路：若 A 能直接生成 B，代价为 w，则连无向边 A～B，边权为 w。用搜索方法建图之后，跑一遍 Kruskal 即可。
    提示：
    - 由于边很少，所以不必判重。即：A、B之间可以保留多条权值不同的边（反正 Kruskal 会进行排序）。
    - 当 n>1 时，S集合内的某些元素可能可以相互生成，但代价不计。有两种方法处理。1. 在这些元素之间连接代价为 0 的边；或 2. 先把这些元素在并查集中联通。

  • 1
    @ 6 年前

    调了一个半小时，思路大概是先用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;
}
    Copy
  • 0
    @ 6 年前

    用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;
}
    Copy
  • 0
    @ 7 年前

    灰常好的题
    就是码量有些大

  • 0
    @ 11 年前

    200行左右....注意一开始的那些数字之间也要连边权为0的边...傻×忘记连了导致WA了7,8次！

  • 0
    @ 15 年前

    pascal 170行……

    膜拜 47行……

  • 0
    @ 15 年前

    把教主的题解贴给大家看看

    教主的难题(problem) BFS，MST

    对于一开始只有一个数字的情况，如果A能生成B那么A向B连一条边，由于所有生成规则都是可逆的，且代价相同，所以连出的是无向边。BFS出所有能生成的数字，并构图，最后即变成了最小生成树的模型，一开始的数为最小生成树的根，生成树上的边为生成数字的过程。由于图比较稀疏，所以用Kruskal就可以。

    对于多个数字的情况，只要一开始在这些数字之间连条权为0的边即可。范围较小，并且图比较一般，不一定要加什么优化。

  • 0
    @ 15 年前

    一个下午总算0msAC了，爽

  • 0
    @ 16 年前

    用链表胡乱搞了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
    @ 16 年前

    愚昧害死人啊!

    insert中,居然num[1]~num[L]打成num[L]~num[1]!白交2次!

  • 0
    @ 16 年前

    编译通过...

    ├ 测试数据 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
    @ 16 年前

    哈。。

    1AC。。。

    秒杀。。。

  • 0
    @ 16 年前

    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

  • 0
    @ 16 年前

    220行,累死我了...

  • 0
    @ 16 年前

    就是像题解中写的一样

    BFS+MST

    BFS时要注意全部的边都要存～是存的下的～

    因为～有平行边～同样两个数可能有不同的转化方法～权值不同

  • 0
    @ 16 年前

    我是第二个AC的！！！！！！！！！！！！！！！！！！！！！！！

    377行啊！！！！！！！！！！！！！！！！！！！！！！！！！！

  • 0
    @ 16 年前

    占座……

  • 0
    @ 16 年前

    herself是何方大牛？

  • 1

教主的难题

信息

ID
1422
难度
6
分类
搜索 | 树结构 | 生成树 点击显示
标签
递交数
467
已通过
131
通过率
28%
被复制
7
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1