CF1728E Red-Black Pepper

_•́へ•́╬_ · 2022-09-11 11:07:25 · 题解

缝

思路

第一部分

他给了 a,b，我要吧他转换成我能利用的形式。

我要计算：f[i] 表示在 n 对数中选 i 个 a 和 n-j 个 b 的最大美味度。

考虑贪心。

先吧所有的数都选 b，这就是 f[0]。

把所有的数按 a-b 排序，每次我选择一个 a-b，就相当于吧一个 b 的贡献减掉再加上 a，意义是吧某一组数由选 b 改为选 a。

所以每次我贪心的选 a-b 最大的，依次得到 f[1\dots n]。

第二部分

我们有了 f，考虑怎么应付询问。

询问长 ux+vy=n 的样子。考虑 exgcd。

根据裴蜀定理判无解。

跑 exgcd 得到一组解 (x_0,y_0)，调整至 x_0 为最小的可行的非负整数。

判 y_0<0 无解。

通解长酱紫：\begin{cases}x=x_0+\frac{v}{g}\times t\\y=y_0-\frac{u}{g}\times t\end{cases}

回归问题：ux+vy=n。

方括号是 \operatorname{lcm} 的意思都知道吧（

考虑根号分治：

code

#include<stdio.h>
#include<algorithm>
#define N 300001
#define B 9
#define int long long
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,a[N],b[N],g,x,y,c[1<<B][1<<B];
inline void exgcd(const int&a,const int&b)
{
    if(!b){g=a;x=1;y=0;return;}
    exgcd(b,a%b);
    int tmp=x-a/b*y;x=y;y=tmp;
}//bx+(a-a/b*b)y=ay+b(x-a/b*y)
inline void max(int&x,const int&y){if(x<y)x=y;}
main()
{
    read(n);b[0]=0;
    for(int i=0,x,y;i<n;++i)
    {
        read(x);read(y);
        a[i]=x-y;
        b[0]+=y;
    }
    sort(a,a+n);
    for(int i=1;i<=n;++i)b[i]=b[i-1]+a[n-i];
    read(m);
    for(int i=1;i<=n&&!(i>>B);++i)for(int j=0;j<=n;++j)max(c[i][j%i],b[j]);
    for(int u,v;m--;)
    {
        read(u);read(v);exgcd(u,v);
        if(n%g){printf("-1\n");continue;}
        x*=n/g;y*=n/g;
        int t=x/(v/g);
        x-=v/g*t;y+=u/g*t;
        if(x>>63)x+=v/g,y-=u/g;
        if(y>>63){printf("-1\n");continue;}
        x*=u;v=u*v/g;
        int maxn=0;
        if((v>>B)||v>n)for(;x<=n;max(maxn,b[x]),x+=v);
        else maxn=c[v][x];
        printf("%lld\n",maxn);
    }
}
/*x:(x*(n/g)+v/g*t)*u
 *y:(y*(n/g)-u/g*t)*v
 */