Aimee

很恶心的一道题

我们在考场上会遇到很多题，无论多难，都要大声喊出："无所谓"。

怎么无所谓，有所谓
--scz

10分做法

爆搜

#include<iostream>
#include<cstdio> 
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int t;
int head[2001];
int zn[2001];
int tem[2001];
struct ed{
    int f;
    int to;
    int ne;
    int v;
} e[2001];
int p;
int vis[2001];
int ans[2001],now[2001];
int x,y,z;
void add(int f,int to){
    p++;
    e[p].f=f;
    e[p].ne=head[f];
    e[p].to=to;
    return ;
}
void simex(){
    for(int i=1;i<=n;++i){
        ans[i]=tem[i];
    }
}
void work(){
    for(int i=1;i<=n;++i){
        tem[zn[i]]=i;
    }
    for(int i=1;i<=n;++i){
        now[i]=tem[i]; 
    }
    int f=0;
    for(int i=1;i<=n;++i){
        if(now[i]<ans[i]){
            f=1;
            simex();
            break;
        }else{
            if(now[i]==ans[i])
            continue;
            break;
        }
    }
    return ;
}
void dfs(int now){
    if(now==n-1){
        work();
        return ;
    }
    for(int i=1;i<n;++i){
        if(!vis[i]){
            swap(zn[e[i].f],zn[e[i].to]);
            vis[i]=now+1;
            dfs(now+1);
            vis[i]=0;
            swap(zn[e[i].f],zn[e[i].to]);
        }
    }
    return ;
}
int main(){
    scanf("%d",&t);
    while(t--){
        p=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&x);
            zn[x]=i;
            head[i]=0;
            ans[i]=0x7ffffff;
        }
        for(int i=1;i<n;++i){
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        dfs(0);
        for(int i=1;i<=n;++i){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

我高考物理满分
---scz

菊花图

      一个更绕的贪心
      #include<iostream>
#include<cstdio> 
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int t;
int head[2001];
int zn[2001];
int tem[2001];
struct ed{
    int f;
    int to;
    int ne;
    int v;
} e[2001];
int p;
int vis[2001];
int ans[2001],now[2001];
int du[2001];
int fa[2001]; 
int x,y,z;
int Aimee;
int put[2001];
void add(int f,int to){
    p++;
    e[p].f=f;
    du[x]++;
    du[to]++;
    Aimee=max(Aimee,max(du[x],du[to]));
    e[p].ne=head[f];
    e[p].to=to;
    return ;
}
void simex(){
    for(int i=1;i<=n;++i){
        ans[i]=tem[i];
    }
}
int find(int x){
    return x==fa[x]? x:fa[x]=find(fa[x]);
}
void work(){
    for(int i=1;i<=n;++i){
        tem[zn[i]]=i;
    }
    for(int i=1;i<=n;++i){
        now[i]=tem[i]; 
    }
    int f=0;
    for(int i=1;i<=n;++i){
        if(now[i]<ans[i]){
            f=1;
            simex();
            break;
        }else{
            if(now[i]==ans[i])
            continue;
            break;
        }
    }
    return ;
}
void dfs(int now){
    if(now==n-1){
        work();
        return ;
    }
    for(int i=1;i<n;++i){
        if(!vis[i]){
            swap(zn[e[i].f],zn[e[i].to]);
            vis[i]=now+1;
            dfs(now+1);
            vis[i]=0;
            swap(zn[e[i].f],zn[e[i].to]);
        }
    }
    return ;
}
void com(int x,int y){
    fa[fa[find(x)]]=fa[find(y)];
    return ;
} 
//花啊 
void flower(){
    for(int i=1;i<=n;++i){
        fa[i]=i;
        now[zn[i]]=i;
        //now 意味着该数字所处的位置 
        vis[i]=0;
    }
    for(int i=1;i<n;++i){
        cout<<"i"<<i<<endl;
        for(int j=1;j<=n;++j){
            if(!vis[j]&&find(now[i])!=find(j)){
                vis[j]=1;
                put[now[i]]=j;
                //那么，就应该把这个数字扔到j上去
                //也就是put i的位置到j
                //但是，因为这是个菊花图
                //你把A扔到了B，那么B是不可能再回到A的
                //因为是菊花图，用一个并查集解决
                //就正如样例中的图
                //1肯定不能留在1，那么最好的办法是把1送到2好点上，也是就put[now[1]]=2;
                //那么这么搞 i号点的位置就会被放个 j
                //交换了
                 //同一个并查集是不能乱跑的 ，因为这是菊花图，既然在其之前没了，那么肯定是没路了
                 //但是因为中间就一个节点，其他地方随便跑
                 //只要还不在一个并查集， 那么肯定有路
                 //而在一个并查集中，那这两个点肯定不能互相抵达了
                 //也就是说对于菊花图，
                 //用数字来决定点的顺序
                 //但是由点来决定能不能跑  
                 //要是两个点在同一个并查集里
                 //那么这两个"点"之间的边肯定被走过了
                 //所以说这个"数字"只能去别的点（并查集以外了）
                 //所以说，这个点就是在确定可以往哪跑
                 //毕竟倘若自己所在的 “点”已经被vis了，那么自己现在肯定处于这个并查集和其他自由区域的
                 //交界处,也就是其他的随便走 
                com(now[i],j);
                 break;
            }
        }
        cout<<"S";
        for(int j=1;j<=n;++j){
            cout<<vis[j]<<" ";
        } 
        cout<<endl;
    }
    for(int i=1;i<n;++i){
        cout<<put[now[i]]<<" ";
    }       
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            cout<<i<<endl;
            break;
        }
    }       
}
int main(){
    scanf("%d",&t);
    while(t--){
        p=0;
        scanf("%d",&n);
        Aimee=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&x);
            du[i]=0;
            zn[x]=i;
            head[i]=0;
            ans[i]=0x7ffffff;
        }
        for(int i=1;i<n;++i){
            scanf("%d%d",&x,&y);
            add(x,y);
        }
            flower();
    }
    return 0;
}

链
这东西没有啥额外的思维难度

主要就是贪心的想法

对于每一个点，送到可行的最小编号的点上，那么问题不大

就是会得到一个边的删除先后问题的问题

？？先后，拓扑排序检查是否合法

那就没有代码了。

100pts

思路很好想？细节恶心

参考了此位大佬

#include<iostream>
#include<cstdio> 
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n;
int t;
int head[2501];
int zn[2005];
int tem[2051];
struct ed{
    int f;
    int to;
    int ne;
    int v;
} e[(2000<<1)+5];
int p;
int fa[2051]; 
int siz[2501];
int x,y,z;
int len[2505][2005],pre[2005][2005],nex[2005][2005],rt[2005][2005][2]; 
int put[2005];
int Aimee;
void add(int f, int to){
    siz[f]++;
    siz[to]++;
    e[++p].ne=head[f];
    e[p].to=to;
    head[f]=p;
    e[++p].ne=head[to];
    e[p].to=f;
    head[to]=p;
    return ;
}
void begin(){
    for(int i=1;i<=n+1;++i){
        for(int j=1;j<=n+1;++j)
        len[i][j]=nex[i][j]=pre[i][j]=rt[i][j][0]=rt[i][j][1]=0;
    }
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        add(x,y);
        rt[x][y][0]=rt[x][y][1]=y;
        rt[y][x][0]=rt[y][x][1]=x;
        len[x][y]=len[y][x]=1;
    }
}
void find(int now,int la){
    int l=rt[now][la][0],r=rt[now][la][1],ll,rr;
    int v;
    if(la==n+1){
        for(int i=head[now];i;i=e[i].ne){
            v=e[i].to;
            ll=rt[now][v][0],rr=rt[now][v][1];
            if(ll!=v||(pre[now][la]==rr&&len[now][ll]<siz[now]))
            continue;
            find(v,now);
        }
    }else{
        if(la==r){
            if(pre[now][n+1]==0&&(nex[now][n+1]!=l||len[now][l]==siz[now]))
            Aimee=min(Aimee,now);
            for(int i=head[now];i;i=e[i].ne){
                v=e[i].to;
                ll=rt[now][v][0],rr=rt[now][v][1];
                if(l==ll||ll!=v||nex[now][n+1]==v)
                continue;
                if(nex[now][n+1]==l&&pre[now][n+1]==rr&&len[now][l]+len[now][ll]<siz[now]){
                    continue;
                }
                find(v,now);
            }
        }
        else find(nex[now][la],now);
    }
}
void com(int now,int h,int t){
    int ll=rt[now][h][0],rr=rt[now][t][1];
    nex[now][h]=t;
    pre[now][t]=h;
    for(int i=ll;i&&i!=n+1;i=nex[now][i]){
        rt[now][i][0]=ll;
        rt[now][i][1]=rr;
    }
    len[now][ll]+=len[now][t];
}
bool mark(int now,int la){
    if(now==Aimee){
        pre[now][n+1]=la;
        nex[now][la]=n+1;
        return 1;
    }
    int v;
    int l=rt[now][la][0],r=rt[now][la][1],ll,rr;
    if(la==n+1){
        for(int i=head[now];i;i=e[i].ne){
            v=e[i].to;
            ll=rt[now][v][0],rr=rt[now][v][1];
            if(ll!=v||(pre[now][la]==rr&&len[now][ll]<siz[now]))
            continue;
            if(mark(v,now)){
                nex[now][n+1]=v;
                pre[now][v]=n+1;
                return 1;
            }
        }
    }else{
        if(la==r){
            for(int i=head[now];i;i=e[i].ne){
                v=e[i].to;
                ll=rt[now][v][0],rr=rt[now][v][1];
                if(l==ll||ll!=v||nex[now][n+1]==v)
                continue;
                if(nex[now][n+1]==l&&pre[now][n+1]==rr&&len[now][l]+len[now][ll]<siz[now]){
                    continue;
                }
                if(mark(v,now)){
                    com(now,la,v);
                    return 1;
                }
            }
        }else
        mark(nex[now][la],now) ;
    }
} 
signed main(){
    scanf("%d",&t);
    while(t--){
        p=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&zn[i]);
            siz[i]=0;       
            head[i]=0;
        }
        begin();
        if(n==1){
            cout<<1<<endl;
            continue;
        }
        for(int i=1;i<=n;++i){
            Aimee=n+1;
            find(zn[i],n+1);
            mark(zn[i],n+1);
            cout<<Aimee<<" "; 
        }
        cout<<endl;
    }
    return 0;
}