T449025 连续 题解

__ryp__ · 2024-04-28 20:41:01 · 个人记录

原题是 P3514

比较简单但是感觉比较有意思的构造。

发现对于所有 k \gt 2 ，只要 k 能被凑出，k - 2 就能凑出。

于是我们分奇数偶数讨论，记录奇偶情况下和的最大值，然后倒推出其他所有 k 的。

具体实现有点压

#include <iostream>
using namespace std;
const int N = 1e6 + 10, K = 2 * N;
int f[2], z[N], sum[N], l[K], r[K];

void dfs (int x)
{
    if (x <= 2) return;
    if (z[l[x]] == 1 && z[r[x]] == 1) l[x - 2] = l[x] + 1, r[x - 2] = r[x] - 1, dfs (x - 2);
    else if (z[l[x]] == 2) l[x - 2] = l[x] + 1, r[x - 2] = r[x], dfs (x - 2);
    else l[x - 2] = l[x], r[x - 2] = r[x] - 1, dfs (x - 2);
}

int main (void)
{
    int n, q, lfi, rfi;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> z[i];
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + z[i];
    for (lfi = 1; lfi <= n && z[lfi] == 2; lfi++);
    for (rfi = n; rfi >= 0 && z[rfi] == 2; rfi--);
    f[sum[n] & 1] = sum[n], l[sum[n]] = 1, r[sum[n]] = n;
    if (sum[n] - sum[lfi] > sum[rfi]) l[f[sum[n] & 1 ^ 1] = sum[n] - sum[lfi]] = lfi + 1, r[f[sum[n] & 1 ^ 1]] = n;
    else l[f[sum[n] & 1 ^ 1] = sum[rfi - 1]] = 1, r[f[sum[n] & 1 ^ 1]] = rfi - 1;
    dfs (f[0]), dfs (f[1]);
    while (q--) {
        int k;
        cin >> k;
        if (k > f[k & 1]) cout << "-1 -1\n";
        else cout << l[k] << ' ' << r[k] << '\n';
    }
    return 0;
}