首页 牛客题解

# Entangled Coins

题目链接

首先我们简化题意

现有一数 xx ，它的可达范围是 [0,n][0,n]​

你可以进行任意多次如下操作：

  • 你可以选择一数 a(0≤a≤k)a(0 \leq a \leq k) ，使得 xx 变为 x+k−2ax+k-2a 且不能超过 xx 的可达范围

问将数 xx 变为数 yy 的最小操作次数，若无解则输出 -1

不难注意到 kk 的奇偶性决定了 xx 的变化情况，所以我们自然地按 kk 的奇偶性进行分类讨论

当 kk 为偶数时，操作任意多次后，xx 的奇偶性是不变的

当 kk 为奇数时，操作偶数次，xx 的奇偶性是不变的，操作奇数次，xx 的奇偶性会改变

此时我们发现只用考虑操作次数的奇偶性即可

当操作次数为偶数次时，xx 的奇偶性不会发生改变，我们设操作前的数为 xx ，操作后的数为 yy

不自然的，对于 n−xn-x 到 n−yn-y 的情况，不难发现是操作是镜像的

我们现考虑 nn 和 kk 都 ≤⌊n2⌋\leq \lfloor \frac{n}{2} \rfloor 的情况

由于操作次数为偶数次，我们将操作拆成任意多个两步操作

设第一步操作为 a1=0a_1 = 0 ，第二步操作为 a2=ka_2 = k ，则数 xx 不发生任何变化

我们在这两步操作的基础上尽可能增大 a1a_1 的值，显然 a1a_1 的变化范围是 [0,min⁡(x,k)][0,\min (x,k)] ，此时两步操作后 xx 值可达到 [max⁡(x−2k,0),x][\max (x-2k,0),x] 间任意和 xx 奇偶性相同的值

同样的，如果我们尽可能减少 a2a_2 的值，显然 a2a_2 的变化范围是 [0,min⁡(x,k)][0,\min(x,k)] ，此时两步操作后 xx 的值可达到 [x,min⁡(x+2k,n)][x,\min(x+2k,n)] 间任意和 xx 奇偶位置相同的值

我们将上面两个情况合并起来，就是 [max⁡(x−2k,0),min⁡(x+2k,n)][\max (x - 2k,0),\min( x + 2k,n)] 间任意和 xx 奇偶位置相同的值

在此基础之上，我们只需要进行 cc 轮操作，就能到达 [x−2kc,x+2kc][x-2kc,x+2kc] 间任意和 xx 奇偶位置相同的值

对于 k≥⌊n2⌋k \geq \lfloor \frac{n}{2} \rfloor 的情况，两轮操作可以看成 a=n−ka=n-k 再让 xx 变成 n−xn-x ，两轮操作下来 xx 变成 n−xn-x 相互抵消掉了，所以 kk 与 n−kn-k 等价，只需要令 k=min⁡(k,n−k)k= \min(k,n-k) 即可

接下来讨论操作次数为奇数的情况

我们先对数 xx 进行一次操作，用原本的 kk 求出 xx 可达区间 [l,r][l,r] ，然后就是跟偶数次操作是一样的，经过 cc 轮操作后，可达区间为 [min⁡(l−2ck,0),max⁡(r+2ck,n)][\min(l-2ck,0),\max(r+2ck,n)]

所有的操作均为 O(1)O(1) 的复杂度，总复杂度为 O(T)O(T)

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
void deal(int n,int k,int s,int t)
{
    int ans1=1e18,ans2=1e18;
    if(s==t) {cout<<0<<endl;return;}
    if(!k||k==n)
    {
        if(s+t==n) cout<<1<<endl;
        else cout<<-1<<endl;
        return;
    }
    // 偶数轮
    if(!(abs(t-s)&1)) ans1=2*ceil(abs(s-t)/(2.0*min(k,n-k)));
    // 奇数轮
    if((abs(t-s)&1&&(k&1))||(!(abs(t-s)&1)&&(!(k&1))))
    {
        int l=s-min(s,k)+k-min(s,k);
        int r=s+min(n-s,k)-(k-min(n-s,k));
        k=min(k,n-k);// 转化为偶数轮操作，k 取 min
        if(l<=t&&t<=r) ans2=1;
        else if(t<l) ans2=1+2*ceil((l-t)/(2.0*k));
        else ans2=1+2*ceil((t-r)/(2.0*k));
    }
    cout<<(min(ans1,ans2)==1e18?-1:min(ans1,ans2))<<endl;
}
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read(),k=read(),s=read(),t=read();
        deal(n,k,s,t);
    }
    return _123hh2;
}