[CSDN竞赛]第五期参赛回顾
体验感想
第一次参加，本来有点小期待，那天还起晚了，结果登录不上去，发现大家都有问题，对我来说反而是好事，本来早上没有下午晚上更加精神。下面是提的建议：
- 上次的登录问题，希望官方下次不要再出现，一定要准备充足
- 为什么不能使用本地IDE，提供的编译器真的不好用
- 题目案例给的太过简单，还没有数据的范围限定
- 这次题目1 、2都跟因数有关，4也有点像数学问题，题型是不是应该多元化
- 这次题目难度分布不是递进式的，2、4题我觉得挺简单，1、3题稍有难度
第一题 寻因找祖
寻找因子个数为n的最小整数x.
题解：考试时候，暴力寻找过了40%；后来看到大佬的解法才知道这不是一道简单的题。（就不在这里写了）
第二题 通货膨胀-x国货币
X国发行货币最高面额为n。 次高面额为n的因子。 以此类推。 X国最多发行多少种货币。
题解：寻找因子的数学问题。只是每次找的是次高的因子。
int main() {
int n;
while (cin>>n){
int res = 1;
for (int i = 2; i * i< n; i++){
if (n % i == 0) {
res++;
n /= i; // 更新n
i = 1;
}
}
if (n != 1)res++;
cout << res << endl;
}
return 0;
}
第三题 莫名其妙的键盘
有一个神奇的键盘，你可以用它输入a到z的字符，然而每当你输入一个元音字母(a,e,i,o,u其中之一)的时候，已输入的字 符串会发生一次反转！ 比方说，当前输入了tw，此时再输入一个o，此时屏幕上的字符串two会反转成owt。 现给出一个 字符串，若用该键盘输入，有多少种方法可以得到？
这题考试时候没有做出来，后来也是看到大佬的思路，这里也不写了。
第四题 三而竭
一鼓作气再而衰三而竭。 小艺总是喜欢把任务分开做。 小艺接到一个任务，任务的总任务量是n。 第一天小艺能完成x份 任务。 第二天能完成x/k… 第t天能完成x/(k^(t-1))。 小艺想知道自己第一天至少完成多少才能完成最后的任务。
解答：法一：暴力模拟过程。太过复杂，但是可以转化成数学问题，等比数列求和，得到第一天完成的任务至少>=n*(k-1)/k，这样相当于剪枝了，暴力模拟[n*(k-1)/k，n]；
法二：二分法，寻找x的值过程就是在寻找能完成和不能完成的界限。加上推导的x最小值，那么应该在[n*(k-1)/k，n]之间二分查找。
bool check(int x, int n, int k) {
int sum = x;
int d = k; // 除数
while (sum < n) {
if (x / d == 0)return false; // 循环结束的点
sum += x / d; // 计算完成的任务总和
d *= k; // 每次更新除数
}
return true;
}
int main() {
int n, k;
while (cin>>n>>k){
int l = n * (k - 1) / k;//最小可能的值
int r = n;
//cout << l << "," << r << endl;
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(mid, n, k)) {
r = mid-1;
}
else {
l = mid + 1;
}
//cout << l << "," << r << endl;
}
cout << l << endl;
}
return 0;
}
