String Theory

0000pnc · 2024-09-23 21:14:46 · 题解

神仙题。

首先如果所有的 a_{i} 之和为奇数那么一定无解。

然后这里有个关键观察：对于 n\ge 2，一个 n-quotation 序列（即由若干个 n-quotation 拼接而成的序列）一定是一个完整的 n-quotation。

证明考虑归纳。首先对于 n=2 是比较容易的，把首尾的两个引号分别去掉后剩下的一定是一个 1-quotation 序列（因为所有数之和是偶数，一定能够找到合适的匹配）。

如果 n=k-1 时成立，那么 n=k 时每个 n-quotation 都会恰好包括一个 (n-1)-quotation。此时这个序列大概长这样：

把首尾的 \{k,k-1,k-2,\cdots,2\} 单独拎出来，那中间的显然是一个 1-quotation 序列（图中未写出“序列”），这样就符合 n-quotation 的定义了。

于是可以枚举答案 x，然后对于每个答案都可以利用这个性质 \mathcal{O}(x) 判断是否合法（即：依次从头和尾删去 x,x-1,x-2,\cdots,2 个引号，每次判断删除操作是否合法即可）。注意到答案的上界是 \min(a_1,a_n)，因此时间复杂度为 \mathcal{O}(V^{2})（或者 \mathcal{O}(nV)？）。

最后可能需要特判答案为 1 的情况，这个也很好处理。

#include <bits/stdc++.h>
using namespace std;

int n, a[105], sm, tmp[105];

bool chk(int x) {
    for (int i = 1; i <= n; i++) tmp[i] = a[i];
    int l = 1, r = n, i;
    for (i = x; i > 1 && l <= r; i--) {
        if (tmp[l] < i) break;
        tmp[l] -= i; if (!tmp[l]) ++l;
        if (tmp[r] < i) break;
        tmp[r] -= i; if (!tmp[r]) --r;
    }
    return (l <= r && i == 1);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), sm += a[i];
    if (sm & 1) return printf("no quotation\n"), 0;
    for (int i = min(a[1], a[n]); i >= 2; i--) {
        if (chk(i)) return printf("%d\n", i), 0;
    }
    return printf(sm == 2 ? "1\n" : "no quotation\n"), 0;
}