题解：P11397 界分数

看前人的题解我是一头雾水。

我来水写一篇通俗易懂的题解。

明确策略

首先，约掉

2

的利益是最大的，这不难理解：

每执行一次操作（除第一次操作），都能约掉一个

2

，所以，如果每一次操作都约掉一个

2

，那么共执行

\log_2n

次操作。如果说要约掉一个

3

，那么至少要执行两次操作，但如果这两次操作每次约掉一个

2

，则相当于约了一个

4

，显然利益更大；同理，要约掉一个

4

，就要执行三次操作，也没有约

2

的利益大。以此类推，可知约掉

2

的利益是最大的。

每一次都必然能约掉一个

2

，这也不难理解，只需：当分母为奇数，执行操作

2

；反之，执行操作

1

。

其次，再考虑第一次操作，应执行操作一，下面给出样例解释。

$8$						总执行次数
执行操作1	$\frac {1}{8}$	$\frac {1} {4}$	$\frac {1} {2}$	$1$		$4$
执行操作2	$\frac {1} {9}$	$\frac {1} {5}$	$\frac {1} {3}$	$\frac {1} {2}$	$1$	$5$

显然，先执行操作

2

可能会多执行一次操作。

那么，我们的策略就是：第一步执行操作

1

，之后分母为偶执行执行操作

1

，分母为奇执行执行操作

2

。

计算过程

已经明确了策略，下一步就是如何计算了。

直接模拟很显然会 TLE，那就要用数学方法。

已经知道执行步数是

\left(\log_2 n \right)+ 1

，但若是每个数都进行计算，还是会 TLE。

所以，这道题旨在减少计算。那就来找一找规律：

	$1$	$2$	$3$	$4$	$5$	$6$
操作次数	$1$	$2$	$3$	$3$	$4$	$4$

这样看可能不太明显，我们换一种方式：

$1 = 1\\$
$2 = 1 + 1\\$
$3 = 1 + 1 + 1\\$
$3 = 1 + 1 + 1\\$
$4 = 1 + 1 + 1 + 1\\$
$4 = 1 + 1 + 1 + 1\\$
$4 = 1 + 1 + 1 + 1\\$
$4 = 1 + 1 + 1 + 1\\$
$5 = 1 + 1 + 1 + 1 + 1\\$

这么看来，我们可以竖着加，即每遇到一个

2

的倍数

t

，就加

n - t

。这样，可以大大减小时间复杂度。

CPP

#include<bits/stdc++.h>
#define int long long//即所有的int变成long long 
using namespace std;

int Mod = 998244353;

signed main()//由于有 int long long，所以此处改为signed 
{
	int n,t = 1;
	cin >> n;
	int s = n;
	while(pow(2,t - 1) < n)
	{
        t++;
        s += n - pow(2,t - 1);
        s %= Mod;
	}
	cout << s % Mod << endl;
	return 0;
}

但是，新的问题又出现了：我们可以通过前面的测试点，但最后一个 subtask 会 WA。那只有可能是在

\bmod \ 998244353

时出现了问题。仔细观察可以发现，最后一个 subtask 的数据超极大，直接加减会超出 long long 数据类型的范围。所以，要稍作改动，先

\bmod\ 998244353

，再加减。

CPP

#include<bits/stdc++.h>
#define int long long//即所有的int变成long long 
using namespace std;

int Mod = 998244353;

signed main()//由于有 int long long，所以此处改为signed 
{
	int n,t = 1;
	cin >> n;
	int s = n;
	while(pow(2,t - 1) < n)
	{
		int x = pow(2,t - 1);//pow函数返回值是double类型，要转成long long 
		s += (n - x) % Mod;
		t++;
	}
	cout << s % Mod << endl;
	return 0;
}

题解：P11397 界分数

文章操作

看前人的题解我是一头雾水。

明确策略

计算过程

相关推荐

评论

题解：P11397 界分数