链接：https://ac.nowcoder.com/acm/contest/124143

A – 幽幽子想吃东西

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int a, b, c, n;
    cin >> a >> b >> c >> n;

    ll ans = n * a;
    if (n <= b)
        ans -= c;

    cout << ans << endl;
}

B – 米斯蒂娅不想被吃掉

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    ll n, x;
    cin >> n >> x;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    ll cur = 0, last = 0;
    for (int i = 1; i <= n; ++i)
    {
        cur = a[i];
        ll need = max(0ll, x - last);

        if (cur < need)
        {
            cout << "No" << endl;
            return;
        }

        cur -= need;
        last = cur;
    }

    cout << "Yes" << endl;
}

C – 三妖精say subsequence ！！！

算法：

    组合数学。

思路：

    先用桶记录一下每个字母出现次数。

    任意选三个不同的字母可组合出 \(cnt[a] * cnt[b] * cnt[c]\) 种组合，那么全部组合的答案就是 \(∑ cnt[a] * cnt[b] * cnt[c]\)，又因为不同排列算不同答案，那么答案就是 \(6 * ∑ cnt[a] * cnt[b] * cnt[c]\)，注意需要取模。

关键代码：

void miyan()
{
    int n;
    string s;
    cin >> n >> s;

    vector<ll> cnt(26, 0);
    for (auto c : s)
        ++cnt[c - 'a'];

    ll ans = 0;
    for (int i = 0; i < 26; ++i)
    {
        if (!cnt[i])
            continue;

        for (int j = i + 1; j < 26; ++j)
        {
            if (!cnt[j])
                continue;

            for (int k = j + 1; k < 26; ++k)
            {
                if (!cnt[k])
                    continue;

                ll cur = cnt[i] * cnt[j] % MOD * cnt[k] % MOD;

                ans = (ans + cur) % MOD;
            }
        }
    }

    cout << (ans * 6) % MOD << endl;
}

D – 恋恋的01串大冒险

算法：

    贪心。

思路：

    简单贪心。

关键代码：

void miyan()
{
    int n, k;
    string s;
    cin >> n >> k >> s;

    s = ' ' + s;

    vector<int> dp(n + 1, 0);
    int pos = 0;
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] - '0')
            cnt = 0;
        else
            ++cnt;

        if (cnt >= k)
        {
            cnt = 0;
            dp[pos] = i - 1;
            ++pos;
        }
    }

    while (pos <= n)
        dp[pos++] = n;

    for (int i = 0; i <= n; ++i)
        cout << dp[i] << ' ';
    cout << endl;
}

E – the world

算法：

    分层 \(bfs\)。

思路：

    无。

关键代码：

void miyan()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<array<int, 2>>> have(n + 1, vector<array<int, 2>>(m + 1, {0, 0}));
    for (int i = 0; i < k; ++i)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        have[x1][y1][1] = have[x2][y2][0] = 1;
    }

    vector dist(n + 1, vector<vector<vector<int>>>(m + 1, vector<vector<int>>(2, vector<int>(4, 1e9))));
    queue<array<int, 4>> q;
    q.push({1, 1, 1, 0});
    dist[1][1][1][0] = 0;

    while (q.size())
    {
        auto [x, y, time, state] = q.front();
        q.pop();

        if (x == n && y == m)
        {
            cout << dist[x][y][time][state] << endl;
            return;
        }

        for (int i = 0; i < 4; ++i)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 1 || a > n || b < 1 || b > m)
                continue;

            if (state == 0)
            {
                if (have[a][b][!time] == 0 && dist[a][b][!time][0] > dist[x][y][time][0] + 1)
                {
                    dist[a][b][!time][0] = dist[x][y][time][0] + 1;
                    q.push({a, b, !time, 0});
                }

                if (have[a][b][time] == 0 && dist[a][b][time][2] > dist[x][y][time][0] + 1)
                {
                    dist[a][b][time][2] = dist[x][y][time][0] + 1;
                    q.push({a, b, time, 2});
                }
            }
            else if (state == 3)
            {
                if (have[a][b][!time] == 0 && dist[a][b][!time][3] > dist[x][y][time][3] + 1)
                {
                    dist[a][b][!time][3] = dist[x][y][time][3] + 1;
                    q.push({a, b, !time, 3});
                }
            }
            else
            {
                if (state == 2)
                {
                    if (have[a][b][time] == 0 && dist[a][b][time][1] > dist[x][y][time][2] + 1)
                    {
                        dist[a][b][time][1] = dist[x][y][time][2] + 1;
                        q.push({a, b, time, 1});
                    }
                }
                else
                {
                    if (have[a][b][!time] == 0 && dist[a][b][!time][3] > dist[x][y][time][1] + 1)
                    {
                        dist[a][b][!time][3] = dist[x][y][time][1] + 1;
                        q.push({a, b, !time, 3});
                    }
                }
            }
        }
    }

    cout << -1 << endl;
}

F – 永远亭的小游戏（续）

算法：

    数论，线性基。

思路：

    题目数据范围给出 \(a_i\) 值域为 \([1, 100]\)，不难想到这就是题目切入点。

    \(100\) 以内只有 \(25\) 个质数。

    根据算术基本定理， 每个大于 \(1\) 的整数都可以唯一表示为质数的乘积，而完全平方数的每一个质数的次数都是偶次，那么问题就转换为了区间内是否存在多个数字（可以为 \(0\) 个）的乘积使得每个质因子都是偶数次。

    由于每个数字的质因子只有奇数次和偶数次，考虑将奇数转换为 \(1\)，偶数转换为 \(0\)，那么将数字质因数分解后，可以将其转换为一个 \(25\) 位的二进制数，两个数字的乘积也就可以使用异或来表示。

    那么完全平方数的表达就为全 \(0\)，既数字 \(0\)，此时就需要快速求得区间内是否存在多个数字的异或和为 \(0\)。

    使用线性基即可。

    根据鸽笼原理，由于只有 \(25\) 个质数，那么基的大小就为 \(25\)，如果有第 \(26\) 个数字，那么超过的数字绝对可以使用另外 \(25\) 个异或得到，所有区间长度大于 \(25\) 直接输出 \(Yes\) 即可。

关键代码：

struct LinearBasis
{
    using ll = long long;
    const int BIT = 62;
    vector<ll> basis;
    int size;  // 基的个数
    bool flag; // 0 是否能被异或得到

    LinearBasis()
    {
        basis.resize(BIT + 1, 0);
        size = flag = 0;
    }

    // 插入
    bool insert(ll val)
    {
        for (int i = BIT; i >= 0; --i)
        {
            if ((val >> i) & 1ll)
            {
                if (basis[i] == 0)
                {
                    ++size;
                    basis[i] = val;
                    return 1;
                }

                val ^= basis[i];
            }
        }

        flag = 1;
        return 0;
    }

    // 判断 0 是否能被异或得到
    bool get_zero() { return flag; }

    // 判断 val 是否能被异或得到
    bool check(ll val)
    {
        for (int i = BIT; i >= 0; --i)
        {
            if ((val >> i) & 1ll)
            {
                if (!basis[i])
                    return 0;

                val ^= basis[i];
            }
        }

        return 1;
    }

    // 异或和最大值
    ll query_max()
    {
        ll ans = 0;
        for (int i = BIT; i >= 0; --i)
            ans = max(ans, ans ^ basis[i]);

        return ans;
    }

    // 异或和最小值
    ll query_min()
    {
        if (flag)
            return 0;

        for (int i = 0; i <= BIT; ++i)
            if (basis[i])
                return basis[i];

        return 0;
    }

    // 能表示出非 0 异或和的个数
    ll query_count() { return (1ll << size) - 1; }
};

const int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                     31, 37, 41, 43, 47, 53, 59, 61, 67,
                     71, 73, 79, 83, 89, 97};

vector<int> mask(101, 0);
void init()
{
    for (int i = 1; i <= 100; ++i)
    {
        int x = i;
        int cur = 0;
        for (int j = 0; j < 25; ++j)
        {
            int cnt = 0;
            while (x % prime[j] == 0)
            {
                ++cnt;
                x /= prime[j];
            }

            if (cnt & 1)
                cur |= 1ll << j;
        }

        mask[i] = cur;
    }
}

void miyan()
{
    init();

    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    while (q--)
    {
        int l, r;
        cin >> l >> r;

        if (r - l + 1 > 25)
        {
            cout << "Yes" << endl;
            continue;
        }

        LinearBasis lb;
        bool ok = 0;
        for (int i = l; i <= r; ++i)
        {
            if (!lb.insert(mask[a[i]]))
            {
                ok = 1;
                break;
            }
        }

        if (ok)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}