我大构造题岂能与区区二分图匹配为伍？

· · 题解

有意思的一道题。

首先，我们可以知道一对数如果是要有用的，它必然会产生至少一个数到 t 中，那么题目中比 n 还大的神秘 p 序列长度限制就是没有用的，因为我们最多会构造出 n 对数。

其次，题目中说了，顺序是不重要的，我们的目的只是让构造出的数对所产生的数和序列中可以一一对应即可。

考虑为了让数尽可能地小于等于 m，我们构造时肯定是取最小的数对是最优的，于是我们想到对于 \le\lfloor \frac{m}{3}\rfloor 的数 x，我们可以通过数对 (2x,3x) 来构造且仅构造出 x 这个数，而对于 >\lfloor \frac{m}{3}\rfloor 的数 x 我们可以通过数对 (2x+y,x+y)（当然 x>\lfloor \frac{m}{2}\rfloor 自然是无解啦）构造出 x 和 y，可是当数对变为 (x,y) 后之后还会有一些数被构造产生，此时问题似乎就变成了有一些物品，选择某个物品可以满足某些条件，问是否存在一种精准覆盖的方案，并且可以满足的条件某些之间可以替换（一个数 x 有多个），解决这个问题显然不弱于解决精准覆盖问题的，是不存在多项式复杂度的解法的。

继续观察性质。

注意到 (x,y) 最后产生的一个数就是 \gcd(x,y)，所以如果我们要使用数对 (2x+y,x+y)，\gcd(x,y) 就必然是在 t 中的，而我们还发现当 y|x 时，我们构造出来的数就只会有 x,y，那么我们用数对 (2x+\gcd(x,y),x+\gcd(x,y)) 去构造必然是不劣于用 (2x+y,x+y) 去构造的（由于 x>\lfloor \frac{m}{3}\rfloor，而 2x+y\le m，那么 y\le\lfloor \frac{m}{3}\rfloor，那么数对 (x,y) 构造出来的数都是 \le\lfloor \frac{m}{3}\rfloor 的，那么这些数我们都是可以用 (3x,2x) 这样的形式去构造的），而 \gcd(x,y) 就告诉我们构造 x 的时候必然是用的 x 的某一个不等于它自己的因数来与 x 组队的。

那么我们就自然地想到把 >\lfloor \frac{m}{3}\rfloor 的数作为一部，\le\lfloor \frac{m}{3}\rfloor 的数作为另一部，将 >\lfloor \frac{m}{3}\rfloor 的数 x 与 \le\lfloor \frac{m}{3}\rfloor 且是它因数的数连边，跑二分图最大匹配，如果 >\lfloor \frac{m}{3}\rfloor 的一部每个点都有匹配，说明有解，否则无解。

输出方案就匹配点 (2x+y,x+y) 一对，其余点 (3x,2x) 一对即可。

时间复杂度取决于你是用啥跑的二分图最大匹配，笔者用的网络流，故复杂度最坏 O(n^2)（O(n\sqrt m) 的东西边数建满就 O(n^2)）。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define INF 214748364719260817ll
using namespace std;
ll n,m;
ll in[2005],b[1005];
map<ll,ll>sum;
bool cmp(ll a,ll b)
{
    return a>b;
}
struct ed
{
    ll v,w,next;
}edge[8010005];
ll head[2005],cnt=1;
void add(ll u,ll v,ll w)
{
    edge[++cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt;
    edge[++cnt].v=u;edge[cnt].next=head[v];head[v]=cnt;
}
ll t;
ll dep[2005],cur[2005];
queue<ll>k;
bool bfs()
{
    cur[0]=head[0];
    for(ll i=1;i<=t;++i)dep[i]=0,cur[i]=head[i];
    dep[0]=1;
    k.push(0);
    while(!k.empty())
    {
        ll id=k.front();k.pop();
        for(ll i=head[id];i;i=edge[i].next)
        {
            ll v=edge[i].v,w=edge[i].w;
            if(!w||dep[v])continue;
            dep[v]=dep[id]+1;
            k.push(v);
        }
    }
    return dep[t];
}
ll dfs(ll id,ll get)
{
    if(id==t)return get;
    ll use=0;
    for(ll i=cur[id];i;i=edge[i].next)
    {
        cur[id]=i;
        ll v=edge[i].v,w=edge[i].w;
        if(!w||dep[v]!=dep[id]+1)continue;
        ll nu=dfs(v,min(get,w));
        edge[i].w-=nu;
        edge[i^1].w+=nu;
        get-=nu;use+=nu;
        if(!nu)dep[v]=0;
        if(!get)return use;
    }
    if(!use)dep[id]=0;
    return use;
}
struct px
{
    ll a,b; 
}ans[2005];
ll tot;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(ll i=1;i<=n;++i)cin>>in[i],b[i]=in[i],++sum[in[i]];
    sort(b+1,b+1+n);
    ll cot=unique(b+1,b+1+n)-b-1;
    sort(b+1,b+1+cot,cmp);
    ll ls=0,rs=0,ns=0;
    for(ll i=1;i<=cot;++i)
    {
        if(b[i]<=m/3)break;
        ++ls;
        add(0,ls,sum[b[i]]);
        ns+=sum[b[i]];
        for(ll j=i+1;j<=cot;++j)
            if(b[i]*2+b[j]<=m&&b[i]%b[j]==0)
            add(i,j,INF);
    }
    t=cot+1;
    for(ll i=ls+1;i<=cot;++i)add(i,t,sum[b[i]]);
    ll lls,res=0;
    while(bfs())
        while(lls=dfs(0,INF))res+=lls;
    if(res!=ns)cout<<-1;
    else
    {
        for(ll i=1;i<=ls;++i)
            for(ll j=head[i];j;j=edge[j].next)
            {
                ll v=edge[j].v;
                if(v)
                {
                    for(ll k=1;k<=edge[j^1].w;++k)ans[++tot].a=b[i]*2+b[v],ans[tot].b=b[i]+b[v];
                }
            }
        for(ll i=ls+1;i<=cot;++i)
            for(ll j=head[i];j;j=edge[j].next)
            {
                ll v=edge[j].v;
                if(v==t)
                for(ll k=1;k<=edge[j].w;++k)ans[++tot].a=b[i]*3,ans[tot].b=2*b[i];
            }
        cout<<tot<<'\n';
        for(ll i=1;i<=tot;++i)cout<<ans[i].a<<' '<<ans[i].b<<'\n';
    }
}