题解：P13830 【MX-X18-T2】「FAOI-R6」二进制与一 III（bit）

题目的特殊性质很有帮助。发现

3

是大于等于

2

中最小的二进制全为

1

的数，所以考虑把

n

尽可能拆出更多的

3

一定是最优的。

考虑对余数分类讨论：

$n \equiv 0 \pmod 3$ ：显然全拆成 $3$ 即可，答案为 $2 \times \frac{n}{3}$ ；
$n \equiv 1 \pmod 3$ ：考虑拆成 $\lfloor \frac{n}{3} \rfloor-1$ 个 $3$ 和两个 $2$ ，答案为 $2 \times (\lfloor \frac{n}{3} \rfloor - 1) + 2$ ；
$n \equiv 2 \pmod 3$ ：考虑拆成 $\lfloor \frac{n}{3} \rfloor$ 个 $3$ 和一个 $2$ ，答案为 $2 \times \lfloor \frac{n}{3} \rfloor + 1$ 。

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
	ll n; cin >> n;
	ll ans;
	if(n % 3 == 0) ans = (n / 3) * 2;
	else if(n % 3 == 1) ans = (n / 3 - 1) * 2 + 2;
	else ans = (n / 3) * 2 + 1;
	cout << ans << '\n';
}

signed main()
{
	ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T; cin >> T;
	while(T --) solve();
	return 0;
}

题解：P13830 【MX-X18-T2】「FAOI-R6」二进制与一 III（bit）

文章操作

相关推荐

评论

题解：P13830 【MX-X18-T2】「FAOI-R6」二进制与一 III（bit）