Diana and Liana

Created by LXC on Sun May 21 23:20:53 2023

https://codeforces.com/problemset/problem/1120/A

ranting: 1900

tag: greedy, implementation, two pointers

题意

给出一个长度为m的序列a，以及一个长度为s的序列b。
如果删除一些数，使得剩余的数按顺序k个一组，能够产生至少n组（不足k个的舍去）。并且其中至少有一组包含了序列b中的所有元素。

请构造出删除的下标序列。

题解

我们可以用滑动窗口，维护窗口[l,r]其恰好包含b中所有序列，且[l+1,r],[l,r-1]都没有完全包含b中所有序列。

这时窗口大小为r-l+1

若r-l+1 < k，则窗口内元素无需删除，我们只需删除前r%k个（注意r<k则无需删除），以便当前窗口能恰好分到一组中。

若r-l+1 >= k，则窗口内元素需要删除r-l+1-k，使其变为长度为k的区间，然后删除[1,l-1]区间中前(l-1)%k个。

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

int a[N], mx[N], mp[N];

void sol() {
    int m, k, n, s;
    cin >> m >> k >> n >> s;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    set<int> st;
    for (int i = 1; i <= s; i++) {
        int b;
        cin >> b;
        mx[b]++;
        st.insert(b);
    }
    int d = st.size();
    int cur = 0;
    for (int r = 1, l = 0; r <= m; r++) {
        // cout << l << " " << r << "\n";
        if (++mp[a[r]] == mx[a[r]])
            cur++;

        if (cur < d)
            continue;
        while (cur == d) {
            if (mp[a[l + 1]]-- == mx[a[l + 1]])
                cur--;
            l++;
        }
        // cout << l << " " << r << "\n";
        // 包含了模板的区间为[l,r]。
        // r-l+1 如果不足k个，r<=k不用删，否则删除r%k个
        // r-l+1
        // 如果大于k个，需要删除r-l+1-k个以达到当前区间为k个，前方需要删除(l-1)%k个
        if (r - l + 1 < k) {
            if (r <= k) {
                cout << "0\n";
                return;
            }
            if (r % k <= m - k * n) {
                cout << r % k << "\n";
                for (int i = 1; i <= r % k; i++) {
                    cout << i << " ";
                }
                return;
            }
        } else {
            int c = r - l - k + 1 + (l - 1) % k;
            if (c <= m - k * n) {
                cout << c << "\n";
                for (int i = 1; i <= (l - 1) % k; i++) {
                    cout << i << " ";
                }
                for (int i = l, cnt = 0; cnt < r - l - k + 1 && i <= r; i++) {
                    if (--mx[a[i]] < 0) {
                        cout << i << " ";
                        cnt++;
                    }
                }
                return;
            }
        }
    }
    cout << "-1\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}