2024.12.7 周六

Q1. 1000

给定01字符串，n,m,k。任意操作将区间长度为k的子串字符全变为1。问保证字符串任意区间没有长度大于等于m的子串字符全为0的最少操作次数。

Q2. 1300

有一个正 n 边形，给定x 个关键点，在关键点两两之间任意连互相不交叉的对角线，使得整个图形被划分出的区域中三角形的数量尽可能多。

Q3. 1200

有 n(1000) 个人围成一圈。最开始第 x 个人拿着一个球。m(1000) 个事件：拿着球的人顺时针/逆时针或者不定时针传一定距离的球。问最终哪些人可能有球。

Q4. 1400

给定长度为 n 的数组 a 和长度为 m 的数组 b。找出数组 a 中长度为 m 的连续子区间，并且区间中有至少 k 个数与数组 b 相同，求满足条件区间数量。(数字不唯一)

------------------------独自思考分割线------------------------

• 被Q2卡了一下，Q3Q4都是30分钟一道，虽然挺顺还是太慢。

A1. 1点

1.经典的双指针贪心。思路好想难在严谨证明。

A2. 2点 数学题

1.观察大法，仅考虑对角线相连最多可形成x-2个三角形。

2.同时，相邻关键点若距离为2也可形成一个三角形。

A3. 2点

1.小tips：逆时针传d==顺时针传n-d。定义函数ne找到下一个位置简化代码。

2.本质是一批人将球传给下一批人，数据量最多也就1000，可以直接搞。也可dp转移。

A4. 3点

1.每个区间注定要log以内计算出来，考虑如何减少计算数量。可以观察到，对于当前区间与上一个区间相比，区间内的数只去掉了上一个区间的区间头，加上了当前区间的区间末尾。

2.区间长度固定，想到双指针滑动窗口维护合法数量cnt。

3.如果数字唯一就秒了：map只需要维护b数组的数。没有唯一要求则：数据结构map维护b数组数的个数和窗口数的个数，在滑动的时候判断cnt有效增减。

------------------------代码分割线------------------------

A1.

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(6);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n, m, k;
    cin >> n >> m >> k;
    string s;
    cin >> s;
    int res = 0;

    for (int i = 0; i < n; i++)
        if (s[i] == '0')
        {
            int j = i;
            for (; j < n && s[j] == '0'; j++)
                if (j - i + 1 == m)
                {
                    j += k;
                    res++;
                    break;
                }
            i = j - 1;
        }
    cout << res << endl;
}

A2.

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(6);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> a;
    for (int i = 0; i < x; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    auto next = [&](int u)
    {
        u += 2;
        if (u > n)
            u -= n;
        return u;
    };
    int res = x - 2;
    sort(a.begin(), a.end());
    for (int i = 0; i + 1 < x; i++)
        if (a[i + 1] == next(a[i]))
            res++;
    if (a.front() == next(a.back()))
        res++;

    cout << res << endl;
}

A3.

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(6);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n, m, x;
    cin >> n >> m >> x;
    auto ne = [&](int f, int u, int d)
    {
        int v = u + d;
        if (f)
            v = u + n - d;
        return v > n ? v - n : v;
    };
    vector<int> res(n + 1);
    res[x] = 1;
    while (m--)
    {
        int d;
        string op;
        cin >> d >> op;
        vector<int> f;
        if (op == "1")
            f.push_back(1);
        else if (op == "0")
            f.push_back(0);
        else
            f.push_back(1), f.push_back(0);
        vector<int> t(n + 1);
        for (int i = 1; i <= n; i++)
            if (res[i])
            {
                for (auto f : f)
                    t[ne(f, i, d)] = 1; //, bug2(i, ne(f, i, d));
            }
        res = t;
        // for (auto v : t)
        //     cout << v << ' ';
        // cout << endl;
    }
    vector<int> t;
    for (int i = 1; i <= n; i++)
        if (res[i])
            t.push_back(i);
    cout << t.size() << endl;
    for (auto v : t)
        cout << v << ' ';
    cout << endl;
}

A4.

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(6);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    map<int, int> s;
    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        s[x]++;
    }
    int cnt = 0, res = 0;
    map<int, int> t;
    for (int i = 1; i <= m; i++)
    {
        t[a[i]]++;
        // bug3(a[i], t[a[i]], s[a[i]]);
        if (t[a[i]] <= s[a[i]])
            cnt++;
    }
    if (cnt >= k)
        res++;
    for (int i = 2; i + m - 1 <= n; i++)
    {
        int al = a[i - 1], ar = a[i + m - 1];
        if (al == ar)
        {
            if (cnt >= k)
                res++;
            continue;
        }
        if (t[ar] < s[ar])
            cnt++;
        if (t[al] <= s[al])
            cnt--;
        t[ar]++;
        t[al]--;
        // bug2(i, cnt);
        if (cnt >= k)
            res++;
    }
    cout << res << endl;
}