牛客11251D - 小红的构造题

• 链接：https://ac.nowcoder.com/acm/contest/11251/D
• 知识点：构造、组合计数、贡献
• 难度：蓝

题意

• 构造一个长度不超过 $2\times 10^{5}2\backslash times10^5$ 的字符串，其中包含 $K(K\le 10^{14})K(K\; \backslash leq\; 10^\{14\})$ 个“red”的子序列。

思路

• “red”的长度仅为3，可以只分析“e”。
• 某个“e”对子序列数量的贡献为 $\mathrm{这}\mathrm{个}e\mathrm{前}\mathrm{面}\mathrm{的}r\mathrm{的}\mathrm{数}\mathrm{量}\times \mathrm{这}\mathrm{个}e\mathrm{后}\mathrm{面}\mathrm{的}d\mathrm{的}\mathrm{数}\mathrm{量}这个e前面的r的数量\; \backslash times\; 这个e后面的d的数量$
• 如果我们将“rerere...”写出，可以发现，

• 在第 1 个re后放置d，每个d对子序列数量的贡献为1，
• 在第 2 个re后放置d，每个d对子序列数量的贡献为3，其中包括第1个e产生的1的贡献和第2个e产生的2的贡献。
• 在第 3 个re后放置d，每个d对子序列数量的贡献为6，其中包括第1个e产生的1的贡献和第2个e产生的2的贡献和第3个e产生的3的贡献。
• ...

• 在第 i 个re后放置d，每个d对子序列数量的贡献为 $\frac{i(1+i)}{2}\backslash frac\{i(1+i)\}\{2\}$
• 我们需要确定像这样的“re”的数量，然后在每个“re”后面放合理数量的“d”即可。
• 当我们确定了像这样“re”的数量，构造时，必然是从后往前放“d”。

“re”的数量如何确定？

• 官方题解给出的方法很好，但是还有一个相对麻烦但易懂的思路。
• 我们发现，最终构造出的字符串长度，随着re数量的增加，是先减后增的关系。
• 考虑三分法确定“re”的数量。

代码

#include <cstdio>
#include <iostream>
#define int long long
const int N		= 1e6+10;
const int LIM	= 2e5;
using namespace std;

int arr[N];
int n;

int APSUM(int x)
{
	return x*(1+x)/2;
}

int Cal(int x)
{
	int tot = 0;
	int rmn = n;
	for (int i=x; i>=1; i--)
	{
		tot+=2;
		if(!rmn)
		{
			arr[i] = 0;
			continue;
		}
		arr[i] = rmn/APSUM(i);
		rmn %= APSUM(i);
		tot+=arr[i];
	}
	
	return tot;
}

void Solve()
{
	if(n==0)
	{
		printf("der\n");
		return;
	}
	
	int l=0,r=LIM;
	while (r-l>5)
	{
		int limL = l+(r-l)/3;
		int limR = r-(r-l)/3;
		
		if(Cal(limL) < Cal(limR))
		{
			r = limR+1;
		}
		else
		{
			l = limL-1;
		}
	}
	int ed;
	
	for (int i=l+1; i<=r; i++)
	{
		int res = Cal(i);
		if(res<=LIM)
		{
			ed = i;
			break;
		}
	}
	
	for (int i=1; i<=ed; i++)
	{
		printf("re");
		for (int j=1; j<=arr[i]; j++)
		{
			printf("d");
		}
	}
	
	
}

signed main()
{
	scanf("%lld",&n);
	Solve();
	return 0;
}