---
url: /algo/pij627v8/index.md
---
## Preface

打得最抽象的一把。$D\sim F$ WIP。

## A. 模糊匹配

签到题，把所有混淆的一些字符改为同一个最后比较字符串即可。

```cpp title="A.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;

void sol()
{
    int s;
    cin >> s;
    string s1, s2;
    cin >> s1 >> s2;
    for (int i = 0; i < s; i++)
    {
        if (s1[i] == 'O' || s1[i] == '0')
        {
            s1[i] = 'O';
        }
        if (s1[i] == 'I' || s1[i] == 'l' || s1[i] == '1')
        {
            s1[i] = '1';
        }
        if (s2[i] == 'O' || s2[i] == '0')
        {
            s2[i] = 'O';
        }
        if (s2[i] == 'I' || s2[i] == 'l' || s2[i] == '1')
        {
            s2[i] = '1';
        }
    }
    if (s1 == s2)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
    }

    return 0;
}
```

## B. 只留专一数

我们观察题面的第三步：令 $a\_j := a\_{n'}$；以及第四步：令 $n' := n' - 1$。我们可以发现 $n'$ 是不断在减小，而 $a\_j$ 每次都是等于的 $a\_{n'}$ 那么如果 $a\_{n'}$ 变成了专一数，我们就可以取 $j=1$ 使其变为 $a\_1$。

其次我们也有一个性质，$\forall ~ x\in \mathbb{N}$ 如果 $a$ 是专一数，那么 $a^n$ 也是专一数。所以这个问题就变成了，判断数组中是否存在专一数。

数据量 $a\_i\leqslant 10^3$，我们考虑预处理 $1\sim 1000$ 的所有专一数，复杂度为 $O(n\sqrt{n})$。

```cpp title="B.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 1000;
vector<bool> is_special(MAX + 1, false);
void compute()
{
    for (int i = 1; i <= MAX; i++)
    {
        if (i == 1)
        {
            is_special[i] = true;
            continue;
        }
        unordered_set<int> factors;
        int tmp = i;
        for (int d = 2; d * d <= tmp; d++)
        {
            if (tmp % d == 0)
            {
                factors.insert(d);
                while (tmp % d == 0)
                {
                    tmp /= d;
                }
            }
        }
        if (tmp > 1)
        {
            factors.insert(tmp);
        }
        if (factors.size() <= 1)
        {
            is_special[i] = true;
        }
    }
}

void sol()
{
    int n;
    cin >> n;
    bool p = false;
    vector<int> vi(n);
    for (int i = 0; i < n; i++)
    {
        cin >> vi[i];
    }
    for (int i = 0; i < n; i++)
    {
        if (is_special[vi[i]])
        {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}

int main()
{
    int t;
    cin >> t;
    compute();
    while (t--)
    {
        sol();
    }

    return 0;
}
```

## C. 左右左右左左右，左右左左右

这才是世界上最绝望的死法，明明思路完全正确 wa 了 4 发。

首先观察式子：

$$
d\_i = \big\lvert a\_0 \cdot \operatorname {pc}(i, \texttt{1}) - a\_1 \cdot \operatorname {pc}(i, \texttt{0}) \big\rvert
$$

其中 $\operatorname {pc}(i, j)$ 表示字符串 $s\_1 s\_2 \dots s\_i$ 中字符 $j$ 出现的次数。注意，其中 $a\_0$ 是字符 “`1`” 的系数，$a\_1$ 是字符 “`0`” 的系数。

要求对数列字典序最小，这一定是贪心思维，因为只有当下的最优解才能保证全局最优解，否则不可能会保证字典序最小。

```cpp title="C.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
    ll n, a0, a1;
    cin >> n >> a0 >> a1;
    vector<ll> res;
    array<ll, 2> cnt;
    fill(cnt.begin(),cnt.end(),0);
    for (ll i = 0; i < n; i++)
    {
        ll c1 = abs(a0 * (cnt[1] + 1) - a1 * (cnt[0]));
        ll c0 = abs(a0 * (cnt[1]) - a1 * (cnt[0] + 1));
        if (c1 == c0)
        {
            res.push_back(1);
            cnt[1]++;
        }
        else if (c1 > c0)
        {
            res.push_back(0);
            cnt[0]++;
        }
        else
        {
            cnt[1]++;
            res.push_back(1);
        }
    }
    for (ll i = 0; i < res.size(); i++)
    {
        cout << res[i];
    }
    cout << "\n";
}

int main()
{
    ll t;
    cin >> t;
    while (t--)
    {
        sol();
    }

    return 0;
}

```