P9508 『STA - R3』存在题解

分析:

逐Subtask的看一下：

Subtask 1:

$n \le 5$ ，可暴力解决，代码略。

Subtask 2:

$n \equiv 0 \pmod 3$ ，分析一下：

若 $n=3$ 时，以样例为例， 1 1 2，可以发现，当 $n$ 为3的倍数时，将样例复制 $n/3$ 遍即满足任意子区间存在主元素。但是，题目中还有一句话:

“在此基础上，要求序列元素的种类数最大。”

这点如何满足呢？

尝试手动枚举:

（稍微贪心一点，先输出新的数字再输出1）

$n=3$ ，有序列 2，1，1；

$n=6$ ，有序列 2，1，1，3，1，1；

$n=9$ ，有序列 2，1，1，3，1，1，4，1，1；

$n=12$ ，有序列 2，1，1，3，1，1，4，1，1，5，1，1；

$\dots$

观察可发现，当 $n$ 为3的倍数时，就输出 $n/3$ 个形如 $\{i,1,1\}$ 的序列即可。其中 $i$ 为当前的序列号+1。

（补充说明: 为什么要连续输出两个1呢？因为当有如 $\{1,2,1,3,1\}$ 的样子的序列时取 $\{2,1,3\}$ 这样的区间就不满足要求了，即两个不同的数中间必须有两个相同的数，这里为了方便起见取1)

核心代码：

void dfs(int k,int i){
    //k为当前剩下的序列长度
    //i和上文含义相同
	if(k==0) return;
	cout<<i<<" "<<1<<" "<<1<<" ";
	dfs(k-3,i+1);
}

Subtask 3（正解):

当 $n$ 为任意正整数时，如何解决呢？

可以将Subtask 2中 $n$ 是3的倍数的情况引申至所有数，可以发现，在优先输出新增加的数字（即上文/代码中的 $i$ ）的情况下，每次输出一定能满足题目条件，只需要对剩余的 $n=2$ 或 $n=1$ 的判定一下即可。时间复杂度 $O(n)$ 。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
void dfs(int k,int i){
	if(k<3){
		if(k==2)cout<<1<<" "<<i;
		if(k==1)cout<<i;
		return;
	}
	cout<<i<<" "<<1<<" "<<1<<" ";
	dfs(k-3,i+1);
} 
int main(){
	int n;
	cin>>n;
	dfs(n,2);
	return 0;
}

这里采用递归实现是因为我认为更好理解一点，但是循环实现亦可。

总结

赛时遇到不会的题可以先看看性质&部分分，亦可手动枚举（蒟蒻一看题面有构造俩字都不想写了（没学过）但是推一推有时候也可以AC）。
蒟蒻第一篇题解，可能有些地方写的不太详细，有问题可以私信我，同时也感谢管理员审核这篇题解。

P9508 『STA - R3』存在 题解