活動地址：?？痛赫兴㈩}訓(xùn)練營 - 編程打卡活動

Easy 小紅的順子

簡要題意

給一個由 挖去一位得到的數(shù)組，求這一位前后數(shù)字個數(shù)的 。

Solution

暴力尋找被挖去的位即可。

Code

void R()
{
	int n;
	cin>>n;
	vector<int> a(n-1);
	for (int &x:a) cin>>x;
	for (int i=0;i<n;i++)
		if (a[i]!=i+1)
		{
			cout<<max(i,n-i-1);
			return;
		}
	cout<<n-1;
	return;
}

Medium 小紅的字符生成

簡要題意

你有 個字母 a，每次可以將兩個相同字母合成為字典序大一位的字母，求最后得到的最短字符串。

Solution

字典序第 大的字母相當(dāng)于 個 a，于是轉(zhuǎn)化為二進(jìn)制拆分問題。

Code

void R()
{
	int x;
	cin>>x;
	for (char c='a';x;x/=2,c++)
		if (x&1) cout<<c;
	return;
}

Hard 最少的完全平方數(shù)

簡要題意

求最少需要多少個完全平方數(shù)，使得它們的和可以表示正整數(shù) 。

Solution

記 表示 的答案，有轉(zhuǎn)移：

Code

void R()
{
	constexpr int inf=1e9;
	int n;
	cin>>n;
	vector<int> dp(n+1,inf);
	dp[0]=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j*j<=i;j++)
			dp[i]=min(dp[i],dp[i-j*j]+1);
	cout<<dp[n];
	return;
}