P10217 [省选联考 2024] 季风 题解

· · 题解

题目传送门

前言

蒟蒻比较菜，在题目背景的启发中才能想到一些东西。

可以把 (x_i,y_i) 想象成季风的向量，然后要求的 (x,y) 是终点。

Solution

Step 1 :

考虑 n=1 这种情况。

假设走了 m 步，那么就可以列出不等式：

|x-mx_0|+|y-my_0|\le mk

左边是季风吹之后和终点的距离，右边是可以修正的最大步数，也就是 (x'_ i,y'_ i)。

这个东西分讨一下解即可 O(1) 解决，不过确实挺难写的。

我不会说考场上把其他东西都想完了，结果就是这一步想复杂了没写出来导致我爆炸的。

Step 2 :

考虑 n\ne 1 的情况。

设 \rm sum 表示 n 个 (x_i,y_i) 向量的向量和。我们发现，只要先走了前 m\bmod n 步之后，剩下的就是一个一个的循环。那我们不妨令 i=m \bmod n，先把前 i 步走完，然后再把剩下的当做若干个 \rm sum 的向量和。所以剩下的还是和 n=1 的情况差不多。

|x-t\times {\rm sumX}|+|y-t\times {\rm sumY}|\le (t\times n+{\rm id}+1)\times k

一种偷懒技巧是可以把 \rm endPoint 减掉 (x_i,y_i)，可以保证 \rm startPoint 还是 (0,0)。

Code

代码在 C++ 14 (GCC 9) 无法通过，不知道为啥。

代码太屎，谨慎观看。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
const ll inf=9e18;
ll inline read()
{
    ll num=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}
    return num*f;
}
int T;ll k,n,ans;
struct data
{
    ll x,y;
    data friend operator +(const data A,const data B){return (data){A.x+B.x,A.y+B.y};}
    data friend operator -(const data A,const data B){return (data){A.x-B.x,A.y-B.y};}
}sum,startPoint,p[N],endPoint;
#define Eset (SolSet){inf,0}
#define Uset (SolSet){0,inf}
struct SolSet
{
    ll l,r;
    SolSet friend operator &(const SolSet A,const SolSet B)
    {
        if(A.l>A.r||B.l>B.r)return Eset;
        return (SolSet){max(A.l,B.l),min(A.r,B.r)};
    }
};
SolSet GreaterEqual(ll k,ll b)
{
    if(k<0)return (b<=0)?(SolSet){0,b/k}:Eset;
    if(k>0)return (b<=0)?Uset:(SolSet){b/k+(b%k!=0),inf};
    return (b<=0)?Uset:Eset;
}
SolSet LessEqual(ll k,ll b)
{
    if(k<0)return (b>=0)?Uset:(SolSet){(b/k)+(b%k!=0),inf};
    if(k>0)return (b>=0)?(SolSet){0,b/k}:Eset;
    return (b>=0)?Uset:Eset;
}
ll calc(int id)
{
    ll t=inf/n+1;SolSet res;

    res=Uset;
    res=res&LessEqual(sum.x,endPoint.x);
    res=res&LessEqual(sum.y,endPoint.y);
    res=res&GreaterEqual(n*k+sum.x+sum.y,endPoint.x+endPoint.y-id*k);
    if(res.l<=res.r)t=min(t,res.l);

    res=Uset;
    res=res&LessEqual(sum.x,endPoint.x);
    res=res&GreaterEqual(sum.y,endPoint.y);
    res=res&GreaterEqual(n*k+sum.x-sum.y,endPoint.x-endPoint.y-id*k);
    if(res.l<=res.r)t=min(t,res.l);

    res=Uset;
    res=res&GreaterEqual(sum.x,endPoint.x);
    res=res&LessEqual(sum.y,endPoint.y);
    res=res&GreaterEqual(n*k-sum.x+sum.y,-endPoint.x+endPoint.y-id*k);
    if(res.l<=res.r)t=min(t,res.l);

    res=Uset;
    res=res&GreaterEqual(sum.x,endPoint.x);
    res=res&GreaterEqual(sum.y,endPoint.y);
    res=res&GreaterEqual(n*k-sum.x-sum.y,-endPoint.x-endPoint.y-id*k);
    if(res.l<=res.r)t=min(t,res.l);

    return t*n+id;
}
/*
ll calc(int id)
{
    if( endPoint.x >= t * sum.x && endPoint.y >= t * sum.y )
    // endPoint.x - t * sum.x + endPoint.y - t * sum.y <= ( t * n + id ) * k
    // endPoint.x + endPoint.y - id * k <= t * ( n * k + sum.x + sum.y )

    if(endPoint.x >= t*sum.x && endPoint.y <= t * sum.y)
    // endPoint.x - t * sum.x + t * sum.y - endPoint.y <= ( t * n + id ) * k
    // endPoint.x - endPoint.y - id * k <= t * ( n * k + sum.x - sum.y )

    if(endPoint.x <= t * sum.x && endPoint.y >= t * sum.y)
    // t * sum.x - endPoint.x + endPoint.y - t * sum.y <= ( t * n + id ) * k
    // - endPoint.x + endPoint.y - id * k <= t * ( n * k - sum.x + sum.y )

    if(endPoint.x <= t * sum.x && endPoint.y <= t * sum.y)
    // t * sum.x - endPoint.x + t * sum.y - endPoint.y <= ( t * n + id ) * k
    // - endPoint.x - endPoint.y - id * k <= t * ( n * k - sum.x - sum.y ) 
    return t*n+id;
}
// | endPoint.x - t * sum.x | + | endPoint.y - t * sum.y | <= ( t * n + id ) * k
*/
void solve()
{
    n=read();k=read();endPoint=(data){read(),read()};
    sum=(data){0,0};ans=inf;
    for(int i=0;i<n;i++)p[i]=(data){read(),read()};
    for(int i=0;i<n;i++)sum=sum+p[i];
    if(!endPoint.x&&!endPoint.y)return printf("0\n"),void();
    for(int i=0;i<n;i++)
    {
        ans=min(ans,calc(i));
        endPoint=endPoint-p[i];
    }
    if(ans!=inf)printf("%lld\n",ans);
    else printf("-1\n");
}
int main(){
    T=read();while(T--)solve();
    return 0;
}

改了稍稍长一点的变量名之后

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
const ll inf=9e18;
ll inline read()
{
    ll num=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}
    return num*f;
}
int T;ll k,n,ans;
struct data
{
    ll x,y;
    data friend operator +(const data A,const data B){return (data){A.x+B.x,A.y+B.y};}
    data friend operator -(const data A,const data B){return (data){A.x-B.x,A.y-B.y};}
}s,p[N],eP;
#define Eset (node){inf,0}
#define Uset (node){0,inf}
struct node
{
    ll l,r;
    node friend operator &(const node A,const node B)
    {
        if(A.l>A.r||B.l>B.r)return Eset;
        return (node){max(A.l,B.l),min(A.r,B.r)};
    }
};
node Ge(ll k,ll b)
{
    if(k<0)return (b<=0)?(node){0,b/k}:Eset;
    if(k>0)return (b<=0)?Uset:(node){b/k+(b%k!=0),inf};
    return (b<=0)?Uset:Eset;
}
node Le(ll k,ll b)
{
    if(k<0)return (b>=0)?Uset:(node){(b/k)+(b%k!=0),inf};
    if(k>0)return (b>=0)?(node){0,b/k}:Eset;
    return (b>=0)?Uset:Eset;
}
ll calc(int id)
{
    ll t=inf/n+1;node res;
    res=Le(s.x,eP.x)&Le(s.y,eP.y)&Ge(n*k+s.x+s.y,eP.x+eP.y-id*k);   if(res.l<=res.r)t=min(t,res.l);
    res=Le(s.x,eP.x)&Ge(s.y,eP.y)&Ge(n*k+s.x-s.y,eP.x-eP.y-id*k);   if(res.l<=res.r)t=min(t,res.l);
    res=Ge(s.x,eP.x)&Le(s.y,eP.y)&Ge(n*k-s.x+s.y,-eP.x+eP.y-id*k);  if(res.l<=res.r)t=min(t,res.l);
    res=Ge(s.x,eP.x)&Ge(s.y,eP.y)&Ge(n*k-s.x-s.y,-eP.x-eP.y-id*k);  if(res.l<=res.r)t=min(t,res.l);
    return t*n+id;
}
void solve()
{
    n=read();k=read();eP=(data){read(),read()};
    s=(data){0,0};ans=inf;
    for(int i=0;i<n;i++)s=s+(p[i]=(data){read(),read()});
    if(!eP.x&&!eP.y)return printf("0\n"),void();
    for(int i=0;i<n;i++)ans=min(ans,calc(i)),eP=eP-p[i];
    if(ans!=inf)printf("%lld\n",ans);
    else printf("-1\n");
}
int main(){
    T=read();while(T--)solve();
    return 0;
}