专栏文章

P14081 题解

ssongtaoran
P14081题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minrxbos
此快照首次捕获于
2025/12/02 07:21
3 个月前
此快照最后确认于
2025/12/02 07:21
3 个月前
查看原文
设区间为 [l,r][l,r]。
很容易看出来，ll 就是满足最小能选出来 mm 条边的 nn，换句话说，最小的满足 n×(n−1)2≥m\frac{n \times (n - 1)}{2} \ge m 的 nn。
然后就是 r=2×m−2r = 2 \times m - 2，因为此时可以 2×i−12 \times i - 1 与 2×i2 \times i 连边，根据规则对面只能选出来 m−1m - 1 条边。显然再大的不可能了。
记得判 l>rl > r。
做完了。
CPP
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll T, m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> T;
	while(T--){
		cin >> m;
		ll l, r = 2 * m - 2, sq = sqrt(m * 2);
		for(ll i = max(1ll, sq - 10); i <= sq + 10; i++)
			if(i * (i - 1) / 2 >= m){
				l = i; break;
			} 
		if(l > r) cout << "Lose!\n";
		else cout << l << ' ' << r << '\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...