当前位置:网站首页>Construction problem of D Xiaohong

Construction problem of D Xiaohong

2022-06-13 04:39:00 I would like to have egg yolk and meat dumplings

Portal :
D Xiao Hong's construction problem

The question : Construct a length that does not exceed 2e5 String of , Make it include k individual “red” Subsequence .(k<=1e14)

analysis : At first, I wanted to get together rreedd This string , Then add the letters . However, the newly added letters have aftereffect and the number of subsequences cannot be added 1, be unable to do sth. .

consider rrrededed This string , Again only again ed Before to add r, Then add... At any position r There will be no aftereffect . If r Yes x individual , So this string has x*(x+1)*x/2 Subsequence , obviously x The length of is pow(1e14,1/3.0) Level , The remaining k The length of x^2 The level of . After that in each ed Add one before r, Will increase i(i+1)/2 Subsequence , And no aftereffect . As if ,- The largest square number is also a function of rapid numerical descent ? Run fast anyway .

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
	// cout<<pow(1e14,1/3.0)<<endl;
	int k;
	cin>>k;
	int x=0;
	while(1)
	{
		if(x*x*(x+1)/2>k)
		{
			x--;
			break;
		}
		else x++;
	}
	cout<<x<<endl;
	k-=x*x*(x+1)/2;
	for(int i=1;i<=x;i++)
	{
		cout<<"r";
	}
	// int cnt=0;
	for(int i=x;i>=1;i--)
	{
		while(k>=i*(i+1)/2)
		{
			k-=i*(i+1)/2;
			cout<<"r";
			// cnt++;
		}
		cout<<"ed";
	}
	cout<<endl;
	// cout<<cnt<<endl;
}

原网站

版权声明
本文为[I would like to have egg yolk and meat dumplings]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/164/202206130436505383.html