NOIP2017模拟赛（二）~（四）填坑计划

时间：2022-12-17 00:06:54

NOIP2017模拟赛（二）

T1：
一开始我写的是floyd，题目讨论的时候也是这种 O(n3) 的方法。然而我后来想了想，貌似有一种 O(n+m) 的方法。对于这幅有向图，我们先DFS一遍找环，有环则输出-1，其中要求环上的所有点g值相等。确定无环之后，我们只保留 0<g[u]<=g[v]<=G 的边 (u,v) ，这就是个DAG。然后我们就是在求DAG的最长路，记忆化搜索即可。
我一开始找环的时候，以为直接搜索即可，结果严重超时。后来我发现，虽然无向图找环是线性的，但有向图并不是，如有50个点：
1 2 3 4 5
25条边全部连
6 7 8 9 10
25条边全部连
……
这样时间就是 510 的。对此，我们需要记一个点是否被搜完过vis[node]，以及它是否已经在当前搜索的路径上path[i]。DFS一个点结束后，再将vis[node]标为true。
CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=55;
const int oo=1000000001;

int C[maxn][maxn];

bool e[maxn][maxn];
int deg[maxn];
int g[maxn];

int vis[maxn];
bool path[maxn];
bool cir;

int t,n,G;

void Dfs1(int node)
{
    path[node]=true;
for (int i=1; i<=n; i++)
if ( e[node][i] && g[node]==g[i] && !vis[i] )
if ( !cir && !path[i] ) Dfs1(i);
else
            {
                cir=true;
break;
            }
    path[node]=false;
    vis[node]=true;
}

int Dfs2(int node)
{
if (vis[node]) return vis[node];
int temp=1;
for (int i=1; i<=n; i++)
if ( e[node][i] && g[node]<=g[i] && g[i]<=G )
            temp=max(temp, Dfs2(i)+1 );
return vis[node]=temp;
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);

for (int i=0; i<maxn; i++) C[i][0]=1;
for (int i=1; i<maxn; i++)
for (int j=1; j<=i; j++)
        {
            C[i][j]=C[i-1][j]+C[i-1][j-1];
if (C[i][j]>oo) C[i][j]=oo;
        }

scanf("%d",&t);
while(t--)
    {
scanf("%d%d",&n,&G);
        cir=false;
for (int i=1; i<=n; i++) deg[i]=g[i]=vis[i]=0;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
            {
char c=getchar();
while ( c!='0' && c!='1' ) c=getchar();
if (c=='0') e[i][j]=false;
else e[i][j]=true,deg[i]++;
            }

for (int i=1; i<=n; i++)
for (int j=3; j<=deg[i]; j++)
            {
                g[i]+=C[ deg[i] ][j];
if (g[i]>oo) g[i]=oo;
            }
for (int i=1; i<=n; i++)
if ( !cir && 0<g[i] && g[i]<=G && !vis[i] ) Dfs1(i);
if (cir)
        {
printf("-1\n");
continue;
        }

int ans=0;
for (int i=1; i<=n; i++) vis[i]=0;
for (int i=1; i<=n; i++)
if ( 0<g[i] && g[i]<=G ) ans=max(ans, Dfs2(i) );
printf("%d\n",ans);
    }

return 0;
}

T2：
这题是有一种贪心的方法的，我们可以先枚举要买多少员工num，然后一开始就不停地买。当员工达到num个时，就等他们攒钱和荣誉，用算出的天数更新答案。然后我猜测以算出的天数为标准，这是个单峰函数，然而我并不会严格的证明，或许我们可以感性地认识一下：假设买太少员工，攒钱的速度就会很慢，如果买太多，买员工需要耗费的金钱和天数又太多，这样必定会在某个地方取到峰值。于是我就写了个三分A掉了，时间复杂度 O(R∗log23R)
CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

int n,x,y,z,a,b;

int Get(int num)
{
int now=n,day=0,A=0;
while (now<num)
    {
while (A<z) A+=x*now,day++;
        A+=(3*x*now-z),day+=3,now++;
    }
while (A<a) A+=num*x,day++;
return day;
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);

    scanf("%d%d%d%d%d%d",&n,&x,&y,&z,&a,&b);
    a+=((b+y-1)/y)*x;
int L=n,R=21;
while (L+2<R)
    {
int mL=(L*2+R)/3;
int mR=(L+R*2)/3;
int vL=Get(mL);
int vR=Get(mR);
if (vL<vR) R=mR;
if (vL==vR) L=mL,R=mR;
if (vL>vR) L=mL;
    }
int ans=Get(L);
    ans=min(ans, Get(L+1) );
    ans=min(ans, Get(R) );
printf("%d\n",ans);

return 0;
}

NOIP2017模拟赛（三）

T2：
我在考场上写的是二分答案+Hash，时间 5002log(500) ，然而我们发现，如果我当前可行的区间是[L,R]，那么L指针右移，R指针至少不会左移。这就是尺取法的前提，于是可以用其替换掉二分答案，时间 5002 。当然，我们发现可以枚举开头，然后将色盲患者的基因扔进trie里，用每一个正常人的基因匹配，看要匹配多长才会走到一个空节点。这样虽然是 5003 ，不过我无聊也写了写代码。
CODE（Hash+尺取法）：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=510;
const int M=300509;
const long long M1=998585857;
const long long M2=311111111;
typedef long long LL;

LL w1[maxn];
LL w2[maxn];

LL val1[maxn<<1][maxn];
LL val2[maxn<<1][maxn];

struct data
{
    LL num1,num2;
int id;
} Hash[M];

char s[maxn];
int n,m;

LL Get1(int i,int x,int y)
{
    LL v=( val1[i][y]- (val1[i][x-1]*w1[y-x+1])%M1 +M1 )%M1;
return v;
}

LL Get2(int i,int x,int y)
{
    LL v=( val2[i][y]- (val2[i][x-1]*w2[y-x+1])%M2 +M2 )%M2;
return v;
}

void Push_in(LL v1,LL v2,int i)
{
    LL v=v1*M2+v2*M1;
int x=v%M;
while (Hash[x].id) x=(x+1)%M;
    Hash[x].num1=v1;
    Hash[x].num2=v2;
    Hash[x].id=i;
}

bool Check(LL v1,LL v2)
{
    LL v=v1*M2+v2*M1;
int x=v%M;
while ( Hash[x].id && ( Hash[x].num1!=v1 || Hash[x].num2!=v2 ) ) x=(x+1)%M;
if (Hash[x].id) return true;
return false;
}

void Push_out(LL v1,LL v2,int i)
{
    LL v=v1*M2+v2*M1;
int x=v%M;
while ( !Hash[x].id || Hash[x].num1!=v1 || Hash[x].num2!=v2 ) x=(x+1)%M;
    Hash[x].id=0;
}

bool Work(int x,int y)
{
for (int i=n+1; i<=n+n; i++)
    {
        LL v1=Get1(i,x,y);
        LL v2=Get2(i,x,y);
        Push_in(v1,v2,i);
    }
bool sol=true;
for (int i=1; i<=n; i++)
    {
        LL v1=Get1(i,x,y);
        LL v2=Get2(i,x,y);
if ( Check(v1,v2) )
        {
            sol=false;
break;
        }
    }
for (int i=n+1; i<=n+n; i++)
    {
        LL v1=Get1(i,x,y);
        LL v2=Get2(i,x,y);
        Push_out(v1,v2,i);
    }
return sol;
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);

    w1[0]=w2[0]=1;
for (int i=1; i<maxn; i++)
        w1[i]=(w1[i-1]*27LL)%M1,w2[i]=(w2[i-1]*27LL)%M2;

scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
    {
scanf("%s",&s);
        val1[i][0]=val2[i][0]=0;
for (int j=1; j<=m; j++)
            val1[i][j]=( val1[i][j-1]*27LL+(long long)(s[j-1]-'A'+1) )%M1,
            val2[i][j]=( val2[i][j-1]*27LL+(long long)(s[j-1]-'A'+1) )%M2;
    }

for (int i=n+1; i<=n+n; i++)
    {
scanf("%s",&s);
        val1[i][0]=val2[i][0]=0;
for (int j=1; j<=m; j++)
            val1[i][j]=( val1[i][j-1]*27LL+(long long)(s[j-1]-'A'+1) )%M1,
            val2[i][j]=( val2[i][j-1]*27LL+(long long)(s[j-1]-'A'+1) )%M2;
    }

for (int i=0; i<M; i++) Hash[i].id=0;
int ans=m,L=1,R=1;
while ( 1 )
    {
if ( !Work(L,R) )
if (R==m) break;
else R++;
else ans=min(ans,R-L+1),L++;
    }
printf("%d\n",ans);

return 0;
}

CODE（trie）：

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxm=250000;
const int maxn=510;

struct Tnode
{
    Tnode *son[4];
} tree[maxm];
Tnode *Root;
int cur;

Tnode *que[maxm];
int head,tail;

char s[maxn<<1][maxn];
int n,m;

Tnode *New_node()
{
    cur++;
for (int i=0; i<4; i++) tree[cur].son[i]=NULL;
return tree+cur;
}

int Get(char c)
{
if (c=='A') return 0;
if (c=='G') return 1;
if (c=='C') return 2;
if (c=='T') return 3;
}

void Insert(int h,int x)
{
    Tnode *P=Root;
for (int i=h; i<m; i++)
    {
int to=Get(s[x][i]);
if (!P->son[to]) P->son[to]=New_node();
        P=P->son[to];
    }
}

int Match(int h,int x)
{
    Tnode *P=Root;
int i;
for (i=h; i<m; i++)
    {
int to=Get(s[x][i]);
if (P->son[to]) P=P->son[to];
else break;
    }
if (i==m) return m;
return i-h+1;
}

int Solve(int h)
{
    cur=-1,Root=New_node();
for (int i=n+1; i<=(n<<1); i++) Insert(h,i);
int temp=1;
for (int i=1; i<=n; i++) temp=max(temp, Match(h,i) );
return temp;
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("my.out","w",stdout);

scanf("%d%d",&n,&m);
for (int i=1; i<=(n<<1); i++) scanf("%s",&s[i]);
int ans=m;
for (int i=0; i<m; i++)
    {
        ans=min(ans, Solve(i) );
int j=i;
    }
printf("%d\n",ans);

return 0;
}

T3：
之前我写的DP时间勉强卡过，而且还要用到组合数，后来在讨论的时候看到kekxy大神写了个四维DP，时间快多了。我们记f[i][j][w][s]表示当前有i个点，j条边，且第i个点向前连边，编号最小的点是w号点，而且i~i-K号点的奇偶性状态为s。我们考虑要不要i向w号点再连一条边，如果再连，就转移到f[i][j-1][w][s^(1 << K)^(1 << K-i+w)]。如果不连，我们就转移到w-1号点，变成f[i][j][w-1][s]，但如果w号点已经是i所能到达的最小的点了呢？我们就考虑将i变成i-1，但前提是i向外连了偶数条边，转移到f[i-1][j][i-2][s << 1]。注意不能在w>i-K的时候就考虑将i转移到i-1，因为我们在f[i][j][w-1][s]的时候已经考虑到了这种情况，再加一次就会算重。这样时间为 O(n2m2K+1) 。
CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=31;
const int maxk=1<<9;
const int M=1000000007;

int f[maxn][maxn][maxn][maxk];
int n,m,K;

int Get(int x)
{
return 1<<x;
}

int Dfs(int i,int j,int k,int s)
{
if (!j)
if (!s) return 1;
else return 0;
if (i==1)
if ( !j && !s ) return 1;
else return 0;
int &v=f[i][j][k][s];
if (v!=-1) return v;
int gk=Get(K),gki=Get(K+k-i);
    v=Dfs(i,j-1,k, s^gk^gki );
if ( k>1 && i-k<K ) v=(v+ Dfs(i,j,k-1,s) )%M;
else if ( !(s&Get(K)) ) v=(v+ Dfs(i-1,j,i-2,s<<1) )%M;
return v;
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);

scanf("%d%d%d",&n,&m,&K);
memset(f,-1,sizeof(f));
printf("%d\n", Dfs(n,m,n-1,0) );

return 0;
}

NOIP2017模拟赛（四）

T1：
本题我之前用的是low数组+LCA，然而可不可以不用LCA呢？在题目讨论的时候老师给出了一种用二分的方法。
我们同样先DFS出low数组，并记录dfs序，以及每一个点的子树对应的区间。删一条树边(u,v)的时候，假设fa[v]=u。如果a或b的其中一个在v的子树内，另一个不在，就要查看v的low，否则必为yes。那如果删一个点呢？若a，b都在这个点的外面或同一个儿子的子树内，则无影响，否则要查看a，b向上走所到达的c的儿子ax，bx的low。那么我们如何在不向上跳的前提下，知道a是在c的哪个儿子的子树中？我们在c处开一个动态数组vector，保存c的每一个儿子，按它们的子树区间从左到右保存。由于它们的区间互不交叉，且已排好序，我们要查询的时候，就用二分即可。
然而像我这种从来不用STL库的手写党而言，我根本就不会vector的用法。我觉得我写个treap都比写vector快，但这样显得很傻逼，有没有什么既用静态数组二分，又不爆空间的方法呢？我想起了我之前写过的一篇NOIP2016Day1T2的深入思考。当我们有很多个小数组需要二分，总空间不超过某个值时，我们可以把这些小数组映射到一个大数组上：
NOIP2017模拟赛（二）~（四）填坑计划
然后我们再记每一个小数组的起始结束位置L，R即可。时间O(nlog(n))。
CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=100100;
const int maxm=500100;

struct edge
{
int obj;
    edge *Next;
} e[maxm<<1];
edge *head[maxn];
int cur=-1;

int bot[maxn<<1];
int L[maxn];
int R[maxn];

int st[maxn];
int ed[maxn];
int Time=0;

int fa[maxn];
int low[maxn];
int n,m,q;

void Add(int x,int y)
{
    cur++;
    e[cur].obj=y;
    e[cur].Next=head[x];
    head[x]=e+cur;
}

void Dfs(int node)
{
    st[node]=++Time;
    low[node]=st[node];
for (edge *p=head[node]; p; p=p->Next)
    {
int son=p->obj;
if (son!=fa[node])
        {
if (!st[son]) fa[son]=node,Dfs(son);
            low[node]=min(low[node],low[son]);
        }
    }
    ed[node]=Time;
}

bool In(int x,int y)
{
return st[x]<=st[y] && st[y]<=ed[x];
}

int Find(int x,int y)
{
int l=L[x],r=R[x];
if (st[y]>ed[ bot[r] ]) return 0;
while (l+1<r)
    {
int mid=(l+r)>>1;
if (st[y]<=ed[ bot[mid] ]) r=mid;
else l=mid;
    }
if (st[y]>=st[ bot[r] ]) return bot[r];
return 0;
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);

scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) head[i]=NULL;
for (int i=1; i<=m; i++)
    {
int x,y;
scanf("%d%d",&x,&y);
        Add(x,y);
        Add(y,x);
    }

    fa[1]=0;
    Dfs(1);

    cur=0;
for (int i=1; i<=n; i++)
    {
        L[i]=R[i]=++cur;
for (edge *p=head[i]; p; p=p->Next)
        {
int son=p->obj;
if (fa[son]==i)
            {
                bot[++cur]=son;
                R[i]=cur;
            }
        }
    }

scanf("%d",&q);
while (q--)
    {
int id;
scanf("%d",&id);
if (id==1)
        {
int a,b,u,v;
scanf("%d%d%d%d",&a,&b,&u,&v);
if ( fa[u]!=v && fa[v]!=u )
            {
printf("yes\n");
continue;
            }
if (fa[u]!=v) swap(u,v);
if ( In(u,a)^In(u,b) )
if (low[u]!=st[u]) printf("yes\n");
else printf("no\n");
else printf("yes\n");
        }
else
        {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
            a=Find(c,a);
            b=Find(c,b);
if ( a && a==b ) printf("yes\n");
else
            {
bool sol=true;
if ( a && low[a]>=st[c] ) sol=false;
if ( b && low[b]>=st[c] ) sol=false;
if (sol) printf("yes\n");
else printf("no\n");
            }
        }
    }

return 0;
}

T3：
这题能不能叫一题多解呢？我觉得不能，因为本质上在求字典序最小的时候都要用到贪心。总之摘录一下别人的方法。
fzh：我也是二分答案+贪心，二分后从小到大枚举。到h[i]的时候，先看一下它是否左右两路都能加进去（h[i]-h[L]<=mid，h[i]-h[R]<=mid），如果有一边不能则返回false。接下来看一下h[i+1]是否两边都能加进，有一边不能（假设是左边，即h[i+1]-h[L]>mid）则要求必须将h[i]加进左边，否则没办法往后做。如果没有要求h[i]必须要加哪边，我们就加到左右两边中高度低的一边（这样肯定比加到高的那边更优）。要求字典序最小的时候，将右边点的尽可能拉到左边，然后从左到右输出即可。
kekxy：先将h[1]，h[3]，h[5]……加一边；h[2]，h[4]，h[6]加另一边，得到答案（这样肯定最优）。然后要求字典序最小，我们就从小到大枚举，能加进左边就加，如果它加进左边导致下一个加不进右边，它就要加进右边。
话说，上面的两种方法本质上和我的方法差(yi)不(mu)多(yi)嘛(yang)。于是我就没有写代码……
tututu：我们先二分答案mid，然后拆点（i拆为入点i与出点i+N，i连向i+N，边的容量为1），连边（ i<j 且 h[j]−h[i]<=mid 就将i+N向j连1），然后跑一下网络流，看看是否有流量为2的从1+N到N的流（即代表两条路径，拆点保证每个h[i] (1<i<N) 只用一次）。输出答案的时候从小到大枚举i，考虑将i加进左边的路径，并且我们记当前右边最高为h[R]。则建立源点s向i，R连边，重新像上面那样构图跑网络流，看是否还有2的流量。
%%%网络流大神tututu。
CODE（网络流）：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=52;
const int maxm=10000;

struct edge
{
int obj,cap;
    edge *Next,*rev;
} e[maxm];
edge *head[maxn<<1];
edge *nhead[maxn<<1];
int cur;

int level[maxn<<1];
int que[maxn<<1];
int he,ta;

int Left[maxn];
int Right[maxn];
int Lcur,Rcur;

int h[maxn];
int ng,N,t,ans;

void Add(int x,int y,int f)
{
    cur++;
    e[cur].obj=y;
    e[cur].cap=f;
    e[cur].rev=&e[cur+1];
    e[cur].Next=head[x];
    head[x]=e+cur;

    cur++;
    e[cur].obj=x;
    e[cur].cap=0;
    e[cur].rev=&e[cur-1];
    e[cur].Next=head[y];
    head[y]=e+cur;
}

bool Bfs()
{
for (int i=0; i<=t; i++) nhead[i]=head[i],level[i]=0;
    he=0,ta=1,que[1]=0,level[0]=1;
while (he<ta)
    {
int node=que[++he];
for (edge *p=head[node]; p; p=p->Next)
        {
int son=p->obj;
if ( !level[son] && p->cap ) level[son]=level[node]+1,que[++ta]=son;
        }
    }
return level[N];
}

int Dfs(int node,int maxf)
{
if ( node==N || !maxf ) return maxf;
int nowf=0;
for (edge *&p=nhead[node]; p; p=p->Next)
    {
int son=p->obj;
if ( level[son]==level[node]+1 && p->cap )
        {
int d=Dfs(son, min(p->cap,maxf) );
            nowf+=d;
            maxf-=d;
            p->cap-=d;
            p->rev->cap+=d;
if (!maxf) break;
        }
    }
if (maxf) level[node]=0;
return nowf;
}

int Dinic()
{
int temp=0;
while ( Bfs() ) temp+=Dfs(0,2);
return temp;
}

bool Judge(int limit)
{
    cur=-1;
for (int i=0; i<=t; i++) head[i]=NULL;
for (int i=1; i<N; i++)
for (int j=i+1; j<=N; j++)
if (h[j]-h[i]<=limit) Add(i+N,j,1);
for (int i=1; i<=N; i++) Add(i,i+N,1);
    Add(0,N+1,2);
return Dinic()>=2;
}

int Binary()
{
int L=0,R=1001;
while (L+1<R)
    {
int mid=(L+R)>>1;
if ( Judge(mid) ) R=mid;
else L=mid;
    }
return R;
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);

scanf("%d",&ng);
while (ng--)
    {
scanf("%d",&N);
for (int i=1; i<=N; i++) scanf("%d",&h[i]);
        sort(h+1,h+N+1);

        t=N<<1;
        ans=Binary();

        Lcur=Rcur=0;
        Right[++Rcur]=1;
for (int i=2; i<N; i++)
        {
            cur=-1;
for (int j=0; j<=t; j++) head[j]=NULL;
for (int j=i; j<N; j++)
for (int k=j+1; k<=N; k++)
if (h[k]-h[j]<=ans) Add(j+N,k,1);
for (int j=Right[Rcur]+1; j<=N; j++)
if ( j>i && h[j]-h[ Right[Rcur] ]<=ans ) Add(Right[Rcur]+N,j,1);
for (int j=1; j<=N; j++) Add(j,j+N,1);
            Add(0,Right[Rcur]+N,1);
            Add(0,i+N,1);
if ( Dinic()>=2 ) Left[++Lcur]=i;
else Right[++Rcur]=i;
        }

printf("%d ",h[1]);
for (int i=1; i<=Lcur; i++) printf("%d ",h[ Left[i] ]);
printf("%d ",h[N]);
for (int i=Rcur; i>=2; i--) printf("%d ",h[ Right[i] ]);
printf("\n");
    }

return 0;
}

老师的提供的一种做法：双路DP。我们记f[i][j]表示左边的路径最下方的点是i号，右边路径最下方的点是j号时的最大差距。做完f数组之后从小到大枚举i，看看是否有 j>i 使得f[i][j]<=ans，有的话就将i加进左边（但注意并不需要一定将j加进右边，这里只是检验i）。
一开始我想，可不可以不用最后贪心一遍，而是一边做f数组一遍求前驱，最后递归打印呢？然而我试了很多种方法都不行（交上去测顶多20分），感觉这样没办法解决字典序最小问题（主要是有多个相同的f值可以更新f[i][j]不知道应该保留哪个作为前驱）。调了一个下午+晚上最后还是放弃了QAQ。
CODE（双路DP+贪心）：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=55;
const int maxm=1001;

int Left[maxn];
int Right[maxn];
int Lcur,Rcur;

int f[maxn][maxn];
int h[maxn];
int ng,N;

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);

scanf("%d",&ng);
while (ng--)
    {
scanf("%d",&N);
for (int i=1; i<=N; i++) scanf("%d",&h[i]);
        sort(h+1,h+N+1);

for (int i=1; i<=N; i++)
for (int j=1; j<=N; j++) f[i][j]=maxm;
        f[N-1][N]=f[N][N-1]=h[N]-h[N-1];

for (int i=N-1; i>=2; i--)
for (int j=i+1; j<=N; j++)
            {
                f[i-1][j]=min(f[i-1][j], max(f[i][j],h[i]-h[i-1]) );
                f[i][i-1]=min(f[i][i-1], max(f[i][j],h[j]-h[i-1]) );
                f[i-1][i]=min(f[i-1][i], max(f[j][i],h[j]-h[i-1]) );
                f[j][i-1]=min(f[j][i-1], max(f[j][i],h[i]-h[i-1]) );
            }

int ans=maxm;
for (int j=2; j<=N; j++)
            f[1][j]=max(f[1][j],h[j]-h[1]),
            f[j][1]=max(f[j][1],h[j]-h[1]),
            ans=min(ans, min(f[1][j],f[j][1]) );

        Lcur=Rcur=0;
        Right[++Rcur]=1;
for (int i=2; i<N; i++)
        {
bool fL=false;
for (int j=i+1; j<=N; j++)
if ( f[i][j]<=ans && h[j]-h[ Right[Rcur] ]<=ans )
                    fL=true;
if (fL) Left[++Lcur]=i;
else Right[++Rcur]=i;
        }

printf("%d ",h[1]);
for (int i=1; i<=Lcur; i++) printf("%d ",h[ Left[i] ]);
printf("%d ",h[N]);
for (int i=Rcur; i>=2; i--) printf("%d ",h[ Right[i] ]);
printf("\n");
    }

return 0;
}
标签：

相关文章