22 8 26 网赛筛补题（哈希，整除分块，与逆序对相关的贪心。）

比赛平台，vj

$firstfirst$： hash

address 问题简介：R，L，U，D，分别右左上下方向。给出一个只包含四个字符的串，表式一个指令集合。有多少个子串表示的命令集合可以回到原地。

• 分析，将每一个字符替换成一个数字，变成一个数组。1.不产生二义的原则下，不改变原来字符串的含义。通过新得符号集合，一段子串指令下可以回到原点的条件为：子数组和为0。解决数组有多少个子数组和为0的问题终，可以使用哈希表来优化。将复杂度降低为$O(nlogn)O(nlogn)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9;
void solve()
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    vector<ll> a(n + 1), sum(n + 1);
    map<long long, ll> rec;
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'R')
            a[i + 1] = inf;
        if (s[i] == 'L')
            a[i + 1] = -inf;
        if (s[i] == 'U')
            a[i + 1] = 1;
        if (s[i] == 'D')
            a[i + 1] = -1;
    }
    rec.insert({0, 1});
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + a[i];
        if (rec.count(sum[i]))
        {
            ans += rec.find(sum[i])->second;
            rec.find(sum[i])->second++;
        }
        else
            rec.insert({sum[i], 1});
    }
    cout << ans << '\n';
}
int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

• 回顾tips：
  • 分别将每个符号赋为inf，-inf，-1，1。该问题规模下，一个值不会产生二义性。二可以优化寻找前的某一段前缀和的大小为本身，这样的查询条件比较简单。

$second\backslash color\{blue\}\; second$ 整除分块

链接 给出两个数：记为m,n。其中有两种操作：$n=n-1n=n-1$,或$m=m+1m=m+1$。问至少多少次操作之后，使得$m\mathrm{\%}nm\backslash \%n$。

• 分析：全部对n枚举的操作数情况全部枚举，枚举量将会非常大。对于某些$n_i\mathrm{，}{n}_{j}n\_i，n\_j$,有$m\mathrm{/}{n}_i=m\mathrm{/}{n}_{j}m/n\_i=m/n\_j$(向下取整)。也就是对它们比较，可以发现，数越小，相对应的操作数只会相等或者变小。
  • 简单证明如下：记集合$S_{i}S\_i$满足$m\mathrm{/}{s}_k=im/s\_k=i$，假设$s_j\in S,s_i=(s_j-1)\in Ss\_\{j\}\backslash in\; S,s\_i=(s\_j-1)\backslash in\; S$。那么操作计算公式为: $sum(n_0)=n-n_0+\lceil \frac{m}{n_0}\rceil \times n_0-msum(n\_0)\; =\; n-n\_0+\backslash left\; \backslash lceil\; \backslash frac\{m\}\{n\_0\}\; \backslash right\; \backslash rceil\; \backslash times\; n\_0-m$记$k=\lceil \frac{m}{n_0}\rceil k=\backslash left\; \backslash lceil\; \backslash frac\{m\}\{n\_0\}\; \backslash right\; \backslash rceil$ 则$sum(s_j)-sum(s_i)=-1+ksum(s\_j)-sum(s\_i)=-1+k$其中$k>=1k>=1$。所以$sum(s_j)>=sum(s_i)sum(s\_j)>=sum(s\_i)$.

怎么找出$minist(S_i)minist(S\_i)$。

//整除分块
for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l);//后边(n/l)一定要加括号，是先向下取整后再被n除
    //执行一些操作
}

解读：

前提： 定义$\mathrm{/}/$为向下取整的整数除法。

1. $minist(S_1)=1,maxist(S_1)=1minist(S\_1)=1,maxist(S\_1)=1$.
2. $minist(S_i)=maxnist(S_{i-1})+1minist(S\_i)=maxnist(S\_\{i-1\})+1$
3. $maxnist(S_i)=m\mathrm{/}imaxnist(S\_i)=m/i$ $\mathrm{看}\mathrm{反}\mathrm{比}\mathrm{例}\mathrm{函}\mathrm{数}\mathrm{琢}\mathrm{磨}\mathrm{一}\mathrm{下}\mathrm{即}\mathrm{可}\mathrm{。}看反比例函数琢磨一下即可。$
4. $i=m\mathrm{/}minsist(S_i)i=m/minsist(S\_i)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
void solve()
{
    ll n, m;
    cin >> n >> m;
    if (n >= m)
    {
        cout << n - m << '\n';
        return;
    }
    if (m % n==0)
    {
        cout << 0 << '\n';
        return;
    }
    ll ans = 1e18;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = (m - 1) / ((m - 1) / l);
        ans = min(ans, ((m + l - 1) / l) * l - m + n - l);
    }
    cout << ans << '\n';
}
int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

$third\backslash color\{blue\}\backslash large\; third$

排列与逆序对。 Triple Shift 分析：对于这种特殊的置换方式。

• 1.只是操作三个元素。当最后第三个数来首位时。与前两个数贡献了0或1或2的逆序对。当最后一个元素来到首位之后。所有情况的序偶对数量都只是变化偶数个。整体上序偶对总数的奇偶性就不会发生改变。
• 2.这就意味着：如果每种数字出现的次数相同，每种数字的出现次数都少于2次。那么当我们把前面的所有数字都确定后，最终虽然中间的处理方案不同，但是最后等待确定的三个必然是序偶对奇数或者偶数是奇数或者是偶数保持变化前相同。奇数有三种，偶数也有三种。最终是其中的某一组中的某一个。而且一组之间可以相互转化。
• 3.综上1，2。如果每种次数出现的次数相同且出现次数不大于1。我们可以确定最后处理的三个位置的序偶对的奇偶性。就是起始的逆序对数与将基本处理后三个以前的逆序对数之差的奇偶性。然后将它和B数组对应的后三个元素的序偶对奇偶性作比较。综合起来，可以发现。只要数组A，B的序偶对的奇偶性相同即可。
• 4.如果某个数字出现的次数大于两次。上述2的结论是不可用的。最后的三个数的奇偶性与整个数组的奇偶性之间并不具有2之间描述的关系。此时如果最后这三个有重复数字。通过循环置换可以得到所有的可能。所以此时"yes”。如果不相同，采取某种构造方法，发现必然可以构造成功。将相同的挤在一起，可以把某个数调整可以把一个数放在奇数位或者偶数位。然后将它向它的应该在的位置靠近。

综上

• 每种数字出现的次数不同，必然“no"
• 每种数字出现的次数都小于两次，就判断两个数组的逆序对数目的奇偶性。
• 如果上条件1满足，一种数字的出现次数大于两次必然有解。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int cunt[5001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    bool _1 = false, _2 = false;
    for (auto &i : a)
    {
        cin >> i;
        cunt[i]++;
        if (cunt[i] > 1)
            _1 = true;
    }
    for (auto &i : b)
    {
        cin >> i;
        cunt[i]--;
        if (cunt[i] < 0)
            _2 = true;
    }
    if (_2)
        cout << "No" << '\n';
    else if (_1)
        cout << "Yes" << '\n';
    else
    {
        int suma = 0, sumb = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
            {
                if (a[i]>a[j])
                    suma++;
                if (b[i] > b[j])
                    sumb++;
            }
        if ((suma & 1) == (sumb & 1))
            cout << "Yes" << '\n';
        else
            cout << "No" << '\n';
    }
}