自动搬运

查看原文

来自洛谷，原作者为

	qhr2023 **

搬运于2025-08-24 23:10:40，当前版本为作者最后更新于2025-03-03 22:43:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

solution

一道普及组的模拟题。

• $k=1$ 时，序列所有元素都为 $1$，一定合法。
• $k=2$ 时，如果序列是 $111 \cdots 222$ 这个形式，或者序列由多个完全相同的子串组成，则合法。
• $k=3$ 时，如果序列是 $k=1$ 时的合法形式拼接上 $k=2$ 时的合法形式，则合法。

考虑实现。对于 $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;
}