[CodeTON Round 2][Codeforces 1704G. Mio and Lucky Array]

· · 题解

题目链接：1704G - Mio and Lucky Array

题目大意：给定数组 a,b，可以对 a 的每个位置 i 进行 0 或 1 次操作。每次操作可以令所有 j\ge i 的 a_j 加上 (-1)^{j-i}\cdot(j-i+1)（对应每个位置的变化量为 1,-2,3,-4,\cdots），问是否可以让 a 存在一个连续子序列与 b 相同。

为了方便起见，我们默认下标从 0 开始。

首先要注意到，在一次操作后，a_i+2a_{i-1}+a_{i-2} 的值是不变的（除了边界部分）。要问为什么能注意到，心路历程大概如下：

那么令 f_i=a_i+2a_{i-1}+a_{i-2}，观察在对 i 进行一次操作后 f 的变化情况。可以发现每次操作只是把 f_i 的值加上了 1，其余位置的值不做更改。

在这里就需要思考一下在操作过后如何判断 a 的一个起始位置为 st，长度为 m 的子序列是否与 b 相同了。类似地，令 g_i=b_i+2b_{i-1}+b_{i-2}，那么两个序列相等当且仅当下式成立：

\begin{cases} f_{st+i}=g_i & i\ge 2 \\ a_{st+i}=b_i & i= 0,1 \end{cases}

由于 f_i 的值最多加一，所以第一个式子有机会成立当且仅当 g_i = f_{st+i} 或 g_i = f_{st+i}+1。考虑利用 bitset 判断所有 st 是否可以合法。

为了判断一个起点是否合法，暴力的话可以有如下代码：

for(int st=0;st<=n-m;st++)
    for(int i=2;i<m;i++)
        ok[st]&=(f[st+i]==g[i])|(f[st+i]==g[i]-1);

既然要利用 bitset，就需要改变枚举的先后顺序，以便一次性对所有的 st 进行赋值操作：

for(int i=2;i<m;i++)
    for(int st=0;st<=n-m;st++)
        ok[st]&=(f[st+i]==g[i])|(f[st+i]==g[i]-1);

于是对数组 f 开 vector，对每个数值记录数组内有哪些位置等于指定值，就可以快速进行处理：

for(int i=2;i<m;i++){
    bitset<N>t;
    for(auto j:d[g[i]])t[j]=1;
    for(auto j:d[g[i]-1])t[j]=1;
    ok&=t>>i;
}

当然为了避免超时，还需要对每个相同的 g_i 分批进行处理，排序后双指针即可。

这样我们就能在 O(\frac{n^2}{W}) 的复杂度内完成对应判断，接下去就需要考虑如何判断头两位的值是否可以满足条件。

对每个符合条件的 st，我们设 d_0=b_0-a_{st},d_1=b_1-a_{st+1}。可以发现，每次若有操作令 a_{st} 加上 k>0，那么对应的 a_{st+1} 就会减去 k+1，减 k 时同理。也就是说，每当 a_{st} 的值增加一次，对应的 d_0+d_1 就会减一，反之亦然。于是我们可以通过 d_0+d_1 的值来判断 a_{st} 的值增加与减少的次数之差，特别地对于只有 a_{st+1} 加一的情况，我们把它看成 a_{st} 的值减少了 0。

这样一来，我们就需要判断在加法操作与减法操作的差为 k 的情况下，是否存在一种操作方式使得 a_{st} 能够到达指定的值，这其中可选的操作为 -0,+1,-2,+3,\cdots ,+(-1)^{st}\cdot (st+1)。

注意到，由于所有的减法操作减去的都是偶数，所以 d_0 的奇偶性就决定了加法或减法操作次数的奇偶性（二者操作次数的差为定值）。另外，当确定了加减法的次数 x,y 后，可以 O(1) 贪心计算得出对应操作次数能够得到的最大值以及最小值 l,r，且可以证明，在 [l,r] 之间与 l,r 奇偶性相同的值都可以取到。我们来看下确定 x,y 后对应的最大值和最小值是什么。

设最大的加法操作为 +M，那么贪心取最大的 x 个加法以及绝对值最小的 y 个减法，对应的最大值为：

\sum_{i=0}^{x-1}(M-2i)-\sum_{i=0}^{y-1}2i=Mx-x(x-1)-y(y-1)

同样设绝对值最大的减法操作为 -M'，那么贪心取最小的 x 个加法以及绝对值最大的 y 个减法，对应的最小值为：

\sum_{i=0}^{x-1}(2i+1)-\sum_{i=0}^{y-1}(M'-2i)=x^2-M'y+y(y-1)

可以发现在上述式子中，y=x+k，而 M,M' 是由 st 确定的定值。于是对于每个 st，最大值和最小值都是与 x 有关的二次函数，计算出系数后对应的极值都可以使用初中数学知识解出来（开心的话也可以三分）。这样我们就能够通过 k 的取值以及 d_0 的奇偶性确定 x 的取值范围，从而得知操作后的值的范围，完成判断。

关于构造的部分，直接暴力找到一个满足条件的 x 然后贪心即可。

#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define LL long long
int T,n,m,a[N];
LL b[N],f[N];
pair<LL,int>g[N];
bitset<N>ok,t;
map<LL,vector<int>>mp;
LL F(LL A,LL B,LL C,LL x){return A*x*x+B*x+C;}
bool check(int st)
{
    LL d0=b[0]-a[st],d1=b[1]-a[st+1];
    LL k=d0+d1,M=st&1?st:(st+1),M_=st&1?(st+1):st;
    LL nx=st/2+1,ny=(st+3)/2;
    LL l=max(0ll,-k),r=min(nx,ny-k);
    LL o=d0&1;

    if(l%2!=o)l++;
    if(r%2!=o)r--;
    if(l>r)return false;

    LL A=-2,B=M-2ll*k+2,C=k-k*k;
    LL x0=-B/(2ll*A);
    LL mn=1e18,mx=-mn;
    for(LL i=x0-5;i<=x0+5;i++)if(i%2==o && l<=i && i<=r)mx=max(mx,F(A,B,C,i));
    mx=max(mx,F(A,B,C,l));
    mx=max(mx,F(A,B,C,r));

    A=2,B=2ll*k-M_-1,C=k*k-(M_+1)*k;
    x0=-B/(2ll*A);
    for(LL i=x0-5;i<=x0+5;i++)if(i%2==o && l<=i && i<=r)mn=min(mn,F(A,B,C,i));
    mn=min(mn,F(A,B,C,l));
    mn=min(mn,F(A,B,C,r));

    if(d0>mx || d0<mn)return false;

    LL x=-1;
    for(LL i=l;i<=r;i++)if(i%2==o){
        mn=F(A,B,C,i);
        mx=F(-2,M-2ll*k+2,k-k*k,i);
        if(mn<=d0 && d0<=mx){x=i;break;}
    }

    set<int>ans;
    LL s=0,y=x+k;
    for(LL i=0;i<x;i++)s+=2ll*i+1,ans.insert(st-2ll*i);
    for(LL i=0;i<y;i++)s-=2ll*i,ans.insert(st-2ll*i+1);
    for(LL i=x-1;i>=0 && s<d0;i--){
        s-=2ll*i+1;
        ans.erase(st-2ll*i);
        while(s+M>d0)M-=2;
        s+=M;
        ans.insert(st-M+1);
        M-=2;
    }

    for(LL i=y-1;i>=0 && s>d0;i--){
        s+=2ll*i;
        ans.erase(st-2ll*i+1);
        while(s-M_<d0)M_-=2;
        s-=M_;
        ans.insert(st-M_+1);
        M_-=2;
    }

    for(LL i=2;i<m;i++)if(f[st+i]==g[i].first-1)ans.insert(st+i);
    printf("%d\n",(int)ans.size());
    for(auto i:ans)printf("%d ",i+1);
    printf("\n");
    return true;
}
void init()
{
    mp.clear();
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]),ok[i]=1;
    scanf("%d",&m);
    for(int i=0;i<m;i++)scanf("%lld",&b[i]);
    for(int i=2;i<n;i++)mp[f[i]=a[i]+2*a[i-1]+a[i-2]].push_back(i);
    for(int i=2;i<m;i++)g[i]=make_pair(b[i]+2ll*b[i-1]+b[i-2],i);
    sort(g+2,g+m);
    for(int i=2;i<m;){
        t.reset();
        for(auto j:mp[g[i].first])t[j]=1;
        for(auto j:mp[g[i].first-1])t[j]=1;
        int j=i;
        while(j<m && g[j].first==g[i].first)ok&=t>>g[j].second,j++;
        i=j;
    }
    for(int i=2;i<m;i++)g[i]=make_pair(b[i]+2ll*b[i-1]+b[i-2],i);
    for(int i=0;i<=n-m;i++)if(ok[i])
        if(check(i))return;
    printf("-1\n");
}
int main()
{
    scanf("%d",&T);
    while(T--)init();
}

求二次函数极值的部分为了省脑子直接在实际极值点的左右选 10 个位置暴力比较判断了，实际上是可以通过计算得出对应位置的。

另外，初步确定满足第一个条件的 st 也可以通过多项式乘法来解决，但由于本弱不会所以才用的 bitset。