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

-1 前言

神人题目。

记得当时是2024年3月3日下午，当时机房里面几个大佬去了省选~~，虽然当时我没有去省选~~，但是这题出在luogu的第一时间我就开始做这题。想了非常长时间，各种结论非常混乱，最后还没能做出来。接近两年之后的省选前夕竟然又看到了这题，两年过去水平应该是有了巨大的变化，但是相同的是依旧没有去省选的资格/ll。

既然说季风和题意还有做法有关系，那么接下来我将严肃思考我常常追忆过去和 bitset 的联系。

0 芝士

• 神秘的数学

1 题意

为避免混淆，下文使用 $X,Y$ 代替原文中给定数值 $x,y$，并且区别于题目的是，下文序列全部为1-index，这并不会影响做题。

题面非常形式化。

但是这个题真的和季风有关系的，把 $(x,y)$ 看成目标点，$(x'_i,y'_i)$ 看成自主移动，$k$ 为限制，$(x_i,y_i)$ 看成季风扰动，问题就是求要移动到目标点的最小步数。如果题面这么写应该会更好看也会更好理解些。

这么说我的追忆旅程疑似是一张DAG。

2 思路

下文参考了Luogu题解区第1,3篇题解，在此感谢。

首先还是，因为有题目里面有这种循环的 $x$ 和 $y$，所以考虑先把这两个当作无限循环的序列。

先来转化一下题目里面的性质。容易发现我们不关心具体的 $x'$ 和 $y'$ 序列，所以对于每一条的具体限制 $|x'_i|+|y'_i|\le k$ 并不重要，只要总体上不超限制就一定可以调整出一组合法的 $x'_i$ 和 $y'_i$ 来。所以有以下式子：

$$\sum^{m} |x'_i|+\sum^{m} |y'_i| \le m\cdot k\\ = |\sum^{m} x_i-X|+|\sum^{m} y_i-Y| \le m\cdot k\\$$

这个对的原因是我们一定可以让 $x'$ 和 $y'$ 整个序列的正负相同，因为序列中同时出现正数和负数肯定可以相加抵消成一个数。

然后是经典的思路之差绝对值：

$$\sum^m (x_i+y_i-k) \le X+Y\\ \sum^m (-x_i+y_i-k) \le -X+Y\\ \sum^m (x_i-y_i-k) \le X-Y\\ \sum^m (-x_i-y_i-k) \le -X-Y$$

上面的移一下项就是很好推的。为了下面代码实现方便再给上面四个全都两边取反：

$$\sum^m (x_i+y_i+k) \ge X+Y\\ \sum^m (-x_i+y_i+k) \ge -X+Y\\ \sum^m (x_i-y_i+k) \ge X-Y\\ \sum^m (-x_i-y_i+k) \ge -X-Y$$

可以发现，上面这四个同时满足的 $m$ 才是合法的 $m$。

这四个式子只有 $x,y$ 和 $X,Y$ 的符号有点小差别，因此我们先用第一个来推一推式子，其余的类似。

考虑由于 $x,y$ 是无限循环的，所以令 $m=hn+b$。同时令 $pre_j=\sum_{i=1}^{j}(x_i+y_i+k)$。则式子可以表示为：

$$h\cdot pre_n + pre_b \ge X+Y$$

显然这个时候 $b$ 是可以枚举的，于是考虑枚举 $b$，求出对应 $h$ 的区间：

• 若 $pre_n=0$，则当且仅当 $pre_b\ge X+Y$ 时解为全非负整数，否则解集为空。

• 若 $pre_n>0$，那么

  $$h \ge \lceil \frac{X+Y-pre_b}{pre_n}\rceil$$

  并且要注意 $h$ 也是非负整数，即上式要满足 $X+Y\ge pre_b$，否则解集为 $h\ge 0$。

• 若 $pre_n< 0$，那么和上文类似的：

  $$h \le \lfloor \frac{X+Y-pre_b}{pre_n}\rfloor$$

  同样的，上式要满足 $X+Y\le pre_b$，否则解集为空。

枚举完 $b$ 我们就得到了 $n$ 个解集。对其他三个式子做一遍类似的过程，得到对应 $b$ 的解集取交，得到每个 $b$ 的最终解集 $[l_i,r_i]$。然后再次枚举一遍 $b$ 算答案，也就是 $ans\leftarrow\min_{b=1}^{n}\{l_i\cdot n+b\}$，就做完了。

细节好像也没什么细节，就是要记得特判一下 $X=Y=0$ 的情况，否则过不去样例。

3 代码

需要注意多测清空和向上取整。

int n,k,x,y,a[N],b[N],pre[N],l[N],r[N];
void solve(int fx,int fy){
    for(int i=1;i<=n;++i){pre[i]=pre[i-1]+fx*a[i]+fy*b[i]+k;}
    int xx=fx*x,yy=fy*y;
    if(pre[n]==0){
        for(int i=1;i<=n;++i){if(pre[i]<xx+yy)r[i]=ivl;}
        return;
    }
    for(int i=1;i<=n;++i){
        if(pre[n]>0){
            if(pre[i]<=xx+yy)l[i]=std::max(l[i],(xx+yy-pre[i])/pre[n]+((xx+yy-pre[i])%pre[n]?1:0));
            else l[i]=;
        }else{
            if(pre[i]<xx+yy)r[i]=ivl;
            else r[i]=std::min(r[i],(xx+yy-pre[i])/pre[n]);   
        }
    }
}
signed main(){
    int T=read();
    while(T--){
        r[0]=ivl;
        n=read(),k=read(),x=read(),y=read();
        for(int i=1;i<=n;++i){
            l[i]=0;r[i]=inf;
        }
        for(int i=1;i<=n;++i){a[i]=read(),b[i]=read();}
        if(!x&&!y){printf("0\n");continue;}
        solve(1,1);
   		solve(1,-1);
        solve(-1,1);
        solve(-1,-1); 
        int ans=inf;
        for(int i=1;i<=n;++i){
            if(l[i]<=r[i]){
                ans=std::min(ans,i+l[i]*n);
            }
        }
        if(ans==inf)printf("-1\n");
        else printf("%lld\n",ans);
    }
    return 0;
}

4 时间复杂度分析

没啥好分析的，简单 $O(n)$。

5 后记

神人题目。

生日愿望是能去 WC2027。我有生之年一定要在WC的舞台上唱白鸟过河滩！！！！1