CSDN 编程竞赛·第五期总结
CSDN 编程竞赛·第五期总结
CSDN 编程竞赛·第五期为笔者参加的第一次 CSDN 编程竞赛，由于报名人数不多，笔者还是有幸凭借自己的三脚猫功夫，拿到了不错的名次，特此写博客一篇，进行总结。
本次编程竞赛一共4题，笔者只完美通过2题，现对比赛的4道题目进行总结。
1.寻因找祖
题目描述： 寻找因子个数为n的最小整数x。
题干十分简略，像笔者这种萌新只能想到暴力法，通过率只有50%。
赛后了解了其他思路： 根据唯一分解定理，如果一个数n可以表示成
的形式那么n的因数的个数为
根据这个思路，我们可以得到以下代码：
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <vector>
const int maxn = 1e6 + 5;
int min_num[maxn], cnt[maxn];
int solution(int n)
{
int result;
memset(min_num, -1, sizeof(min_num));
for (int i = 1; i < maxn; i++)
for (int j = i; j < maxn; j += i)
cnt[j]++;
for (int i = 1; i < maxn; i++)
if (min_num[cnt[i]] == -1)
min_num[cnt[i]] = i;
result = min_num[n]
return result;
}
int main()
{
int n;
std::cin >> n;
int result = solution(n);
std::cout << result << std::endl;
return 0;
}其中
cnt[i]为i的因子个数，min_num[n]为因子个数为n的最小整数。
2.通货膨胀-x国货币
题目描述： X国发行货币最高面额为n。 次高面额为n的因子。 以此类推。 X国最多发行多少种货币。
本题时间要求比较低，笔者的做法：
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
int solution(int n)
{
if (n == 1)
return 1;
int result = 0;
for (int i = n / 2; i >= 1; i--)
{
if (n % i == 0)
{
result += 1 + solution(i);
break;
}
}
return result;
}
int main()
{
int n;
std::cin >> n;
int result = solution(n);
std::cout << result << std::endl;
return 0;
}3.莫名其妙的键盘
题目描述： 有一个神奇的键盘，你可以用它输入a到z的字符，然而每当你输入一个元音字母(a,e,i,o,u其中之一)的时候，已输入的字符串会发生一次反转！ 比方说，当前输入了tw，此时再输入一个o，此时屏幕上的字符串two会反转成owt。 现给出一个字符串，若用该键盘输入，有多少种方法可以得到？
题干还算比较长，但只是个普通的递归，笔者这题用的是Python：
class Solution:
def __init__(self) -> None:
pass
def solution(self, str):
if len(str) == 1:
return 1
result = 0
if str[0] in ('a', 'e', 'i', 'o', 'u'):
result += self.solution(str[1:][::-1])
if str[-1] not in ('a', 'e', 'i', 'o', 'u'):
result += self.solution(str[:-1])
return result
if __name__ == "__main__":
str = input().strip()
s = Solution()
result = s.solution(str)
print(result)4.三而竭
题目描述： 一鼓作气再而衰三而竭。 小艺总是喜欢把任务分开做。 小艺接到一个任务，任务的总任务量是n。 第一天小艺能完成x份任务。 第二天能完成x/k。 。。。 第t天能完成x/(k^(t-1))。 小艺想知道自己第一天至少完成多少才能完成最后的任务。
该题的测试用例为：n=59，k=9 输出 x=54
笔者开始是使用等比数列前n项和求极限来计算n，最后解出用例的x=53，猜测可能不能累加小数部分。
下面的代码是赛后笔者写的，笔者觉得应该是正确：
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
int solution(std::vector<int> &vec)
{
int result;
int n = vec.at(0);
int k = vec.at(1);
for (int i = n; i > 0; i--)
{
int sum = i;
for (int j = k; i / j >= 1;j*=k)
{
sum += i / j;
}
if(sum < n)
{
result = i + 1;
break;
}
}
return result;
}
int main()
{
std::vector<int> vec;
std::string line_0, token_0;
getline(std::cin >> std::ws, line_0);
std::stringstream tokens_0(line_0);
while (std::getline(tokens_0, token_0, ' '))
{
vec.push_back(std::stoi(token_0));
}
int result = solution(vec);
std::cout << result << std::endl;
return 0;
}以上就是这次CSDN 编程竞赛的全部内容了，如有错误，请读者指正。
腾讯云开发者
