题目 | Cyperation

2023牛客暑期多校训练营7

G - Cyperation

https://ac.nowcoder.com/acm/contest/57361/G

题意

给定长度为 $n$ 的环 $\{a{\}}_{i=1}^n$，每次可以选择环上最近距离为 $k$ 的两点 $i,j$ 使得 $a_i$ 和 $a_j$ 都减 $1$。问能不能经过若干次操作让整个环上的数字清零。多测，$1\le T\le {10}^6$，$2\le \sum n\le {10}^6$，$1\le k\le n$。

题解

特判全 $0$ 情况，直接输出 YES.

特判 $2k>n$ 的情况，直接输出 NO.（这种情况 $min(t,n-t)=k$ 无解所以不成立）

---

对于给出的环 $\{a{\}}_{i=1}^n$，将距离为 $k$ 的所有点都提取出来放到一起，相当于将原来的大环拆成若干个小环。每个小环互相独立，可以分别求解。要注意的是，拆分出的小环不一定顺序和以前一样，因为要保证相邻两位在原大环中距离为 $k$。

当且仅当所有小环能够有解时，原问题有解。

例如输入 $[1,4,6,2,8,10]$ 且 $k=2$，那么将会拆分成 $[1,6,8]$ 和 $[4,2,10]$ 两个小环。

接下来就要对每个小环求解了，由于已经进行了拆分，小环中每次操作相当于就是相邻两位一起 $-1$ 了。

---

对于一个小环 $[a_1,a_2,\dots ,a_n]$，设如果要将整个环清零，需要对 $[a_1,a_2]$ 这个区间进行 $x$ 次减操作，那么：

• $a_1$ 变成了 $a_1-x$
• $a_2$ 经过上一步变成了 $a_2-x$，还要对 $[a_2,a_3]$ 区间进行 $a_2-x$ 次减操作才能置零。
• $a_3$ 经过上一步变成了 $a_3-a_2+x$，还要对 $[a_3,a_4]$ 区间进行 $a_3-a_2+x$ 次减操作才能置零。
• $a_4$ 经过上一步变成了 $a_4-(a_3-a_2)-x$，还要对 $[a_4,a_5]$ 区间进行 $a_4-(a_3-a_2)-x$ 次减操作才能置零。
• $⋮$
• $a_n$ 经过上一步变成了 $a_n-(a_{n-1}-(a_{n-2}-(\cdots (a_3-a_2)\cdots )))+(-1{)}^{n-1}x$，还要对 $[a_n,a_1]$ 区间进行前面那个式子次减操作才能置零。

综上，如果假设了 $[a_1,a_2]$ 区间的操作次数 $x$，剩下区间的操作次数全部都确定了，且均是一次式 $p\pm x$ 这种格式。

为了方便起见，令 $p_2=a_2,p_i=a_i-p_{i-1},i=3,4,\dots$，特别的，由于序列是环，令 $p_1=a_1-p_n$.

首先由于操作次数 $\ge 0$，所以 $x$ 需要满足：

$$\{\begin{array}{l}{p}_2-x\ge 0\\ p_3+x\ge 0\\ ⋮\\ p_n+(-1{)}^{n-1}x\ge 0\end{array}$$

另外别忘了还有 $a_1-x\ge 0$，整合一下就是：

$$\begin{gathered} l\le x\le r \\ \mathrm{其}\mathrm{中}:\{\begin{array}{l}l=max\{0,-p_3,-p_5,-p_7,\dots \}\\ r=min\{a_1,p_2,p_4,p_6,\dots \}\end{array} \end{gathered}$$

如果求出来 $l>r$ 的话很明显 $x$ 无解，直接输出 NO.

对于 $l\le r$ 的情况，也不一定有解，根据上面可以发现，我们假设了对 $[a_1,a_2]$ 操作了 $x$ 次，最后会算出来对 $[a_n,a_1]$ 的操作次数，这两个操作对 $a_1$ 的总操作次数不一定能将 $a_1$ 置零。用公式来说就是，要满足：

$$x+p_n+(-1{)}^{n-1}x=a_1$$

由于 $x$ 的符号与 $n$ 有关，所以需要分类讨论。

若 $n$ 为偶数，化简后就是：

$$a_1-p_n=p_1=0$$

直接检查就行，不符合则不成立输出 NO.

若 $n$ 为奇数，化简后就是：

$$2x=a_1-p_n=p_1$$

首先检测是否有整数解（即 $p_1$ 是否为偶数），若解出 $x$，回代到 $l\le x\le r$ 进行验证，若验证通过则有解。

代码

代码中为方便取模下标从 $0$ 开始，但思路和公式完全一致。

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

bool check(vector<int> &a)
{
    int n = a.size();
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        p[(i + 1) % n] = a[(i + 1) % n] - p[i];
    bool op = false; // 1+ 0-
    int l = 0, r = a.front();
    for (int i = 1; i < n; i++)
    {
        if (op)
            l = max(l, -p[i]);
        else
            r = min(r, p[i]);
        if (l > r)
            return false;
        op ^= 1;
    }
    if (n & 1)
    {
        if (p.front() & 1)
            return false;
        int ans = p.front() / 2;
        return l <= ans && ans <= r;
    }
    return p.front() == 0;
}

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    bool all_zero = true;
    for (int i = 0; i < n; i++)
    {
        if (a[i])
        {
            all_zero = false;
            break;
        }
    }
    if (all_zero)
    {
        cout << "YES" << endl;
        return;
    }
    if (2 * k > n)
    {
        cout << "NO" << endl;
        return;
    }
    vector<bool> vis(n + 10);
    for (int i = 0; i < n; i++)
    {
        if (vis[i])
            continue;
        vector<int> ring;
        int pos = i;
        while (!vis[pos])
        {
            vis[pos] = true;
            ring.push_back(a[pos]);
            pos = (pos + k) % n;
        }
        if (!check(ring))
        {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
    return;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}