正题

题目链接:https://www.luogu.com.cn/problem/AT2363

题目大意

给出\(n\)，要求构造一个字符串\(s\)，使得能够找出恰好\(n\)个子序列使得这个子序列能划分成前后相等的两份。

要求\(|s|\leq 200\)，字符集为\([1,100]\)

\(1\leq n\leq 10^{12}\)

解题思路

很妙的想法，我们把\(s\)分成两半，一半是\(1\sim x\)，然后后一半是一个\(1\sim x\)的排列，这样答案就是这个排列的上升子序列数。

这样就化成了一个很简单的构造了，从小到大加，加到前面就是\(+1\)，后面就是\(\times 2\)。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define ll long long

using namespace std;

ll n,cnt,flag;deque<ll> q;

signed main()

{

	scanf("%lld",&n);n++;

	for(ll i=63;i>=0;i--){

		if(flag){

			cnt++;

			q.push_back(cnt);

		}

		if((n>>i)&1){

			if(flag)cnt++,q.push_front(cnt);

			flag=1;

		}

	}

	printf("%lld\n",cnt*2);

	for(ll i=1;i<=cnt;i++)

		printf("%lld ",i);

	for(ll i=1;i<=cnt;i++)

		printf("%lld ",q.front()),q.pop_front();

	return 0;

}

巴特西

AT2363-[AGC012C]Tautonym Puzzle【构造】

正题

题目大意

解题思路

code

最新文章

热门文章