2025牛客寒假训练营1蒻蒻题解（K,L,I）

喵蛋原来写的题解被知乎吞了，所以来牛客发一发

K.硝基甲苯之魇

求满足gcd和异或和相等的区间个数。注意到gcd减少次数有限，所以可以每次去二分查找断点（即gcd变化的位置），然后用map维护区间所有异或前缀和的结果，找到对应的就可以（设原数组为a，异或前缀和数组为b，则对于满足条件的 $[l,r]$ ，只需要 $gcd([a_l,...,a_r])\text{^}b[l-1]\text{=}b[r]$ 即可）。时间复杂度 $O(nlog^2n)$ 。

#include <bits/stdc++.h>
using namespace std;
// #define int long long

const int N = 2e5 + 5;
const int LogN = 19;
int t, n;
int brr[N];
int st[N][LogN];
int Log[N];

void Build()
{
    // 初始化st表的第0维+求解log
    for (int i = 1, now = 2; i <= n; i++)
    {
        Log[i] = Log[i - 1];
        if (now == i)
            Log[i]++, now <<= 1;
    }

    // 倍增求解st表
    for (int j = 1, now = 1; j < 19; j++, now <<= 1)
        for (int i = 1; i <= n; i++)
            st[i][j] = __gcd(st[i][j - 1], st[min(i + now, n)][j - 1]);
}

int Query(int l, int r)
{
    int dep = Log[r - l + 1], red = (1 << dep) - 1;
    return __gcd(st[l][dep], st[r - red][dep]);
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n;
        long long ans = 0;
        map<int, vector<int>> mp;
        for (int i = 1; i <= n; i++)
        {
            cin >> st[i][0];
            brr[i] = brr[i - 1] ^ st[i][0];
            mp[brr[i]].push_back(i);
        }
        Build();

        for (int i = 1; i <= n; i++)
        {
            int now = st[i][0], L = i;
            while (1)
            {
                // r即为最后一个满足区间[i,r]的gcd为now的地方
                int l = L, r = n;
                while (l <= r)
                {
                    int mid = l + r >> 1;
                    if (Query(i, mid) < now)
                        r = mid - 1;
                    else
                        l = mid + 1;
                }

                int tar = now ^ brr[i - 1];
                ans += lower_bound(mp[tar].begin(), mp[tar].end(), r + 1) - lower_bound(mp[tar].begin(), mp[tar].end(), L);

                if ((L = r + 1) > n)
                    break;
                now = __gcd(now, st[L][0]);
            }
        }
        cout << ans - n << '\n';
    }
    return 0;
}

L.一念神魔之耀

求任意一种操作方案（如果可以的话），每次连续翻转x个或y个使得序列全1。

实质上，x和y可以统一成gcd(x,y)，即一次可以翻的最小长度为gcd(x,y)。对于前l-x+1个数，如果是0可以无脑连续翻x个；而对于最后x-1个数，如果还遇到0，则需要借助前面的空间去翻。

虽然代码里没有exgcd，但翻数（最后x-1个）的实质就是扩欧。时间复杂度 $O(wl^2)$ ，其中 $w$ 表示凑出gcd的操作的复杂度。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>

const int inf = 4e18;
const int N = 5e2 + 5;
int t = 1, n, x, y, c;
bool arr[N];
bool op[N][N];
string s;

void Build(int pos)
{
    int f = pos <= n - x + 1, now = pos + (f ? 0 : c - 1);
    if (f)
    {
        op[pos][pos + x - 1] ^= 1;
        for (int j = 0; j < x; j++)
            arr[pos + j] ^= 1;
    }
    else
    {
        do
        {
            op[now - (x - 1)][now] ^= 1;
            now -= x - 1;
            while (now + y <= pos)
            {
                op[now][now + (y - 1)] ^= 1;
                now += y;
            }
        } while (now-- != pos);

        for (int j = 0; j < c; j++)
            arr[pos + j] ^= 1;
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n >> x >> y >> s;
        for (int i = 1; i <= n; i++)
        {
            arr[i] = s[i - 1] - '0';
            for (int j = i; j <= n; j++)
                op[i][j] = 0;
        }
        if (x < y)
            swap(x, y);
        c = __gcd(x, y);

        bool valid = 1;
        for (int i = 1; i <= n; i++)
            if (!arr[i])
            {
                if (n - i + 1 < c)
                {
                    valid = 0;
                    break;
                }
                Build(i);
            }

        if (valid)
        {
            vector<PII> g;
            for (int i = 1; i <= n; i++)
                for (int j = i; j <= n; j++)
                    if (op[i][j])
                        g.push_back({i, j});

            cout << g.size() << '\n';
            for (PII i : g)
                cout << i[0] << ' ' << i[1] << '\n';
        }
        else
            cout << "-1\n";
    }
    return 0;
}

I.井然有序之桠

构造排列 $b$ ，满足 $\sum gcd(a_i,b_i)=k$ 。

首先要注意到排列a给出的数字的排列顺序不重要，实质上都是在求 $1,2,3,...,n$ 的合法匹配。

①考虑 $\Delta=k-n$ ，这个即为我们构造时需要多构造的量。那么如果 $\Delta=0$ ，则只需要将所有数向右移1位即可（构造为 $n,1,2,...,n-1$ ）；

②如果让某个数和它自身匹配，则其会提供 $a_i-1$ 的贡献。基于此，我们从大到小地匹配（不从小到大考虑的原因是因为比较小的数中有1,2等简单数，后续调整相对简单）。设 $cur$ 为失配指针（即暂时不配对的最后一个位置），初始 $cur=n$ ，当目前的 $\Delta\ge cur-1$ 时，即可将 $\Delta$ 减少 $cur-1$ ，同时将 $cur$ 与自身匹配后，将 $cur$ 向左移动1位。

③根据上述结论，当失配指针 $cur$ 不再移动后，我们实际上只需要考虑元素 $[1,cur]$ 的配对方式。初始时，先按照①的结论配好（即 $cur,1,2,...,cur-1$ ）。

易知： $\Delta\in[0,cur-2]$ 。考虑现在这些需要匹配的数：

-->1.首先，如果 $\Delta=0$ ，那我们就一点都不用动了，现在的就是我们要的结果；

-->2.然后，我们发现，每相邻两个数交换，存在如下性质： alt 除了第一组交换产生的贡献不确定外，其余都是确定且有规律的。

根据上述的规律很容易构建出几乎所有+ $\Delta$ 的交换方式（比如要 + $3$ ，就交换 [4,5] 位置上的；要 + $4$ ，就同时交换 [2,3][4,5] ）。但 $\Delta=2$ 是个特例，需要自己手搓一个合法的交换方式（不难，可以稍微思考一下怎么构造）。

时间复杂度 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>

const int N = 1e5 + 5;
int t = 1, n, k;
int a[N], ans[N];

signed main()
{
   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   cin >> t;
   while (t--)
   {
       cin >> n >> k;
       for (int i = 1; i <= n; i++)
           cin >> a[i];
       if (k < n)
       {
           cout << "-1\n";
           continue;
       }

       int now = k - n, cur = n;
       while (now && (now >= cur - 1)) // 如果退出循环，now的值必定为[now,cur-2]
       {
           now -= cur - 1;
           ans[cur] = cur;
           cur--;
       }
       for (int i = 2; i <= cur; i++) // 接下来需要处理[1,cur]这些数
           ans[i] = i - 1;
       ans[1] = cur;

       // 只要想办法处理好+0~+cur-2(now的可能范围)即可
       if (now == 2)
       {
           ans[2] = 4, ans[3] = 1, ans[4] = 2;
           if (cur == 4)
               ans[1] = 3;
           else
               ans[5] = 3;
       }
       else if (now)
       {
           if (now % 2 == 0)
               swap(ans[2], ans[3]), now--;
           swap(ans[now + 1], ans[now + 2]);
       }

       for (int i = 1; i <= n; i++)
           cout << ans[a[i]] << ' ';
       cout << '\n';
   }
   return 0;
}