题解：CF2056C Palindromic Subsequences

人类智慧。

思路

发现第三组样例中

g(a)=190

，我们只需要在这一组的答案之后输出一些没出现过的数就可以通过

n\ge15

的点。这是非常显然的，如果一个数字只出现过一次那么它不会构成更长的回文序列。
同理第二组样例中

g(a)=24

，用它通过

9\le n<15

的点。
发现在第一组样例之后接上一个

3

后

g(a)=9

。用它通过

n\in\{8,9\}

的点。

n=6

输出样例。

代码

好想但是没正解好写。

CPP

#include<bits/stdc++.h>
using namespace std;
int T,n;
int main(){
	scanf("%d",&T);
	while(T --){
		scanf("%d",&n);
		if(n == 6) printf("1 1 2 3 1 2");
		else if(n == 7) printf("1 1 2 3 1 2 3");
		else if(n == 8) printf("1 1 2 3 1 2 3 4");
		else if(n >= 9 && n <= 14){
			printf("7 3 3 7 5 3 7 7 3 ");
			for(int i = 10;i <= n;i ++) printf("%d ",i); //注意不要和前面的数字重复，需要保证刚好 n 个数字
		}
		else{
			printf("15 8 8 8 15 5 8 1 15 5 8 15 15 15 8 ");
			for(int i = 16;i <= n;i ++) printf("%d ",i);
		}
		printf("\n");
	}
}

正解思路

参考完善 jzjr的题解。

考虑

f(a)

的值。

f(a)=1

肯定不行，长度为

1

的子序列只有

n

个。

f(a)=2

不行，这样的序列势必由两个相同的数字构成，每个数字出现

2

次，只有

\frac{n}{2}

个。

f(a)=3

：要求的子序列由两端相同的数字和中间一个数字构成。构造：可以在左端放两个

1

，右端放一个

1

，中间的每一个数字任意放，互不相同即可。
左端靠右的

1

作为中间数做出了

1

的贡献，中间每一个数作为中间做出

2

的贡献，易知

g(a)=2n-5

。在

n\ge6

时恒成立。

正解代码

CPP

#include<bits/stdc++.h>
using namespace std;
int T,n;
int main(){
	scanf("%d",&T);
	while(T --){
		scanf("%d",&n);
		printf("1 1 ");
		for(int i = 4;i <= n;i ++) printf("%d ",i);
		printf("1\n");
	}
	return 0;
}

题解：CF2056C Palindromic Subsequences

文章操作

思路

代码

正解思路

正解代码

相关推荐

评论

题解：CF2056C Palindromic Subsequences