P9502 题解

发布时间 2023-09-10 14:15:48作者: 群星之路

普通模拟的别的题解应该都有了,现在我来介绍一种不同寻常的偷懒方法!

思路分析

确定最大值

题目要我们求 \(2^m\) 次方,常规的方法是对于 \(m\) 一个一个试过去,最终找到答案。

但是,我们可以发现,\(m\) 不就是 \(\log_2 n\) 嘛!(不考虑偶数和小于的条件下)

所以我们可以使用 C++ 中的 log2() 函数,快速求出 \(\log_2 n\) 的值。

不过,可不能这样结束。

进行微调

题目中提到了,要使 \(2^m<n\),所以如果 \(n\)\(2\) 的幂次,那么 \(2^m\) 就会与 \(n\) 相等这不符合题意。所以,我们需要特判 \(2^m\) 是否与 \(n\) 相等,如果相等就将 \(m\) 减少 \(1\)

另外,题目强烈提醒我们 \(m\) 一定为偶数,所以,在执行上一个调整后,我们还要判断 \(m\) 是否为奇数。如果是,那么我们还要将 \(m\) 减少 \(1\)

程序实现

#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
	cin >> n;
	int m = floor(log2(n)); // 将log2(n)的值向下取整
	if ((1 << m) == n) m--; // 第一类微调
	if (m & 1) m--; // 第二类微调
	cout << m;
	return 0;
}