题解 P6515 【[QkOI#R1] Quark and Game】

· · 题解

首先，把这 n 个二元组 (a_i,b_i) 看成向量的形式，记 \vec{v_i}=\begin{bmatrix}a_i\\b_i\end{bmatrix}，默认向量的起点在原点。

可以发现，这两种操作对应了两个线性变换，把操作一和操作二对应的矩阵分别称作 M_1,M_2。那么题目就是要找到一个由矩阵 M_1,M_2 构成的序列 A_1,A_2,\cdots,A_k，使得对于所有 \vec{v_i}，A_kA_{k-1}\cdots A_1\vec{v_i} 的结果一定至少有一维非正。

在刚才转化后的题意中，似乎漏了一个只有当 b_i>0 时才能继续操作的限制，但可以证明只要有一维非正，那么接下来的操作不会使 a_i,b_i 重新同时变为正数。

接着，我们来考虑这个序列会漏掉哪些向量，也就是经过一系列变换后向量依旧在第一象限。比如空序列漏掉了第一象限的向量，只包含一个 M_1 的序列漏掉了直线 y=x 和 x=0 右上方的向量。多举几个例子就可以发现漏掉的向量都在两条过原点的直线的右上方（不包括直线上），详细证明这个结论只需要考虑线性变换的性质。

然后，我们对这 n 个向量按极角从小到大排序，那么如果要想让这 n 个向量都不被漏掉，这两条直线就一定会在两个相邻向量之间。先特判一下两条直线在 \vec{v_1} 下面或在 \vec{v_n} 左面的情况（对应先进行一次操作二，再一直进行操作一或一直进行操作一）。我们发现这个问题现在只和这两个相邻的向量有关了。不妨设两条直线在 \vec{v_1},\vec{v_2} 之间，下面分几种情况讨论：

  1. 当 \vec{v_1},\vec{v_2} 均在直线 y=x 下面或直线上时，应当进行操作二（左乘 M_2），若进行操作一，那么 \vec{v_1},\vec{v_2} 将同时变得不可操作，此时漏掉向量的区域就会在 \vec{v_2} 上方。
  2. 当 \vec{v_1},\vec{v_2} 均不在直线 y=x 下面或直线上时，应当进行操作一（左乘 M_1），若进行操作二，那就又回到了情况 1，但是情况 1 又只能再翻回来。
  3. 当 \vec{v_1},\vec{v_2} 中有恰好一个向量在 y=x 直线下面或直线上时，只要进行操作一，那么就会使一个向量变得不可操作，所以我们要讨论一下操作一之前是否需要做一次操作二。假设不可操作的向量是 \vec{v_1}，我们做完操作一（这时使 \vec{v_1} 不可操作）后再进行一次操作二，最后做若干次操作一使得 \vec{v_2} 变得不可操作。注意这个时候我们让 \vec{v_1} 不可操作后不能继续接着进行操作一，因为我们的目的是让漏掉向量的区域在这两个向量之间，所以我们必须先翻转，再进行操作一让 \vec{v_2} 不可操作。这一步就是在原来的序列上左乘 M_1^{t_1}M_2M_1 或者 M_1^{t_2}M_2M_1M_2，其中 t_1,t_2 是这种情况下让 \vec{v_2} 不可操作的进行操作 1 的最小次数。

我们对每对相邻向量都进行这些讨论，最后选取花费最少的方案即可，时间复杂度是 O(n(a+b))。现在的瓶颈在于情况 2 可能会重复很多遍，所以我们可以直接算出来需要进行多少次，然后一遍完成。因为操作 3 只会进行一次，操作 1 和操作 2 实际上就是辗转相除法，所以最后的时间复杂度是 O(n\log\min(a,b))。在实现时可以直接在原向量上修改，不需要使用矩阵，这里用矩阵说明只是为了便于理解。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
struct pt
{
    int a,b;
}c[100005];
int n;
ll ans,p,q;
bool cmp(const pt x,const pt y)
{
    return 1ll*x.a*y.b>1ll*y.a*x.b;  //使用叉积可以避免浮点运算 
}
int main()
{
    scanf("%d%lld%lld",&n,&p,&q);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&c[i].a,&c[i].b);
    sort(c+1,c+n+1,cmp);
    ans=min(1ll*(c[n].b+c[n].a-1)/c[n].a*p,1ll*(c[1].a+c[1].b-1)/c[1].b*p+q); //特判 
    for(int i=1;i<n;i++)
    {
        pt u=c[i],v=c[i+1];
        if(1ll*u.a*v.b==1ll*v.a*u.b) continue;
        ll nw=0;
        while(1)
        {
            if(u.a>=u.b&&v.a>=v.b)  //case 1 
            {
                swap(u.a,u.b),swap(v.a,v.b);
                nw+=q;
            }
            else if(u.a<u.b&&v.a<v.b)  //case 2 
            {
                int ct=min((u.b-1)/u.a,(v.b-1)/v.a);
                u.b-=ct*u.a,v.b-=ct*v.a;
                nw+=ct*p;
            }
            else  //case 3 
            {
                if(u.a>=u.b) swap(u,v);
                ll nw1=0,nw2=0;
                pt w=u;
                w.b-=w.a;
                nw1=q+p+1ll*(w.a+w.b-1)/w.b*p;  //case 3.1
                if(v.a>v.b)
                {
                    w=v;
                    swap(w.a,w.b);
                    w.b-=w.a;
                    nw2=p+q*2+1ll*(w.a+w.b-1)/w.b*p;  //case 3.2
                    nw1=min(nw1,nw2);
                }
                nw+=nw1;
                break;
            }
        }
        ans=min(ans,nw);
    }
    printf("%lld",ans);
    return 0;
}