题解：P11838 [USACO25FEB] Printing Sequences B

qhr2023 · 2025-03-03 22:43:15 · 题解

solution

一道普及组的模拟题。

考虑实现。对于 k=2，把所有相邻且相等的元素看成一个块，若序列块数不超过 2，则满足第一个形式；否则，若所有相隔的块元素和长度都相同，则满足第二个形式。可以用一个二元组的数组来维护。

对于实现 k=3，枚举一个分界点，若分界点左边是 k=1 时的合法形式，右边是 k=2 时的合法形式，或者反过来，即合法。

code

#include <bits/stdc++.h>
using namespace std; 
int T, a[105], n, k;
bool sol1 (int l, int r) {
    for (int i=l+1; i<=r; ++i)
        if (a[i]!=a[i-1])
            return 0;
    return 1;
}
bool sol2 (int l, int r) {
    vector<pair<int, int>> b;
    for (int i=l; i<=r; ++i)
        if (b.size()&&a[i]==a[i-1])
            b.back().second++;
        else
            b.push_back({a[i], 1});
    if (b.size()<=2||b.size()%2==0){
        for (int i=0; i+2<(int)b.size(); ++i)
            if (b[i]!=b[i+2])
                return 0;
        return 1;
    }
    return 0;
}
bool sol3 (int l, int r) {
    for (int len=1; l+len-1<=r; ++len) 
        if ((r-l+1)%len==0) {
            bool f=1;
            for (int i=l; i+len<=r; ++i)
                f&=(a[i]==a[i+len]);
            if (!f)
                continue;
            for (int i=l; i<=l+len; ++i)
                if ((sol1(l, i)&&sol2(i+1, l+len-1))||(sol2(l, i)&&sol1(i+1, l+len-1)))
                    return 1;
        }
    return 0;
}
int main () {
    cin >> T;
    while (T--) {
        cin >> n >> k;
        for (int i=1; i<=n; ++i)
            cin >> a[i];
        if (k==1) puts(sol1(1, n)?"YES":"NO");
        if (k==2) puts(sol2(1, n)?"YES":"NO");
        if (k==3) puts(sol3(1, n)?"YES":"NO");
    }
    return 0;
}